LeetCode《编程能力 入门》刷题笔记

基本数据类型
- 1. 在区间范围内统计奇数数目
- - _解法1：暴力迭代
  - _解法2：数学（找规律）
- 2. 去掉最低工资和最高工资后的工资平均值
- - _解法1：迭代
运算符
- 3. 位1的个数
- - _解法1：迭代
  - _解法2：位运算
- 4. 整数的各位积和之差
- - _解法1：迭代
  - 解法2：转字符串再转数组
条件语句
- 5. 三角形的最大周长
- - _解法1：排序 + 迭代
- 6. 找到最近的有相同X或Y坐标的点
- - _解法1：迭代
循环
- 7. 数组元素积的符号
- - _解法1：reduce
  - _解法2：迭代
- 8. 判断能否形成等差数列
- - 解法1：模拟（迭代）
- 9. 快乐数
- - _解法1：模拟
  - 解法2：快慢指针
- 10. 仅执行一次字符串交换能否使两个字符串相等
- - _解法1：模拟
函数
- 11. N 叉树的前序遍历
- - _解法1：递归
- 12. 下一个更大元素 I
- - _解法1：模拟
  - _解法2：单调栈
- 13. 缀点成线
- - _解法1：数学 + 模拟
数组
- 14. 所有奇数长度数组的和
- - 解法1：暴力
  - 解法2：前缀和
- 15. 移动零
- - 解法1：双指针
- 16. 最富有客户的资产总量
- - _解法1：暴力模拟
- 17. 矩阵对角元素的和
- - _解法1：模拟
- 18. 重塑矩阵
- - _解法1：模拟
  - 解法2：数学
字符串
- 19. 交替合并字符串
- - _解法1：模拟
- 20. 设计 Goal 解析器
- - _解法1：字符串替换
  - _解法2：迭代 + 分情况
- 21. 找不同
- - _解法1：哈希
  - _解法2：位运算
  - 解法3：字符和之差
- 22. 转换成小写字母
- - _解法1：模拟
  - 解法2：位运算
- 23. 解码字母到整数映射
- - 解法1：模拟
- 24. 验证外星语词典(todo)
- - _解法1：map + 迭代
  - 解法2：高阶函数
链表 & 树
- 25. 二进制链表转整数
- - _解法1：哈希
  - 解法2：位运算
- 26. 链表的中间结点
- 27. 二叉树的最大深度
- - _解法1：递归
  - 解法2：DFS
  - 解法3：BFS
- 28. 左叶子之和
- - _解法1：DFS
容器 & 库
- 29. 根据数字二进制下1的数目排序
- - _解法1：自定义排序
- 30. 用栈实现队列
- - _解法1：模拟
- 31. 有效的字母异同位
- - _解法1：sort API
  - _解法2：哈希 / 数组
- 32. 存在重复元素
- - _解法1：set
类 & 对象
- 33. 设计停车系统
- - _解法1：模拟
- 34. 区域和检索 – 数组不可变
- - _解法1：模拟
  - _解法2：前缀和数组

小标题以 _ 开头的题目和解法代表独立想到思路及编码完成，其他是对题解的学习。

每次做完题目（不管做没做出来）都会精心研究其他题解并做笔记认真学习。

思路最简单的解法、最优解法，这里都有！

基本数据类型

1. 在区间范围内统计奇数数目

题目：1523. 在区间范围内统计奇数数目

_解法1：暴力迭代

/*** @param {number} low* @param {number} high* @return {number}* https://leetcode-cn.com/problems/count-odd-numbers-in-an-interval-range/* 暴力*/
var countOdds = function (low, high) {let count = 0;for (let i = low; i <= high; i++)if (i & 1 == 1) count++return count
};

_解法2：数学（找规律）

/*** @param {number} low* @param {number} high* @return {number}* 数学*/
var countOdds = function (low, high) {let lowOdd = (low & 1) === 1 // low 是否为奇数let highOdd = (high & 1) === 1 // high 是否为奇数if (lowOdd && highOdd) return 1 + (high - low) / 2return (high - low) / 2      
};

2. 去掉最低工资和最高工资后的工资平均值

题目：1491. 去掉最低工资和最高工资后的工资平均值

_解法1：迭代

/*** @param {number[]} salary* @return {number}* 迭代*/
var average = function (salary) {let sum = 0, min = salary[0], max = salary[0]salary.forEach(s => {min = Math.min(min, s)max = Math.max(max, s)sum += s})return (sum - max - min) / (salary.length - 2)
};

