devbox
小小林熬夜学编程
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

leetcode 最常见的150道前端面试题_前端leetcode

作者：小小林熬夜学编程 | 2024-02-16 13:17:20

赞

踩

前端leetcode

举例：存在重复元素（类似题还有3道，后面一起说，解法一样）

 

题目描述如下：

给定一个整数数组，判断是否存在重复元素。

如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。

  1. 示例 1:
  2.  
  3. 输入: [1,2,3,1]
  4. 输出: true
  5.  
  6. 示例 2:
  7.  
  8. 输入: [1,2,3,4]
  9. 输出: false
  10. 复制代码

这题一看就是 计数问题，题目中如果存在一值在数组中出现至少两次，这句话就告诉我们记录每一个数字出现的次数就能解决问题了。

解决思路：

我们遍历数组时，经过数组中的每一项就往map中添加，比如[1,2,3,1]

  • 第一项：遍历到第一个1时，对象返回{ 1: 1 },代表1出现1次

  • 第二项：遍历到2时，返回 { 1: 1, 2: 1 }

  • 第三项：遍历到3时，返回 { 1: 1, 2: 1， 3: 1 }

  • 第四项：遍历到第二个1时，发现原来的对象里已经有1了，返回false

所以，代码自然也就出来了，如下：

  1. const containsDuplicate = function(nums) {
  2.     let map = new Map();
  3.     for(let i of nums){
  4.         if(map.has(i)){
  5.             return true;
  6.         }else{
  7.             map.set(i, 1);
  8.         }
  9.     }
  10.     return false;
  11. };
  12. 复制代码

哈希表 + 计数类型

除了上面的那道题，在最热门的简单题型中还有一些记数类型的题，我们一一解答，这是一类题型

387. 字符串中的第一个唯一字符

一看题目，唯一，条件反射，记数题啊，map走起！我们先看一下题目：

给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

  1. 示例：
  2.  
  3. s = "leetcode"
  4. 返回 0
  5.  
  6. s = "loveleetcode"
  7. 返回 2
  8.  
  9. // 提示：你可以假定该字符串只包含小写字母
  10. 复制代码

思路：

  • 遍历字符串

  • 用一个对象{}来记数，出现过一次就+1，

    • 遍历完毕，再次遍历字符串，看它们在之前记录的对象里的值，是否是1，是就返回下标，不是返回-1。

参考答案：

  1. var firstUniqChar = function(s) {
  2.   const map = {};
  3.   for(let v of s) map[v] = (map[v] || 0) + 1;
  4.   for(let i = 0; i < s.length; i++) if(map[s[i]] === 1) return i;
  5.   return -1;
  6. };
  7. 复制代码

242. 有效的字母异位词

我们先看一下题目：

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

  1. 示例 1:
  2.  
  3. 输入: s = "anagram", t = "nagaram"
  4. 输出: true
  5. 示例 2:
  6.  
  7. 输入: s = "rat", t = "car"
  8. 输出: false
  9. 复制代码

思路：这个题一看字眼，出现次数相同，次数不就是记数吗，记数题型，map走起！

  • 声明计数器，一个对象 const obj = {}

  • 遍历s字符串，如果遍历到字符串的'a'字母，去看obj[a]是否存在

  • 不存在说明第一次遍历到'a'字母，那么初始化obj[a] = 1

  • 如果存在则obj[a] += 1

  • t字符串同理，它每次减1

  • 遍历完s字符串后，遍历obj对象，看它的每一对key：value，是否value都是0

  1. var isAnagram = function(s, t) {
  2.  
  3.   const sLen = s.length;
  4.   const tLen = t.length;
  5.   if(sLen !== tLen ) {
  6.       return false;
  7.   }
  8.   const obj = {};
  9.   for(let i = 0 ; i < sLen ; i++){
  10.       const currentS = s[i];
  11.       const currentT = t[i];
  12.       obj[currentS] ? obj[currentS]++ : obj[currentS] = 1;
  13.       obj[currentT] ? obj[currentT]-- : obj[currentT] = -1;
  14.   }
  15.   return Object.values(obj).every(v=>v===0);
  16. };
  17. 复制代码

169. 多数元素

我们先看题目（题目里有次数两个字，又是记数题型，map继续走起）：

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

  1. 示例 1：
  2.  
  3. 输入：[3,2,3]
  4. 输出：3
  5. 示例 2：
  6.  
  7. 输入：[2,2,1,1,1,2,2]
  8. 输出：2
  9. 复制代码

思路：

  • 声明一个计数器,也就是一个对象const map = {}

  • 遍历字符串，开始记数，如果字符串的字母第一次碰见，map[第一次碰见的字母] = 1

  • 如果map已经记录过这个字母，则map[记录过的的字母] += 1

  • 在遍历的过程中，看map[记录过的的字母] 是否大于 数组总长度/2

解答：

  1. var majorityElement = function(nums) {
  2.   const map = {}
  3.   const n = nums.length >> 1 // >>是右移运算符，意思是除以2
  4.   for(let i = 0; i < nums.length; i++){
  5.       map[nums[i]] = map[nums[i]] !== undefined ? map[nums[i]] + 1 : 1
  6.       if(map[nums[i]] > n) return nums[i]
  7.   }
  8. }
  9. 复制代码

只出现一次的数字

这个题一看，出现一次，map走起，但是呢，这个题比较巧的是，因为题目的一些限制条件，可以有更好的解法，我们先看题：

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

  1. 示例 1:
  2.  
  3. 输入: [2,2,1]
  4. 输出: 1
  5. 示例 2:
  6.  
  7. 输入: [4,1,2,1,2]
  8. 输出: 4
  9. 复制代码

这里我们用map记录一遍，类似这样的代码，

  1. const countMap = {};
  2. 数组.forEach((item)=> { countMap[item] ? countMap[item] += 1 : countMap[item] = 1 } )
  3. 最后再遍历一次countMap，然后看谁的次数是`1`，就解决了
  4. 复制代码

但是这套题有另一个解法，用异或运算符，首先我们看看异或运算符有啥用：

异或运算符(^)，我们了解下，这个运算符的功能

  • 任何数和自己做异或运算，结果为 0，即 a⊕a=0。

  • 任何数和 0 做异或运算，结果还是自己，即 a⊕0=a。

  • 异或运算中，满足交换律和结合律，也就是a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。

所以出现两次的字母异或运算得0，跟出现一次的字母异或运算得到自己

解答：

  1. var singleNumber = function(nums) {
  2.   let init = nums[0];
  3.   for(let i = 1; i < nums.length; i++){
  4.       init ^=  nums[i];
  5.   }
  6.   return init;
  7. };
  8. 复制代码

位1的个数

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明重量）。

  1. 示例 1：
  2.  
  3. 输入：00000000000000000000000000001011
  4. 输出：3
  5. 解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
  6. 示例 2：
  7.  
  8. 输入：00000000000000000000000010000000
  9. 输出：1
  10. 解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
  11. 复制代码

思路：

计算个数，按照我们之前的思路，把整个数字转为字符串，类似这样：

  1. 数字 0001 => String(0001) => '0001' => 遍历看1的个数
  2. 复制代码

然后直接遍历计算就可以了，这是我为什么把它归为记数类别的原因，当然也可以把它归为数学类，我们用数学的算法来解，先看答案，我们再解析。

  1. var hammingWeight = function(n) {
  2.     let ret = 0;
  3.     while(n){
  4.         n &= (n - 1);
  5.         ret++;
  6.     }
  7.     return ret;
  8. };
  9. 复制代码

原理：

每执行一次x = x & (x-1)，会将x用二进制表示时最右边的一个1变为0，因为x-1将会将该位(x用二进制表示时最右边的一个1)变为0。因此，对 x 重复该操作，直到 x 变成 0，则操作次数即为 x 的二进制数中的 1 的数目。

接下来，我们把其他类型的哈希表题也介绍了（相同的题型没那么多）

哈希表 + 映射功能

哈希表有一个非常常见的功能就是建立映射关系，比如说设计模式里的策略模式，思路是一样的，映射表常常见于后端的枚举类型，typescript也是一样，我们举一个js的例子

  1. // 后端只会返回0，1，2
  2. const TYPE = {
  3.     2: 'orange',
  4.     1: 'red',
  5.     0: 'blue'
  6. }
  7.  
  8. // 然后前端会这样用
  9. TYPE[后端返回的数字0或1或2]
  10. 复制代码

对应的题有：

  • 1.两数之和

  • 349.两个数组的交集

两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

  1. 示例 1：
  2.  
  3. 输入：nums = [2,7,11,15], target = 9
  4. 输出：[0,1]
  5. 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
  6. 示例 2：
  7.  
  8. 输入：nums = [3,2,4], target = 6
  9. 输出：[1,2]
  10. 示例 3：
  11.  
  12. 输入：nums = [3,3], target = 6
  13. 输出：[0,1]
  14. 复制代码

用 hashMap 存储遍历过的元素和对应的索引。每遍历一个元素，看看 hashMap 中是否存在满足要求的目标数字。所有事情在一次遍历中完成（用了空间换取时间）

  1. var twoSum = function(nums, target) {
  2.     const map = new Map();
  3.     for(let i = 0, len = nums.length; i < len; i++){
  4.         if(map.get(nums[i]) !== undefined){
  5.             return [map.get(nums[i]), i];
  6.         } else {
  7.             map.set(target - nums[i], i);
  8.         }
  9.     }
  10.     return [];
  11. };
  12. 复制代码

两数组交集

题目如下：给定两个数组，编写一个函数来计算它们的交集。

  1. 示例 1：
  2.  
  3. 输入：nums1 = [1,2,2,1], nums2 = [2,2]
  4. 输出：[2]
  5. 示例 2：
  6.  
  7. 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
  8. 输出：[9,4]
  9.  
  10.  
  11. 说明：
  12.  
  13. 输出结果中的每个元素一定是唯一的。
  14. 我们可以不考虑输出结果的顺序。
  15. 复制代码

这道题可以用set，很简单,但是空间复杂度和时间复杂度都太高，不太优雅

  1. var intersection = function (nums1, nums2) {
  2.     return result =[...new Set(nums1)].filter(item=>new Set(nums2).has(item))
  3. };
  4. 复制代码

我们可以用map来做，时间和空间复杂度都低很多 思路：

  • 用一个map去存nums1数组里的每一项，类似map[nums1[i]] = true

  • 然后去遍历nums2，如果在map中已经有的值，类似map[nums2[i]], 就把它push到一个数组里

  • 并且将map[nums2[i]]设为false，后面有相同的值就不push到数组了

  1. var intersection = function(nums1, nums2) {
  2.     const map = {};
  3.     const ret = [];
  4.     for(let i = 0; i < nums1.length; i++){
  5.         map[nums1[i]] = true;
  6.     }
  7.     for(let i = 0; i < nums2.length; i++){
  8.         if(map[nums2[i]]){
  9.             ret.push(nums2[i])
  10.             map[nums2[i]] = false
  11.         }
  12.     }
  13.     return ret;
  14. };
  15. 复制代码

找规律题

这类题一般画个图或者稍微分析一下就能得出答案

13. 罗马数字转整数

这个题，我来简单描述一下，罗马数字对应我们阿拉伯数字的map如下：

  1.         I: 1,
  2.         V: 5,
  3.         IV: 4,
  4.         IX: 9,
  5.         X: 10,
  6.         XL: 40,
  7.         XC: 90,
  8.         L: 50,
  9.         C: 100,
  10.         CD: 400,
  11.         CM: 900,
  12.         D: 500,
  13.         M: 1000,
  14. 复制代码

