一个算法题的解决方案往往不止一个,如果你只会暴力法解决算法,那你可能最时间复杂度和空间复杂度了解不够,下面看看如下算法题!
给定一个字符串,判定其是否有效,()有效,()(这个无效,使用栈解决匹配问题,左括号进栈右括号出栈
function isValid(str) { let temp = []; for (let i = 0; i < str.length; i++) { if (str[i] == '(') { temp.push('('); } else { if (temp.length === 0) return false; temp.pop(); } } return temp.length === 0 ? true : false; } console.log(isValid('(())()')); // true console.log(isValid('(((((')); // false上面代码时间复杂度和空间复杂度都为n,其实空间复杂度可以优化为O(1),使用一个变量,初始为0,左括号+1,右括号-1,结果为0即有效
function isValid(str) { let sum = 0; for (let i = 0; i < str.length; i++) { if (str[i] == '(') { sum++; } else { if (sum === 0) return false; sum--; } } return sum === 0 ? true : false; } console.log(isValid('(())()')); // true console.log(isValid('(((((')); // false难度升级,计算最长有效括号,原理·差不多,只是增加计算的括号数量统计
function longestStr(str) { let max = 0; if (str.length == 0 || str.length == 1) return max; let stack = []; for (let i = 0; i < str.length; i++) { let tempMax = 0; // 当前括号匹配长度 for (let j = i; j < str.length; j++) { if (str[j] == '(') { stack.push('('); tempMax++; } else if (str[j] == ')') { if (stack.length < 1) { // 结束,计算max max = max < tempMax ? tempMax : max; break; // 外层下一个循环 } else { stack.pop(); tempMax++; } } } if (stack.length == 0) { max = max < tempMax ? tempMax : max; } stack = []; // 清空栈,下一轮重新开始 } return max; } console.log(longestStr('(())(')); // 4这个算法看似解决了问题,其实他的时间复杂度为O(n^2),我们实际上一次遍历就可以完成,只存下标进栈,计算有效长度。
function longestValidStr(str) { let max = 0; if (str.length < 2) return max; let stack = [-1]; // -1 作为哨兵 for (let i = 0; i < str.length; i++) { if (str[i] == '(') { stack.push(i); } else { stack.pop(); if (stack.length < 1) { stack.push(i); // 栈底元素没有了,有效匹配都匹配,重新进栈 } else { max = Math.max(max, i - stack[stack.length - 1]); } } } return max; } console.log(longestValidStr(')()())')); //这个问题的解决办法很多,比如你可以遍历数组记录出现的次数,但是你是否记得还有一个异或运算符(异或运算满足交换律),即相同的数异或为(n^n=0),任何数与0异或为该数本身,所以不用再创建多余的栈或堆记录遍历结果,节省空间
let arr = [1,2,3,4,5,2,3,4,5]; let res = arr.reduce((pre, next) => { return pre ^ next; }); console.log(res); // 1这个问题想到要记录次数,所以你很可能会选择创建对象存储记录,第一次出现记录1,后面出现累加。
let arr = [1,2,4,2,1,2,3,3,8,4,5,7,6]; function count(arr) { let hash = {}; for (let i of arr) { console.log(i) if (!hash[i]) { hash[i] = 1; } else { hash[i] ++; } } return hash; } console.log(count(arr));这个题目找目标值你得找到一个基准值去与你的目标值比较,这里你可以选择最右边的值为基准去比较,如果比基准值大,继续下一轮比较,找到目标值返回true即可。
let arr = [ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ]; function find(target, array) { var row=array.length, col=array[0].length, i=0, j=col-1; while(i<row&&j>=0){ if(array[i][j]>target){ j--; continue; }else if(array[i][j]<target){ i++; continue; }else{ return true; } return false; } } console.log(find(9, arr)); // true这个问题我相信有算法经验的肯定想用双重循环暴力法求两个元素为目标值,但是时间复杂度就为n^2,其实遍历一次就可以找到结果,将元素记录到hash中,如果遍历中出现了满足的结果,直接从集合中取出即可,这样时间复杂和空间复杂度都为n。
let arr = [2, 7, 11, 15]; var twoSum = function(nums, target) { let mp = new Map(); for (let i = 0; i < nums.length; i++) { if (mp.has(target - nums[i])) { return [mp.get(target - nums[i]),i]; } mp.set(nums[i],i) } }; console.log(twoSum(arr, 9)); //[0,1]问题处理很简单,将数组拼接并排好序,然后取中位数,(1.2 | 0)这个是向下取整的方法。
let num1 = [1,3]; let num2 = [2]; function com(x, y) { let res = x.concat(y).sort((a, b) => { return a - b; }); if (res.length % 2 !== 0) { return res[(res.length / 2) | 0]; } else { return (res[(res.length / 2 - 1)] + res[(res.length / 2)]) / 2; } } console.log(com(num1, num2));主要方法就是字符串转数组,取反之后再转回字符串String(num).split(’’).reverse().join(’’)。
lfunction redo(num) { let r = String(num).split('').reverse().join(''); if (num < 0) { if (r.slice(0,1) == '0') { r = r.slice(1); } r = '-' + r.slice(0,r.length - 1); return Number(r); } else { if (r.slice(0,1) == '0') { r = r.slice(1); } return Number(r); } } console.log(redo(180));很经典的有效括号匹配,使用栈解决,遇到左括号进栈,相同的右括号出栈
function isValid(str) { let temp = { '(': ')', '[': ']', '{': '}' }; let stack = []; for (let i = 0; i < str.length; i++) { if (temp[str[i]]) { stack.push(str[i]); } else if (!stack.length || temp[stack.pop()] !== str[i]) { return false; } } return stack.length == 0; } console.log(isValid('{[()]}')); // true