简介
文中所有题目均为精心挑选过的超高频题目，所以大家可以收藏起来
适用人群
针对有一定数据结构基础(了解链表, 二叉树, 二叉堆, 递归)的基本概念,并对时间空间复杂度有基本认知的。
食用指南
将文中列出的每道题至少手写 3 遍
面试前可以按照本文整理出来的题目直接过一遍
说明
文章更新频率: 除休息日外,每天在题目下方更新一道题的题解
有 LeetCode 原题的将贴上原地址，不在文章内做题目描述
Tc: Time complexity (时间复杂度)
Sc: Space complexity (空间复杂度)
题目类型
数组篇
1.twoSum [要求 Tc: O(n) Sc:O(n)] (字节跳动)
LeetCode 第 1 题
按照题目要求,我们第一时间想到的会是两层循环暴力解法：
解法 1：Time = O(n²), Space = O(1)
思路:遍历每个元素 nums[j]，并查找是否存在一个值与 target - nums[j] 相等的目标元素。
function twoSum(nums, target) { for (let i = 0; i < nums.length; i++) { for (let j = i + 1; j < nums.length; j++) { if (nums[j] == target - nums[i]) { return [i,j]; } } } return [];}
复制代码
**解法 2:Time = O(n), Space = O(n)**：
我们可以通过哈希表空间换时间。在进行迭代并将元素插入到表中的同时，我们回过头来检查哈希表中是否已经存在当前元素所对应的目标元素，如果存在，那我们就找到了问题的解，将其返回即可.(时间复杂度为 O(n),空间复杂度也为 O(n))
符合题目要求 bingo✌
var twoSum = function(nums, target) { let reduceHash = {}; for (let i = 0; i < nums.length; i++) { let reduceResult = target - nums[i]; if (reduceHash[reduceResult] !== undefined) { return [reduceHash[reduceResult], i]; } reduceHash[nums[i]] = i; }};
复制代码
参考视频：传送门
2.缺失的数字 [要求 Tc: O(n) Sc:O(n)] (字节跳动)
剑指 Offer 第 53 题
解法：
思路:我们先把所有输入了的数字存入 hash 表,因为给定的数组是有序的，所以可以再过一遍 hash 表，遍历过程中如果某个数字在 hash 表中不存在，则该数字就是缺失的那个数字
var missingNumber = function(nums) { const hash = {}; for (let i = 0; i < nums.length; i++) { hash[nums[i]] = true; } let expectedNumCount = nums.length + 1; for (let i = 0; i < expectedNumCount; i++) { if (!hash[i]) { return i; } } return -1;};
console.log(missingNumber([0,1,2,4]));//3
复制代码
3.移动零 [要求 Tc: O(n) Sc:O(1), 移动后不能改变原来其他元素的相对位置] (二线公司)
LeetCode 第 283 题
解法：
思路: 双指针同向而行,fast 指针遇到非 0 就把 slow 指针位置的字符替换掉，slow 指针前进一步。直到 fast 指针把数组所有元素遍历完毕。(典型的两个挡板，三个区域思想),再把 slow 指针后面的所有元素替换为 0。
同向性质:
变量的物理意义: slow 的左侧不包含 slow 都是非 0 的数字，slow 的右侧包含 slow 都应该为 0，按照这个物理意义就可以达到原地算法的要求。因为快慢指针是同向而行的，所以算法为稳定算法(不会影响元素的相对位置)
var moveZeroes = function(nums) { let slow = 0; for (let fast = 0; fast < nums.length; fast++) { if (nums[fast] !== 0) { nums[slow++] = nums[fast]; } } while (slow < nums.length) { nums[slow++] = 0; }};const input = [0,1,5,8,4,3,0,5,0];moveZeroes(input);console.log(input);
复制代码
4.洗牌算法(乱序数组)[要求 Tc: O(n) Sc:O(1),要求每个元素的打乱的概率相同] (快手)
LeetCode 第 384 题
解法:
思路: 本题思路就是使用 Fisher-Yates 洗牌算法。
function shuffle(arr) { let m = arr.length; while (m) { let random = (Math.random() * m--) | 0; [arr[random],arr[m]] = [arr[m],arr[random]]; } return arr;}console.log(shuffle([1,5,6,7,6]));
复制代码
5.两个数组的交集 [要求 Tc: O(n) Sc:O(n)] (阿里)
LeetCode 第 349 题
解法:
思路: 本题思路是看 nums1 数组里是否含有 nums2 的元素，如果有就添加到结果中返回。
let res = [];for (let i = 0; i < nums1.length; i++) { const cur = nums1[i]; if (nums2.includes(cur)) { res.push(cur); }}return Array.from(new Set(res));
复制代码
6.RainbowSort [要求 Tc: O(n) Sc:O(1)] (盛大)
给定一系列球，其中球的颜色只能是红色，黄色或蓝色，对球进行排序，以使所有红色球都分组在左侧，所有黄色球都分组在中间，所有蓝色球分组在右侧。
例：
[红]被排序为[红]
[黄，红]被排序为[红，黄]
[黄,红,红,蓝,黄,红,蓝]被排序为[红,红,红,黄,黄,蓝,蓝]
假设条件:
输入数组不为 null。
corner case:
如果输入数组的长度为零怎么办？在这种情况下，我们应该直接返回空数组。
解法：
思路: 本题思路是挡板思想,使用三个挡板四个区域的思想进行划分(交换数组元素位置)
挡板的物理意义: [0-i)全是红色,[i,j)之间为黄色,(k->n-1]全为蓝色，[j-k]为未知探索区域
j 为快指针
const input = ['黄','红','红','蓝','黄','红','蓝']function rainbowSort(rainbow) { let i = 0, j = 0, k = rainbow.length - 1; while (j <= k) { if (rainbow[j] === '红') { swap(rainbow,i,j); i++; j++; } if (rainbow[j] === '黄') { j++; } if (rainbow[j] === '蓝') { swap(rainbow, j, k); //这里不写j++是因为从k交换过来的元素不能保证就是黄色,为了安全起见下次循环再检查一次j位置。 k--; } }}//辅助交换函数function swap(arr,i,j) { [arr[i],arr[j]] = [arr[j],arr[i]]}rainbowSort(input);console.log(input);
复制代码
7.移除元素 [要求 Tc: O(n) Sc:O(1)]
LeetCode 第 27 题
解法：
思路: 双指针同向而行,快指针遇到非 val 就把 slow 指针位置的字符替换掉，slow 指针前进，直到数组所有元素遍历完毕。(典型的两个挡板，三个区域思想)
变量的物理意义: slow 的左侧不包含 slow 都是非 val 的元素，slow 的右侧包含 slow 都应该为不包含 val 的元素，按照这个物理意义就可以达到原地算法的要求。因为快慢指针是同向而行的，所以算法为稳定算法(不会影响元素的相对位置)
挡板性质:
同向而行: slow 指针左边是处理好的元素 fast 指针右边是未知探索区域,两个挡板中间不关注(最后的结果不会改变元素相对位置)
var removeElement = function(nums, val) { let slow = 0; for(let fast = 0; fast < nums.length; fast++) { if (nums[fast] !== val) { nums[slow++] = nums[fast]; } } return slow; //想要拿到去除后的数组可以: nums.slice(0,slow);};
复制代码
8.按奇偶排序数组[要求 Tc: O(n) Sc:O(1)] (腾讯)
LeetCode 第 905 题
解法：
思路: 继续使用挡板思想,两个挡板三个区域,同向而行,[0-i)是偶数,[j-n-1]是未探索区域
挡板性质:
同向而行: slow 指针左边是处理好的元素 fast 指针右边是未知探索区域,两个挡板中间不关注(最后的结果不会改变元素相对位置)
解法 1:(不改变元素相对位置:同向而行)
var sortArrayByParity = function(A) { for (let i = 0, j = 0; j < A.length; j++) { if (A[j] % 2 === 0) swap(A, i++, j); } return A;};function swap(arr,l,r) { [arr[l],arr[r]] = [arr[r],arr[l]];}
console.log(sortArrayByParity([3,1,2,4]));
复制代码
挡板性质:
相向而行: left 指针左边是处理好的元素,right 指针右边也是处理好的元素, 两个挡板中间是未处理区域(最后的结果可能会改变元素相对位置)
解法 2:(改变元素相对位置:相向而行)
var sortArrayByParityII = function(A) { let i = 0, j = A.length - 1; while (i <= j) { if (A[i] % 2 === 0) { i++; } else if (A[j] % 2 !== 0) { j--; } else { //i % 2 !== 0 && j % 2 === 0 swap(A,i,j); i++; j--; } } return A;};function swap(arr, l, r) { [arr[l], arr[r]] = [arr[r], arr[l]];}
console.log(sortArrayByParityII([3,1,2,4]));
复制代码
9.数组中出现次数超过一半的数字 [要求 Tc: O(n) Sc:O(1)]
LeetCode 第 169 题
思路: 这道题属于火拼问题,见一个 sha 一个(抵消),最后留下的就是超过一半的元素。
先保留第一个元素，接着遍历，如果遇到和他相同的则加次数，否则就减次数，如果次数为 0 了就要换另一个元素了。
比如: A B C A
第一次保留 A,用 A 跟剩下的打架，碰到不是 A 的就把 A 的个数减 1，如果遇到 A 就增加个数，直到遇到不同的元素把 A 的次数抵消完就把 A 踢下去,并且把次数重新设置为 1。
如此下去最后肯定有个多出来的就是题解了。
var majorityElement = function(array) { let count = 1; let num = array[0]; for (let i = 1; i < array.length; i++) { if (num !== array[i]) { count--; if (count === 0) { num = array[i]; count = 1; } } else { count++; } } return num;};let halfValue = majorityElement([1,1,2,3]);console.log(halfValue); //1
复制代码
10.合并两个有序数组 [要求 Tc: O(m + n) Sc:O(n)] (腾讯)
例:
输入:nums1 = [1,3], nums2 = [4,5,7]
输出: [1,3,4,5,7]
function merge(left, right) { let result = []; let i = 0, j = 0; while (i < left.length && j < right.length) { result.push(left[i] < right[j] ? left[i++] : right[j++]); } while (i < left.length) { result.push(left[i++]); } while (j < right.length) { result.push(right[j++]); } return result;}let merged = merge([1,3],[4,5,7]);console.log(merged);
复制代码
11.有序数组中小于某个数的个数 [要求 Tc: O(logn) Sc:O(1)] (今日头条)
例:
输入:[1, 2, 3, 4]
输入目标值:2
输出: 1
思路: 题目提到有序数组，第一时间就应该想到二分(再加之复杂度要求 logn 级别)。其实这道题就是让写个二分查找,仔细想想，你要找的那个数的下标不就代表前面有几个比他小的数字吗？
function binarySearch(array, target) { let low = 0; let high = array.length - 1; while (low <= high) { const mid = (low + (high - low) / 2) | 0; const middleValue = array[mid]; if (middleValue > target) { high = mid - 1; } else if (middleValue < target) { low = mid + 1; } else { return mid; } }}const minCount = binarySearch([1, 2, 3, 4], 2);console.log(minCount); // 1
复制代码
12.数组去重[要求 Tc: O(n) Sc:O(1)]
LeetCode 第 26 题
该算法要求原地算法，所以继续使用挡板思想(没理解的可以回到上文提及处继续理解)。
因为他至少有一个元素是不会重复的(至少会保留一个元素)，所以从下标 1 开始处理。
解法 1: 从索引 1 开始(处理好的元素不包含 slow 位置)
var removeDuplicates = function(arr) { let slow = 1; for (let fast = 1; fast < arr.length; fast++) { if (arr[fast] === arr[slow - 1]) { continue; } arr[slow++] = arr[fast]; } return slow; //想要拿到去除后的数组可以: arr.slice(0, slow);};
复制代码
解法 2: 从索引 0 开始,(处理好的元素包含 slow 位置)
var removeDuplicates = function(arr) { let slow = 0; for (let fast = 1; fast < arr.length; fast++) { if (arr[fast] === arr[slow]) { continue; } arr[++slow] = arr[fast]; } return slow + 1; //想要拿到去除后的数组可以: arr.slice(0, slow + 1);};
复制代码
13.去掉连续的 a 和 c,保留所有 b [要求 Tc: O(n) Sc:O(1) 元素相对位置不变] (字节跳动)
思路: 还是使用快慢指针,同向而行
function removeAC(arr) { let slow = 0,fast = 0; while (fast < arr.length) { if (arr[fast] === 'b') { arr[slow++] = arr[fast++]; } else { let begin = fast; while (fast < arr.length && arr[fast + 1] === arr[begin]) { fast++; } if (fast - begin === 0) { arr[slow++] = arr[fast++]; } else { fast++; } } } return arr.slice(0,slow).join('');}const result = j1(['a','a','b','c','b','c','c']);console.log(result);//bcb
复制代码
14.最长公共前缀 (拼多多)
例: ['aaafsd', 'aawwewer', 'aaddfff'] => 'aa'
LeetCode 第 14 题
function LCP(arr) { if (!arr.length) { return ''; } let ans = arr[0]; for (let i = 1; i < arr.length; i++) { let j = 0; for (;j < ans.length && j < arr[i].length; j++) { if (ans[j] !== arr[i][j]) { break; } } ans = ans.substr(0,j); if (ans === "") { return ans; } } return ans;}let result = LCP(['aaafsd', 'aawwewer', 'aaddfff']);console.log(result);
复制代码
15.给定一个整数数组 a，其中 1 ≤ a[i] ≤ n （n 为数组长度）, 其中有些元素出现两次而其他元素出现一次,找到所有出现两次的元素[要求 Tc: O(n) Sc:O(1)] (字节跳动)
例:输入:[4,3,2,7,8,2,3,1]输出:[2,3]
解：目前没有思路
16.数组中所有元素组成的最大数是多少 (作业帮)
例: [50, 2, 5, 9] => 95502
思路: 我们把最大的数字依次排序肯定就是最大数(降序排列)
var largestNumber = function(nums) { nums = nums.sort((a, b) => { let S1 = `${a}${b}`; let S2 = `${b}${a}`; return S2 - S1; }); return nums[0] ? nums.join('') : '0';};
复制代码
LeetCode 第 179 题
字符串篇
1.回文数 [要求 Tc: O(log10n) Sc:O(1) 或 Tc: O(n) Sc:O(1)] (腾讯)
LeetCode 第 9 题
思路: 使用双指针一个在前，一个在后, 前后对比。遇到两个指针不同就返回 false。
function palindrome(x) { let i = 0, j = x.length - 1; while (i <= j) { if (x[i] !== x[j]) { return false; } else { i++; j--; } } return true;}let result = palindrome('lol');console.log(result);
复制代码
2.反转字符串 [要求 Tc: O(n) Sc:O(1)]
LeetCode 第 344 题
思路: 使用双指针一个在前，一个在后, 每次都交换即可
var reverseString = function(s) { let slow = 0; for (let fast = s.length - 1, slow = 0; fast >= slow; fast--) { swap(s, slow++, fast); }};function swap(arr, l, r){ let temp = arr[l]; arr[l] = arr[r]; arr[r] = temp;}
复制代码
3.翻转单词顺序 [要求 Tc: O(n) Sc:O(n)] (字节跳动)
剑指 Offer 第 58 题
思路: 将字符串按空格分割,然后按照上题的方法交换单词顺序即可。
var reverseWords = function(s) { let strArr = s.split(' ').filter(Boolean); let reversed = strArr; reverse(reversed, 0, reversed.length - 1); return reversed.join(' ');};function reverse(input, left, right) { if (left >= right) { return; } swap(input, left, right); reverse(input, left + 1, right -1);}function swap(arr, l, r) { [arr[l],arr[r]] = [arr[r],arr[l]];}
复制代码
4.有效的字母异位词(Anagram) [要求 Tc: O(n) Sc:O(n)]
LeetCode 第 242 题
思路: 我们可以使用 hash 存储每个单词出现的次数，再用另一个字符串遍历一次进行减减操作，只要次数有不等于 0 的字母则返回 false
var isAnagram = function(s, t) { if (s.length !== t.length) return false;
let map = new Map();
for (let item of s) { if (map.get(item)) { map.set(item, map.get(item) + 1); } else { map.set(item, 1); } } for (let item of t) { if (map.get(item)) { map.set(item, map.get(item) - 1); } else { return false; } } return true;};
复制代码
5.找出字符串中出现次数最多的字母 [要求 Tc: O(n) Sc:O(n)]
例 1: 输入 'abccdtc'
输出: 'c'
例 2: 输入 'abbbbccdtc'
输出: 'b'
function maxCount(str) { let hash = {}; let maxCount = 0; let maxElement = ''; for (let i = 0; i < str.length; i++) { let cur = str[i]; if (hash[cur]) { hash[cur]++; } else { hash[cur] = 1; } if (maxCount < hash[cur]) { maxElement = cur; maxCount = hash[cur]; } } return maxElement;}let letter = maxCount('abccdtc');console.log(letter);
复制代码
6.替换空格 [要求 Tc: O(n) Sc:O(1) 不允许使用正则表达式] (今日头条)
剑指 Offer 第 5 题
思路: 使用快慢指针,同向而行，快指针负责判断是不是空格，慢指针左侧都是处理好的元素。
var replaceSpace = function(s) { s = s.split(''); for (let fast = 0; fast < s.length; fast++) { if (s[fast] === ' ') { s[fast] = '%20'; } } return s.join('');};
复制代码
其他解法(不推荐面试中使用):
var replaceSpace = function(s) { s = s.split(' ').join('%20'); return s;};
var replaceSpace = function(s) { s = s.replace(/\s+/g,'%20'); return s;};
复制代码
7.第一个只出现一次的字符 [要求 Tc: O(n) Sc:O(n)]
剑指 Offer 第 50 题
思路: 遍历过程中存 hash 表,如果当前值第一次出现就设置为 false,后续处理遍历值为 false 的,遇到为 false 的就直接返回。
var firstUniqChar = function(s) { let hash = {}; let firstAppearLetter = ''; if (s === '') { return ' '; } else { for (let i = 0; i < s.length; i++) { if (hash[s[i]] === undefined) { hash[s[i]] = false; } else { hash[s[i]] = true; } } } for (let [key, value] of Object.entries(hash)) { if (!value) { return key; } } return ' '};
复制代码
8.左旋转字符串 [要求 Tc: O(n) Sc:O(n)]
剑指 Offer 第 58 题
var reverseLeftWords = function(s, n) { let frontStr = s.slice(0, n); let backStr = s.slice(n); return backStr + frontStr;};
复制代码
9.字符串全排列 [要求 Tc: O(n!) Sc:O(n²)] (阿里)
剑指 Offer 第 38 题
var permutation = function(s) { let solution = []; if (s.length === 0) { return solution; } permutationHelper(s, solution); return solution;};function permutationHelper(s, solution, used = [], path = []) { if (path.length === s.length) { solution.push(path.slice(0).join('')); return; } let levelSet = new Set(); for (let i = 0; i < s.length; i++) { if (!levelSet.has(s[i])) { if (!used[i]) { used[i] = true; levelSet.add(s[i]); path.push(s[i]); permutationHelper(s, solution, used, path); used[i] = false; //回溯 path.pop();//回到母节点往右走时应该删除添加过的节点,防止保留意外的结果 } } }}
复制代码
10.合并连续数字 [要求 Tc: O(n) Sc:O(1)] (今日头条)
题目描述:
输入:[0, 2, 3, 5, 6, 7, 8, 9, 11, 13, 56, 57]
输出结果：
0,2-3,5-9,11,13,56-57
思路: 三指针,同向而行,slow 左边的为处理好的元素,f 指针快速向前走,begin 指针记录区间开始区间, prev 指针记录区间结束位置。
function combine(arr) { let f = 1, slow = 0; let prev = -1; while (f < arr.length) { let begin = f - 1; prev = arr[begin]; while (f < arr.length && arr[f] - prev === 1) { prev = arr[f]; f++; } if (f - begin === 1) { if (arr[f + 1] - arr[f] !== 1) { !begin ? arr[slow++] = arr[begin] : arr[slow++] = arr[f]; } else { if (!begin) arr[slow++] = arr[begin]; } f++; } else { arr[slow++] = arr[begin] + `-` + prev; } } return arr.slice(0, slow).join(',');}let res = combine([0, 2, 3, 5, 6, 7, 8, 9, 11, 13, 56, 57]);console.log(res);
复制代码
11.字符串相加 (腾讯)
LeetCode 第 415 题
var addStrings = function(num1, num2) { let res = []; let i = num1.length - 1, j = num2.length - 1, carry = 0; while (i >= 0 || j >= 0) { let n1 = i >= 0 ? num1.charAt(i) - 0: 0; let n2 = j >= 0 ? num2.charAt(j) - 0: 0; let tmp = n1 + n2 + carry; carry = parseInt(tmp / 10);//算出十位数 res.push(tmp % 10);//算出个位数 i--; j--; } if(carry == 1) res.push('1'); return res.reverse().join('')};
复制代码
栈/队列篇
1.实现一个栈，入栈 push、出栈 pop、返回最小值 min 的复杂度为 0(1) (滴滴)
LeetCode 第 115 题
思路: stack2 为存储最小值的数组,使用同步加同步减的思路,stack1 进来的新元素比 stack2 的 top 元素大则无视,否则 stack2 顶部的元素变成刚刚进来的小值。
var MinStack = function() { this.stack1 = []; this.stack2 = []; };/** * @param {number} x * @return {void} */MinStack.prototype.push = function(x) { //同步加同步减push pop this.stack1.push(x); if (this.stack2.length === 0) { this.stack2.push(x); } else { let temp = this.stack2[this.stack2.length - 1]; if (x < temp) { this.stack2.push(x) } else { this.stack2.push(temp); } }};
/** * @return {void} */MinStack.prototype.pop = function() { if (this.stack1.length) { this.stack1.pop(); this.stack2.pop(); }
};
/** * @return {number} */MinStack.prototype.top = function() { return this.stack1[this.stack1.length - 1];};
/** * @return {number} */MinStack.prototype.getMin = function() { return this.stack2[this.stack2.length - 1];};
复制代码
2.使用两个栈实现一个队列 (滴滴)
剑指 Offer 第 9 题
思路: 我们既然要实现队列,那肯定就是要有其中一个栈作为辅助栈，用来倒腾另一个栈中的数据(我们这里的 stack1 为主栈，stack2 为辅助栈);
var CQueue = function() { this.stack1 = [];//2 1 this.stack2 = []; this.count = 0;};
/** * @param {number} value * @return {void} */CQueue.prototype.appendTail = function(value) { while (this.stack1.length) { //如果stack1中有元素那就先把stack1中所有元素放到stack2中 this.stack2.push(this.stack1.pop()); } this.stack1.push(value);//添加新的值到stack1中 while (this.stack2.length) { this.stack1.push(this.stack2.pop()); //然后再把stack2中的元素放到stack1中 } //这几步的意思是让stack1具有队列的性质(先进先出) 因为stack2代表stack1中之前的数据，然后会压到新数据的上面 this.count++;
};
/** * @return {number} */CQueue.prototype.deleteHead = function() { if (this.count == 0) { return -1; } this.count--; return this.stack1.pop();//使用pop栈的方法，因为咱们利用辅助栈倒腾了一下所以直接pop后结果就是按照队列的性质输出了先进的值};
复制代码
3.有效的括号[要求 Tc: O(n) Sc:O(n)] (哔哩哔哩)
LeetCode 第 20 题
思路: 使用栈保存括号，遇到左括号直接入栈，遇到右括号就把栈顶的弹出来和当前的右括号匹配,如果匹配失败说明不合法直接返回 false,最后判断栈是不是空(是不是所有括号都抵消完毕了),不为空也说明不合法。
var isValid = function(str) { let map = { '{': '}', '(': ')', '[': ']' } let stack = [] for (let i = 0; i < str.length; i++) { if (map[str[i]]) { stack.push(str[i]); } else if (str[i] !== map[stack.pop()]) { return false; } } return stack.length === 0};
复制代码
链表篇
1.从尾到头打印单链表[要求 Tc: O(n) Sc:O(n)]
剑指 Offer 第 6 题
思路: 基于 stack 的特性(后进先出),所以我们从头到尾过一遍链表，最后按照栈的顺序弹出就可以得到结果。
var reversePrint = function(head) { let stack = []; let cur = head; while (cur !== null) { stack.push(cur.val); cur = cur.next; } let print = []; while (stack.length) { print.push(stack.pop()) } return print;};
复制代码
2.删除链表的倒数第 K 个结点[要求 Tc: O(L) Sc:O(1)]
LeetCode 第 19 题
var removeNthFromEnd = function(head, n) { let dummyNode = new ListNode(0); dummyNode.next = head; let fast = dummyNode, slow = dummyNode; // 快先走 n+1 步 while(n--) { fast = fast.next } // fast、slow 一起前进 while(fast && fast.next) { fast = fast.next slow = slow.next } slow.next = slow.next.next return dummyNode.next};
复制代码
3.判断单链表是否有环[要求 Tc: O(n) Sc:O(1)] (有赞)
LeetCode 第 141 题
var hasCycle = function(head) { if (head === null) { return false; } let slow = fast = head; while (fast.next !== null && fast.next.next !== null) { slow = slow.next; fast = fast.next.next; if (slow === fast) { return true; } } return false;};
复制代码
4.反转单链表[要求 Tc: O(n) Sc:O(1)] (链表类超高频)
剑指 Offer 第 24 题
反转思路如下过程:
原始链表:head -> 2 -> 3 -> 4 -> null
<- 2 3 -> 4 -> nullpre(null) cur next
null <- 2 <- 3 4 -> null pre cur next
null <- 2 <- 3 <- 4 null cur next pre null <- 2 <- 3 <- 4 null pre cur next <--------------------pre is the newHead to be returned
复制代码
迭代解法(从左到右反转):
var reverseList = function(head) { if (head === null || head.next === null) { return head; } let pre = null, cur = head; while (cur !== null) { let next = cur.next; cur.next = pre; pre = cur; cur = next; } return pre;};
复制代码
递归解法:(从右往左反转)
var reverseList = function(head) { if(head === null || head.next === null) { return head; } let newHead = reverseList(head.next); head.next.next = head; head.next = null; return newHead;}
复制代码
原始链表:2 -> 3 -> null
第一次调用 reverseList:
2 -> 3 -> nullhead newHead
复制代码
head.next.next = head 干的事是: (2的next是3,将3的next指向2)：2 <-> 3
复制代码
head.next = null 干的事是:null <- 2 <- 3 head
复制代码
return newHead 干的事是:null <- 2 <- 3 newHead
复制代码
第二次调用 reverseList:
2 -> 3 -> null head base case: return newHead = 3
复制代码
5.判断两个链表是否相交，若相交，求交点(链表没有环)[要求 Tc: O(m+n) Sc:O(n)] (字节跳动)
LeetCode 第 160 题
headA:a+c+b
headB:b+c+a
因为 a+c+b === b+c+a 因此终有一刻他们能相交
var getIntersectionNode = function(headA, headB) { if (headA === null || headB === null) { return null; } let nodeA = headA; let nodeB = headB; while (nodeA !== nodeB) { nodeA = nodeA ? nodeA.next : headB; nodeB = nodeB ? nodeB.next : headA; } return nodeA;};
复制代码
6.查找单链表的中间节点，要求只能遍历一次链表[要求 Tc: O(n) Sc:O(1)]
LeetCode 第 876 题
var middleNode = function(head) { let slow = head; let fast = head; while (fast !== null && fast.next !== null) { slow = slow.next; fast = fast.next.next; } return slow;};
复制代码
7.合并两个有序链表，合并后依然有序[要求 Tc: O(m+n) Sc:O(1)]
剑指 Offer 第 25 题
var mergeTwoLists = function(l1, l2) { let dummyHead = new ListNode(0); let cur1 = l1; let cur2 = l2; let tail = dummyHead; while (cur1 !== null && cur2 !== null) { if (cur1.val < cur2.val) { tail.next = cur1; cur1 = cur1.next; } else { tail.next = cur2; cur2 = cur2.next; } tail = tail.next; } if (cur1 !== null) { tail.next = cur1; } if (cur2 !== null) { tail.next = cur2; } return dummyHead.next;};
复制代码
8.查找单链表的倒数第 K 个节点，要求只能遍历一次链表[要求 Tc: O(n) Sc:O(1)]
剑指 Offer 第 22 题
var getKthFromEnd = function(head, k) { let fast = head, slow = head; for (let i = 0; i < k; i++) { fast = fast.next; } while (fast != null) { fast = fast.next; slow = slow.next; } return slow;}
复制代码
二叉树篇
1.二叉树的删除实现[要求 Tc: O(H) Sc:O(H)] (字节跳动)
LeetCode 第 450 题
var deleteNode = function(root, key) { this.root = recursionDelete(root, key); return this.root;};function recursionDelete(root, key) { if (root === null) { return null; } if (root.val > key) { root.left = recursionDelete(root.left, key); return root; } else if (root.val < key) { root.right = recursionDelete(root.right, key); return root; } else { //3种情况 if (root.left === null && root.right === null) { //1 root === null; return root; } if (root.left === null) { //2 root = root.right; return root; } else if (root.right === null) { //2 root = root.left; return root; } let aux = null; //3 let current = root.right; while (current != null && current.left != null) { current = current.left; } aux = current; root.val = aux.val; root.right = recursionDelete(root.right,aux.val); return root; }}
复制代码
2.判断一棵树是否是平衡树[要求 Tc: O(n) Sc:O(n)] (字节跳动)
LeetCode 第 110 题
var isBalanced = function(root) { if (root === null) { return true; } const lh = maxDepth(root.left); const rh = maxDepth(root.right); if (Math.abs(lh - rh) > 1) { return false; } return isBalanced(root.left) && isBalanced(root.right);};function maxDepth(root) { if (root === null) { return 0; } const left = maxDepth(root.left); const right = maxDepth(root.right); return Math.max(left, right) + 1;};
复制代码
3.二叉树最大深度[要求 Tc: O(n) Sc:O(n)] (阿里)
剑指 Offer 第 55 题
function maxDepth(root) { if (root === null) { return 0; } const left = maxDepth(root.left); const right = maxDepth(root.right); return Math.max(left, right) + 1;};
复制代码
5.二叉树中和为某一值的路径[要求 Tc: O(n) Sc:O(n)] (字节跳动)
剑指 Offer 第 34 题
第 34 题解:
var pathSum = function(root, sum) { if(!root) return []; const solution = []; let path = [] pathSumHelper(root,sum,solution,path); return solution;};function pathSumHelper(root,sum,solution,path) { path.push(root.val); if(root.left == null && root.right == null && calcPath(path) == sum) { solution.push([...path]); } if(root.left){ pathSumHelper(root.left,sum,solution,path); } if(root.right){ pathSumHelper(root.right,sum,solution,path); } path.pop();}function calcPath(path){ let total = 0; for(let i = 0;i<path.length;i++){ total += path[i]; } return total;}
复制代码
6.LCA[要求 Tc: O(n) Sc:O(n)] (字节跳动)
LeetCode 第 236 题
var lowestCommonAncestor = function(root, p, q) { if(!root || root.val == p.val || root.val == q.val) return root; let left = lowestCommonAncestor(root.left, p, q); let right = lowestCommonAncestor(root.right, p, q); //如果left不存在p或q就返回right的结果。如果left存在，right不存在就返回left结果。如果left和right都存在就返回根节点 if(left == null) return right; else if(right == null) return left; return root;};
复制代码
7. 二叉树层序遍历[要求 Tc: O(n) Sc:O(n)] (必会题)
LeetCode 第 102 题
var levelOrder = function(root) { if (root === null) { return []; } const result = []; let queue = [root]; while (queue.length) { const level = []; let size = queue.length; for (let i = 0; i < size; i++) { let cur = queue.shift(); if (cur.left) { queue.push(cur.left); } if (cur.right) { queue.push(cur.right); } level.push(cur.val); } result.push(level); } return result;};
复制代码
8.是否是 BST[要求 Tc: O(n) Sc:O(n)] (有赞)
LeetCode 第 98 题
var isValidBST = function(root) { let min = -Infinity; let max = Infinity; return isValidBSTHelper(root, min, max);};function isValidBSTHelper(root, min, max) { if (root === null) { return true; } if(root.val <= min || root.val >= max) { return false; } return isValidBSTHelper(root.left, min, root.val) && isValidBSTHelper(root.right, root.val, max);}
复制代码
9.是否是完全二叉树[要求 Tc: O(n) Sc:O(n)] (字节跳动)
LeetCode 第 958 题
var isCompleteTree = function(root) { if (root === null) { return true; } let queue = [root]; let flag = false; while (queue.length) { let cur = queue.shift(); if (cur.left === null) { flag = true; } else if (flag) { return false; } else { queue.push(cur.left); } if (cur.right === null) { flag = true; } else if (flag) { return false; } else { queue.push(cur.right); } } return true;};
复制代码
10.翻转二叉树[要求 Tc: O(n) Sc:O(n)]
LeetCode 第 226 题
var invertTree = function(root) { if(root == null) { return []; } invertTreeHelper(root); return root;};function invertTreeHelper(root) { if (root == null) { return; } let tmp = root.left; root.left = root.right; root.right = tmp; invertTree(root.left); invertTree(root.right);}
复制代码
11.二叉树的右视图[要求 Tc: O(n) Sc:O(n)] (字节跳动)
LeetCode 第 199 题
var rightSideView = function(root) { const result = []; if (root === null) { return result; } let queue = [root]; while (queue.length) { const level = []; let size = queue.length; for (let i = 0; i < size; i++) { let cur = queue.shift(); if (i === size - 1) { level.push(cur.val); } if (cur.left) { queue.push(cur.left); } if (cur.right) { queue.push(cur.right); } } result.push(level); } return result;};
复制代码
12.判断对称二叉树[要求 Tc: O(n) Sc:O(n)]
LeetCode 第 101 题
var isSymmetric = function(root) { return isSymmetricHelper(root, root);};function isSymmetricHelper(one, two) { if (one === null && two === null) { return true; } else if (one === null || two === null) { return false; } else if (one.val !== two.val) { return false; } return isSymmetricHelper(one.left,two.right) && isSymmetricHelper(one.right,two.left);}
复制代码
13. 二叉树的锯齿形层次遍历[要求 Tc: O(n) Sc:O(n)] (字节跳动)
LeetCode 第 103 题
var zigzagLevelOrder = function(root) { const printArr = [] if (!root) return printArr const list = [] list.push({ level: 0, node: root }) while(list.length > 0) { const { level, node } = list.shift() if (!printArr[level]) { printArr[level] = [] } if (level % 2 === 0) { printArr[level].push(node.val) } else { printArr[level].unshift(node.val) } node.left && list.push({ level: level + 1, node: node.left }) node.right && list.push({ level: level + 1, node: node.right }) } return printArr};
复制代码
14.构造二叉树
LeetCode 第 106 题
var buildTree = function(preorder, inorder) { function help(inorder) { if (!inorder|| !inorder.length) return null; let top = preorder.shift(), p = inorder.indexOf(top); let root = new TreeNode(top); root.left = help(inorder.slice(0, p)); root.right = help(inorder.slice(p+1)); return root; } return help(inorder);};
复制代码
LeetCode 第 105 题
var buildTree = function(preorder, inorder) { function help(inorder) { if (!inorder|| !inorder.length) return null; let top = preorder.shift(), p = inorder.indexOf(top); let root = new TreeNode(top); root.left = help(inorder.slice(0, p)); root.right = help(inorder.slice(p + 1)); return root; } return help(inorder);};
复制代码
堆/优先队列篇
1.寻找第 k 大元素[要求 Tc: O(nlogn) Sc:O(1)] (腾讯, 字节跳动, 阿里)
常见题型
二分查找篇
1.查找给定值[要求 Tc: O(logn) Sc:O(1)] (二分查找高频)
LeetCode 第 704 题
function binarySearch(array, target) { let left = 0; let right = array.length - 1; while (left <= right) { const mid = (left + (right - left) / 2) | 0; const middleValue = array[mid]; if (middleValue > target) { right = mid - 1; } else if (middleValue < target) { left = mid + 1; } else { return mid; } }}const index = binarySearch([1, 2, 3, 4], 2);console.log(index); // 1
复制代码
2.查找最接近目标值的值[要求 Tc: O(logn) Sc:O(1)]
给定目标整数 T 和按升序排序的整数数组 A，找到 A 中的索引 i，以使 A [i]最接近 T。
假设条件:
数组中可以有重复的元素，并且我们可以返回具有相同值的任何索引。
例:
A = [1,2,3]，T = 2，返回 1
A =[1，4，6]，T = 3，返回 1
A = [1，4，6]，T = 5，返回 1 或 2
A = [1、3、3、4]，T = 2，返回 0 或 1 或 2
corner case:
如果 A 为空或 A 为零长度怎么办？在这种情况下，我们应该返回-1。
function binarySearch(array, target) { if (array.length === 0) { return -1; } let left = 0; let right = array.length - 1; while (left < right - 1) { const mid = (left + (right - left) / 2) | 0; const middleValue = array[mid]; if (middleValue === target) { return mid; } else if (middleValue < target) { left = mid; } else { right = mid; } } if (Math.abs(target - array[left]) >= Math.abs(target - array[right])) { return right; } else { return left; }}const index = binarySearch([1, 2, 5, 6], 4);console.log(index); // 2
复制代码
3.第一个出现的目标值[要求 Tc: O(logn) Sc:O(1)] (二分查找高频)
给定目标整数 T 和按升序排序的整数数组 A，请找到 A 中 T 首次出现的索引，如果没有这样的索引，则返回-1。
假设条件
数组中可以有重复的元素。
例:
A = [1,2,3]，T = 2，返回 1
A = [1,2,3]，T = 4，返回-1
A = [1,2,2,2,3]，T = 2，返回 1
corner case:
如果 A 为零或长度为零的 A 怎么办？在这种情况下，我们应该返回-1。
function binarySearch(array, target) { if (array.length === 0) { return -1; } let left = 0; let right = array.length - 1; while (left < right - 1) { const mid = (left + (right - left) / 2) | 0; const middleValue = array[mid]; if (middleValue === target) { right = mid; } else if (middleValue < target) { left = mid + 1; } else { right = mid + 1; } } return array[right] === target ? right : array[left] === target ? left : -1;}console.log(binarySearch([1,2,2,2,3], 2)); //1
复制代码
4.查找最接近目标值的 k 个数[要求 Tc: O(logn + k) Sc:O(1)]
给定目标整数 T，非负整数 K 和按升序排序的整数数组 A，找到 A 中最接近 T 的 K 个数字。 如果存在平局，则始终首选较小的元素。
假设条件:
A 不为空 K 保证大于等于 0，K 保证小于等于 A.length 返回大小为 K 的整数数组，其中包含 A 中的 K 个最接近的数字（不是索引），并按数字和 T 之间的差值升序排列。
例:
A = [1，2，3]，T = 2，K = 3，返回[2，1，3]或[2，3，1]
A = [1，4，6，8]，T = 3，K = 3，返回[4，1，6]
function binarySearch(array, target, k) { if (array.length === 0) { return -1; } let left = 0; let right = array.length - 1; while (left < right - 1) { const mid = (left + (right - left) / 2) | 0; const middleValue = array[mid]; if (middleValue === target) { right = mid; } else if (middleValue < target) { left = mid; } else { right = mid; } } // post-processing find the closest number let closeIdx = 0; if (Math.abs(array[left] - target) <= Math.abs(array[right] - target)) { closeIdx = left; } else { closeIdx = right; } // These two should be the closest to target let result = new Array(k); let l = closeIdx; let r = closeIdx + 1; // this is a typical merge operation for (let i = 0; i < k; i++) { // we can advance the left pointer when: // 1. right pointer is already out of bound // 2. right pointer is not out of bound, left pointer is not out of bound and array[left] is closer to target. if (r >= array.length) {//can be merged two conditions result[i] = array[l--]; } else if (l < 0) { result[i] = array[r++]; } else if (Math.abs(array[l] - target) <= Math.abs(array[r] - target)) { result[i] = array[l--]; } else { result[i] = array[r++]; } } return result;}console.log(binarySearch([1,4,6,8], 3, 3)); // [4，1，6]
复制代码
动态规划篇
1.斐波那契数列(要求 Tc: O(n) Sc:O(n)/O(1)) (动态规划类超高频)
LeetCode 第 704 题
var fib = function(n) { let a = 0, b = 1, sum; for (let i = 0; i < n; i++) { sum = a + b; a = b; b = sum; } return a;};
复制代码
2.爬楼梯(要求 Tc: O(n) Sc:O(n)/O(1)) (动态规划类超高频)
LeetCode 第 70 题
var climbStairs = function(n) { if (n === 1) { return 1; } let dp = []; dp[1] = 1; dp[2] = 2; for (let i = 3; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n];};
复制代码
递归篇
1.岛屿数量(要求 Tc: O(MN) Sc:O(MN)) (微信)
LeetCode 第 200 题
let dfs = function (grid, i, j) { // 把当前项变为0, 防止重新查找 grid[i][j] = 0; // 当前项 上下左右检查 if (grid[i - 1] && grid[i - 1][j] == 1) dfs(grid, i - 1, j); // 上 if (grid[i + 1] && grid[i + 1][j] == 1) dfs(grid, i + 1, j); // 下 if (grid[i][j - 1] && grid[i][j - 1] == 1) dfs(grid, i, j - 1); // 左 if (grid[i][j + 1] && grid[i][j + 1] == 1) dfs(grid, i, j + 1); // 右}var numIslands = function(grid) { if (grid.length < 1) return 0; let islands = 0; for (let i = 0; i < grid.length; i++) { for (let j = 0; j < grid[0].length; j++) { if (grid[i][j] == 1) { islands++; // 岛屿加1 dfs(grid, i, j); // 寻找与当前项相邻的 1 并把它们变成0 } } } return islands;};
复制代码
2.从一个数组中找出 N 个数，其和为 M 的所有可能(不能重复使用已经使用过的元素) (今日头条)
参考题解 1
参考题解 2
3.子集(要求 Tc: O(N×2N) Sc:O(N×2N)) (腾讯)
LeetCode 第 78 题
var subsets = function(nums) { if (!nums.length) { return []; } let solution = []; let levelResult = []; subsetsHelper(nums,0,levelResult,solution); return solution;};function subsetsHelper(nums,level,lresult,solution) { //base base if (level === nums.length) { solution.push([].concat(lresult)); return; } lresult.push(nums[level]); subsetsHelper(nums, level + 1,lresult, solution);//回溯 lresult.pop(); subsetsHelper(nums, level + 1, lresult, solution);//回溯}
复制代码
5.扁平化对象(虾皮)
输入:
{ "a": { "b": { "c": { "d": 1 } } }, "aa": 2, "c": [ 1, 2 ]}
复制代码
要求输出:
{ 'a.b.c.d': 1, aa: 2, 'c[0]': 1, 'c[1]': 2 }
复制代码
function convert(obj) { let str = '', res = {}; const inner = (obj) => { const keys = Object.keys(obj); keys.forEach((item) => { const type = Object.prototype.toString.call(obj[item]).slice(8, -1); if (type === 'Object') { str += item + '.'; inner(obj[item], str, res); } else if (type === 'Array') { obj[item].forEach((items, index) => { const key = `${item}[${index}]`; res[key] = items; }); } else { str += item; res[str] = obj[item]; str = ''; } }); return res; }; return inner(obj);}
console.log(convert(obj));
复制代码
6.归类(天猫)
输入:
const industry_list = [ { "parent_ind": "女装", "name": "连衣裙" }, { "name": "女装" }, { "parent_ind": "女装", "name": "半身裙" }, { "parent_ind": "女装", "name": "A字裙" }, { "name": "数码" }, { "parent_ind": "数码", "name": "电脑配件" }, { "parent_ind": "电脑配件", "name": "内存" },];> 输出:/*{ "数码": { "电脑配件": { "内存" : {} } }, "女装" : { "连衣裙": {}, "半身裙": {}, "A字裙": {} }}*/function convert_format(data) { const res = {}; const map = data.reduce((res, v) => (res[v.name] = v, res), {}); console.log(map); for (const item of data) { if (!item.parent_ind) { res[item.name] = {}; } } for (const item of data) { if (item.parent_ind in map) { if (map[item.parent_ind].parent_ind) { const path = dfs(item.name); let re = res[path[0]]; for (let i = 1; i < path.length; i++) { if (i === path.length - 1) { re[path[i]] = {}; } else { re = re[path[i]]; } } } else { res[item.parent_ind][item.name] = {}; } } } return res;
function dfs(name) { let path = []; const inner = (name, path) => { path.unshift(name); if (!map[name].parent_ind) { return; } inner(map[name].parent_ind, path); }; inner(name, path); return path; }}
const result = convert_format(industry_list);console.log(result);
复制代码
排序篇
1.快速排序(要求 Tc: O(nlogn) Sc:O(nlogn)) (排序类超高频)
function quickSort(array) { if (array === null || array.length === 0) { return array; } doQuickSort(array, 0, array.length - 1); return array;}function doQuickSort(array,left,right) { if (left >= right) { return; } let pivotPos = partition(array,left,right); doQuickSort(array,left, pivotPos - 1); doQuickSort(array,pivotPos + 1, right);}function partition(array,left,right) { let pivotIdx = (left + Math.random() * (right - left + 1)) | 0; let pivot = array[pivotIdx]; // swap pivot 元素到最右边的位置 swap(array, right, pivotIdx);
let leftBound = left; let rightBound = right - 1;
while (leftBound <= rightBound) { // [0,leftBound),(rightBound,right-1]是已探索区域，[leftBound+1,rightBound-1]是未探索区域。 // 当 leftBound == rightBound时, 索引不需要检查了 if (array[leftBound] < pivot) { leftBound++; } else if (array[rightBound] >= pivot) { rightBound--; } else { swap(array, leftBound, rightBound); leftBound++; rightBound--; } } // leftBound == rightBound + 1 // swap 回 pivot元素到中间的位置 swap(array, leftBound, right); return leftBound;}function swap(array, i, j) { let tmp = array[i]; array[i] = array[j]; array[j] = tmp;}
复制代码
2.归并排序(要求 Tc: O(nlogn) Sc:O(n))
function mergeSort(array) { if (array.length > 1) { const length = array.length; const mid = Math.floor(length / 2); const left = mergeSort(array.slice(0,mid)); const right = mergeSort(array.slice(mid,length)); array = merge(left,right); } return array;}function merge(left,right) { let i = 0,j = 0; const result = []; while (i < left.length && j < right.length) { result.push(left[i] > right[j] ? left[i++] : right[j++]); } return result.concat(i < left.length ? left.slice(i) : right.slice(j));}
复制代码
3.插入排序(要求 Tc: O(n²) Sc:O(1))
function insertionSort(array) { for (let i = 1; i < array.length; i++) { let j = i; temp = array[i]; while (j > 0 && array[j - 1] > temp) { array[j] = array[j - 1]; j--; } array[j] = temp; } return array;}
复制代码
LeetCode 第 912 题
结语
以上题目均为精选高频题，希望对大家有帮助.
评论