题目是给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。

  1. 示例 1:
  2.  
  3. 输入: "III"
  4. 输出: 3
  5. 示例 2:
  6.  
  7. 输入: "IV"
  8. 输出: 4
  9. 示例 3:
  10.  
  11. 输入: "IX"
  12. 输出: 9
  13. 示例 4:
  14.  
  15. 输入: "LVIII"
  16. 输出: 58
  17. 解释: L = 50, V= 5, III = 3.
  18. 复制代码

解题思路就是我们发现这些案例的规律，就是把map表里面对应数字加起来就行了，比如说

"LVIII" = 'L'（对应map表50）+ 'V'（对应map表5）+ 'I'（对应map表1） + 'I'对应map表1） + 'I'（对应map表1）

所以解答就很简单了，就是遍历数字把对应的值加起来，如下：

  1. var romanToInt = function(s) {
  2.     const map = {
  3.         I: 1,
  4.         V: 5,
  5.         IV: 4,
  6.         IX: 9,
  7.         X: 10,
  8.         XL: 40,
  9.         XC: 90,
  10.         L: 50,
  11.         C: 100,
  12.         CD: 400,
  13.         CM: 900,
  14.         D: 500,
  15.         M: 1000,
  16.     }
  17.     let res = 0;
  18.     let index = 0;
  19.     let len = s.length;
  20.     while(index < len){
  21.         if(index + 1 < len && map[s.slice(index, index+2)]){
  22.             res += map[s.slice(index, index+2)];
  23.             index += 2;
  24.         }else{
  25.             res += map[s.slice(index, index+1)];
  26.             index += 1;
  27.         }
  28.     }
  29.     return res;
  30. };
  31. 复制代码

14. 最长公共前缀

题目如下：

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

  1. 示例 1：
  2.  
  3. 输入：strs = ["flower","flow","flight"]
  4. 输出："fl"
  5. 示例 2：
  6.  
  7. 输入：strs = ["dog","racecar","car"]
  8. 输出：""
  9. 解释：输入不存在公共前缀。
  10.  
  11.  
  12. 提示：
  13.  
  14. 0 <= strs.length <= 200
  15. 0 <= strs[i].length <= 200
  16. strs[i] 仅由小写英文字母组成
  17. 复制代码

思路：这个题的思路就是，假如你求数组里3个元素的最长公共前缀

  • 你先拿前两个比较，求出他们两个的最长公共前缀

  • 然后上面求出的结果去跟第三个元素求最长公共前缀

  • n个元素就一直这么reduce下去

  1. // 这个是求出两个元素最长公共前缀的方法
  2. var longestCommonPrefix = function (strs) {
  3.   if (strs.length === 0) return ''
  4.   if (strs.length === 1) return strs[0];
  5.   return strs.reduce(getSameStr, strs[0]);
  6. };
  7.  
  8. function getSameStr(a, b) {
  9.   let res = ''
  10.   for (let j = 0; j < a.length; j++) {
  11.     if (a[j] === b[j]) {
  12.       res += a[j];
  13.     } else {
  14.       return res;
  15.     }
  16.   }
  17.   return res
  18. }
  19. 复制代码

21. 合并两个有序链表

这个题简而言之就是看图找规律，就是合并为升序链表，具体题目如下：

我们先看一下题目：

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

image.png

  1. 示例 1：
  2.  
  3.  
  4. 输入：l1 = [1,2,4], l2 = [1,3,4]
  5. 输出：[1,1,2,3,4,4]
  6. 示例 2：
  7.  
  8. 输入：l1 = [], l2 = []
  9. 输出：[]
  10. 示例 3：
  11.  
  12. 输入：l1 = [], l2 = [0]
  13. 输出：[0]
  14.  
  15.  
  16. 提示：
  17.  
  18. 两个链表的节点数目范围是 [0, 50]
  19. -100 <= Node.val <= 100
  20. l1 和 l2 均按 非递减顺序 排列
  21. 复制代码

思路:

那就挨个遍历，按顺序谁小拼接谁，接着进入下一轮循环，看代码更清晰一些：

  1. // 链表定义函数
  2. function ListNode(val, next) {
  3.     this.val = (val===undefined ? 0 : val)
  4.     this.next = (next===undefined ? null : next)
  5. }
  6.  
  7. var mergeTwoLists = function(l1, l2) {
  8.   const dummpy = node = new ListNode();
  9.   while(l1 && l2){
  10.       if(l1.val >= l2.val){
  11.           node.next = l2;
  12.           node = node.next;
  13.           l2 = l2.next;
  14.       } else {
  15.           node.next = l1;
  16.           node = node.next;
  17.           l1 = l1.next;
  18.       }
  19.   }
  20.   node.next = l1 || l2;
  21.   return dummpy.next;
  22. };
  23. 复制代码

28. 实现str（）

题目如下：

实现 strStr() 函数。

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。

  1. 示例 1：
  2.  
  3. 输入：haystack = "hello", needle = "ll"
  4. 输出：2
  5. 示例 2：
  6.  
  7. 输入：haystack = "aaaaa", needle = "bba"
  8. 输出：-1
  9. 示例 3：
  10.  
  11. 输入：haystack = "", needle = ""
  12. 输出：0
  13.  
  14.  
  15. 提示：
  16.  
  17. 0 <= haystack.length, needle.length <= 5 * 104
  18. haystack 和 needle 仅由小写英文字符组成
  19. 复制代码

思路：

本来这道题最佳算法是KMP，这个算法理解起来对我来说有难度，所以自己换了另一种思路

  • 遍历字符串看是否有和需要找的字符串第一个字母相同

  • 如果相同，就截取字符串跟需要找的字符串相同长度的字符串对比

  • 相同就返回下标，不同就继续遍历原字符串

  1. var strStr = function (haystack, needle) {
  2.   if (needle === "") return 0
  3.   for (var i = 0; i < haystack.length; i++) {
  4.       if (haystack[i] === needle[0]) {
  5.           if (haystack.substring(i, i + needle.length) === needle) return i;
  6.       }
  7.   }
  8.   return -1
  9. };
  10. 复制代码

118. 杨辉三角

这个可是找规律的代表题，并且这道题可以训练一下你对二维数组 转化为 代码的能力：

给定一个非负整数 numRows， 生成杨辉三角的前 numRows 行。

image.png

在杨辉三角中，每个数是它左上方和右上方的数的和。

示例:

  1. 输入: 5
  2. 输出:
  3. [
  4.      [1],
  5.     [1,1],
  6.    [1,2,1],
  7.   [1,3,3,1],
  8.  [1,4,6,4,1]
  9. ]
  10. 复制代码

思路：

  • 看到上图可以发现，生成杨辉三角numRows行，数组就有numRows行

  • 每一行，它的数组第一个位置和最后一个位置都是1

  • 每一行，除了第一个和最后一个位置，其它位置的值等于上一行的两个值相加

把思路翻译成代码即可：

  1. var generate = function(numRows) {
  2.   if(numRows === 0){ return [] }
  3.   const result = Array.from(new Array(numRows), ()=>[])
  4.   for(let i = 0; i < numRows; i++){
  5.     result[i][0] = 1; result[i][i] = 1;
  6.       for(let j = 1; j < i; j++){
  7.       result[i][j] = result[i-1][j-1] + result[i-1][j] 
  8.     }
  9.   }
  10. return result
  11. };
  12. 复制代码

121. 买卖股票的最佳时机

接下来这道题，你简单看下题目就行，解答原理超级简单，看图说话，找规律！

我们先看题：

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

  1. 示例 1：
  2.  
  3. 输入：[7,1,5,3,6,4]
  4. 输出：5
  5. 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
  6.      注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
  7. 示例 2：
  8.  
  9. 输入：prices = [7,6,4,3,1]
  10. 输出：0
  11. 解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
  12.  
  13.  
  14. 提示：
  15.  
  16. 1 <= prices.length <= 105
  17. 0 <= prices[i] <= 104
  18. 复制代码

解题思路：我们先看一张图，假设给定的数组为：[7, 1, 5, 3, 6, 4]

image.png

  • 第一天是7，我们记录一下，因为还没到第二天不知道这个价格是高是低，标记最小值是7

  • 第二天是1，比7小，那么只要当前天数的值比前面小，就说明不卖，因为它是最小值，标记最小值是7

  • 第三天是5，5比前一天大，说明比最小值要大，那么可以卖，利润就是5-1=4

  • 第四天发现是3，比5小，还是一样的道理，比之前小，最小值就要变为当前值，啥也不干，标记最小值是3

  • 第五天发现是6...，第六天发现是4，规律是一样的

意思是只要今天比昨天低，就可以用今天的减去最小值，就是利润，然后每次都比较这个利润是不是最大就行了

结合一下代码，就会清楚

  1. var maxProfit = function(prices) {
  2.   let res = 0;
  3.   let min = prices[0];
  4.   for(let i = 1; i < prices.length; i++){
  5.       if(prices[i] < min){
  6.           min = prices[i]
  7.       } else {
  8.           res = Math.max(res, prices[i] - min)
  9.       }   
  10.   }
  11.   return res;
  12. };
  13. 复制代码

122. 买卖股票的最佳时机2

又来一道看图说话题目，简单！走起！

先看题目：

给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

  1. 示例 1:
  2.  
  3. 输入: prices = [7,1,5,3,6,4]
  4. 输出: 7
  5. 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
  6.      随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
  7. 示例 2:
  8.  
  9. 输入: prices = [1,2,3,4,5]
  10. 输出: 4
  11. 解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
  12.      注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
  13. 示例 3:
  14.  
  15. 输入: prices = [7,6,4,3,1]
  16. 输出: 0
  17. 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
  18. 复制代码

思路，看图马上思路就出来了：

我们的利润就跟上图绿色部分显示的一样，也就是说只要今天减去昨天，是正数就是利润，简单吧，哈哈！

  1. var maxProfit = function(prices) {
  2.   let result = 0
  3.   for(let i = 1; i < prices.length; i++){
  4.       if(prices[i] > prices[i-1]){
  5.           result += prices[i] - prices[i - 1]
  6.       }
  7.   }
  8.   return result
  9. };
  10. 复制代码

206. 反转链表

这个题必须掌握牢实，是解很多链接表题的基础的基础。先看题目：

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

image.png

  1. 输入：head = [1,2,3,4,5]
  2. 输出：[5,4,3,2,1]
  3. 复制代码

示例 2：

image.png

  1. 输入：head = [1,2]
  2. 输出：[2,1]
  3. 复制代码

解题思路依然是看图找规律，下图就是，我们把链表前面加一个null，这样翻转前和翻转后就一致了。

解答：

  1. var reverseList = function(head) {
  2.   let [pre, node] = [null, head];
  3.   while(node){
  4.       const temp = node.next;
  5.       node.next = pre;
  6.       pre = node;
  7.       node = temp;
  8.   }
  9.   return pre;
  10. };
  11. 复制代码

双指针

双指针是解数组类型题最常见解法

  • 比如有头尾分别有指针，然后依次向中间靠拢的双指针，

  • 还有一种是快慢是指针，两个指针都是从左边开始，一个走的快，一个走得慢

具体的细节还是需要从题里体会，我们现在就开始！

26. 删除数组中的重复项

先看一下题目：

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

  1. 示例 1：
  2.  
  3. 输入：nums = [1,1,2]
  4. 输出：2, nums = [1,2]
  5. 解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
  6. 示例 2：
  7.  
  8. 输入：nums = [0,0,1,1,1,2,2,3,3,4]
  9. 输出：5, nums = [0,1,2,3,4]
  10. 解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
  11.  
  12.  
  13. 提示：
  14.  
  15. 0 <= nums.length <= 3 * 104
  16. -104 <= nums[i] <= 104
  17. nums 已按升序排列
  18. 复制代码

