本文包括js學(xué)習(xí)中簡單功能的算法
包括對js以及DOM和BOM的研究過程中一些有意思的代碼實現(xiàn)
本文還包括公司面試相關(guān)算法問題的代碼段，但不會指出是哪個公司出的題
數(shù)據(jù)結(jié)構(gòu)及基本排序、查找算法
這個部分內(nèi)容比較多，請查看一下博客：
遞歸實現(xiàn)斐波那契數(shù)列
function reFib(n){
if (n < 2) return n;
else return reFib(n - 1) + reFib(n - 2);
}
動態(tài)規(guī)劃實現(xiàn)斐波那契數(shù)列
function dynFib(n){
var val = [];
for(var i = 0; i <= n; i++)
val.push(0);
if (n == 1 || n == 2) return 1;
else{
val[1] = 1;
val[2] = 2;
for (var i = 3; i <= n; ++i)
val[i] = val[i - 1] + val[i - 2];
return val[n - 1];
}
}
迭代實現(xiàn)斐波那契數(shù)列
function iterFib(n){ //得到第n個數(shù)列值
var a = 1, b = 1, temp;
for(var i = 2; i <= n; i++){
temp = b;
b = a + b;
a = temp;
}
return a;
}
迭代實現(xiàn)斐波那契數(shù)列 ES6
function* fibs(){
let a = 1;
let b = 1;
while(1){
yield a;
[a, b] = [a, a + b];
}
}
var [first, second, third, forth, fifth, sixth] = fibs();
數(shù)組元素去重復(fù)
function unique(arr) {
return arr.filter(function(item, index){
return arr.indexOf(item) === index;
});
} //除去所以 undefined
//以下是 ES6 方法
function unique(arr){
return Array.from(new Set(arr));
} //保留數(shù)組中的 undefined
Fisher Yates Shuffle
Array.prototype.shuffle = function(){
var len = this.length;
for(var i = len - 1; i > 0; i--){
var j = Math.round(Math.random() * i);
// debugger;
[this[i],this[j]] = [this[j],this[i]];
}
return this;
}
查找2個字符串的最長公共子串
function lcs(word1, word2){
var max = 0;
var index = 0;
var lcsarr = [];
var str = "";
for(var i = 0; i <= word1.length + 1; ++i){
lcsarr[i] = [];
for(var j = 0; j <= word2.length + 1; ++i)
lcsarr[i][j] = 0;
}
for(var i = 1; i <= word1.length; ++i){
for(var j = 1; j <= word2.length; ++j){
if(word1[i - 1] === word2[j - 1])
lcsarr[i][j] = lcsarr[i - 1][j - 1] + 1;
if(max < lcsarr[i][j]){
max = lcsarr[i][j];
index = i;
}
}
}
if(max === 0)
return "";
else {
for(var i = index - max; i < index; ++i)
str += word1[i];
return str;
}
}
背包問題 遞歸
/**
* [knapsack description]
* @param number capacity 背包容量（最大承重）
* @param array weights 背包內(nèi)物品重量
* @param array value 物品對應(yīng)的價值
* @param number n 物品數(shù)量
* @return number 求的的最大價值
*/
function knapsack(capacity, weights, value, n){
if(n === 0 || capacity === 0) return 0;
if(weights[n -1] > capacity) return knapsack(capacity, weights, value, n - 1);
else return Math.max(value[n - 1] + knapsack(capacity - weights[n - 1], weights, value, n - 1), knapsack(capacity, weights, value, n - 1));
}
背包問題 動態(tài)規(guī)劃
/**
* [knapsack description]
* @param number capacity 背包容量（最大承重）
* @param array weights 背包內(nèi)物品重量
* @param array value 物品對應(yīng)的價值
* @param number n 物品數(shù)量
* @return number 求的的最大價值
*/
function dKnapsack(capacity, weights, value, n){
var K = []; //價格矩陣
for(var i = 0; i <= n; i++)
K[i] = [];
for(var i = 0; i <= n; i++){
for(var w = 0; w <= capacity; w++){
if(i == 0 || w == 0)
K[i][w] = 0;
else if(weights[i - 1] <= w)
K[i][w] = Math.max(value[i - 1] + K[i - 1][w - weights[i - 1]], K[i - 1][w]);
else
K[i][w] = K[i - 1][w];
console.log(K[i][w] + " ");
}
console.log();
}
return K[n][capacity];
}
背包問題 貪心法
/**
* [knapsack description]
* @param number capacity 背包容量（最大承重）
* @param array weights 背包內(nèi)物品重量
* @param array value 物品對應(yīng)的價值
* @return number 求的的最大價值
*/
function dKnapsack(capacity, weights, values){
var load = 0;
var i = 0;
var w = 0;
while(load < capacity && i < 4){
if(weight[i] <= (capacity - load)){
w += value[i];
load += weight[i];
} else {
var r = (capacity - load) / weight[i];
w += r * value[i];
load += weights[i];
}
++i;
}
return w;
}
找零問題 貪心法
function makeChange(origAmt, coins){
var remainAmt = 0;
if(origAmt % .25 < origAmt){
coins[3] = parseInt(origAmt / .25);
remainAmt = origAmt % .25;
origAmt = remainAmt;
}
if(origAmt % .1 < origAmt){
coins[2] = parseInt(origAmt / .1);
remainAmt = origAmt % .1;
origAmt = remainAmt;
}
if(origAmt % .05 < origAmt){
coins[1] = parseInt(origAmt / .05);
remainAmt = origAmt % .05;
origAmt = remainAmt;
}
coins[0] = parseInt(origAmt / .01);
}
function showChange(coins){
if(coins[3] > 0) console.log("25美分數(shù)量- " + coins[3] + " - " + coins[3] * .25);
if(coins[2] > 0) console.log("10美分數(shù)量- " + coins[2] + " - " + coins[2] * .1);
if(coins[1] > 0) console.log("5美分數(shù)量- " + coins[1] + " - " + coins[1] * .05);
if(coins[0] > 0) console.log("1美分數(shù)量- " + coins[0] + " - " + coins[0] * .01);
}
最大公約數(shù) 輾轉(zhuǎn)相除法
function gcd(a, b){
return b === 0 ? a : gcd(b, a%b);
}
最大公約數(shù) 更相減損術(shù)
function gcd(a, b){
return a === b ? a : a < b ? gcd(a, b-a) : gcd(b, a-b);
}
hanoi塔 遞歸
function re_hanoi(n, a, b, c){
if(n !== 0){
re_hanoi(n - 1, a, c, b);
console.log(a + " => " + b + "\n");
re_hanoi(n - 1, c, b, a);
}
}
hanoi塔 非遞歸
function hanoi(n){ //0 1 2 共3個塔
for(var t = 1; t < 1 << n; t++){
var first, second;
switch((t & t - 1) % 3){
case 0: first = 'a'; break;
case 1: first = 'b'; break;
case 2: first = 'c'; break;
default: break;
}
switch(((t | t - 1) + 1) % 3){
case 0: second = 'a'; break;
case 1: second = 'b'; break;
case 2: second = 'c'; break;
default: break;
}
console.log(first + " => " + second + "\n")
}
}
查找n以內(nèi)的最大質(zhì)數(shù)(埃拉托色尼法)
function maxPrime(n){
var a = new Array(n + 1);
var max = Math.floor(Math.sqrt(n));
var p = 2;
while(p <= max){
for(var i = 2 * p; i <= n; i += p)
a[i] = 1;
while(a[++p]) /* empty */;
}
while(a[n]) n--;
return n;
}
身份證號碼末尾校驗碼
/**
* [indentify description]
* @param String str 身份證號碼
* @return Boolean 是否合法身份證號
*/
function indentify(str)
{
var weight = [7, 9, 10, 5, 8, 4, 2, 1, 6, 3, 7, 9, 10, 5, 8, 4, 2];
var check = ["1", "0", "X", "9", "8", "7", "6", "5", "4", "3", "2"];
if(str.length !== 18) {
alert("input error");
str="";
} else {
var substr = str.slice(0, 17);
var last = str.slice(-1);
var S = 0;
for(var i = 0; i < 17; i++) {
S += substr[i] * weight[i];
}
S = S % 11;
if(check[S] === last.toUpperCase()) {
return true;
} else {
str="";
return false;
}
}
}
青蛙跳臺階 動態(tài)規(guī)劃
一只青蛙一次可以跳上1級臺階，也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法。
function jumpFloor(number){
if(number < 1){
return 0;
}
if(number === 1){
return 1;
}
if(number === 2){
return 2;
}
var temp = 0, a = 1, b = 2;
for(var i = 3; i <= number; i++){
temp = a + b;
a = b;
b = temp;
}
return temp;
}