运算符

3. 位1的个数

题目：191. 位1的个数

_解法1：迭代

/*** @param {number} n - a positive integer* @return {number}* 暴力(超时)*/
var hammingWeight = function (n) {let count = 0while (n != 0) {if (n & 1) count++;n <<= 1}return count
};

_解法2：位运算

/*** @param {number} n - a positive integer* @return {number}* 位运算*/
var hammingWeight = function (n) {let count = 0while (n != 0) {n &= (n - 1) // 消去最后一位1count++}return count
};

4. 整数的各位积和之差

题目：1281. 整数的各位积和之差

JS 中转整数：

res = Math.floor(res);返回值为 小于等于 其数值参数的最大整数值

res = Math.ceil(res); 返回值为 大于等于 其数字参数的最小整数

_解法1：迭代

/*** @param {number} n* @return {number}* 迭代*/
var subtractProductAndSum = function (n) {let sum = 0, product = 1while (n > 0) {let num = Math.floor(n % 10)sum += numproduct *= numn = Math.floor(n / 10)}return product - sum
}

解法2：转字符串再转数组

/*** @param {number} n* @return {number}* 转字符串转数组再迭代*/
var subtractProductAndSum = function (n) {let nums = n.toString().split('').map(e => parseInt(e))let sum = 0, product = 1for (let num of nums) {sum += numproduct *= num}return product - sum
}

条件语句

5. 三角形的最大周长

_解法1：排序 + 迭代

/*** @param {number[]} nums* @return {number}* 排序后遍历相邻元素*/
var largestPerimeter = function (nums) {nums = nums.sort((a, b) => b - a)for (let i = 2; i < nums.length; i++) {let a = nums[i - 2], b = nums[i - 1], c = nums[i]if (b + c > a)return a + b + c}return 0
};

6. 找到最近的有相同X或Y坐标的点

题目：1779. 找到最近的有相同 X 或 Y 坐标的点

_解法1：迭代

/*** @param {number} x* @param {number} y* @param {number[][]} points* @return {number}*/var nearestValidPoint = function(x, y, points) {let min = Number.MAX_VALUE, idx = -1for (let i = 0; i < points.length; i++) {let point = points[i]let distance = getManhattanDistance(point, [x, y])// 剪枝, 遇到相同坐标直接返回if (distance === 0) return i// 寻找曼哈顿距离最小的下标if ((point[0] == x || point[1] == y) && distance < min) {min = distanceidx = i}}return idx
};/*** 计算曼哈顿距离* @param {number[]} p1* @param {number[]} p2* @return {number}*/
var getManhattanDistance = (p1, p2) => {return Math.abs(p1[0] - p2[0]) + Math.abs(p1[1] - p2[1]) 
}

循环

7. 数组元素积的符号

题目：Loading Question… – 力扣（LeetCode） (leetcode-cn.com)

_解法1：reduce

/*** @param {number[]} nums* @return {number}*/
var arraySign = function (nums) {return nums.reduce((pre, cur) => pre * (cur > 0 ? 1 : (cur < 0 ? -1 : 0)), 1)
};

_解法2：迭代

 var arraySign = function(nums) {let res = 1for (let i = 0; i < nums.length; i++) {// 剪枝if (nums[i] == 0) return 0;res *= nums[i] > 0 ? 1 : -1}return res
};

8. 判断能否形成等差数列

题目：1502. 判断能否形成等差数列

解法1：模拟（迭代）

/*** https://leetcode-cn.com/problems/can-make-arithmetic-progression-from-sequence/* @param {number[]} arr* @return {boolean}*/
var canMakeArithmeticProgression = function (arr) {// js 负数排序, 需要传入函数, 否则是字符串排序arr = arr.sort((a, b) => a - b)let step = arr[1] - arr[0] // 根据前两个数算出步长 for (let i = 1; i < arr.length; i++)if (arr[i] != arr[i - 1] + step)return false;return true;
};var canMakeArithmeticProgression = function (arr) {arr = arr.sort((a, b) => a - b)for (let i = 1; i < arr.length - 1; i++)return false;return true;
};

9. 快乐数

题目：202. 快乐数

_解法1：模拟

/*** 快乐数* @param {number} n* @return {boolean}* 模拟(map)*/
var isHappy = function (n) {let newVal = 0, set = new Set()while (newVal != 1) {newVal = 0while (n) {newVal += Math.pow(~~(n % 10), 2)n /= 10}if (set.has(newVal)) return false;set.add(newVal)n = newVal}return true
};

比较优雅的写法：

var isHappy = function (n) {let set = new Set()while (n != 1) {n = bitSquareSum(n)if (set.has(n)) return false;set.add(n)}return true
};/*** 求每位平方和*/
var bitSquareSum = function (n) {let sum = 0while (n) {sum += ~~(n % 10) * ~~(n % 10)n /= 10}return sum
}

解法2：快慢指针

判断循环要想到快慢指针。

/*** 快慢指针*/
var isHappy = function (n) {let slow = n, fast = ndo {slow = bitSquareSum(slow);fast = bitSquareSum(fast);fast = bitSquareSum(fast);} while (slow != fast)return slow == 1
};/*** 求每位平方和*/
var bitSquareSum = function (n) {let sum = 0while (n) {sum += ~~(n % 10) * ~~(n % 10)n /= 10}return sum
}

10. 仅执行一次字符串交换能否使两个字符串相等

题目：仅执行一次字符串交换能否使两个字符串相等

提示：

1 <= s1.length, s2.length <= 100
s1.length == s2.length
s1 和 s2 仅由小写英文字母组成

_解法1：模拟

思路：

count 记录不同的字符的个数，必须为 2
- 循环过程中发现大于 2 直接返回（剪枝操作），比如 “aaaxyz” “bbbxyz”
- 循环结束发现只有 1 个字符不同，肯定无法交换成一样的，比如 “aa” “ab”
由于确定不同字符个数必须为 2，idx1, idx2 分别记录位置
- 循环结束后，查看 s1[idx2] 是否等于 s2[idx1]，s2[idx1] 是否等于 s1[idx2]

/*** https://leetcode-cn.com/problems/check-if-one-string-swap-can-make-strings-equal/* 仅执行一次字符串交换能否使两个字符串相等* @param {string} s1* @param {string} s2* @return {boolean}*/
var areAlmostEqual = function (s1, s2) {let count = 0, idx1 = -1, idx2 = -1for (let i in s1) {if (s1[i] != s2[i]) {idx1 < 0 ? idx1 = i : idx2 = icount++}if (count > 2) return false}if (count == 1) return false;return s1[idx1] == s2[idx2] && s1[idx2] == s2[idx1]
};

函数

11. N 叉树的前序遍历

题目：589. N 叉树的前序遍历

_解法1：递归

/*** // Definition for a Node.* function Node(val, children) {*    this.val = val;*    this.children = children;* };*//*** @param {Node|null} root* @return {number[]}* 递归*/
var preorder = function (root) {if (root == null) return []let res = [root.val]for (let n of root.children)res.push(...preorder(n))return res
};

12. 下一个更大元素 I

题目：496. 下一个更大元素 I

提示：

1 <= nums1.length <= nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 104
nums1 和 nums2 中所有整数互不相同
nums1 中的所有整数同样出现在 nums2 中

_解法1：模拟

/*** @param {number[]} nums1* @param {number[]} nums2* @return {number[]}*/
var nextGreaterElement = function (nums1, nums2) {let res = new Array(nums1.length), idx = 0for (let i = 0; i < nums1.length; i++) {for (let j = nums2.indexOf(nums1[i]); j < nums2.length; j++) {if (nums2[j] > nums1[i]) {res[idx++] = nums2[j]break}if (j == nums2.length - 1)res[idx++] = -1}}return res
};

_解法2：单调栈

13. 缀点成线

题目：1232. 缀点成线

提示：

2 <= coordinates.length <= 1000
coordinates[i].length == 2
-10^4 <= coordinates[i][0], coordinates[i][1] <= 10^4
coordinates 中不含重复的点

_解法1：数学 + 模拟

/*** @param {number[][]} coordinates* @return {boolean}* 数学 + 模拟*/
var checkStraightLine = function (coordinates) {// 取两个点来决定 fx 方程let p1 = coordinates[0], p2 = coordinates[1]// x = aif (p1[0] - p2[0] == 0) {for (let coordinate of coordinates)if (coordinate[0] != p1[0])return falsereturn true}// y = bif (p1[1] - p2[1] == 0) {for (let coordinate of coordinates)if (coordinate[1] != p1[1])return falsereturn true}// y = kx + blet k = (p1[1] - p2[1]) / (p1[0] - p2[0])let b = p1[1] - k * p1[0] // b = y - kxconst fx = (x, k, b) => k * x + bfor (let coordinate of coordinates)if (coordinate[1] != fx(coordinate[0], k, b))return falsereturn true
};

数组

14. 所有奇数长度数组的和

题目：1588. 所有奇数长度子数组的和

解法1：暴力

// 暴力
// [1,4,2,5,3]
// 1, 14, 142, 14253
// 4, 425
// 2, 253
// 5
// 3
var sumOddLengthSubarrays = function (arr) {let sum = 0;const n = arr.length;for (let start = 0; start < n; start++) {for (let length = 1; start + length <= n; length += 2) { // 奇数const end = start + length - 1;for (let i = start; i <= end; i++)sum += arr[i];}}return sum;
};

解法2：前缀和

/*** 前缀和* 利用前缀和，可以快速的计算出两个下标之间的所有元素的和*/
var sumOddLengthSubarrays = function (arr) {const n = arr.length;const prefixSums = new Array(n + 1).fill(0);for (let i = 0; i < n; i++)prefixSums[i + 1] = prefixSums[i] + arr[i];let sum = 0;for (let start = 0; start < n; start++) {for (let length = 1; start + length <= n; length += 2) {const end = start + length - 1;sum += prefixSums[end + 1] - prefixSums[start];}}return sum;
};

15. 移动零

题目：283. 移动零 – 力扣（LeetCode） (leetcode-cn.com)

解法1：双指针

常规思路：

遍历时将整数全部移动到前面, 剩下的补 0
left 记录不为 0 的数字个数

var moveZeroes = function (nums) {let left = 0, right = 0while (right < nums.length) {if (nums[right] != 0)nums[left++] = nums[right]right++}while (left < nums.length)nums[left++] = 0
};

优化成一轮循环：

遍历时 right 遇到不为 0 的数字，就和前面为 0 的 left 交换
遇到为 0 的数字，left 不动，right 继续往前

var moveZeroes = function (nums) {let left = 0, right = 0while (right < nums.length) {if (nums[right] != 0) {if (nums[left] == 0) {[nums[left], nums[right]] = [nums[right], nums[left]]}left++}right++}
};

16. 最富有客户的资产总量

题目：1672. 最富有客户的资产总量

_解法1：暴力模拟

/*** @param {number[][]} accounts* @return {number}*/
var maximumWealth = function (accounts) {let max = -1for (let i = 0; i < accounts.length; i++) {let sum = 0for (let j = 0; j < accounts[0].length; j++)sum += accounts[i][j]max = Math.max(max, sum)}return max
};/*** 高阶函数简化代码*/
var maximumWealth = function (accounts) {let max = -1for (let account of accounts)max = Math.max(max, account.reduce((pre, cur) => pre + cur), 0)return max
}

17. 矩阵对角元素的和

题目：矩阵对角线元素的和

_解法1：模拟

var diagonalSum = function (mat) {let sum = 0, len = mat.length// 左上角 -> 右下角let i = 0, j = 0while (i < len && j < len) {sum += mat[i][j]mat[i++][j++] = -1}// 右上角 -> 左下角i = 0, j = len - 1while (i < len && j >= 0) {if (mat[i][j] != -1)sum += mat[i][j]i++j--}return sum
};

优化写法：一轮循环

var diagonalSum = function (mat) {let len = mat.length, sum = 0for (let i = 0; i < len; i++)sum += mat[i][i] + mat[i][len - i - 1]return len & 1 ? sum - mat[~~(len / 2)][~~(len / 2)] : sum
};

18. 重塑矩阵

题目：566. 重塑矩阵

_解法1：模拟

/*** @param {number[][]} mat* @param {number} r* @param {number} c* @return {number[][]}*/
var matrixReshape = function (mat, r, c) {let m = mat.length, n = mat[0].lengthif (m * n != r * c) return matlet idx = 0, tmpArr = new Array(), res = []for (let i = 0; i < m; i++) {for (let j = 0; j <= n; j++) {if (idx == c) {res.push(tmpArr)tmpArr = []idx = 0}if (j == n) breaktmpArr.push(mat[i][j])idx++}}return res
};

解法2：数学

class Solution {public int[][] matrixReshape(int[][] mat, int r, int c) {int m = mat.length, n = mat[0].length;if (m * n != r * c) return mat;int[][] res = new int[r][c];for (int i = 0; i < m * n; i++) res[i / c][i % c] = mat[i / n][i % n];return res;}
}

字符串

19. 交替合并字符串

题目：1768. 交替合并字符串

提示：

1 <= word1.length, word2.length <= 100
word1 和 word2 由小写英文字母组成

_解法1：模拟

/*** @param {string} word1* @param {string} word2* @return {string}*/
var mergeAlternately = function (word1, word2) {let chars1 = [...word1], chars2 = [...word2]let p1 = 0, p2 = 0, res = []while (p1 < chars1.length || p2 < chars2.length) {if (p1 < chars1.length) res.push(chars1[p1++])if (p2 < chars2.length) res.push(chars2[p2++])}return res.join("")
};

代码优化：

var mergeAlternately = function (word1, word2) {let res = []for (let i = 0; i < word1.length || i < word2.length; i++) {if (i < word1.length) res.push(word1[i])if (i < word2.length) res.push(word2[i])}return res.join('')
};

20. 设计 Goal 解析器

题目：1678. 设计 Goal 解析器

提示：

1 <= command.length <= 100
command 由 "G"、"()" 和 / 或 "(al)" 按某种顺序组成

_解法1：字符串替换

var interpret = function (command) {return command.replaceAll('()', 'o').replaceAll('(al)', 'al')
};

_解法2：迭代 + 分情况

var interpret = function (command) {let res = []for (let i = 0; i < command.length; i++) {if (command[i] == 'G') res.push('G')if (command[i] == '(') {if (command[i + 1] == ')') {res.push('o')i++} else {res.push('al')i += 3}}}return res.join('')
};

21. 找不同

题目：389. 找不同

_解法1：哈希

 var findTheDifference = function (s, t) {let map = new Map()for (let c of s)map.set(c, map.has(c) ? map.get(c) + 1 : 1)for (let c of t) {if (!map.has(c)) return cif (map.get(c) > 0)map.set(c, map.get(c) - 1)else if (map.get(c) == 0)return c}return ''
};

_解法2：位运算

class Solution {public char findTheDifference(String s, String t) {int res = 0;for (char c : t.toCharArray())res += c;for (char c : s.toCharArray())res -= c;return (char) res;}/** 位运算 一行*/public char findTheDifference1(String s, String t) {return (char) (s + t).chars().reduce(0, (a, b) -> a ^ b);}
}

解法3：字符和之差

public char findTheDifference(String s, String t) {int res = 0;for (char c : t.toCharArray())res += c;for (char c : s.toCharArray())res -= c;return (char) res;
}

22. 转换成小写字母

题目：709. 转换成小写字母

_解法1：模拟

var toLowerCase = function (s) {return [...s].map(e => e >= 'A' && e <= 'Z' ? e.toLowerCase() : e).join('')
};

解法2：位运算

大写变小写、小写变大写：a ^= 32
大写变小写、小写变小写：a |= 32
小写变大写、大写变大写：a &= -33

func toLowerCase(s string) string {res := ""for _, v := range s {if v >= 'A' && v <= 'Z' {v |= 32}res += fmt.Sprintf("%c", v)}return res
}

23. 解码字母到整数映射

题目：1309. 解码字母到整数映射

提示：

1 <= s.length <= 1000
s[i] 只包含数字（'0'–'9'）和 '#' 字符。
s 是映射始终存在的有效字符串。

解法1：模拟

思路有 正向遍历 和 反向遍历：

class Solution {/*** 正向遍历*/public String freqAlphabets(String s) {StringBuilder sb = new StringBuilder();char[] chars = s.toCharArray();for (int i = 0; i < chars.length; i++) {if (i + 2 < chars.length && chars[i + 2] == '#') {int tmp = (int) (chars[i] - '0') * 10 + (int) (chars[i + 1] - '0');sb.append((char) (tmp + 'a' - 1));i += 2;} else {sb.append((char) (chars[i] + 'a' - '1'));}}return sb.toString();}/*** 反向遍历*/public String freqAlphabets1(String s) {StringBuilder sb = new StringBuilder();for (int i = s.length() - 1; i >= 0; i--) {if (s.charAt(i) == '#') {int tmp = s.charAt(--i) - '1' + (s.charAt(--i) - '0') * 10;sb.append((char) ('a' + tmp));} else {sb.append((char) ('a' + s.charAt(i) - '1'));}}return sb.reverse().toString();}
}

JS 正向遍历：

JS 利用 模板字符串，将两个字符拼到一起很方便

var freqAlphabets = function (s) {let res = ""for (let i = 0; i < s.length; i++) {if (s[i + 2] === '#') {let value = +`${s[i]}${s[i + 1]}` + 96res += String.fromCharCode(value)i += 2} else {res += String.fromCharCode(+s[i] + 96)}}return res
}

24. 验证外星语词典(todo)

题目：953. 验证外星语词典

提示：

1 <= words.length <= 100
1 <= words[i].length <= 20
order.length == 26
在 words[i] 和 order 中的所有字符都是英文小写字母。

_解法1：map + 迭代

其实就是每两个单词，从首字母开始比较字典序（按照给出的 order 中字母的顺序，越前面的字母相当于字典序越大）

两个字母相同：就比较这两个单词的下一个字母
两个字母不同：看是不是前面的单词的字母的字典序比较大
- 是的话，说明这两个单词的顺序没问题，继续比较下两个单词
- 不是的话，直接返回 false
以上过程注意处理特殊情况

比如 ‘apple’ 和 ‘app’，取第4个索引时，JS 就是在比较 'l' 和 undefined，因此提前给 undefined 设置最大字典序就行（其他语言不能这么玩）

function isAlienSorted(words: string[], order: string): boolean {let map = new Map()// 注：这样映射, 对应的数字越小, 字典序越大for (let i = 0; i < order.length; i++)map.set(order[i], i)// JS 中字符串取超出长度时为 undefined, 设置为最大字典序map.set(undefined, -1)// 单词之间两两比较for (let i = 0; i < words.length - 1; i++) {for (let j = 0; j < Math.max(words[i].length, words[i + 1].length); j++) {// 相同字母, 跳到下轮比较if (words[i][j] == words[i + 1][j]) continue// 前面的字母字典序中比较小(数字大), 则返回 falseelse if (map.get(words[i][j]) > map.get(words[i + 1][j]))return false;// 前面的字母字典序比较大, 进入 下两个单词的比较else break}}return true
};

解法2：高阶函数

思路：相当于先翻译，再用默认排序，然后比较排序结果和翻译的结果

function isAlienSorted (words: string[], order: string): boolean {// 将每个单词的每个字母，替换成【order 中的索引对应的 ASCII 码】//（目的是防止索引较长出现多个字符，ASCII 码只对应一个字符）const newWords = words.map(word => {return word.split('').map(c => String.fromCharCode(order.indexOf(c))).join('')})// 浅拷贝后排序const sortedNewWords = [...newWords].sort()return equalArr(newWords, sortedNewWords);
}
// 比较两个数组的每个元素是否相同
const equalArr = (arrA, arrB) => arrA.every((x, i) => x === arrB[i])

链表 & 树

25. 二进制链表转整数

题目：1290. 二进制链表转整数

提示：

链表不为空。
链表的结点总数不超过 30。
每个结点的值不是 0 就是 1。

_解法1：哈希

/*** @param {ListNode} head* @return {number}* 哈希*/
var getDecimalValue = function (head) {let res = 0let map = new Map(), idx = 0while (head) {map.set(idx++, head.val)head = head.next}map.forEach((k, v) => res += Math.pow(2, idx - v - 1) * k)return res
};

其实不需要用哈希，使用数组即可：

var getDecimalValue = function (head) {let res = 0, arr = []while (head) {arr.push(head.val)head = head.next}arr.forEach((val, i) => res += (2 ** (arr.length - i - 1)) * val)return res
};

解法2：位运算

var getDecimalValue = function (head) {let res = 0while (head) {res = (res << 1) + head.valhead = head.next}return res
}

26. 链表的中间结点

题目：876. 链表的中间结点

解法：快慢指针。

此题做过。

27. 二叉树的最大深度

题目：104. 二叉树的最大深度

_解法1：递归

var maxDepth = function (root) {if (!root) return 0return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
};

解法2：DFS

let maxLevel = 0
var maxDepth = function (root) {dfs(root, 1)return maxLevel
};const dfs = (root, level) => {if (!root) returnlevel > maxLevel && (maxLevel = level)dfs(root.left, level + 1)dfs(root.right, level + 1)
}

解法3：BFS

var maxDepth = function (root) {if (!root) return 0let level = 0, queue = [root]while (queue.length) {level++for (let i = queue.length - 1; i >= 0; i--) {let node = queue.pop()node.left && queue.unshift(node.left)node.right && queue.unshift(node.right)}}return level
};

28. 左叶子之和

题目：404. 左叶子之和

提示:

节点数在 [1, 1000] 范围内
-1000 <= Node.val <= 1000

_解法1：DFS

var sumOfLeftLeaves = function (root) {let sum = 0return dfs(root, false, sum)
};const dfs = (root, isLeft, sum) => {if (!root) return 0// 是左节点, 且是叶子节点if (isLeft && !root.left && !root.right)sum += root.valreturn sum + dfs(root.left, true, sum) + dfs(root.right, false, sum)
}

另一种递归写法：

var sumOfLeftLeaves = function (root) {if (!root) return 0let sum = 0// 判断节点是否是左叶子节点, 是则累加其和if (root.left && !root.left.left && !root.left.right)sum += root.left.valreturn sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right) + sum
};

容器 & 库

29. 根据数字二进制下1的数目排序

题目：1356. 根据数字二进制下 1 的数目排序

_解法1：自定义排序

function sortByBits(arr: number[]): number[] {arr.sort((a, b) => {let aNum = getBinOneNum(a), bNum = getBinOneNum(b)return aNum == bNum ? a - b : aNum - bNum})return arr
};/*** 获取 num 的二进制表示中数字 1 的个数*/
const getBinOneNum = (num: number) => {let count = 0while (num) {num &= num - 1count++}return count
}

30. 用栈实现队列

题目：232. 用栈实现队列

提示：

1 <= x <= 9
最多调用 100 次 push、pop、peek 和 empty
假设所有操作都是有效的（例如，一个空的队列不会调用 pop 或者 peek 操作）

进阶：

你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。

_解法1：模拟

// ts
class MyQueue {inStack: number[]outStack: number[]constructor() {this.inStack = []this.outStack = []}push(x: number) {this.inStack.push(x)}pop(): number {if (!this.outStack.length) {while (this.inStack.length) {this.outStack.push(this.inStack.pop())}}return this.outStack.pop()}peek(): number {if (!this.outStack.length) {while (this.inStack.length) {this.outStack.push(this.inStack.pop())}}return this.outStack[this.outStack.length - 1]}empty(): boolean {return !this.inStack.length && !this.outStack.length}
}

// java
class MyQueue {Stack<Integer> inStack, outStack;public MyQueue() {inStack = new Stack<>();outStack = new Stack<>();}public void push(int x) {inStack.push(x);if (outStack.isEmpty()) {while (!inStack.isEmpty()) {outStack.push(inStack.pop());}}}public int pop() {if (outStack.isEmpty()) {while (!inStack.isEmpty()) {outStack.push(inStack.pop());}}return outStack.pop();}public int peek() {if (outStack.isEmpty()) {while (!inStack.isEmpty()) {outStack.push(inStack.pop());}}return outStack.peek();}public boolean empty() {return inStack.isEmpty() && outStack.isEmpty();}
}

31. 有效的字母异同位

题目：242. 有效的字母异位词

_解法1：sort API

function isAnagram(s: string, t: string): boolean {return [...s].sort().toString() == [...t].sort().toString()
};

_解法2：哈希 / 数组

function isAnagram(s: string, t: string): boolean {let map = new Map<string, number>()// 将 s 中的字符与其出现次数做映射for (let c of s)map.set(c, (map.get(c) ?? 0) + 1)// 遍历 t 中的字符, map 中存在其映射则 -1for (let c of t) {// 剪枝, 如果 t 中找不到 s 中某个字符, 一定不满足条件if (!map.has(c)) return falsemap.set(c, map.get(c) - 1)}// 如果 map 中字符的映射次数还有 > 0 的, 说明不满足条件for (let val of map.values())if (val > 0) return falsereturn true
};

似乎只要范围是英文字母，基本都可以把哈希优化成数组

function isAnagram(s: string, t: string): boolean {let counts = new Array<number>(26).fill(0)for (let c of s)counts[c.charCodeAt(0) - 'a'.codePointAt(0)]++for (let c of t) if (counts[c.charCodeAt(0) - 'a'.codePointAt(0)] == 0) return falsefor (let num of counts)if (num != 0) return falsereturn true
}

32. 存在重复元素

题目：217. 存在重复元素

_解法1：set

const containsDuplicate = function (nums: number[]): boolean {let set = new Set<number>()for (let num of nums) {if (set.has(num)) return trueset.add(num)}return false
};

简化写法：

const containsDuplicate = function (nums: number[]): boolean {return new Set(nums).size < nums.length
}

Java 简化写法：

class Solution {public boolean containsDuplicate(int[] nums) {return Arrays.stream(nums).distinct().count() < nums.length;}
}

类 & 对象

33. 设计停车系统

题目：1603. 设计停车系统

_解法1：模拟

class ParkingSystem {private int big;private int medium;private int small;public ParkingSystem(int big, int medium, int small) {this.big = big;this.medium = medium;this.small = small;}public boolean addCar(int carType) {if (carType == 1) {return big > 0 ? (big-- >= 0) : false;} else if (carType == 2) {return medium > 0 ? (medium-- >= 0) : false;} else if (carType == 3) {return small > 0 ? (small-- >= 0) : false;} elsereturn false; // 非法数据}
}

利用数组存储代码更简洁：

class ParkingSystem {int[] cars = new int[3];public ParkingSystem(int big, int medium, int small) {cars[0] = big;cars[1] = medium;cars[2] = small;}public boolean addCar(int carType) {return cars[carType - 1]-- > 0;}
}

34. 区域和检索 – 数组不可变

题目：303. 区域和检索 – 数组不可变

_解法1：模拟

class NumArray {private int[] nums;public NumArray(int[] nums) {this.nums = nums; }public int sumRange(int left, int right) {int sum = 0;for (int i = left; i <= right; i++) sum += nums[i];return sum;}
}

_解法2：前缀和数组

class NumArray {int[] preSums;public NumArray(int[] nums) {preSums = new int[nums.length + 1]; for (int i = 1; i < preSums.length; i++)preSums[i] = preSums[i - 1] + nums[i - 1];System.out.println(Arrays.toString(preSums));}public int sumRange(int left, int right) {return preSums[right + 1] - preSums[left];}
}
// nums = [1, 2, 3, 4, 5]
// preSums = [0, 1, 3, 6, 10, 15]

LeetCode《编程能力入门》刷题笔记（34 题全）

LeetCode《编程能力入门》刷题笔记

基本数据类型

1. 在区间范围内统计奇数数目

_解法1：暴力迭代

_解法2：数学（找规律）

2. 去掉最低工资和最高工资后的工资平均值

_解法1：迭代

运算符

3. 位1的个数

_解法1：迭代

_解法2：位运算

4. 整数的各位积和之差

_解法1：迭代

解法2：转字符串再转数组

条件语句

5. 三角形的最大周长

_解法1：排序 + 迭代

6. 找到最近的有相同X或Y坐标的点

_解法1：迭代

循环

7. 数组元素积的符号

_解法1：reduce

_解法2：迭代

8. 判断能否形成等差数列

解法1：模拟（迭代）

9. 快乐数

_解法1：模拟

解法2：快慢指针

10. 仅执行一次字符串交换能否使两个字符串相等

_解法1：模拟

函数

11. N 叉树的前序遍历

_解法1：递归

12. 下一个更大元素 I

_解法1：模拟

_解法2：单调栈

13. 缀点成线

_解法1：数学 + 模拟

数组

14. 所有奇数长度数组的和

解法1：暴力

解法2：前缀和

15. 移动零

解法1：双指针

16. 最富有客户的资产总量

_解法1：暴力模拟

17. 矩阵对角元素的和

_解法1：模拟

18. 重塑矩阵

_解法1：模拟

解法2：数学

字符串

19. 交替合并字符串

_解法1：模拟

20. 设计 Goal 解析器

_解法1：字符串替换

_解法2：迭代 + 分情况

21. 找不同

_解法1：哈希

_解法2：位运算

解法3：字符和之差

22. 转换成小写字母

_解法1：模拟

解法2：位运算

23. 解码字母到整数映射

解法1：模拟

24. 验证外星语词典(todo)

_解法1：map + 迭代

解法2：高阶函数

链表 & 树

25. 二进制链表转整数

_解法1：哈希

解法2：位运算

26. 链表的中间结点

27. 二叉树的最大深度

_解法1：递归

解法2：DFS

解法3：BFS

28. 左叶子之和