初始状态是：

image.png

  • 慢指针是i，快指针是j

  • 如果nums[i] 等于 nums[j] 说明是相同的元素，j继续走，i还在原位

  • 如果nums[i] 不等于 nums[j] 说明是不相同的元素，那么nums[i++] = nums[j]，j继续向前走

依次类推，就相当于i指针保证它和它前面的数字都是不重复的，j就是一个遍历器

  1. var removeDuplicates = function(nums) {
  2.   let i = 0;
  3.   for(let j = 1; j < nums.length; j++){
  4.       if(nums[j] !== nums[i]){
  5.           nums[i+1] = nums[j];
  6.           i++
  7.       }
  8.   }
  9.   return i + 1
  10. };
  11. 复制代码

88. 合并两个有序数组

我们先看题目：

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。

  1. 示例 1：
  2.  
  3. 输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
  4. 输出：[1,2,2,3,5,6]
  5. 示例 2：
  6.  
  7. 输入：nums1 = [1], m = 1, nums2 = [], n = 0
  8. 输出：[1]
  9.  
  10.  
  11. 提示：
  12.  
  13. nums1.length == m + n
  14. nums2.length == n
  15. 0 <= m, n <= 200
  16. 1 <= m + n <= 200
  17. -109 <= nums1[i], nums2[i] <= 109
  18. 复制代码

这道题大家很容易想到，新创建一个数组，然后分别比较这两个数组里的每一项，push进去就行了

然而因为是有序数组，第一个数组还有正好满足假如第二数组的空间，所以这里可以采取双指针来解答，从后往前遍历

参考如下：

  1. var merge = function (nums1, m, nums2, n) {
  2.   let len = m + n - 1;
  3.   m--, n--;
  4.   while (m >= 0 && n >= 0) {
  5.     if (nums1[m] > nums2[n]) {
  6.       nums1[len] = nums1[m--]
  7.     } else {
  8.       nums1[len] = nums2[n--]
  9.     }
  10.     len--;
  11.   }
  12.   if(m === -1){
  13.     return nums1.splice(0, len+1, ...nums2.slice(0, n + 1));
  14.   }
  15.   if(n === -1){
  16.     return nums1;
  17.   }
  18. };
  19. 复制代码

125. 验证回文串

请看题目：

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串。

  1. 示例 1:
  2.  
  3. 输入: "A man, a plan, a canal: Panama"
  4. 输出: true
  5. 解释："amanaplanacanalpanama" 是回文串
  6. 示例 2:
  7.  
  8. 输入: "race a car"
  9. 输出: false
  10. 解释："raceacar" 不是回文串
  11. 复制代码

这个题太简单了，以至于不用写思路了，看代码就知道，就是用用双指针头尾向中间靠拢的解法，

  1. var isPalindrome = function(s) {
  2.   s = s.replace(/[^\w]/g, '').toLowerCase();
  3.   let leftPointer = 0;
  4.   let rightPointer = s.length - 1;
  5.   while(rightPointer > leftPointer){
  6.       if(s[leftPointer++] === s[rightPointer--]){
  7.           continue;
  8.       }else{
  9.           return false;
  10.       }
  11.   }
  12.   return true;
  13. };
  14. 复制代码

234. 回文链表

这个题思路跟上面是一样的，都是双指针对比，但是主要这个题写起来很麻烦，要用到我们之前说的翻转链表，

解题思路：

  • 先用快慢指针的手法，让我们知道这个链表的中点是哪，然后从中点截断

  • 然后截断成为两个链表，把后面的链表翻转

  • 最后依次去判断这两个链表每一项是否相同

关键点：如何从中点截断这个链表,方法如下，让一个指针每次走一步，另一个指针每次走两步，这样他们每次走的倍数就相差2倍。代码如下：

  1.   let fast = head;
  2.   let slow = head;
  3.   let prev;
  4.   while (fast && fast.next) {
  5.     prev = slow;
  6.     slow = slow.next;
  7.     fast = fast.next.next;
  8.   }
  9. prev.next = null;  // 断成两个链表
  10. 复制代码

  • 接着我们需要翻转链表

  1.  // 翻转后半段
  2.   let head2 = null;
  3.   while (slow) {
  4.     const tmp = slow.next;
  5.     slow.next = head2;
  6.     head2 = slow;
  7.     slow = tmp;
  8.   }
  9. 复制代码

  • 最后对比就看下面具体代码了

  1. const isPalindrome = (head) => {
  2.   if (head == null || head.next == null) {
  3.     return true;
  4.   }
  5.   let fast = head;
  6.   let slow = head;
  7.   let prev;
  8.   while (fast && fast.next) {
  9.     prev = slow;
  10.     slow = slow.next;
  11.     fast = fast.next.next;
  12.   }
  13.   prev.next = null;  // 断成两个链表
  14.   // 翻转后半段
  15.   let head2 = null;
  16.   while (slow) {
  17.     const tmp = slow.next;
  18.     slow.next = head2;
  19.     head2 = slow;
  20.     slow = tmp;
  21.   }
  22.   // 比对
  23.   while (head && head2) {
  24.     if (head.val != head2.val) {
  25.       return false;
  26.     }
  27.     head = head.next;
  28.     head2 = head2.next;
  29.   }
  30.   return true;
  31. };
  32. 复制代码

237. 删除链表中的节点

题目如下：

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为 要被删除的节点 。

现有一个链表 -- head = [4,5,1,9]，它可以表示为:

image.png

  1. 示例 1：
  2.  
  3. 输入：head = [4,5,1,9], node = 5
  4. 输出：[4,1,9]
  5. 解释：给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
  6. 示例 2：
  7.  
  8. 输入：head = [4,5,1,9], node = 1
  9. 输出：[4,5,9]
  10. 解释：给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
  11.  
  12.  
  13. 提示：
  14.  
  15. 链表至少包含两个节点。
  16. 链表中所有节点的值都是唯一的。
  17. 给定的节点为非末尾节点并且一定是链表中的一个有效节点。
  18. 不要从你的函数中返回任何结果。
  19. 复制代码

这个题很简单，其实这个node是个引用类型，你只需要把node的val变为node.next的val，然后node的next指向node.next.next，就移花接木，完成任务了！自己可以试着在草稿上画一下，结合代码很快就会明白！

  1. var deleteNode = function(node) {
  2.   node.val = node.next.val
  3.   node.next = node.next.next
  4. };
  5. 复制代码

283. 移动零

题目如下：给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

  1. 示例:
  2.  
  3. 输入: [0,1,0,3,12]
  4. 输出: [1,3,12,0,0]
  5. 说明:
  6.  
  7. 必须在原数组上操作，不能拷贝额外的数组。
  8. 尽量减少操作次数。
  9. 复制代码

如动画所示，我们可以用快慢指针来解答，具体不好用语言叙述，看动图

show

  1. var moveZeroes = function(nums) {
  2.   let i = j = 0;
  3.   while(i < nums.length) {
  4.       if(nums[i] !== 0){
  5.           [nums[i], nums[j]] = [nums[j], nums[i]]
  6.           j++
  7.       }
  8.       i++
  9.   }
  10.  
  11.   return nums
  12. };
  13. 复制代码

344. 反转字符串

题目如下：

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

  1. 示例 1：
  2.  
  3. 输入：["h","e","l","l","o"]
  4. 输出：["o","l","l","e","h"]
  5. 示例 2：
  6.  
  7. 输入：["H","a","n","n","a","h"]
  8. 输出：["h","a","n","n","a","H"]
  9. 复制代码

这个题目实在太简单了，知道用首位双指针即可，看参考：

  1. var reverseString = function(s) {
  2.   let l = 0 ;
  3.   let r = s.length - 1;
  4.   while(l < r){
  5.     [s[l], s[r]] = [s[r], s[l]];
  6.     l++; r--;
  7.   }
  8.   return s;
  9. };
  10. 复制代码

350. 两个数组的交集II

题目如下：给定两个数组，编写一个函数来计算它们的交集。

  1. 示例 1：
  2.  
  3. 输入：nums1 = [1,2,2,1], nums2 = [2,2]
  4. 输出：[2,2]
  5. 示例 2:
  6.  
  7. 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
  8. 输出：[4,9]
  9.  
  10. 说明：
  11.  
  12. 输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。
  13. 我们可以不考虑输出结果的顺序。
  14.  
  15. 复制代码

这个取交集需要保留重复元素，可以是用双指针来解答，具体思路和代码如下

  • 如果两个数组是有序的，则可以使用双指针的方法得到两个数组的交集。

  • 首先对两个数组进行排序，然后使用两个指针遍历两个数组。

    • 初始时，两个指针分别指向两个数组的头部。每次比较两个指针指向的两个数组中的数字，如果两个数字不相等，则将指向较小数字的指针右移一位，如果两个数字相等，将该数字添加到答案，并将两个指针都右移一位。当至少有一个指针超出数组范围时，遍历结束

  1. var intersect = function(nums1, nums2) {
  2.   nums1 = nums1.sort((a, b) => a - b);
  3.   nums2 = nums2.sort((a, b) => a - b);
  4.   let l1 = 0;
  5.   let l2 = 0;
  6.   const nums1Len = nums1.length;
  7.   const nums2Len = nums2.length;
  8.   const ret = [];
  9.   while(l1 < nums1Len && l2 < nums2Len){
  10.     if(nums1[l1] === nums2[l2]){
  11.       ret.push(nums1[l1]);
  12.       l1++;
  13.       l2++;
  14.     }
  15.     if(nums1[l1] > nums2[l2]) l2++;
  16.     if(nums1[l1] < nums2[l2]) l1++;
  17.   }
  18.   return ret;
  19. };
  20. 复制代码

d7948dc5e50e70cc84cfbd0e0cf989da40eb96167f03b710392be45b8c415662.png

我们可以看到这其中的规律，就是深度优先遍历，先遍历左子树，再遍历右子树，这里我们不用递归，因为一些大厂严格要求二叉树遍历不用递归，递归太简单了。

重点思路就是：深度优先遍历，先遍历左子树，再遍历右子树，

所以，我们需要一套如何遍历一颗二叉树，并且是先左子树，再右子树的通用模板，如下

  1. var Traversal = function(root) {
  2.     const stack = [];
  3.     while (root || stack.length){
  4.       while(root){
  5.         stack.push(root);
  6.         root = root.left;
  7.       }
  8.       root = stack.pop();
  9.       root = root.right;
  10.     }
  11.     return res;
  12. };
  13. 复制代码

我们结合图片发现这个遍历产生的整体压栈的顺序是

  • A、B、D入栈，

  • D出栈

  • B出栈

  • E入栈

  • E出栈

  • A出栈

  • C入栈

  • C出栈

  • F入栈

  • F出栈

我们把上面入栈的元素按顺序排列一下就是，A、B、D、E、C、F，而这就是前序遍历的顺序！解答完毕！

是不是很有意思，下面的中序遍历，我们看看出栈顺序是不是中序遍历的要求：D、B、E、A、C、F（这就是中序遍历的要求，好了，两个题解决）

放具体前序遍历代码：

  1. var preorderTraversal = function(root) {
  2.     // 初始化数据
  3.     const res =[];
  4.     const stack = [];
  5.     while (root || stack.length){
  6.       while(root){
  7.         res.push(root.val);
  8.         stack.push(root);
  9.         root = root.left;
  10.       }
  11.       root = stack.pop();
  12.       root = root.right;
  13.     }
  14.     return res;
  15. };
  16. 复制代码

