本文包括js學習中簡單功能的算法數據結構及基本排序、查找算法
包括對js以及DOM和BOM的研究過程中一些有意思的代碼實現
本文還包括公司面試相關算法問題的代碼段,但不會指出是哪個公司出的題
這個部分內容比較多,請查看一下博客:
基于 Javascript 的排序算法
基于 javascript 的基本數據結構和查找算法
遞歸實現斐波那契數列function reFib(n){ if (n < 2) return n; else return reFib(n - 1) + reFib(n - 2); }動態規劃實現斐波那契數列
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]; } }迭代實現斐波那契數列
function iterFib(n){ //得到第n個數列值 var a = 1, b = 1, temp; for(var i = 2; i <= n; i++){ temp = b; b = a + b; a = temp; } return a; }迭代實現斐波那契數列 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();數組元素去重復
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)); } //保留數組中的 undefinedFisher 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 背包內物品重量 * @param array value 物品對應的價值 * @param number n 物品數量 * @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)); }背包問題 動態規劃
/** * [knapsack description] * @param number capacity 背包容量(最大承重) * @param array weights 背包內物品重量 * @param array value 物品對應的價值 * @param number n 物品數量 * @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 背包內物品重量 * @param array value 物品對應的價值 * @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美分數量- " + coins[3] + " - " + coins[3] * .25); if(coins[2] > 0) console.log("10美分數量- " + coins[2] + " - " + coins[2] * .1); if(coins[1] > 0) console.log("5美分數量- " + coins[1] + " - " + coins[1] * .05); if(coins[0] > 0) console.log("1美分數量- " + coins[0] + " - " + coins[0] * .01); }最大公約數 輾轉相除法
function gcd(a, b){ return b === 0 ? a : gcd(b, a%b); }最大公約數 更相減損術
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 + " "); 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以內的最大質數(埃拉托色尼法)
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; } } }青蛙跳臺階 動態規劃
一只青蛙一次可以跳上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; }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/97610.html
摘要:哪吒社區技能樹打卡打卡貼函數式接口簡介領域優質創作者哪吒公眾號作者架構師奮斗者掃描主頁左側二維碼,加入群聊,一起學習一起進步歡迎點贊收藏留言前情提要無意間聽到領導們的談話,現在公司的現狀是碼農太多,但能獨立帶隊的人太少,簡而言之,不缺干 ? 哪吒社區Java技能樹打卡?【打卡貼 day2...
摘要:本文介紹支付寶中的深度學習引擎。因而無論在運行速度和內存占用等性能指標還是在兼容性上,支付寶的移動端都必須做到極致,才能較大幅度地降低使用門檻。五大目標支付寶是針對國民環境定制開發的移動端解決方案,項目制定了如下技術目標。 本文介紹支付寶App中的深度學習引擎——xNN。xNN通過模型和計算框架兩個方面的優化,解決了深度學習在移動端落地的一系列問題。xNN的模型壓縮工具 (xqueeze) ...
閱讀 2022·2023-04-25 23:30
閱讀 1452·2021-11-24 10:18
閱讀 3069·2021-10-09 09:54
閱讀 2017·2021-10-08 10:05
閱讀 3431·2021-09-23 11:21
閱讀 3161·2019-08-30 15:52
閱讀 1560·2019-08-30 13:05
閱讀 1056·2019-08-30 13:02