简介
文中所有题目均为精心筛选过的超高频题目，所以大家能够珍藏起来
适用人群
针对有肯定数据结构根底(理解链表, 二叉树, 二叉堆, 递归)的基本概念,并对工夫空间复杂度有根本认知的。
食用指南
将文中列出的每道题至多手写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]));//33.挪动零 [要求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); //110.合并两个有序数组 [要求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); // 112.数组去重[要求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);//bcb14.最长公共前缀 (拼多多)
例: ['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 nextnull <- 2 <- 3 4 -> null pre cur nextnull <- 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 newHeadhead.next.next = head 干的事是: (2的next是3,将3的next指向2)：2 <-> 3head.next = null 干的事是:null <- 2 <- 3 headreturn newHead 干的事是:null <- 2 <- 3 newHead第二次调用reverseList:
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 因而终有一刻他们能相交
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); // 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。
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。
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]
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题
结语
以上题目均为精选高频题，心愿对大家有帮忙.