中序遍历是一个意思，在前序遍历的基础上改造一下

  1. var preorderTraversal = function(root) {
  2.     // 初始化数据
  3.     const res =[];
  4.     const stack = [];
  5.     while (root || stack.length){
  6.       while(root){
  7.         stack.push(root);
  8.         root = root.left;
  9.       }
  10.       root = stack.pop();
  11.       res.push(root.val);
  12.       root = root.right;
  13.     }
  14.     return res;
  15. };
  16. 复制代码

后序遍历有点不太一样，但是套路是一样的，我们需要先遍历右子树，再遍历左子树，反着来，就可以了，代码如下：

image.png

  1. var postorderTraversal = function(root) {
  2.   // 初始化数据
  3.     const res =[];
  4.     const stack = [];
  5.     while (root || stack.length){
  6.       while(root){
  7.         stack.push(root);
  8.         res.unshift(root.val);
  9.         root = root.right;
  10.       }
  11.       root = stack.pop();
  12.       root = root.left;
  13.     }
  14.     return res;
  15. };
  16. 复制代码

对称二叉树

这个题简而言之就是判断一个二叉树是对称的，比如说：

二叉树 [1,2,2,3,4,4,3] 是对称的。

  1.     1
  2.    / \
  3.   2   2
  4.  / \ / \
  5. 3  4 4  3
  6. 复制代码

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

  1.     1
  2.    / \
  3.   2   2
  4.    \   \
  5.    3    3
  6.  
  7. 复制代码

思路：

递归解决：

  • 判断两个指针当前节点值是否相等

  • 判断 A 的右子树与 B 的左子树是否对称

  • 判断 A 的左子树与 B 的右子树是否对称

  1. function isSame(leftNode, rightNode){
  2.     if(leftNode === null && rightNode === null) return true;
  3.     if(leftNode === null || rightNode === null) return false;
  4.     return leftNode.val === rightNode.val && isSame(leftNode.left, rightNode.right) && isSame(leftNode.right, rightNode.left)
  5. }
  6. var isSymmetric = function(root) {
  7.     if(!root) return root;
  8.     return isSame(root.left, root.right);
  9. };
  10. 复制代码

二叉树的最大深度

这个题在面试滴滴的时候遇到过，主要是掌握二叉树遍历的套路

  • 只要遍历到这个节点既没有左子树，又没有右子树的时候

  • 说明就到底部了，这个时候如果之前记录了深度，就可以比较是否比之前记录的深度大，大就更新深度

  • 然后以此类推，一直比较到深度最大的

  1. var maxDepth = function(root) {
  2.     if(!root) return root;
  3.     let ret = 1;
  4.     function dfs(root, depth){
  5.         if(!root.left && !root.right) ret = Math.max(ret, depth);
  6.         if(root.left) dfs(root.left, depth+1);
  7.         if(root.right) dfs(root.right, depth+1);
  8.     }
  9.     dfs(root, ret);
  10.     return ret
  11. };
  12. 复制代码

将有序数组转化为二叉搜索树

我们先看题：

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例 1：

image.png

  1. 输入：nums = [-10,-3,0,5,9]
  2. 输出：[0,-3,9,-10,null,5]
  3. 解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
  4. 复制代码

示例 2：

image.png

  1. 输入：nums = [1,3]
  2. 输出：[3,1]
  3. 解释：[1,3] 和 [3,1] 都是高度平衡二叉搜索树。
  4.  
  5.  
  6. 提示：
  7.  
  8. 1 <= nums.length <= 104
  9. -104 <= nums[i] <= 104
  10. nums 按 严格递增 顺序排列
  11. 复制代码

思路：

  • 构建一颗树包括：构建root、构建 root.left 和 root.right

  • 题目要求"高度平衡" — 构建 root 时候，选择数组的中间元素作为 root 节点值，即可保持平衡。

  • 递归函数可以传递数组，也可以传递指针，选择传递指针的时候：l r 分别代表参与构建BST的数组的首尾索引。

  1. var sortedArrayToBST = function(nums) {
  2.     return toBST(nums, 0, nums.length - 1)
  3. };
  4. const toBST = function(nums, l, r){
  5.     if( l > r){
  6.         return null;
  7.     }
  8.     const mid = l + r >> 1;
  9.     const root = new TreeNode(nums[mid]);
  10.     root.left = toBST(nums, l, mid - 1);
  11.     root.right = toBST(nums, mid + 1, r);
  12.  
  13.     return root;
  14. }
  15. 复制代码

栈

栈是一种先进先出的数据结构，所以涉及到你需要先进先出这个想法后，就可以使用栈。

其次我觉得栈跟递归很相似，递归是不是先压栈，然后先进来的先出去，就跟函数调用栈一样。

20. 有效的括号

这是一道很典型的用栈解决的问题， 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。

  1. 示例 1：
  2.  
  3. 输入：s = "()"
  4. 输出：true
  5. 示例 2：
  6.  
  7. 输入：s = "()[]{}"
  8. 输出：true
  9. 示例 3：
  10.  
  11. 输入：s = "(]"
  12. 输出：false
  13. 示例 4：
  14.  
  15. 输入：s = "([)]"
  16. 输出：false
  17. 复制代码

思路：这道题有一规律：

  1. 右括号前面，必须是相对应的左括号，才能抵消！

  2. 右括号前面，不是对应的左括号，那么该字符串，一定不是有效的括号！

也就是说左括号我们直接放入栈中即可，发现是右括号就要对比是否跟栈顶元素相匹配，不匹配就返回false

  1. var isValid = function(s) {
  2.     const map = { '{': '}', '(': ')', '[': ']' };
  3.     const stack = [];
  4.     for(let i of s){
  5.         if(map[i]){
  6.             stack.push(i);
  7.         } else {
  8.             if(map[stack[stack.length - 1]] === i){
  9.                 stack.pop()
  10.             }else{
  11.                 return false;
  12.             }
  13.         }
  14.     }
  15.     return stack.length === 0;
  16. };
  17. 复制代码

155、 最小栈

先看题目：

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

  • push(x) —— 将元素 x 推入栈中。

  • pop() —— 删除栈顶的元素。

  • top() —— 获取栈顶元素。

  • getMin() —— 检索栈中的最小元素。

  1. 示例:
  2.  
  3. MinStack minStack = new MinStack();
  4. minStack.push(-2);
  5. minStack.push(0);
  6. minStack.push(-3);
  7. minStack.getMin();   --> 返回 -3.
  8. minStack.pop();
  9. minStack.top();      --> 返回 0.
  10. minStack.getMin();   --> 返回 -2.
  11.  
  12. 提示：
  13.  
  14. pop、top 和 getMin 操作总是在 非空栈 上调用。
  15. 复制代码

我们先不写getMin方法，满足其他方法实现就非常简单，我们来看一下：

  1. var MinStack = function() {
  2.     this.stack = [];
  3. };
  4.  
  5. MinStack.prototype.push = function(x) {
  6.     this.stack.push(x);
  7. };
  8.  
  9. MinStack.prototype.pop = function() {
  10.     this.stack.pop();
  11. };
  12.  
  13. MinStack.prototype.top = function() {
  14.     return this.stack[this.stack.length - 1];
  15. };
  16. 复制代码

如何保证每次取最小呢，我们举一个例子：

如上图，我们需要一个辅助栈来记录最小值，

  • 开始我们向stack push -2

  • 此时辅助栈minStack，因为此时stack最小的是-2，也push -2

  • stack push 0

  • 此时辅助站minStack 会用 0 跟 -2对比，-2更小，minstack会push -2

  • stack push -3

  • 此时辅助站minStack 会用 -3 跟 -2对比，-3更小，minstack会push -3

所以我们取最小的时候，总能在minStack中取到最小值，所以解法就出来了：

  1. var MinStack = function() {
  2.     this.stack = [];
  3.     // 辅助栈
  4.     this.minStack = [];
  5. };
  6.  
  7. MinStack.prototype.push = function(x) {
  8.     this.stack.push(x);
  9.     // 如果是第一次或者当前x比最小栈里的最小值还小才push x
  10.     if(this.minStack.length === 0 || x < this.minStack[this.minStack.length - 1]){
  11.         this.minStack.push(x)
  12.     } else {
  13.          this.minStack.push( this.minStack[this.minStack.length - 1])
  14.     }
  15. };
  16.  
  17. MinStack.prototype.pop = function() {
  18.     this.stack.pop();
  19.     this.minStack.pop();
  20. };
  21.  
  22. MinStack.prototype.top = function() {
  23.     return this.stack[this.stack.length - 1];
  24. };
  25.  
  26. MinStack.prototype.getMin = function() {
  27.     return this.minStack[this.stack.length - 1];
  28. };
  29. 复制代码

动态规划

动态规划，一定要知道动态转移方程，有了这个，就相当于解题的钥匙，我们从题目中体会一下

53. 最大子序和

题目如下：

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

  1. 示例 1：
  2.  
  3. 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
  4. 输出：6
  5. 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
  6. 示例 2：
  7.  
  8. 输入：nums = [1]
  9. 输出：1
  10. 示例 3：
  11.  
  12. 输入：nums = [0]
  13. 输出：0
  14. 复制代码

思路：

  • 这道题可以用动态规划来解决，关键是找动态转移方程

  • 我们动态转移方程中，dp表示每一个nums下标的最大自序和，所以dp[i]的意思为：包括下标i之前的最大连续子序列和为dp[i]。

确定转义方程的公示：

dp[i]只有两个方向可以推出来：

  • 1、如果dp[i - 1] < 0，也就是当前遍历到nums的i，之前的最大子序和是负数，那么我们就没必要继续加它了，因为dp[i] = dp[i - 1] + nums[i] 会比nums[i]更小，所以此时还不如dp[i] = nums[i]，就是目前遍历到i的最大子序和呢

  • 2、同理dp[i - 1] > 0，说明nums[i]值得去加dp[i - 1]，此时回避nums[i]更大

这样代码就出来了，其实更多的就是求dp，遍历nums每一个下标都会产生最大子序和，我们记录下来即可

  1. var maxSubArray = function(nums) {
  2.   let res = nums[0];
  3.   const dp = [nums[0]];
  4.   for(let i=1;i < nums.length;i++){
  5.       if(dp[i-1]>0){
  6.         dp[i]=nums[i]+dp[i-1]
  7.       }else{
  8.        dp[i]=nums[i]
  9.       }
  10.       
  11.     res=Math.max(dp[i],res)
  12.   }
  13.     return res
  14. };
  15. 复制代码

70. 爬楼梯

先看题目：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

  1. 示例 1：
  2.  
  3. 输入： 2
  4. 输出： 2
  5. 解释： 有两种方法可以爬到楼顶。
  6. 1.  1 阶 + 1 阶
  7. 2.  2 阶
  8. 示例 2：
  9.  
  10. 输入： 3
  11. 输出： 3
  12. 解释： 有三种方法可以爬到楼顶。
  13. 1.  1 阶 + 1 阶 + 1 阶
  14. 2.  1 阶 + 2 阶
  15. 3.  2 阶 + 1 阶
  16. 复制代码

涉及到动态规划，一定要知道动态转移方程，有了这个，就相当于解题的钥匙，

这道题我们假设dp[10]表示爬到是你爬到10阶就到达楼顶的方法数，

那么，dp[10] 是不是就是你爬到8阶，然后再走2步就到了，还有你走到9阶，再走1步就到了，

所以 dp[10] 是不是等于 dp[9]+dp[8]

延伸一下 dp[n] 是不是等于 dp[n \- 1] + dp[n \- 2]

