用户投稿这週归纳了两个演算法技巧，于Matters介绍
我的Matters：前端野人
1.Subarray Sum Equals K
说明: 计算符合k的子组串数量
Example 1:
Input:nums = [1,1,1], k = 2Output: 2思维：
这题我一开始想说可以应用上礼拜的DP来运算，但反而卡住了，我从中得到一个经验，解题目不要预设思维。
这题有个思维很简单，就是每个元素都找出所有组合是否符合k，简单好懂，能AC但速度上是很慢的。
var subarraySum = function(nums, k) { let sum = k let answer = 0 for(let i = 0; i < nums.length ; i ++){ let sum = 0 for(let j = i ; j < nums.length;j++){ sum += nums[j] if(sum == k) answer +=1 } } return answer};这题最佳解是用hashmap，hashmap的解法是一直累加sum，然后在判断 sum -k的值有没有在hashmap里面，有的话就累计。
Answer：
var subarraySum = function(nums, k) { let sum = 0 let hash = new Map() hash.set(0,1) let answer = 0 for(let i = 0 ; i < nums.length ; i++){ sum += nums[i] if(hash.has(sum - k)){ answer += hash.get(sum - k) } hash.set(sum, (hash.get(sum) || 0) + 1) } return answer };2.Bitwise AND of Numbers Range
说明: 程式语言的位元运算子，可参考Bitwise and (or &) of a range - GeeksforGeeks
思维: 题目意思就是得到两个之间所有数字得二进位的共同位数，
而程式语言已经有判断的运算值，只要用&就可以找到了，所以这题问题就会变成是怎么重複做a & b。
我一开始是想试一下以前所学的技巧recursion，所以这样写：
var rangeBitwiseAnd = function(m, n) { let nums = [] let answer = 0 let bitwise = (a,b) =>{ if(b > n) return answer = a & b bitwise(answer, b + 1) } if (m==n) return m & n bitwise(m,m+1) return answer};这样写观念是正确的，但有个致命缺点就是如果跑太多次会出现Maximum call stack size exceeded的错误，所以这是不可行的做法。
最佳解是使用>>运算，>>会将数字的二进位的最右边拿掉，如下面所示，这样就可以找到相似值，但因为是shift，所以结束时要用 <<补0，count是纪录要补几个0。
符合后因为这个运算做了两次，所以答案要补两个
0，100 = 4
var rangeBitwiseAnd = function(m, n) { let count = 0; while (m != n) { count++; m >>= 1; n >>= 1; } return m << count;};3.LRU Cache
说明: 实作 LRU Cache。
Example:
LRUCache cache = new LRUCache( 2 /* capacity */ );cache.put(1, 1);cache.put(2, 2);cache.get(1); // returns 1cache.put(3, 3); // evicts key 2cache.get(2); // returns -1 (not found)cache.put(4, 4); // evicts key 1cache.get(1); // returns -1 (not found)cache.get(3); // returns 3cache.get(4); // returns 4解析:
跟js的Map很像，但存取机制却是跟pop、push一样，而且有容量限制。所以还要在function get(key)，颠倒存放顺序，把后面移到前面，因为当超过容量时，可以使用Map.keys()取得第一个key值，因为Map没有pop的操作，所以要用这种方式，剩下的就可以照题意实作。
Answer:
var LRUCache = function(capacity) { this.capacity =capacity this.hash = new Map()};/** * @param {number} key * @return {number} */LRUCache.prototype.get = function(key) { if(!this.hash.get(key)){ return -1 } const value = this.hash.get(key); this.hash.delete(key); this.hash.set(key, value); return value;};/** * @param {number} key * @param {number} value * @return {void} */LRUCache.prototype.put = function(key, value) { if(this.hash.has(key)) this.hash.delete(key) this.hash.set(key,value) // 超过就把第一个value删掉。 if(this.hash.size > this.capacity){ const ind =this.hash.keys().next().value this.hash.delete(ind) }};4.Jump Game
说明：以阵列中的元素作为移动距离，依照元素加总向右位移，判断能否指向最后一个元素。
Example 1:
Input: nums = [2,3,1,1,4]Output: trueExplanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.Example 2:
Input: nums = [3,2,1,0,4]Output: falseExplanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it 思维：
这题有一个最基本的解法是用Backtracking，因为是使用recursion，所以数组太多时会Time Limit Exceeded，但是观念来说是有助于理解这题的解法。
题目所述，每个元素代表的是maximum jump length，所以最少为1，而Backtracking则是判断每个可能移动的距离来确认要选哪个距离量并往下探访直到不能走为止，所以这样走确实会因为数组长度太大而不能AC。
var canJump = function(nums) { const canJumpFormPosition = (position, nums) => { if(position == nums.length -1 ){ return true } const furthestJump = Math.min( position + nums[position] , nums.length -1) for(let nextPosition = furthestJump ; nextPosition > position ; nextPosition --){ if(canJumpFormPosition(nextPosition ,nums)) return true } return false } return canJumpFormPosition(0,nums)};但是Backtracking仍然是正确的思路，所以如果要AC就要让Backtracking不做没有必要的走访。为了减少不必要的走访，就要暂存确定不能走的索引值，所以要用memo来判断是否能用。首先先记录所有元素是Unknown，只要是能继续走访的元素就是Good。如果不是那就是Bad，虽然能AC但这是最差的解法，最后还有最佳优化解。
var canJump = function(nums) { const type ={ Good:"G", Bad :"B", Unknown:"U", } let memo = new Array(nums.length) for(let i = 0 ; i < nums.length ; i++){ memo[i] = type.Unknown } memo[nums.length - 1] = type.Good const canJumpFormPosition = (position, nums) => { if(memo[position] !== type.Unknown){ return memo[position] == type.Good ? true : false; } const furthestJump = Math.min( position + nums[position] , nums.length -1) for(let nextPosition = furthestJump ; nextPosition > position ; nextPosition --){ if(canJumpFormPosition(nextPosition ,nums)){ memo[position] = type.Good return true } } memo[position] = type.Bad; return false } return canJumpFormPosition(0,nums)};最佳解为Greedy，我们可以观察到如果元素不是0的话通常是能到终点的，而Greedy就直接判断，i + nums[i]是否刚好或是大于nums.length，因为能到达终点的话距离一定会大于nums.length或是刚好等于nums.length，Greedy从最后一个元素开始找。只要能超过那该元素的索引值就往回找而且到达该索引的距离一定大于或等于到该索引的长度，如果是能过的话那最后一定会找到起点。这样确实快很多，但思维就跟Backtracking截然不同，Backtracking是照题意思考，而Greedy则是归纳出最简单解的思维而得出。
var canJump = function(nums) { let lastInd = nums.length - 1 for(let i = lastInd ; i >= 0 ; i--){ if(i + nums[i] >= lastInd){ lastInd = i } } return lastInd == 0};5.Longest Common Subsequence
说明：经典的最长公子序列。
Example 1:
Input: text1 = "abcde", text2 = "ace" Output: 3 Explanation: The longest common subsequence is "ace" and its length is 3.Example 2:
Input: text1 = "abc", text2 = "abc"Output: 3Explanation: The longest common subsequence is "abc" and its length is 3.Example 3:
Input: text1 = "abc", text2 = "def"Output: 0Explanation: There is no such common subsequence, so the result is 0.思维：一开始我是想用hashmap纪录所有相同的字母数量然后累计最小次数，但有一个问题是题目有补充：(eg, "ace" is a subsequence of "abcde" while "aec" is not)如果顺序不对的话就不算，所以这想法就只能放弃。
所以最后还是要回来看LCS的原理，下图是LCS的演算法图示，LCS使用DP做出两个字串比对的二维阵列，但长宽会比两个字串的长度还多1，原因是在于DP会用dp[i-1]累计，所以开头要有初始值，迴圈开始判断有没有相符合的字母，但下面的走访图会发现一个问题，好像走访并没有看顺序而是累计一样的次数而已，其实LCS是找出可能的子序列最后在找出最长的序列，下面第二张图可以看到真正走访的结果。
这张图才是LCS真正做的事，LCS找出了A、G、AC、GC、GA，这几个子序列，其中最长的子序列为2。所以DP是用来纪录可能的子序列长度
var longestCommonSubsequence = function(text1, text2) { const dp = []; let m = text1.length; let n = text2.length; for (let i = 0; i <= m; i++) { dp[i] = new Array(n + 1).fill(0); } for (let i = 1; i <= m; i++) { for (let j = 1; j <= n; j++) { if (text1.charAt(i - 1) != text2.charAt(j - 1)) { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } else { dp[i][j] = dp[i - 1][j - 1] + 1; } } } return dp[m][n];};6. Maximal Square
说明在二维阵列中找出1的範围所围成最大正方形。
Example:
Input: 1 0 1 0 01 0 `1 1` 11 1 `1 1` 11 0 0 1 0Output: 4思维：
首先要先找出，二维阵列的长宽(m,n)
let rows = matrix.length let cols = row !== 0 ? 0 : matrix[0]再来是设计dp，max为正方形的长宽，最小的正方形为一个1，所以在设计dp时就需要找出max，因为dp都是从dp[1][1]开始所以要先设定好最外围的值。
for(let i = 0 ; i < rows ; i++){ dp[i] = new Array(cols).fill(0)}for (let i = 0; i < rows; i++) { dp[i][0] = Number(matrix[i][0]); max = Math.max(max, dp[i][0]);}for (let j = 0; j < cols; j++) { dp[0][j] = Number(matrix[0][j]); max = Math.max(max, dp[0][j]);}[ [ 1, 0, 1, 0, 0 ], [ 1, 0, 0, 0, 0 ], [ 1, 0, 0, 0, 0 ], [ 1, 0, 0, 0, 0 ] ]找出，matrix最外围的值后就可以开始从dp[1][1]运算，每次找到1就要判断他是否为正方形，所以就要找1的左上角，上面，左边是否为1，假设有一角是0那dp纪录当下的元素1，提供下一个元素判断。
for (let i = 1; i < rows; i++) { for (let j = 1; j < cols; j++) { if (matrix[i][j] === 1) { dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1; max = Math.max(max, dp[i][j]); } }}照判断走完，最后会得到结果:
[ [ 1, 0, 1, 0, 0 ], [ 1, 0, 1, 1, 1 ], [ 1, 1, 1, 2, 2 ], [ 1, 0, 0, 1, 0 ] ]dp的思维是把dp[1][1]当作是正方形的右下角，这样就可以用dp的特性找出其他三角是否都有1，假设右下角为1再找min(其他三角)为多少，只要其他三角都一样长度，那自然就能在右下角得到正方形的长宽。
7. Binary Tree Maximum Path Sum
说明：找出二元树中最大的子树。
思维：先想哪个root,left,right加起来最大，所以会先得出一个规则:
sum = node.left + node.right + node.val但又要思考，每个root又可能是其他node的left或是right，所以要想如果是root节点的left跟right是不是就是这节点之下最大的和。
这样就能套用到每个node，以example 2当例子。
Example 1:
Input: [1,2,3] 1 / \ 2 3Output: 6Example 2:
Input: [-10,9,20,null,null,15,7] -10 / \ 9 20 / \ 15 7Output: 42而我们只抓max(sum)所以答案是42，所以dfs就是找当下节点下这棵树最大值为何。
Answer：
var maxPathSum = function(root) { let sum = root.val; const dfs = (node) => { if (!node) return 0; const left = Math.max(dfs(node.left), 0), right = Math.max(dfs(node.right), 0); sum = Math.max(left + right + node.val, sum); return Math.max(left, right) + node.val; } dfs(root); return sum;};结尾
好不容易做好第一篇系列文，但没想到后面这么硬，但也因此学到比较深入的程式思维
原本计画这系列写完就开始做side project，而刚好今天 @海绵宝宝 想找人做 open source 我就顺势接下去玩了。
微信扫一扫打赏
支付宝扫一扫打赏
