JS算法与数据结构
文章目录
行列互换
将一个数组中的行和列进行互换,应用场景:消消乐中找到横竖排相连的3个相同的元素 (横排好找,找到竖排中的相同元素就主要用到了行列互换)
/**
* 行列互换函数
* @param {array} arr 输入的原始数组, 一维数组
* @param {Num} rowSize 每行的列个数
* @return {array} resultArr 新的数组
*/
function changeXY(arr, rowSize) {
var resultArr = [],
iNow = 0;
(function() {
if (iNow == rowSize) return;
for (var i = 0; i < arr.length; i++) {
if (i % rowSize == iNow) {
resultArr.push(arr[i]);
}
};
iNow++;
arguments.callee();
})();
return resultArr;
}
排列组合
排列的树形表示法
![树形表示法][1]
/**
* 排列函数
* @param Array arr 输入数组
* @param Num num 取出的排列个数
* @return Array 前几位表示排列的可能性,最后一位表示排列的情况数
*/
function arrange(arr, num) {
var resultArr = [],
resultNum = 0,
iLayer = 1; //当前在第几层
if (num == 1) {
resultArr = arr.concat();
resultNum = arr.length;
};
function change(arr, iLayer, str) {
for (var i = 0; i < arr.length; i++) {
var arrClone = arr.concat();
var strClone = str + arrClone.splice(i, 1);
if (num == iLayer) {
for (var j = 0; j < arrClone.length; j++) {
resultArr.push(strClone + arrClone[j]);
};
resultNum += arrClone.length;
} else {
change(arrClone, iLayer+1, strClone);
}
};
}
//是从第二层开始执行,第一层通过for循环得出
change(arr, iLayer+1, '');
resultArr.push(resultNum);
return resultArr;
}
排列的数学表示法
function A(m, n) {
return f(m) / f(m-n);
}
function f(m) {
if (m <= 1) return 1;
return m * f(m-1);
}
console.log(A(3,1));
组合函数
组合的树形表达法:先采用排列的方式获取可能的值然后过滤掉其中重复的值
/**
* 组合函数
* @param Array arr 输入数组
* @param Num num 取出的组合个数
* @return Array 前几位表示组合的可能性,最后一位表示排列的情况数
*/
function combination(arr, num) {
var resultArr = [],
resultNum = 0,
iLayer = 1; //当前在第几层
if (num == 1) {
resultArr = arr.concat();
resultNum = arr.length;
};
function change(arr, iLayer, str) {
for (var i = 0; i < arr.length; i++) {
var arrClone = arr.concat();
var strClone = str + arrClone.splice(i, 1);
if (num == iLayer) {
for (var j = 0; j < arrClone.length; j++) {
resultArr.push(strClone + arrClone[j]);
};
resultNum += arrClone.length;
} else {
change(arrClone, iLayer+1, strClone);
}
};
}
//是从第二层开始执行,第一层通过for循环得出
change(arr, iLayer+1, '');
resultArr = unique(resultArr);
resultArr.push(resultArr.length);
return resultArr;
}
function unique(arr) {
var validator = {};
var resultArr = [];
for (var i = 0; i < arr.length; i++) {
var key = arr[i].split('').sort().join('');
if (!validator[key]) {
resultArr.push(arr[i]);
validator[key] = 1;
};
};
return resultArr;
}
console.log(combination(arr, 2));
组合的数学表达法
/**
* 组合的数学表示法
* C(m, n) = m! / ((m-n)! * n!)
*/
function C(m, n) {
return f(m) / (f(m-n) * f(n));
}
function f(m) {
if (m <= 1) return 1;
return m * f(m-1);
}
console.log(C(3,2));
有课学是一站式程序员专属课程返现平台,支持极客时间,慕课网、网易云课堂、知识星球、小专栏。
【有课学,学好课,有所获】
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论