代码如下：

  1. var climbStairs = function(n) {
  2.     const dp = {};
  3.     dp[1] = 1;
  4.     dp[2] = 2;
  5.     for(let i = 3; i <= n; i++){
  6.         dp[i] = dp[i-1] + dp[i-2]
  7.     }
  8.     return dp[n]
  9. };
  10. 复制代码

数学问题

以下更多的是涉及数学问题，这些解法非常重要，因为在中级题里面会经常用到，比如我们马上讲到的加一这个题， 中级的两数相加都是一个模板。

66. 加一

题目如下：

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

  1. 示例 1：
  2.  
  3. 输入：digits = [1,2,3]
  4. 输出：[1,2,4]
  5. 解释：输入数组表示数字 123。
  6. 示例 2：
  7.  
  8. 输入：digits = [4,3,2,1]
  9. 输出：[4,3,2,2]
  10. 解释：输入数组表示数字 4321。
  11. 示例 3：
  12.  
  13. 输入：digits = [0]
  14. 输出：[1]
  15. 复制代码

这个题的关键有两点：

  • 需要有一个进位的变量carry记录到底进位是几

  • 还需要一个每次迭代都重置和的变量sum来帮我们算是否进位，以及进位后的数字

记住这个题，这是两数字相加的套路，这次是+1，其实就是两数相加的题（腾讯面试遇到过两数相加）

  1. var plusOne = function(digits) {
  2.   let carry = 1; // 进位（因为我们确定+1，初始化进位就是1）
  3.   for(let i = digits.length - 1; i >= 0; i--){
  4.       let sum = 0; // 这个变量是用来每次循环计算进位和digits[i]的值的
  5.       sum = digits[i] + carry; 
  6.       digits[i] = sum % 10; // 模运算取个位数
  7.       carry = (sum / 10) | 0; //  除以10是取百位数，并且｜0表示舍弃小数位
  8.   }
  9.   if(digits[0] === 0) digits.unshift(carry);
  10.   return digits
  11. };
  12. 复制代码

69 x的平方根

题目如下：实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:

  1. 输入: 4
  2. 输出: 2
  3. 复制代码

示例 2:

  1. 输入: 8
  2. 输出: 2
  3. 说明: 8 的平方根是 2.82842..., 
  4.      由于返回类型是整数，小数部分将被舍去。
  5. 复制代码

这道题是典型的二分法解题，所以我们需要熟悉二分法的通用模板，我们出一个题：

在 [1, 2, 3, 4, 5, 6] 中找到 4，若存在则返回下标，不存在返回-1

  1. const arr = [1, 2, 3, 4, 5, 6];
  2. function getIndex1(arr, key) {
  3.   let low = 0;
  4.   const high = arr.length - 1;
  5.   while (low <= high) {
  6.     const mid = Math.floor((low + high) / 2);
  7.     if (key === arr[mid]) {
  8.       return mid;
  9.     }
  10.     if (key > arr[mid]) {
  11.       low = mid + 1;
  12.     } else {
  13.       height = mid - 1;
  14.     }
  15.   }
  16.   return -1;
  17. }
  18. console.log(getIndex1(arr, 5)); // 4
  19. 复制代码

所以这道题的意思就是，我们找一个数平方跟x最相近的数，二分法的用法中也有找相近数的功能

所以代码如下：

  1. var mySqrt = function(x) {
  2.     let [l , r] = [0, x];
  3.     let ans = -1;
  4.     while(l <= r) {
  5.         const mid = (l + r) >> 1;
  6.         if(mid * mid > x){
  7.             r = mid - 1
  8.         } else if(mid * mid < x){
  9.             ans = mid; // 防止越界
  10.             l = mid + 1;
  11.         } else {
  12.             ans = mid;
  13.             return ans;
  14.         }
  15.     }
  16.     return ans;
  17. };
  18. };
  19. 复制代码

171. Excel表序列号

这个题比较重要，也比较基础，简而言之就是进制转换，必须牢牢掌握

题目如下：

给你一个整数 columnNumber ，返回它在 Excel 表中相对应的列名称。

例如：

  1. A -> 1
  2. B -> 2
  3. C -> 3
  4. ...
  5. Z -> 26
  6. AA -> 27
  7. AB -> 28 
  8. ...
  9. 复制代码
  1. 示例 1：
  2.  
  3. 输入：columnNumber = 1
  4. 输出："A"
  5. 示例 2：
  6.  
  7. 输入：columnNumber = 28
  8. 输出："AB"
  9. 示例 3：
  10.  
  11. 输入：columnNumber = 701
  12. 输出："ZY"
  13. 示例 4：
  14.  
  15. 输入：columnNumber = 2147483647
  16. 输出："FXSHRXW"
  17. 复制代码

说白了，这就是一道26进制的问题，以前我们知道10进制转2进制就是不停的除2，把余数加起来，26进制也是一样，不停的除26

思路：

  • 初始化结果 ans = 0，遍历时将每个字母与 A 做减法，因为 A 表示 1，所以减法后需要每个数加 1，计算其代表的数值 num = 字母 - ‘A’ + 1

  • 因为有 26 个字母，所以相当于 26 进制，每 26 个数则向前进一位

  • 所以每遍历一位则ans = ans * 26 + num

  • 以 ZY 为例，Z 的值为 26，Y 的值为 25，则结果为 26 * 26 + 25=701

  1. var titleToNumber = function(columnTitle) {
  2.     let ans = 0;
  3.     for(let i = 0; i < columnTitle.length; i++){
  4.         ans = ans * 26 + (columnTitle[i].charCodeAt() - 'A'.charCodeAt() + 1)
  5.     }
  6.     return ans;
  7. };
  8. 复制代码

172. 阶乘中的零

题目：

给定一个整数 n，返回 n! 结果尾数中零的数量。

  1. 示例 1:
  2.  
  3. 输入: 3
  4. 输出: 0
  5. 解释: 3! = 6, 尾数中没有零。
  6. 示例 2:
  7.  
  8. 输入: 5
  9. 输出: 1
  10. 解释: 5! = 120, 尾数中有 1 个零.
  11. 复制代码

这道题很简单，有多少个5就有多少个0，为什么这么说呢，我们分析一下题目

比如说 5!，

  • 也就是 5 * 4 * 3 * 2 * 1 = 120，我们发现只有1个0，怎么产生的呢，主要造成者就是 2 * 5 构造了一个0

  • 再看看10!

10! = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 其中，除了10 = 2 * 5和本身有一对2 * 5，所以有两个0，这样这道题的规律就出来了，我们再精进一步

image.png

如上图，每四个数字都会出现一个或者多个2的因子，但是只有每 5 个数字才能找到一个或多个5的因子。所以总体上看来，2的因子是远远多于5的因子的，所以我们只需要找5的倍数就可以了。

我们再进一步，按照上面的说法，我们需要计算比如10的阶乘有多少个0，要把10的阶乘算出来，其实我们只需要算10有几个5就好了，为什么呢

我们发现只有5的倍数的阶乘，才会产生5, 所以我们需要看看阶层数有多少个5，代码如下：

  1. var trailingZeroes = function (n) {
  2.   let r = 0;
  3.   while (n > 1) {
  4.     n = Math.floor(n / 5);
  5.     r += n;
  6.   }
  7.   return r;
  8. };
  9. 复制代码

190.颠倒二进制位

题目如下：

颠倒给定的 32 位无符号整数的二进制位。

示例 1：

  1. 输入: 00000010100101000001111010011100
  2. 输出: 00111001011110000010100101000000
  3. 解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
  4.      因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。
  5. 复制代码

示例 2：

  1. 输入：11111111111111111111111111111101
  2. 输出：10111111111111111111111111111111
  3. 解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293，
  4.      因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。
  5. 复制代码

这类题，就是翻转字符串，我们可以把其转为字符串，再转成数组，再reverse一下，这里我们选用数学的方式去解答，不用这种转字符串的方式。

解答这道题之前，我们需要了解的前置知识：

  1. 与预算 `&`

  1. 1 & 1 // 1的2进制最后一位是1，得到1
  2. 2 & 0 // 2的2进制最后一位是0，得到0
  3. 3 & 1 // 3的2进制最后一位是1，得到1
  4. 4 & 0 // 4的2进制最后一位是0，得到0
  5. 复制代码

所以我们知道了怎么取10进制最后1位的2进制是几。

  1. JavaScript 使用 32 位按位运算数(意思是我们的按位运算都会转成32位，你的数字不能超过32位，会出问题)

  • JavaScript 将数字存储为 64 位浮点数，但所有按位运算都以 32 位二进制数执行。

  • 在执行位运算之前，JavaScript 将数字转换为 32 位有符号整数。

  • 执行按位操作后，结果将转换回 64 位 JavaScript 数。

  1. '<< 1' 运算

这个运算实际上就是把10进制乘以2，这个乘2在2进制上表现出右边填了一个0，我们距举例来说，

  • 2的2进制是 10，2 << 1 得到4， 4的2进制是100，所以比10多了个0

  • 3的2进制是 11，3 << 1 得到6。6的2进制是110，所以比11多了个0

以上就是规律

思路：循环取最后一位拼接起来即可

  1. var reverseBits = function (n) {
  2.   let result = 0
  3.   for (let i = 0; i < 32; i++) {
  4.     result = (result << 1) + (n & 1)
  5.     n = n >> 1
  6.   }
  7.   // 为什么要 >>> 0 呢，一位javascript没有无符号整数，全是有符号的
  8.   // 不>>>0的话，得出来的值是负数，但是无符号整数是没有符号的
  9.   // javascript 有符号转化为无符号的方法就是>>>0
  10.   return result >>> 0
  11. }
  12. 复制代码

268. 丢失的数字

题目如下：

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

进阶：

你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?

  1. 示例 1：
  2.  
  3. 输入：nums = [3,0,1]
  4. 输出：2
  5. 解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。
  6. 示例 2：
  7.  
  8. 输入：nums = [0,1]
  9. 输出：2
  10. 解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。
  11. 复制代码

这题很简单，就是用0-n的总和减去数组总和

  • 0 - n 的总和用等差数列:（首数+尾数）* 项数 / 2 来求

  1.  var missingNumber = function(nums) {
  2.     const len = nums.length
  3.  
  4.    let sum = ((1 + len) * len) / 2
  5.  
  6.    for (let i = 0; i < len; i++) {
  7.      sum -= nums[i]
  8.    }
  9.  
  10.    return sum
  11.  }
  12. 复制代码

3的幂

题目如下：

给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3的x次方

  1. 示例 1：
  2.  
  3. 输入：n = 27
  4. 输出：true
  5. 示例 2：
  6.  
  7. 输入：n = 0
  8. 输出：false
  9. 示例 3：
  10.  
  11. 输入：n = 9
  12. 输出：true
  13. 复制代码

思路

  • 我们拿27来说：27 = 3 * 3 * 3，所以27是3的幂次方

  • 我们拿29来说：29 = 3 * 3 * 3点几

也就是说，如果是3的幂次方，一直除以3，除到最后就等于1比如27/3/3/3等于1 如果不是3的幂次方，除到最后就是3点几/3 等于1点几

代码就出来了判断是不是等于1即可

  1. var isPowerOfThree = function(n) {
  2.     while(n >= 3){
  3.         n /= 3;
  4.     }
  5.     return n === 1;
  6. };
  7. 复制代码

412. Fizz Buzz

这个题没啥好说的，就按照题目说的写代码就行，先看题目：

