简介
文中所有题目均为精心筛选过的超高频题目，所以大家能够珍藏起来
适用人群
针对有肯定数据结构根底 (理解链表, 二叉树, 二叉堆, 递归) 的基本概念, 并对工夫空间复杂度有根本认知的。
食用指南
将文中列出的每道题至多手写 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 -> null
pre(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 -> null
head 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 题
结语
以上题目均为精选高频题，心愿对大家有帮忙.