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：BFS28. 左叶子之和_解法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-/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-)
_解法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-/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 <= 100s1.length == s2.lengths1和s2仅由小写英文字母组成
_解法1：模拟
思路：
count记录不同的字符的个数，必须为 2 循环过程中发现大于 2 直接返回（剪枝操作），比如 “aaaxyz” “bbbxyz”循环结束发现只有 1 个字符不同，肯定无法交换成一样的，比如 “aa” “ab” 由于确定不同字符个数必须为 2，idx1,idx2分别记录位置 循环结束后，查看 s1[idx2] 是否等于 s2[idx1]，s2[idx1] 是否等于 s1[idx2]
/*** https://leetcode-/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 <= 10000 <= nums1[i], nums2[i] <= 104nums1和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 <= 1000coordinates[i].length == 2-10^4 <= coordinates[i][0], coordinates[i][1] <= 10^4coordinates中不含重复的点
_解法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// 3var 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-)
解法1：双指针
常规思路：
遍历时将整数全部移动到前面, 剩下的补 0left 记录不为 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 <= 100word1和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 <= 100command由"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 &= -33func 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 <= 1000s[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 <= 1001 <= words[i].length <= 20order.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 = 0var 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：模拟
// tsclass 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}}
// javaclass 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 题全）》对你有帮助，请点赞、收藏，并留下你的观点哦！