写一个程序，输出从 1 到 n 数字的字符串表示。

  1. 如果 n 是3的倍数，输出“Fizz”；

  2. 如果 n 是5的倍数，输出“Buzz”；

  3. 如果 n 同时是3和5的倍数，输出 “FizzBuzz”。

  1. 示例：
  2.  
  3. n = 15,
  4.  
  5. 返回:
  6. [
  7.     "1",
  8.     "2",
  9.     "Fizz",
  10.     "4",
  11.     "Buzz",
  12.     "Fizz",
  13.     "7",
  14.     "8",
  15.     "Fizz",
  16.     "Buzz",
  17.     "11",
  18.     "Fizz",
  19.     "13",
  20.     "14",
  21.     "FizzBuzz"
  22. ]
  23. 复制代码
  1.   var fizzBuzz = function (n) {
  2.     const list = [];
  3.     for (let i = 1; i <= n; i++) {
  4.       const is3Times = i % 3 === 0; // 是否是3的倍数
  5.       const is5Times = i % 5 === 0; // 是否是5的倍数
  6.       const is15Times = is3Times && is5Times; // 是否是15的倍数
  7.       if (is15Times) {
  8.         list.push('FizzBuzz');
  9.         continue;
  10.       }
  11.       if (is3Times) {
  12.         list.push('Fizz');
  13.         continue;
  14.       }
  15.       if (is5Times) {
  16.         list.push('Buzz');
  17.         continue;
  18.       }
  19.       list.push(`${i}`);
  20.     }
  21.     return list;
  22.   };
  23. 复制代码

    1. 整数反转

这个题跟之前的excel序号题差不多，我们先看题目：

屏幕快照 2021-07-27 上午10.55.40.png

思路如下：这道题可以将数字转字符串然后翻转，我们不用这种方法，用更纯正的数学方法，速度和效率更好。

假设我们有一个数字12345，下图展示了翻转的过程

image.png

  1. var reverse = function(x) {
  2.     let ret = 0;
  3.     while(x){
  4.         ret = ret * 10 + x % 10;
  5.         if(ret > Math.pow(2, 31) - 1 || ret < Math.pow(-2, 31)) return 0;
  6.         x = (x / 10) | 0
  7.     }
  8.     return ret
  9. };
  10. 复制代码

环问题

这类问题的特点就是，你要循环寻找，到底怎么循环寻找，看题便知。

141. 环形链表

题目如下：

给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。否则，返回 false 。

示例 1：

image.png

  1. 输入：head = [3,2,0,-4], pos = 1
  2. 输出： true
  3. 解释： 链表中有一个环，其尾部连接到第二个节点。
  4. 复制代码

示例 2：

  1. 输入：head = [1,2], pos = 0
  2. 输出： true
  3. 解释： 链表中有一个环，其尾部连接到第一个节点。
  4. 复制代码

我们采用标记法：

给遍历过的节点打记号，如果遍历过程中遇到有记号的说明已环

  1. var hasCycle = function(head) {
  2.     let traversingNode = head;
  3.     while(traversingNode){
  4.         if(traversingNode.isVistitd) return true
  5.         traversingNode.isVistitd = true
  6.         traversingNode = traversingNode.next
  7.     }
  8.     return false;
  9. };
  10. 复制代码

160. 相交链表

题目如下：

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交：

image.png

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

示例 1：

image.png

  1. 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
  2. 输出：Intersected at '8'
  3. 解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
  4. 从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
  5. 在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
  6. 复制代码

示例 2：

image.png

  1. 输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
  2. 输出：Intersected at '2'
  3. 解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
  4. 从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。
  5. 在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
  6. 复制代码

稍后更新本文章

202. 快乐数

题目如下：编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为：

  • 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。

  • 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。

  • 如果 可以变为 1，那么这个数就是快乐数。

  • 如果 n 是快乐数就返回 true ；不是，则返回 false 。

image.png

快乐数怎么分析呢？

我们来看一个表，就会得出结论，一个数按照快乐数定义的方式分别每个数字平方，会有两种情况

    1. 得到1

    1. 无限循环

无限循环参照下图

image.png

有人会说会不会一直变大，答案是不会：我们看下面列表，

  • 可以看到如果你是13位，你的下一次快乐数算法会变为4位1053，

  • 如果你是9999, 4位，下一个快乐数是324

format,png

所以代码只要判断这两种就行了，代码如下：

  1. // 封装获取快乐数的方法
  2. function getNext(n){
  3.     n = String(n);
  4.     let sum = 0;
  5.     for(let num of n){
  6.         sum = sum + Math.pow(+num, 2);
  7.     }
  8.     return sum;
  9. }
  10. var isHappy = function(n) {
  11.     // 哈希表来看是否循环
  12.     const map = {};
  13.     while( n !== 1 ){
  14.         map[n] = true;
  15.         n = getNext(n)
  16.         if(map[n]) return false
  17.     }
  18.     return true
  19. };
  20. 复制代码

二叉树（DFS）

二叉树前中后遍历套路详解

前序遍历题目如下：

root节点是A节点（下图的A节点），然后让你按照下图数字的顺序依次打印出节点。

我们可以看到这其中的规律，就是深度优先遍历，先遍历左子树，再遍历右子树，这里我们不用递归，因为一些大厂严格要求二叉树遍历不用递归，递归太简单了。

重点思路就是：深度优先遍历，先遍历左子树，再遍历右子树，

所以，我们需要一套如何遍历一颗二叉树，并且是先左子树，再右子树的通用模板，如下

  1. var Traversal = function(root) {
  2.     const stack = [];
  3.     while (root || stack.length){
  4.       while(root){
  5.         stack.push(root);
  6.         root = root.left;
  7.       }
  8.       root = stack.pop();
  9.       root = root.right;
  10.     }
  11.     return res;
  12. };
  13. 复制代码

我们结合图片发现这个遍历产生的整体压栈的顺序是

  • A、B、D入栈，
  • D出栈
  • B出栈
  • E入栈
  • E出栈
  • A出栈
  • C入栈
  • C出栈
  • F入栈
  • F出栈

我们把上面入栈的元素按顺序排列一下就是，A、B、D、E、C、F，而这就是前序遍历的顺序！解答完毕！

是不是很有意思，下面的中序遍历，我们看看出栈顺序是不是中序遍历的要求：D、B、E、A、C、F（这就是中序遍历的要求，好了，两个题解决）

放具体前序遍历代码：

  1. var preorderTraversal = function(root) {
  2.     // 初始化数据
  3.     const res =[];
  4.     const stack = [];
  5.     while (root || stack.length){
  6.       while(root){
  7.         res.push(root.val);
  8.         stack.push(root);
  9.         root = root.left;
  10.       }
  11.       root = stack.pop();
  12.       root = root.right;
  13.     }
  14.     return res;
  15. };
  16. 复制代码

中序遍历是一个意思，在前序遍历的基础上改造一下

  1. var preorderTraversal = function(root) {
  2.     // 初始化数据
  3.     const res =[];
  4.     const stack = [];
  5.     while (root || stack.length){
  6.       while(root){
  7.         stack.push(root);
  8.         root = root.left;
  9.       }
  10.       root = stack.pop();
  11.       res.push(root.val);
  12.       root = root.right;
  13.     }
  14.     return res;
  15. };
  16. 复制代码

后序遍历有点不太一样，但是套路是一样的，我们需要先遍历右子树，再遍历左子树，反着来，就可以了，代码如下：

  1. var postorderTraversal = function(root) {
  2.   // 初始化数据
  3.     const res =[];
  4.     const stack = [];
  5.     while (root || stack.length){
  6.       while(root){
  7.         stack.push(root);
  8.         res.unshift(root.val);
  9.         root = root.right;
  10.       }
  11.       root = stack.pop();
  12.       root = root.left;
  13.     }
  14.     return res;
  15. };
  16. 复制代码

对称二叉树

这个题简而言之就是判断一个二叉树是对称的，比如说：

二叉树 [1,2,2,3,4,4,3] 是对称的。

  1.     1
  2.    / \
  3.   2   2
  4.  / \ / \
  5. 3  4 4  3
  6. 复制代码

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

  1.     1
  2.    / \
  3.   2   2
  4.    \   \
  5.    3    3
  6.  
  7. 复制代码

思路：

递归解决：

  • 判断两个指针当前节点值是否相等
  • 判断 A 的右子树与 B 的左子树是否对称
  • 判断 A 的左子树与 B 的右子树是否对称
  1. function isSame(leftNode, rightNode){
  2.     if(leftNode === null && rightNode === null) return true;
  3.     if(leftNode === null || rightNode === null) return false;
  4.     return leftNode.val === rightNode.val && isSame(leftNode.left, rightNode.right) && isSame(leftNode.right, rightNode.left)
  5. }
  6. var isSymmetric = function(root) {
  7.     if(!root) return root;
  8.     return isSame(root.left, root.right);
  9. };
  10. 复制代码

二叉树的最大深度

这个题在面试滴滴的时候遇到过，主要是掌握二叉树遍历的套路

  • 只要遍历到这个节点既没有左子树，又没有右子树的时候
  • 说明就到底部了，这个时候如果之前记录了深度，就可以比较是否比之前记录的深度大，大就更新深度
  • 然后以此类推，一直比较到深度最大的
  1. var maxDepth = function(root) {
  2.     if(!root) return root;
  3.     let ret = 1;
  4.     function dfs(root, depth){
  5.         if(!root.left && !root.right) ret = Math.max(ret, depth);
  6.         if(root.left) dfs(root.left, depth+1);
  7.         if(root.right) dfs(root.right, depth+1);
  8.     }
  9.     dfs(root, ret);
  10.     return ret
  11. };
  12. 复制代码

将有序数组转化为二叉搜索树

我们先看题：

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例 1：

  1. 输入：nums = [-10,-3,0,5,9]
  2. 输出：[0,-3,9,-10,null,5]
  3. 解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
  4. 复制代码

示例 2：

  1. 输入：nums = [1,3]
  2. 输出：[3,1]
  3. 解释：[1,3] 和 [3,1] 都是高度平衡二叉搜索树。
  4.  
  5.  
  6. 提示：
  7.  
  8. 1 <= nums.length <= 104
  9. -104 <= nums[i] <= 104
  10. nums 按 严格递增 顺序排列
  11. 复制代码

思路：

  • 构建一颗树包括：构建root、构建 root.left 和 root.right
  • 题目要求"高度平衡" — 构建 root 时候，选择数组的中间元素作为 root 节点值，即可保持平衡。
  • 递归函数可以传递数组，也可以传递指针，选择传递指针的时候： l r 分别代表参与构建BST的数组的首尾索引。
  1. var sortedArrayToBST = function(nums) {
  2.     return toBST(nums, 0, nums.length - 1)
  3. };
  4. const toBST = function(nums, l, r){
  5.     if( l > r){
  6.         return null;
  7.     }
  8.     const mid = l + r >> 1;
  9.     const root = new TreeNode(nums[mid]);
  10.     root.left = toBST(nums, l, mid - 1);
  11.     root.right = toBST(nums, mid + 1, r);
  12.  
  13.     return root;
  14. }
  15. 复制代码

栈

栈是一种先进后出的数据结构，所以涉及到你需要先进后出这个想法后，就可以使用栈。

其次我觉得栈跟递归很相似，递归是不是先压栈，然后先进来的先出去，就跟函数调用栈一样。

20. 有效的括号

这是一道很典型的用栈解决的问题， 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。  

  1. 示例 1：
  2.  
  3. 输入：s = "()"
  4. 输出：true
  5. 示例 2：
  6.  
  7. 输入：s = "()[]{}"
  8. 输出：true
  9. 示例 3：
  10.  
  11. 输入：s = "(]"
  12. 输出：false
  13. 示例 4：
  14.  
  15. 输入：s = "([)]"
  16. 输出：false
  17. 复制代码

