简介
文中所有题目均为精心挑选过的超高频题目，所以大家可以收藏起来
适用人群
针对有一定数据结构基础(了解链表, 二叉树, 二叉堆, 递归)的基本概念,并对时间空间复杂度有基本认知的。
食用指南
将文中列出的每道题至少手写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)
思路:遍历每个元素numsj，并查找是否存在一个值与 target - numsj 相等的目标元素。
代码语言：javascript复制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✌
代码语言：javascript复制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表中不存在，则该数字就是缺失的那个数字
代码语言：javascript复制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]));//33.移动零 要求Tc: O(n) Sc:O(1), 移动后不能改变原来其他元素的相对位置
LeetCode第283题
解法：
思路: 双指针同向而行,fast指针遇到非0就把slow指针位置的字符替换掉，slow指针前进一步。直到fast指针把数组所有元素遍历完毕。(典型的两个挡板，三个区域思想),再把slow指针后面的所有元素替换为0。
同向性质:
变量的物理意义: slow的左侧不包含slow都是非0的数字，slow的右侧包含slow都应该为0，按照这个物理意义就可以达到原地算法的要求。因为快慢指针是同向而行的，所以算法为稳定算法(不会影响元素的相对位置)
代码语言：javascript复制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洗牌算法。
参考视频：传送门
代码语言：javascript复制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的元素，如果有就添加到结果中返回。
代码语言：javascript复制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为快指针
代码语言：javascript复制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指针右边是未知探索区域,两个挡板中间不关注(最后的结果不会改变元素相对位置)
代码语言：javascript复制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:(不改变元素相对位置:同向而行)
代码语言：javascript复制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:(改变元素相对位置:相向而行)
代码语言：javascript复制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。
如此下去最后肯定有个多出来的就是题解了。
代码语言：javascript复制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); //110.合并两个有序数组 要求Tc: O(m n) Sc:O(n)
例:
代码语言：javascript复制输入: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级别)。其实这道题就是让写个二分查找,仔细想想，你要找的那个数的下标不就代表前面有几个比他小的数字吗？
代码语言：javascript复制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); // 112.数组去重要求Tc: O(n) Sc:O(1)
LeetCode第26题
该算法要求原地算法，所以继续使用挡板思想(没理解的可以回到上文提及处继续理解)。
因为他至少有一个元素是不会重复的(至少会保留一个元素)，所以从下标1开始处理。
解法1: 从索引1开始(处理好的元素不包含slow位置)
代码语言：javascript复制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位置)
代码语言：javascript复制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) 元素相对位置不变
思路: 还是使用快慢指针,同向而行
代码语言：javascript复制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);//bcb14.最长公共前缀 (拼多多)
例: 'aaafsd', 'aawwewer', 'aaddfff' => 'aa'
LeetCode第14题
代码语言：javascript复制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 ≤ ai ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次,找到所有出现两次的元素要求Tc: O(n) Sc:O(1)
例: 输入: 4,3,2,7,8,2,3,1 输出: 2,3
解：目前没有思路
16.数组中所有元素组成的最大数是多少 (作业帮)
例: 50, 2, 5, 9 => 95502
思路: 我们把最大的数字依次排序肯定就是最大数(降序排列)
代码语言：javascript复制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。
代码语言：javascript复制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题
思路: 使用双指针一个在前，一个在后, 每次都交换即可
代码语言：javascript复制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题
思路: 将字符串按空格分割,然后按照上题的方法交换单词顺序即可。
代码语言：javascript复制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
代码语言：javascript复制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)
代码语言：javascript复制例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题
思路: 使用快慢指针,同向而行，快指针负责判断是不是空格，慢指针左侧都是处理好的元素。
代码语言：javascript复制var replaceSpace = function(s) {
s = s.split('');
for (let fast = 0; fast < s.length; fast ) {
if (s[fast] === ' ') {
s[fast] = ' ';
}
}
return s.join('');
};其他解法(不推荐面试中使用):
代码语言：javascript复制var replaceSpace = function(s) {
s = s.split(' ').join(' ');
return s;
};
var replaceSpace = function(s) {
s = s.replace(/s /g,' ');
return s;
};7.第一个只出现一次的字符 要求Tc: O(n) Sc:O(n)
剑指Offer第50题
思路: 遍历过程中存hash表,如果当前值第一次出现就设置为false,后续处理遍历值为false的,遇到为false的就直接返回。
代码语言：javascript复制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题
代码语言：javascript复制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题
代码语言：javascript复制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指针记录区间结束位置。
代码语言：javascript复制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题
代码语言：javascript复制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顶部的元素变成刚刚进来的小值。
代码语言：javascript复制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为辅助栈);
代码语言：javascript复制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,最后判断栈是不是空(是不是所有括号都抵消完毕了),不为空也说明不合法。
代码语言：javascript复制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的特性(后进先出),所以我们从头到尾过一遍链表，最后按照栈的顺序弹出就可以得到结果。
代码语言：javascript复制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题
代码语言：javascript复制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题
代码语言：javascript复制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
代码语言：text复制 <- 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迭代解法(从左到右反转):
代码语言：javascript复制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;
};递归解法:(从右往左反转)
代码语言：javascript复制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:
代码语言：rust复制2 -> 3 -> null
head newHeadhead.next.next = head 干的事是: (2的next是3,将3的next指向2)：
2 <-> 3head.next = null 干的事是:
null <- 2 <- 3
headreturn newHead 干的事是:
null <- 2 <- 3
newHead第二次调用reverseList:
代码语言：c#复制2 -> 3 -> null
head
base case: return newHead = 35.判断两个链表是否相交，若相交，求交点(链表没有环)要求Tc: O(m n) Sc:O(n)
LeetCode第160题
headA:a c b
headB:b c a
因为 a c b === b c a 因此终有一刻他们能相交
代码语言：javascript复制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题
代码语言：javascript复制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题
代码语言：javascript复制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题
代码语言：javascript复制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题
代码语言：javascript复制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题
代码语言：javascript复制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题
代码语言：javascript复制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题解:
代码语言：javascript复制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题
代码语言：javascript复制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题
代码语言：javascript复制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题
代码语言：javascript复制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题
代码语言：javascript复制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题
代码语言：javascript复制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题
代码语言：javascript复制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题
代码语言：javascript复制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题
代码语言：javascript复制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题
代码语言：javascript复制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题
代码语言：javascript复制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)
常见题型
代码语言：javascript复制二分查找篇
1.查找给定值要求Tc: O(logn) Sc:O(1)
LeetCode第704题
代码语言：javascript复制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); // 12.查找最接近目标值的值要求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。
代码语言：javascript复制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); // 23.第一个出现的目标值要求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。
代码语言：javascript复制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)); //14.查找最接近目标值的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
代码语言：javascript复制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题
代码语言：javascript复制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题
代码语言：javascript复制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)) s
LeetCode第200题
代码语言：javascript复制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题
代码语言：javascript复制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.扁平化对象(虾皮)
代码语言：css复制输入:
{
"a": {
"b": {
"c": {
"d": 1
}
}
},
"aa": 2,
"c": [
1,
2
]
} 代码语言：css复制要求输出:
{ '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.归类(天猫)
代码语言：javascript复制输入:
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)) (排序类超高频)
代码语言：javascript复制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))
代码语言：javascript复制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))
代码语言：javascript复制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题
结语
以上题目均为精选高频题，希望对大家有帮助.