思路： 这道题有一规律：

  1. 右括号前面，必须是相对应的左括号，才能抵消！
  2. 右括号前面，不是对应的左括号，那么该字符串，一定不是有效的括号！

也就是说左括号我们直接放入栈中即可，发现是右括号就要对比是否跟栈顶元素相匹配，不匹配就返回false

  1. var isValid = function(s) {
  2.     const map = { '{': '}', '(': ')', '[': ']' };
  3.     const stack = [];
  4.     for(let i of s){
  5.         if(map[i]){
  6.             stack.push(i);
  7.         } else {
  8.             if(map[stack[stack.length - 1]] === i){
  9.                 stack.pop()
  10.             }else{
  11.                 return false;
  12.             }
  13.         }
  14.     }
  15.     return stack.length === 0;
  16. };
  17. 复制代码

155、 最小栈

先看题目：

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

  • push(x) —— 将元素 x 推入栈中。
  • pop() —— 删除栈顶的元素。
  • top() —— 获取栈顶元素。
  • getMin() —— 检索栈中的最小元素。  
  1. 示例:
  2.  
  3. MinStack minStack = new MinStack();
  4. minStack.push(-2);
  5. minStack.push(0);
  6. minStack.push(-3);
  7. minStack.getMin();   --> 返回 -3.
  8. minStack.pop();
  9. minStack.top();      --> 返回 0.
  10. minStack.getMin();   --> 返回 -2.
  11.  
  12. 提示：
  13.  
  14. pop、top 和 getMin 操作总是在 非空栈 上调用。
  15. 复制代码

我们先不写getMin方法，满足其他方法实现就非常简单，我们来看一下：

  1. var MinStack = function() {
  2.     this.stack = [];
  3. };
  4.  
  5. MinStack.prototype.push = function(x) {
  6.     this.stack.push(x);
  7. };
  8.  
  9. MinStack.prototype.pop = function() {
  10.     this.stack.pop();
  11. };
  12.  
  13. MinStack.prototype.top = function() {
  14.     return this.stack[this.stack.length - 1];
  15. };
  16. 复制代码

如何保证每次取最小呢，我们举一个例子：

如上图，我们需要一个辅助栈来记录最小值，

  • 开始我们向stack push -2
  • 此时辅助栈minStack，因为此时stack最小的是-2，也push -2
  • stack push 0
  • 此时辅助站minStack 会用 0 跟 -2对比，-2更小，minstack会push -2
  • stack push -3
  • 此时辅助站minStack 会用 -3 跟 -2对比，-3更小，minstack会push -3

所以我们取最小的时候，总能在minStack中取到最小值，所以解法就出来了：

  1. var MinStack = function() {
  2.     this.stack = [];
  3.     // 辅助栈
  4.     this.minStack = [];
  5. };
  6.  
  7. MinStack.prototype.push = function(x) {
  8.     this.stack.push(x);
  9.     // 如果是第一次或者当前x比最小栈里的最小值还小才push x
  10.     if(this.minStack.length === 0 || x < this.minStack[this.minStack.length - 1]){
  11.         this.minStack.push(x)
  12.     } else {
  13.          this.minStack.push( this.minStack[this.minStack.length - 1])
  14.     }
  15. };
  16.  
  17. MinStack.prototype.pop = function() {
  18.     this.stack.pop();
  19.     this.minStack.pop();
  20. };
  21.  
  22. MinStack.prototype.top = function() {
  23.     return this.stack[this.stack.length - 1];
  24. };
  25.  
  26. MinStack.prototype.getMin = function() {
  27.     return this.minStack[this.stack.length - 1];
  28. };
  29. 复制代码

动态规划

动态规划，一定要知道动态转移方程，有了这个，就相当于解题的钥匙，我们从题目中体会一下

53. 最大子序和

题目如下：

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。  

  1. 示例 1：
  2.  
  3. 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
  4. 输出：6
  5. 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
  6. 示例 2：
  7.  
  8. 输入：nums = [1]
  9. 输出：1
  10. 示例 3：
  11.  
  12. 输入：nums = [0]
  13. 输出：0
  14. 复制代码

思路：

  • 这道题可以用动态规划来解决，关键是找动态转移方程
  • 我们动态转移方程中，dp表示每一个nums下标的最大自序和，所以dp[i]的意思为：包括下标i之前的最大连续子序列和为dp[i]。

确定转义方程的公示：

dp[i]只有两个方向可以推出来：

  • 1、如果dp[i - 1] < 0，也就是当前遍历到nums的i，之前的最大子序和是负数，那么我们就没必要继续加它了，因为dp[i] = dp[i - 1] + nums[i] 会比nums[i]更小，所以此时还不如dp[i] = nums[i]，就是目前遍历到i的最大子序和呢
  • 2、同理dp[i - 1] > 0，说明nums[i]值得去加dp[i - 1]，此时回避nums[i]更大

这样代码就出来了，其实更多的就是求dp，遍历nums每一个下标都会产生最大子序和，我们记录下来即可

  1. var maxSubArray = function(nums) {
  2.   let res = nums[0];
  3.   const dp = [nums[0]];
  4.   for(let i=1;i < nums.length;i++){
  5.       if(dp[i-1]>0){
  6.         dp[i]=nums[i]+dp[i-1]
  7.       }else{
  8.        dp[i]=nums[i]
  9.       }
  10.       
  11.     res=Math.max(dp[i],res)
  12.   }
  13.     return res
  14. };
  15. 复制代码

70. 爬楼梯

先看题目：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

  1. 示例 1：
  2.  
  3. 输入： 2
  4. 输出： 2
  5. 解释： 有两种方法可以爬到楼顶。
  6. 1.  1 阶 + 1 阶
  7. 2.  2 阶
  8. 示例 2：
  9.  
  10. 输入： 3
  11. 输出： 3
  12. 解释： 有三种方法可以爬到楼顶。
  13. 1.  1 阶 + 1 阶 + 1 阶
  14. 2.  1 阶 + 2 阶
  15. 3.  2 阶 + 1 阶
  16. 复制代码

涉及到动态规划，一定要知道动态转移方程，有了这个，就相当于解题的钥匙，

这道题我们假设dp[10]表示爬到是你爬到10阶就到达楼顶的方法数，

那么，dp[10] 是不是就是你爬到8阶，然后再走2步就到了，还有你走到9阶，再走1步就到了，

所以 dp[10] 是不是等于 dp[9]+dp[8]

延伸一下 dp[n] 是不是等于 dp[n - 1] + dp[n - 2]

代码如下：

  1. var climbStairs = function(n) {
  2.     const dp = {};
  3.     dp[1] = 1;
  4.     dp[2] = 2;
  5.     for(let i = 3; i <= n; i++){
  6.         dp[i] = dp[i-1] + dp[i-2]
  7.     }
  8.     return dp[n]
  9. };
  10. 复制代码

数学问题

以下更多的是涉及数学问题，这些解法非常重要，因为在中级题里面会经常用到，比如我们马上讲到的加一这个题， 中级的两数相加都是一个模板。

66. 加一

题目如下：

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

  1. 示例 1：
  2.  
  3. 输入：digits = [1,2,3]
  4. 输出：[1,2,4]
  5. 解释：输入数组表示数字 123。
  6. 示例 2：
  7.  
  8. 输入：digits = [4,3,2,1]
  9. 输出：[4,3,2,2]
  10. 解释：输入数组表示数字 4321。
  11. 示例 3：
  12.  
  13. 输入：digits = [0]
  14. 输出：[1]
  15. 复制代码

这个题的关键有两点：

  • 需要有一个进位的变量carry记录到底进位是几
  • 还需要一个每次迭代都重置和的变量sum来帮我们算是否进位，以及进位后的数字

记住这个题，这是两数字相加的套路，这次是+1，其实就是两数相加的题（腾讯面试遇到过两数相加）

  1. var plusOne = function(digits) {
  2.   let carry = 1; // 进位（因为我们确定+1，初始化进位就是1）
  3.   for(let i = digits.length - 1; i >= 0; i--){
  4.       let sum = 0; // 这个变量是用来每次循环计算进位和digits[i]的值的
  5.       sum = digits[i] + carry; 
  6.       digits[i] = sum % 10; // 模运算取个位数
  7.       carry = (sum / 10) | 0; //  除以10是取百位数，并且｜0表示舍弃小数位
  8.   }
  9.   if(digits[0] === 0) digits.unshift(carry);
  10.   return digits
  11. };
  12. 复制代码

69 x的平方根

题目如下： 实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:

  1. 输入: 4
  2. 输出: 2
  3. 复制代码

示例 2:

  1. 输入: 8
  2. 输出: 2
  3. 说明: 8 的平方根是 2.82842..., 
  4.      由于返回类型是整数，小数部分将被舍去。
  5. 复制代码

这道题是典型的二分法解题，所以我们需要熟悉二分法的通用模板，我们出一个题：

在 [1, 2, 3, 4, 5, 6] 中找到 4，若存在则返回下标，不存在返回-1

  1. const arr = [1, 2, 3, 4, 5, 6];
  2. function getIndex1(arr, key) {
  3.   let low = 0;
  4.   const high = arr.length - 1;
  5.   while (low <= high) {
  6.     const mid = Math.floor((low + high) / 2);
  7.     if (key === arr[mid]) {
  8.       return mid;
  9.     }
  10.     if (key > arr[mid]) {
  11.       low = mid + 1;
  12.     } else {
  13.       height = mid - 1;
  14.     }
  15.   }
  16.   return -1;
  17. }
  18. console.log(getIndex1(arr, 5)); // 4
  19. 复制代码

所以这道题的意思就是，我们找一个数平方跟x最相近的数，二分法的用法中也有找相近数的功能

所以代码如下：

  1. var mySqrt = function(x) {
  2.     let [l , r] = [0, x];
  3.     let ans = -1;
  4.     while(l <= r) {
  5.         const mid = (l + r) >> 1;
  6.         if(mid * mid > x){
  7.             r = mid - 1
  8.         } else if(mid * mid < x){
  9.             ans = mid; // 防止越界
  10.             l = mid + 1;
  11.         } else {
  12.             ans = mid;
  13.             return ans;
  14.         }
  15.     }
  16.     return ans;
  17. };
  18. };
  19. 复制代码

171. Excel表序列号

这个题比较重要，也比较基础，简而言之就是进制转换，必须牢牢掌握

题目如下：

给你一个整数 columnNumber ，返回它在 Excel 表中相对应的列名称。

例如：

  1. A -> 1
  2. B -> 2
  3. C -> 3
  4. ...
  5. Z -> 26
  6. AA -> 27
  7. AB -> 28 
  8. ...
  9. 复制代码
  1. 示例 1：
  2.  
  3. 输入：columnNumber = 1
  4. 输出："A"
  5. 示例 2：
  6.  
  7. 输入：columnNumber = 28
  8. 输出："AB"
  9. 示例 3：
  10.  
  11. 输入：columnNumber = 701
  12. 输出："ZY"
  13. 示例 4：
  14.  
  15. 输入：columnNumber = 2147483647
  16. 输出："FXSHRXW"
  17. 复制代码

说白了，这就是一道26进制的问题，n进制转10进制，都是一个算法。 例如2进制101.1如何转化为10进制。（有些同学觉得可以用parseInt('101.1', 2)，这个是不行的，因为parseInt返回整数）

转化方法如下（按权相加法）： 2进制的 101.1 = 1 x 22 + 0 x 21 + 1 x 20 + 1 x 2-1

规律就是二进制的每个数去乘以2的相应次方,注意小数点后是乘以它的负相应次方。

所以这个26进制的是一样 思路，但是注意A是从1开始数，没有0，所以注意+1。

  1. var titleToNumber = function(columnTitle) {
  2.     let ans = 0;
  3.     let columnTitleLen = columnTitle.length - 1;
  4.     for(let i = columnTitleLen; i >= 0; i--){
  5.         ans += (26 ** (columnTitleLen - i)) * (columnTitle[i].charCodeAt() - 'A'.charCodeAt() + 1);
  6.     }
  7.     return ans;
  8. };
  9. 复制代码

172. 阶乘中的零

题目：

给定一个整数 n，返回 n! 结果尾数中零的数量。

  1. 示例 1:
  2.  
  3. 输入: 3
  4. 输出: 0
  5. 解释: 3! = 6, 尾数中没有零。
  6. 示例 2:
  7.  
  8. 输入: 5
  9. 输出: 1
  10. 解释: 5! = 120, 尾数中有 1 个零.
  11. 复制代码

这道题很简单，有多少个5就有多少个0，为什么这么说呢，我们分析一下题目

比如说 5!，

  • 也就是 5 * 4 * 3 * 2 * 1 = 120，我们发现只有1个0，怎么产生的呢，主要造成者就是 2 * 5 构造了一个0

  • 再看看10! 10! = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 其中，除了10 = 2 * 5和本身有一对2 * 5，所以有两个0，这样这道题的规律就出来了，我们再精进一步

如上图，每四个数字都会出现一个或者多个2的因子，但是只有每 5 个数字才能找到一个或多个5的因子。所以总体上看来，2的因子是远远多于5的因子的，所以我们只需要找5的倍数就可以了。

我们再进一步，按照上面的说法，我们需要计算比如10的阶乘有多少个0，要把10的阶乘算出来，其实我们只需要算10有几个5就好了，为什么呢

我们发现只有5的倍数的阶乘，才会产生5, 所以我们需要看看阶层数有多少个5，代码如下：

  1. var trailingZeroes = function (n) {
  2.   let r = 0;
  3.   while (n > 1) {
  4.     n = Math.floor(n / 5);
  5.     r += n;
  6.   }
  7.   return r;
  8. };
  9. 复制代码

190.颠倒二进制位

题目如下：

颠倒给定的 32 位无符号整数的二进制位。

示例 1：

  1. 输入: 00000010100101000001111010011100
  2. 输出: 00111001011110000010100101000000
  3. 解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
  4.      因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。
  5. 复制代码

示例 2：

  1. 输入：11111111111111111111111111111101
  2. 输出：10111111111111111111111111111111
  3. 解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293，
  4.      因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。
  5. 复制代码

这类题，就是翻转字符串，我们可以把其转为字符串，再转成数组，再reverse一下，这里我们选用数学的方式去解答，不用这种转字符串的方式。

解答这道题之前，我们需要了解的前置知识：

  1. 与预算 &
  1. 1 & 1 // 1的2进制最后一位是1，得到1
  2. 2 & 0 // 2的2进制最后一位是0，得到0
  3. 3 & 1 // 3的2进制最后一位是1，得到1
  4. 4 & 0 // 4的2进制最后一位是0，得到0
  5. 复制代码

所以我们知道了怎么取10进制最后1位的2进制是几。

  1. JavaScript 使用 32 位按位运算数(意思是我们的按位运算都会转成32位，你的数字不能超过32位，会出问题)

  • JavaScript 将数字存储为 64 位浮点数，但所有按位运算都以 32 位二进制数执行。

  • 在执行位运算之前，JavaScript 将数字转换为 32 位有符号整数。

  • 执行按位操作后，结果将转换回 64 位 JavaScript 数。

  1. '<< 1' 运算

这个运算实际上就是把10进制乘以2，这个乘2在2进制上表现出右边填了一个0，我们距举例来说，

  • 2的2进制是 10，2 << 1 得到4， 4的2进制是100，所以比10多了个0
  • 3的2进制是 11，3 << 1 得到6。 6的2进制是110，所以比11多了个0

以上就是规律

思路：循环取最后一位拼接起来即可

  1. var reverseBits = function (n) {
  2.   let result = 0
  3.   for (let i = 0; i < 32; i++) {
  4.     result = (result << 1) + (n & 1)
  5.     n = n >> 1
  6.   }
  7.   // 为什么要 >>> 0 呢，一位javascript没有无符号整数，全是有符号的
  8.   // 不>>>0的话，得出来的值是负数，但是无符号整数是没有符号的
  9.   // javascript 有符号转化为无符号的方法就是>>>0
  10.   return result >>> 0
  11. }
  12. 复制代码

268. 丢失的数字

题目如下：

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

进阶：

你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?  

  1. 示例 1：
  2.  
  3. 输入：nums = [3,0,1]
  4. 输出：2
  5. 解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。
  6. 示例 2：
  7.  
  8. 输入：nums = [0,1]
  9. 输出：2
  10. 解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。
  11. 复制代码

这题很简单，就是用0-n的总和减去数组总和

  • 0 - n 的总和用等差数列:（首数+尾数）* 项数 / 2 来求
  1.  var missingNumber = function(nums) {
  2.     const len = nums.length
  3.  
  4.    let sum = ((1 + len) * len) / 2
  5.  
  6.    for (let i = 0; i < len; i++) {
  7.      sum -= nums[i]
  8.    }
  9.  
  10.    return sum
  11.  }
  12. 复制代码

3的幂

题目如下：

给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3的x次方  

  1. 示例 1：
  2.  
  3. 输入：n = 27
  4. 输出：true
  5. 示例 2：
  6.  
  7. 输入：n = 0
  8. 输出：false
  9. 示例 3：
  10.  
  11. 输入：n = 9
  12. 输出：true
  13. 复制代码

思路

  • 我们拿27来说：27 = 3 * 3 * 3，所以27是3的幂次方
  • 我们拿29来说： 29 = 3 * 3 * 3点几 也就是说，如果是3的幂次方，一直除以3，除到最后就等于1比如27/3/3/3等于1 如果不是3的幂次方，除到最后就是3点几/3 等于1点几

代码就出来了判断是不是等于1即可

  1. var isPowerOfThree = function(n) {
  2.     while(n >= 3){
  3.         n /= 3;
  4.     }
  5.     return n === 1;
  6. };
  7. 复制代码

412. Fizz Buzz

这个题没啥好说的，就按照题目说的写代码就行，先看题目：

写一个程序，输出从 1 到 n 数字的字符串表示。

  1. 如果 n 是3的倍数，输出“Fizz”；

  2. 如果 n 是5的倍数，输出“Buzz”；

  3. 如果 n 同时是3和5的倍数，输出 “FizzBuzz”。

  1. 示例：
  2.  
  3. n = 15,
  4.  
  5. 返回:
  6. [
  7.     "1",
  8.     "2",
  9.     "Fizz",
  10.     "4",
  11.     "Buzz",
  12.     "Fizz",
  13.     "7",
  14.     "8",
  15.     "Fizz",
  16.     "Buzz",
  17.     "11",
  18.     "Fizz",
  19.     "13",
  20.     "14",
  21.     "FizzBuzz"
  22. ]
  23. 复制代码
  1.   var fizzBuzz = function (n) {
  2.     const list = [];
  3.     for (let i = 1; i <= n; i++) {
  4.       const is3Times = i % 3 === 0; // 是否是3的倍数
  5.       const is5Times = i % 5 === 0; // 是否是5的倍数
  6.       const is15Times = is3Times && is5Times; // 是否是15的倍数
  7.       if (is15Times) {
  8.         list.push('FizzBuzz');
  9.         continue;
  10.       }
  11.       if (is3Times) {
  12.         list.push('Fizz');
  13.         continue;
  14.       }
  15.       if (is5Times) {
  16.         list.push('Buzz');
  17.         continue;
  18.       }
  19.       list.push(`${i}`);
  20.     }
  21.     return list;
  22.   };
  23. 复制代码
    1. 整数反转 这个题跟之前的excel序号题差不多，我们先看题目：

思路如下： 这道题可以将数字转字符串然后翻转，我们不用这种方法，用更纯正的数学方法，速度和效率更好。

假设我们有一个数字12345，下图展示了翻转的过程

  1. var reverse = function(x) {
  2.     let ret = 0;
  3.     while(x){
  4.         ret = ret * 10 + x % 10;
  5.         if(ret > Math.pow(2, 31) - 1 || ret < Math.pow(-2, 31)) return 0;
  6.         x = (x / 10) | 0
  7.     }
  8.     return ret
  9. };
  10. 复制代码

环问题

这类问题的特点就是，你要循环寻找，到底怎么循环寻找，看题便知。

141. 环形链表

题目如下：

给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。 否则，返回 false 。

示例 1：

  1. 输入： head = [3,2,0,-4], pos = 1
  2. 输出： true
  3. 解释： 链表中有一个环，其尾部连接到第二个节点。
  4. 复制代码

示例 2：

  1. 输入： head = [1,2], pos = 0
  2. 输出： true
  3. 解释： 链表中有一个环，其尾部连接到第一个节点。
  4. 复制代码

我们采用标记法：

给遍历过的节点打记号，如果遍历过程中遇到有记号的说明已环

  1. var hasCycle = function(head) {
  2.     let traversingNode = head;
  3.     while(traversingNode){
  4.         if(traversingNode.isVistitd) return true
  5.         traversingNode.isVistitd = true
  6.         traversingNode = traversingNode.next
  7.     }
  8.     return false;
  9. };
  10. 复制代码

160. 相交链表

题目如下：

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

示例 1：

  1. 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
  2. 输出：Intersected at '8'
  3. 解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
  4. 从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
  5. 在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
  6. 复制代码

示例 2：

  1. 输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
  2. 输出：Intersected at '2'
  3. 解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
  4. 从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。
  5. 在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
  6. 复制代码

思路：

使用双指针的思路，两个指针分别指向两个链表的头部

参考解答：

  1. var getIntersectionNode = function(headA, headB) {
  2.     let tempHeadA = headA;
  3.     let tempHeadB = headB;
  4.  
  5.     while(tempHeadA !== tempHeadB){
  6.         tempHeadA = tempHeadA !== null ? tempHeadA.next : headB;
  7.         tempHeadB = tempHeadB !== null ? tempHeadB.next : headA;
  8.     }
  9.  
  10.     return tempHeadA;
  11. };
  12. 复制代码

202. 快乐数

题目如下： 编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为：

  • 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
  • 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
  • 如果 可以变为  1，那么这个数就是快乐数。
  • 如果 n 是快乐数就返回 true ；不是，则返回 false 。

快乐数怎么分析呢？

我们来看一个表，就会得出结论，一个数按照快乐数定义的方式分别每个数字平方，会有两种情况

    1. 得到1
    1. 无限循环

无限循环参照下图

有人会说会不会一直变大，答案是不会： 我们看下面列表，

  • 可以看到如果你是13位，你的下一次快乐数算法会变为4位1053，
  • 如果你是9999, 4位，下一个快乐数是324
    位数位数对应最大值下一个快乐数
    1981
    299162
    3999243
    49999324
    1399999999999991053

所以代码只要判断这两种就行了，代码如下：

  1. // 封装获取快乐数的方法
  2. function getNext(n){
  3.     n = String(n);
  4.     let sum = 0;
  5.     for(let num of n){
  6.         sum = sum + Math.pow(+num, 2);
  7.     }
  8.     return sum;
  9. }
  10. var isHappy = function(n) {
  11.     // 哈希表来看是否循环
  12.     const map = {};
  13.     while( n !== 1 ){
  14.         map[n] = true;
  15.         n = getNext(n)
  16.         if(map[n]) return false
  17.     }
  18.     return true
  19. };

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/93654
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号