LeetCode《算法入门》刷题笔记（31 题全）
二分查找1. 二分查找_解法1：二分搜索（迭代）解法2：二分搜索（递归）2. 第一个错误的版本_解法1：二分3. 搜索插入位置_解法1：二分双指针4. 有序数组的平方_解法1：map + sort解法2：双指针5. 轮转数组_解法1：额外空间解法2：JS API解法3：反转 3 次数组6. 移动零解法1：双指针7. 两数之和 II - 输入有序数组_解法1：map解法2：双指针_解法3：暴力 + 二分8. 反转字符串_解法1：双指针解法2：递归9. 反转字符串中的单词 III_解法1：高阶函数 API10. 链表的中间结点_解法1：哈希_解法2：快慢指针11. 删除链表的倒数第 N 个结点_解法1：双指针解法2：递归滑动窗口12. 无重复的最长子串解法1：滑动窗口13. 字符串的排列解法1：滑动窗口 + 字典DFS / BFS14. 图像渲染解法1：DFS解法2：BFS15. 岛屿的最大面积_解法1：DFS16. 合并二叉树_解法1：递归17. 填充每个节点的下一个右侧节点指针_解法1：递归18. 0 1 矩阵**解法1：BFS解法2：DFS19. 腐烂的橘子**解法1：BFS递归 / 回溯20. 合并两个有序链表_解法1：递归解法2：迭代21. 反转链表解法1：递归解法2：迭代22. 组合**解法1：回溯23. 全排列**_解法1：回溯24. 字母大小写全排列*解法1：回溯动态规划25.爬楼梯我的题解：递归、记忆化递归 、动态规划26. 打家劫舍我的题解27. 三角形的最小路径和我的题解：动态规范、递归位运算28. 2的幂我的题解29. 位1的个数我的题解30. 颠倒二进制位我的题解：API、位运算31. 只出现一次的数字我的题解：位运算二分查找
1. 二分查找
题目：704. 二分查找
_解法1：二分搜索（迭代）
/*** @param {number[]} nums* @param {number} target* @return {number}*/var search = function (nums, target) {return binarySearch(nums, target, 0, nums.length - 1)};/*** 在 nums 的 [left, right] 中搜索 target, 返回搜索到值的索引* @param {number[]} nums 执行搜索的目标数组* @param {number} target 搜索的目标数* @param {number} left 搜索的左边界* @param {number} right 搜索的右边界* @return {number} 目标数的索引, 不存在返回 -1*/var binarySearch = function (nums, target, left, right) {while (left <= right) {let mid = (left + right) >> 1if (nums[mid] > target)right = mid - 1else if (nums[mid] < target)left = mid + 1else return mid}return -1}
解法2：二分搜索（递归）
var search = function (nums, target) {return binarySearch(nums, target, 0, nums.length - 1)};var binarySearch = function (nums, target, left, right) {if (left > right) return -1let mid = (left + right) >> 1if (nums[mid] == target) return mid;return nums[mid] < target? binarySearch(nums, target, mid + 1, right): binarySearch(nums, target, left, mid - 1)}
2. 第一个错误的版本
题目：278. 第一个错误的版本
_解法1：二分
~~是 js 中 浮点数 转 整数 最快的方法：
console.log(~~6.95) // 最快
/*** @param {function} isBadVersion()* @return {function}*/var solution = function (isBadVersion) {/*** @param {integer} n Total versions* @return {integer} The first bad version*/return function (n) {let left = 1, right = nwhile (left < right) {// 浮点数 --> 整数let mid = ~~(left + (right - left) / 2)isBadVersion(mid) ? right = mid : left = mid + 1}return left};};
3. 搜索插入位置
题目：35. 搜索插入位置
_解法1：二分
/*** @param {function} isBadVersion()* @return {function}*/var solution = function (isBadVersion) {/*** @param {integer} n Total versions* @return {integer} The first bad version*/return function (n) {let left = 1, right = nwhile (left < right) {let mid = ~~(left + (right - left) / 2)isBadVersion(mid) ? right = mid : left = mid + 1}return left};};
双指针
4. 有序数组的平方
题目：977. 有序数组的平方
_解法1：map + sort
/*** https://leetcode-/problems/squares-of-a-sorted-array/* 有序数组的平方* @param {number[]} nums* @return {number[]}*/var sortedSquares = function (nums) {return nums.map(n => n * n).sort((a, b) => a - b)};
解法2：双指针
var sortedSquares = function (nums) {let left = 0, right = nums.length - 1, idx = rightlet res = new Array(nums.length)while (left <= right) {if (Math.pow(nums[left], 2) > Math.pow(nums[right], 2))res[idx--] = Math.pow(nums[left++], 2)elseres[idx--] = Math.pow(nums[right--], 2)}return res};
5. 轮转数组
题目：189. 轮转数组
_解法1：额外空间
/*** https://leetcode-/problems/rotate-array/* 轮转数组* @param {number[]} nums* @param {number} k* @return {void} Do not return anything, modify nums in-place instead.*/var rotate = function (nums, k) {let len = nums.lengthlet res = new Array(len)// 计算好索引, 放到新数组for (let i = 0; i < len; i++)res[(i + k) % len] = nums[i]// 修改传入的数组for (let i = 0; i < len; i++)nums[i] = res[i]};
以上写法中，“修改传入的数组” 这步可以利用 JS API 简化：
var rotate = function (nums, k) {let len = nums.lengthlet res = new Array(len)for (let i = 0; i < len; i++)res[(i + k) % len] = nums[i]nums.splice(0, len, ...res)};
解法2：JS API
var rotate = function (nums, k) {nums.splice(0, 0, ...nums.splice(-(k % nums.length)))};var rotate = function (nums, k) {const len = nums.lengthnums.unshift(...nums.splice(len - k % len))};
解法3：反转 3 次数组
思路：
nums = "----->-->"; k =3result = "-->----->";reverse "----->-->" we can get "<--<-----"reverse "<--" we can get "--><-----"reverse "<-----" we can get "-->----->"
/*** 反转 3 次数组*/var rotate = function (nums, k) {k %= nums.lengthreverse(nums, 0, nums.length - 1)reverse(nums, 0, k - 1)reverse(nums, k, nums.length - 1)}/*** 反转数组*/let reverse = (nums, start, end) => {while (start < end)[nums[start++], nums[end--]] = [nums[end], nums[start]]}
6. 移动零
题目：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++}};
7. 两数之和 II - 输入有序数组
题目：两数之和 II - 输入有序数组
提示：
2 <= numbers.length <= 3 * 104-1000 <= numbers[i] <= 1000numbers按非递减顺序排列-1000 <= target <= 1000仅存在一个有效答案
_解法1：map
题目要求常量级的额外空间，因此这种做法不符合题意
思路：
通过一次遍历，建立 numbers 中元素 和 对应索引 的 映射再次遍历，寻找target - numbers[i]是否在 map 的 key 中
/*** @param {number[]} numbers* @param {number} target* @return {number[]}*/var twoSum = function (numbers, target) {let map = new Map()numbers.forEach((val, i) => map.set(val, i))for (let i = 0; i < numbers.length; i++)if (map.has(target - numbers[i]))return [i + 1, map.get(target - numbers[i]) + 1]return []};
解法2：双指针
思路：
关键在于输入的是有序数组，可以定义两个指针，分别指向首尾计算两个指针指向元素和，大了就right--，小了就left++
var twoSum = function (numbers, target) {let left = 0, right = numbers.length - 1while (left < right) {let sum = numbers[left] + numbers[right]if (sum == target) return [left + 1, right + 1]else if (sum > target) right--;else left++;}return []};
_解法3：暴力 + 二分
/*** 二分*/var twoSum = function (numbers, target) {for (let i = 0; i < numbers.length; i++) {let idx = leftBoundBinarySearch(numbers, target - numbers[i], i + 1, numbers.length - 1)if (idx !== -1) return [i + 1, idx + 1]}return []};/*** 寻找左边界的二分搜索*/const leftBoundBinarySearch = (nums, target, left, right) => {while (left <= right) {let mid = (left + right) >> 1if (nums[mid] >= target)right = mid - 1else if (nums[mid] < target)left = mid + 1}if (left >= nums.length || nums[left] != target)return -1return left}
8. 反转字符串
题目：344. 反转字符串
正常都是使用库函数：
var reverseString = function (s) {s.reverse()};
_解法1：双指针
/*** @param {character[]} s* @return {void} Do not return anything, modify s in-place instead.*/var reverseString = function (s) {let left = 0, right = s.length - 1while (left <= right)[s[left++], s[right--]] = [s[right], s[left]]}
解法2：递归
var reverseString = function (s) {var help = (s, left, right) => {if (left >= right) return[s[left], s[right]] = [s[right], s[left]]help(s, ++left, --right)}help(s, 0, s.length - 1)};
9. 反转字符串中的单词 III
题目：557. 反转字符串中的单词 III
_解法1：高阶函数 API
/*** @param {string} s* @return {string}*/var reverseWords = function (s) {return s.split(" ").map(s => s.split("").reverse().join("")).join(" ")};
10. 链表的中间结点
题目：876. 链表的中间结点
_解法1：哈希
var middleNode = function (head) {let map = new Map(), idx = 0while (head) {map.set(idx++, head)head = head.next}return map.get(Math.ceil(--idx / 2))};
_解法2：快慢指针
/*** 快慢指针*/var middleNode = function (head) {let slow = head, fast = headwhile (fast.next) {slow = slow.nextfast = fast.nextfast.next && (fast = fast.next)}return slow};/*** 快慢指针*/var middleNode = function (head) {let slow = head, fast = headwhile (fast && fast.next) {slow = slow.nextfast = fast.next.next}return slow};
11. 删除链表的倒数第 N 个结点
题目：19. 删除链表的倒数第 N 个结点
提示：
链表中结点的数目为sz1 <= sz <= 300 <= Node.val <= 1001 <= n <= sz
_解法1：双指针
*/var removeNthFromEnd = function (head, n) {if (!head.next) return nulllet slow = head, fast = headwhile (n--)fast = fast.nextif (!fast) return head.nextwhile (fast && fast.next) {slow = slow.nextfast = fast.next}slow.next = slow.next.nextreturn head};/*** @param {ListNode} head* @param {number} n* @return {ListNode}*/var removeNthFromEnd = function (head, n) {if (!head.next) return nulllet slow = head, fast = headwhile (n--)fast = fast.nextif (!fast) return head.nextwhile (fast && fast.next) {slow = slow.nextfast = fast.next}slow.next = slow.next.nextreturn head};
解法2：递归
Java 可以跑通，JS 就不能跑通，有点奇怪。。
class Solution {int cur = 0;public ListNode removeNthFromEnd(ListNode head, int n) {if (head == null) return null;head.next = removeNthFromEnd(head.next, n);cur++;if (cur == n) return head.next;return head;}}
滑动窗口
12. 无重复的最长子串
题目：3. 无重复字符的最长子串
解法1：滑动窗口
var lengthOfLongestSubstring = function (s) {let set = new Set(), max = 0let left = 0, right = 0while (right < s.length) {let c = s[right]while (set.has(c))set.delete(s[left++])set.add(s[right])max = Math.max(max, right - left + 1)right++}return max};
13. 字符串的排列
题目：567. 字符串的排列
解法1：滑动窗口 + 字典
class Solution {public boolean checkInclusion(String s1, String s2) {// 不可能的情况int m = s1.length(), n = s2.length();if (m > n) return false;// cnt 数组: 记录 s1 中字母出现的次数// cur 数组: 记录滑动的窗口中的字母出现的次数int[] cnt = new int[26], cur = new int[26];for (char c : s1.toCharArray())cnt[c - 'a']++;for (int i = 0; i < m; i++)cur[s2.charAt(i) - 'a']++;for (int i = m; i < n; i++) {cur[s2.charAt(i) - 'a']++;cur[s2.charAt(i - m) - 'a']--;if (Arrays.equals(cnt, cur)) return true;}return false;}}
var checkInclusion = function (s1, s2) {let m = s1.length, n = s2.lengthif (m > n) return falselet cnt1 = new Array(26).fill(0), cnt2 = new Array(26).fill(0)for (let c of s1)cnt1[c.charCodeAt() - 'a'.charCodeAt()]++for (let i = 0; i < m; i++)cnt2[s2[i].charCodeAt() - 'a'.charCodeAt()]++if (check(cnt1, cnt2)) return truefor (let i = m; i < n; i++) {cnt2[s2[i].charCodeAt() - 'a'.charCodeAt()]++cnt2[s2[i - m].charCodeAt() - 'a'.charCodeAt()]--if (check(cnt1, cnt2)) return true}return false}let check = (nums1, nums2) => {for (let i = 0; i < nums1.length; i++)if (nums1[i] != nums2[i])return falsereturn true}
DFS / BFS
14. 图像渲染
题目：733. 图像渲染
提示:
m == image.lengthn == image[i].length1 <= m, n <= 500 <= image[i][j], newColor < 2160 <= sr < m0 <= sc < n
解法1：DFS
class Solution {public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {dfs(image, sr, sc, newColor, image[sr][sc]);return image;}/*** @param image 二维数组* @param sr当前行* @param sc当前列* @param newColor 新颜色* @param originColor 旧颜色*/void dfs(int[][] image, int sr, int sc, int newColor, int originColor) {// 越界, 停止遍历if (sr < 0 || sr >= image.length || sc < 0 || sc >= image[0].length) return;// 不满足上色要求, 或是已经上色过, 停止遍历if (image[sr][sc] != originColor || image[sr][sc] == newColor) return;// 上色image[sr][sc] = newColor;dfs(image, sr - 1, sc, newColor, originColor);dfs(image, sr, sc + 1, newColor, originColor);dfs(image, sr + 1, sc, newColor, originColor);dfs(image, sr, sc - 1, newColor, originColor);}}
const floodFill = function (image, sr, sc, newColor) {dfs(image, sr, sc, newColor, image[sr][sc])return image};const dfs = (image, sr, sc, newColor, originColor) => {// 越界if (sr < 0 || sr >= image.length || sc < 0 || sc >= image[0].length) return// 不满足上色要求, 或已经上色过if (image[sr][sc] != originColor || image[sr][sc] == newColor) return;// 上色image[sr][sc] = newColordfs(image, sr - 1, sc, newColor, originColor)dfs(image, sr, sc + 1, newColor, originColor)dfs(image, sr + 1, sc, newColor, originColor)dfs(image, sr, sc - 1, newColor, originColor)}
解法2：BFS
class Solution {int[] dx = {1, 0, 0, -1 };int[] dy = {0, 1, -1, 0 };public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {// 保存初始颜色int originColor = image[sr][sc];// 如果初始颜色和新上的颜色相同, 直接返回原数组if (originColor == newColor) return image;// 初始位置入队Queue<int[]> queue = new LinkedList<>() {{offer(new int[] {sr, sc }); }};// 上色image[sr][sc] = newColor;while (!queue.isEmpty()) {int[] cell = queue.poll();int x = cell[0], y = cell[1];for (int i = 0; i < 4; i++) {int mx = x + dx[i], my = y + dy[i];// 没有越界, 并且还未上过色, 才继续搜索if (mx >= 0 && mx < image.length && my >= 0 && my < image[0].length&& image[mx][my] == originColor) {queue.offer(new int[] {mx, my });image[mx][my] = newColor;}}}return image;}}
15. 岛屿的最大面积
题目：695. 岛屿的最大面积
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 50grid[i][j]为0或1
_解法1：DFS
使用全局变量：
let area = 0var maxAreaOfIsland = function (grid) {let max = -1for (let i = 0; i < grid.length; i++) {for (let j = 0; j < grid[0].length; j++) {area = 0dfs(grid, i, j)max = Math.max(max, area)}}return max};const dfs = (grid, cr, cc) => {// 越界if (cr < 0 || cr >= grid.length || cc < 0 || cc >= grid[0].length) return// 已访问过, 或者不是岛屿if (grid[cr][cc] === -1 || grid[cr][cc] === 0) return// 面积+1, 并标记已经访问area++grid[cr][cc] = -1dfs(grid, cr - 1, cc) // 上dfs(grid, cr, cc + 1) // 右dfs(grid, cr + 1, cc) // 下dfs(grid, cr, cc - 1) // 左}
不使用全局变量：
var maxAreaOfIsland = function (grid) {let max = -1for (let i = 0; i < grid.length; i++)for (let j = 0; j < grid[0].length; j++)max = Math.max(max, dfs(grid, i, j))return max};const dfs = (grid, cr, cc) => {// 越界if (cr < 0 || cr >= grid.length || cc < 0 || cc >= grid[0].length) return 0// 已访问过, 或者不是岛屿if (grid[cr][cc] === -1 || grid[cr][cc] === 0) return 0// 面积+1, 并标记已经访问grid[cr][cc] = -1let area = 1area += dfs(grid, cr - 1, cc) // 上area += dfs(grid, cr, cc + 1) // 右area += dfs(grid, cr + 1, cc) // 下area += dfs(grid, cr, cc - 1) // 左return area}
16. 合并二叉树
题目：617. 合并二叉树
_解法1：递归
/*** @param {TreeNode} root1* @param {TreeNode} root2* @return {TreeNode}*/var mergeTrees = function (root1, root2) {if (root1 && !root2) return root1if (!root1 && root2) return root2if (!root1 && !root2) return nulllet root = new TreeNode(root1.val + root2.val)root.left = mergeTrees(root1.left, root2.left)root.right = mergeTrees(root1.right, root2.right)return root}
17. 填充每个节点的下一个右侧节点指针
题目：116. 填充每个节点的下一个右侧节点指针
提示：
树中节点的数量在 [0, 212 - 1] 范围内-1000 <= node.val <= 1000
进阶：
你只能使用常量级额外空间。使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
_解法1：递归
var connect = function (root) {if (!root) return nullif (root.left) {// 处理下一层root.left.next = root.right// 循环处理后面的层let tmp1 = root.left, tmp2 = root.rightwhile (tmp1.right) {tmp1.right.next = tmp2.lefttmp1 = tmp1.righttmp2 = tmp2.left}}connect(root.left)connect(root.right)return root}
评论区看到更简洁的递归：
var connect = function (root) {if (!root) return nullif (root.left) {root.left.next = root.rightif (root.next)root.right.next = root.next.left}connect(root.left)connect(root.right)return root}
18. 0 1 矩阵**
题目：542. 01 矩阵
解法1：BFS
题解：2种BFS，详解DP， 🤷♀️必须秒懂！
/*** BFS* 首先将所有的 0 入队, 并且将 1 的位置设置为 -1, 表示该位置未被访问过* 遍历队列中的 0, 如果四邻域的点是 -1, 表示这个点是没有访问过的 1* 这个点到 0 的距离更新成 matrix[x][y] + 1*/class Solution {public int[][] updateMatrix(int[][] matrix) {// 首先将所有的 0 入队, 并且将 1 的位置设置为 -1, 表示该位置未被访问过int m = matrix.length, n = matrix[0].length;Queue<int[]> queue = new LinkedList<>();for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (matrix[i][j] == 0) queue.offer(new int[] {i, j });else matrix[i][j] = -1;}}int[] dx = new int[] {-1, 1, 0, 0 };int[] dy = new int[] {0, 0, -1, 1 };while (!queue.isEmpty()) {int[] point = queue.poll();int x = point[0], y = point[1];for (int i = 0; i < 4; i++) {int newX = x + dx[i], newY = y + dy[i];// 如果四邻域的点是 -1, 表示这个点是未被访问过的 1// 所以这个点到 0 的距离可以更新成 matrix[x][y] + 1if (newX >= 0 && newX < m && newY >= 0 && newY < n // 没有越界&& matrix[newX][newY] == -1) {// 没有访问过matrix[newX][newY] = matrix[x][y] + 1;queue.offer(new int[] {newX, newY });}}}return matrix;}}
解法2：DFS
速度很慢。
class Solution {private int min;public int[][] updateMatrix(int[][] mat) {int m = mat.length, n = mat[0].length;boolean[][] visited = new boolean[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (mat[i][j] == 0) continue;min = Integer.MAX_VALUE;dfs(mat, i, j, 0, visited);mat[i][j] = min;}}return mat;}void dfs(int[][] mat, int i, int j, int dis, boolean[][] visited) {if (i < 0 || i >= mat.length || j < 0 || j >= mat[0].length || visited[i][j])return;// 剪枝if (dis > min) return;if (mat[i][j] == 0) {min = Math.min(min, dis);return;}// 标记已访问visited[i][j] = true;dfs(mat, i - 1, j, dis + 1, visited);dfs(mat, i, j + 1, dis + 1, visited);dfs(mat, i + 1, j, dis + 1, visited);dfs(mat, i, j - 1, dis + 1, visited);// 回溯visited[i][j] = false;}}
19. 腐烂的橘子**
题目：994. 腐烂的橘子
解法1：BFS
写法 1：不使用方向数组
import java.util.Queue;class Solution {public int orangesRotting(int[][] grid) {int m = grid.length, n = grid[0].length;Queue<int[]> queue = new LinkedList<>();// 将腐烂的橘子放到队列int count = 0; // 新鲜橘子的个数for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == 1)count++;else if (grid[i][j] == 2)queue.offer(new int[] {i, j });}}int round = 0; // 腐烂的分钟数// 当没有新鲜橘子 或者 队列为空 停止循环while (count > 0 && !queue.isEmpty()) {round++;int size = queue.size();for (int i = 0; i < size; i++) {int[] orange = queue.poll();int x = orange[0], y = orange[1];if (x - 1 >= 0 && grid[x - 1][y] == 1) {// 上grid[x - 1][y] = 2;count--; // 每感染一个, 减少新鲜橘子的数量queue.add(new int[] {x - 1, y });}if (x + 1 < m && grid[x + 1][y] == 1) {// 下grid[x + 1][y] = 2;count--;queue.add(new int[] {x + 1, y });}if (y - 1 >= 0 && grid[x][y - 1] == 1) {// 左grid[x][y - 1] = 2;count--;queue.add(new int[] {x, y - 1 });}if (y + 1 < n && grid[x][y + 1] == 1) {// 右grid[x][y + 1] = 2;count--;queue.add(new int[] {x, y + 1 });}}}return count > 0 ? -1 : round;}}
写法2：使用方向数组：
class Solution {public int orangesRotting(int[][] grid) {int m = grid.length, n = grid[0].length;Queue<int[]> queue = new LinkedList<>();// 将腐烂的橘子放到队列int count = 0; // 新鲜橘子的个数for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == 1)count++;else if (grid[i][j] == 2)queue.offer(new int[] {i, j });}}int[] dx = {1, -1, 0, 0 };int[] dy = {0, 0, -1, 1 };int round = 0; // 橘子腐烂的时间// 当没有新鲜橘子 或者 队列为空 停止循环while (count > 0 && !queue.isEmpty()) {round++;int size = queue.size();for (int i = 0; i < size; i++) {int[] orange = queue.poll();int x = orange[0], y = orange[1];// 边界内某个方向有新鲜橘子, 则遍历for (int j = 0; j < 4; j++) {int newX = x + dx[j], newY = y + dy[j];if (newX >= 0 && newX < m && newY >= 0 && newY < n &&grid[newX][newY] == 1) {grid[newX][newY] = 2; // 新鲜橘子变腐烂count--; // 新鲜橘子数量减少queue.offer(new int[] {newX, newY });}}}}// 能腐烂的橘子都腐烂后, 新鲜橘子的数量还 > 0, 说明无法腐烂, 返回 - 1return count > 0 ? -1 : round;}}
递归 / 回溯
20. 合并两个有序链表
题目：21. 合并两个有序链表
提示：
两个链表的节点数目范围是[0, 50]-100 <= Node.val <= 100l1和l2均按非递减顺序排列
_解法1：递归
递归1：需要创建新结点
/** 递归（需要创建新结点）* 旧写法*/let mergeTwoLists = function (list1: ListNode | null, list2: ListNode | null): ListNode | null {if (!list1 && !list2) return nullif (list1 && !list2) return list1if (!list1 && list2) return list2// list1 && list2 的情况return list1.val <= list2.val? new ListNode(list1.val, mergeTwoLists(list1.next, list2)): new ListNode(list2.val, mergeTwoLists(list1, list2.next))};/*** 递归（需要创建新结点）* 新写法（更简洁）*/mergeTwoLists = function (list1: ListNode | null, list2: ListNode | null): ListNode | null {if (!list2) return list1if (!list1) return list2return list1.val <= list2.val? new ListNode(list1.val, mergeTwoLists(list1.next, list2)): new ListNode(list2.val, mergeTwoLists(list1, list2.next))};
递归2：不需要创建新结点
const mergeTwoLists = function (list1: ListNode | null, list2: ListNode | null): ListNode | null {if (!list1) return list2if (!list2) return list1if (list1.val < list2.val) {list1.next = mergeTwoLists(list1.next, list2)return list1} else {list2.next = mergeTwoLists(list1, list2.next)return list2}}
解法2：迭代
const mergeTwoLists = function (list1: ListNode | null, list2: ListNode | null): ListNode | null {let res = new ListNode(0), cur = reswhile (list1 && list2) {if (list1.val <= list2.val) {cur.next = list1list1 = list1.next} else {cur.next = list2list2 = list2.next}cur = cur.next}cur.next = list1 ?? list2;return res.next}
21. 反转链表
题目：206. 反转链表
解法1：递归
递归核心思想 ：
1 -> 2 <- 3 <- 4 <- 5| |res node
let reverseList = function (head: ListNode | null): ListNode | null {if (!head || !head.next) return headlet node = reverseList(head.next)head.next.next = headhead.next = nullreturn node}
解法2：迭代
/*** 迭代, map*/const reverseList = function (head: ListNode | null): ListNode | null {let map = new Map(), idx = 0while (head) {map.set(idx++, head.val)head = head.next}let newHead = new ListNode(0), res = newHeadwhile (idx > 0) {newHead.next = new ListNode(map.get(--idx))newHead = newHead.next}return res.next}
/*** 迭代, 交换指针* 1 -> 2 -> 3 -> 4 -> null* null <- 1 <- 2 <- 3 <- 4*/const reverseList = function (head: ListNode | null): ListNode | null {// prev 前节点, cur 当前节点let prev = null, cur = head// 每次循环, 将 当前节点 指向 前节点, 然后 当前节点 和 前节点 后移while (cur) {let tmpNode = cur.next // 保存 当前节点 的下一节点cur.next = prev // 当前节点 指向 前节点prev = cur // 前节点后移cur = tmpNode // 当前节点后移}return prev}
22. 组合**
题目：77. 组合
解法1：回溯
这道题属于组合问题，重点在于找对遍历的开始位置
class Solution {List<List<Integer>> res = new ArrayList<>();int k, n;public List<List<Integer>> combine(int n, int k) {this.k = k;this.n = n;dfs(1, new ArrayList<>());return res;}/*** @param begin 开始搜索的数字* @param path 已经访问过的路径*/void dfs(int begin, List<Integer> path) {// 剪枝: 当前访问过 path 长度 + [begin, n] 的长度 < k// 不可能走到长度为 k 的 pathif (path.size() + (n - begin + 1) < k) return;// 访问过 k 个数字, 加入结果if (path.size() == k) {res.add(new ArrayList<>(path));return;}for (int i = begin; i <= n; i++) {path.add(i);dfs(i + 1, path);// 回溯path.remove(path.size() - 1);}}}
let res: number[][]function combine(n: number, k: number): number[][] {res = new Array()dfs(n, k, 1, new Array())return res};const dfs = function (n: number, k: number, begin: number, path: number[]) {// 剪枝if (path.length + (n - begin + 1) < k) return;if (path.length == k) {res.push([...path]);return;}for (let i = begin; i <= n; i++) {path.push(i)dfs(n, k, i + 1, path);// 回溯path.pop()}}
23. 全排列**
题 目：46. 全排列
_解法1：回溯
这道题属于排列问题，每次遍历整个数组，用 visited 记录访问过的位置
class Solution {List<List<Integer>> res = new ArrayList<>();public List<List<Integer>> permute(int[] nums) {boolean[] visited = new boolean[nums.length];dfs(nums, new ArrayList<>(), visited);return res;}void dfs(int[] nums, List<Integer> path, boolean[] visited) {if (path.size() == nums.length) {res.add(new ArrayList<>(path));return;}for (int i = 0; i < nums.length; i++) {if (visited[i]) continue;// 标记已访问visited[i] = true;path.add(nums[i]);// 继续搜索dfs(nums, path, visited);// 回溯visited[i] = false;path.remove(path.size() - 1);}}}
let res: number[][]function permute(nums: number[]): number[][] {res = new Array();let visited = new Array();dfs(nums, new Array(), visited)return res;};const dfs = function (nums: number[], path: number[], visited: boolean[]) {if (path.length == nums.length) {res.push([...path]);return;}for (let i = 0; i < nums.length; i++) {if (visited[i]) continue;// 标记已访问visited[i] = true;path.push(nums[i]);// 继续搜索dfs(nums, path, visited)// 回溯visited[i] = false;path.pop()}}
24. 字母大小写全排列*
题目：784. 字母大小写全排列
解法1：回溯
这道题属于组合问题，重点在于找对遍历的开始位置
/*** https://leetcode-/problems/letter-case-permutation/* 字母大小写全排列*/class Solution {List<String> res = new ArrayList<>();public List<String> letterCasePermutation(String s) {char[] cs = s.toCharArray();dfs(cs, 0);return res;}/*** @param cs 搜索的字符数组* @param begin 开始搜索的位置*/void dfs(char[] cs, int begin) {res.add(String.valueOf(cs));for (int i = begin; i < cs.length; i++) {// 数字, 则跳过if (isDigit(cs[i])) continue;// 大小写反转cs[i] = changeLetter(cs[i]);// 搜索dfs(cs, i + 1);// 回溯, 大小写反转回来cs[i] = changeLetter(cs[i]);}}/*** 反转大小写* 'A' --> 'a' * 'a' --> 'A'*/public char changeLetter(char c) {return (c >= 'a' && c <= 'z') ? (char) (c - 32) : (char) (c + 32);}/*** 判断是否是数字 (此题中的字符, 非字母即数字)*/public boolean isDigit(char c) {return c >= '0' && c <= '9';}}
function letterCasePermutation(s: string): string[] {let res = new Array()const dfs = function (s: string, idx: number) {res.push(s)for (let i = idx; i < s.length; i++) {// 数字, 跳过此轮循环if (isDigit(s[i])) continue;// 字母, 反转字母大小写s = s.substr(0, i) + changeLetter(s[i]) + s.substr(i + 1)// 搜索dfs(s, i + 1)// 回溯, 将字母大小写反转回来s = s.substr(0, i) + changeLetter(s[i]) + s.substr(i + 1)}}dfs(s, 0)return res};/*** 反转字母大小写*/const changeLetter = function (s: String): String {return s >= 'a' && s <= 'z' ? s.toUpperCase() : s.toLowerCase()}/*** 判断是否是数字*/const isDigit = function (s: String): Boolean {return s >= '0' && s <= '9'}
动态规划
25.爬楼梯
题目：70. 爬楼梯
我的题解：递归、记忆化递归 、动态规划
先来个大家都会的，很基本的算法基础：
解法1：递归（超时）
const climbStairs = function (n: number): number {if (n <= 2) return nreturn climbStairs(n - 1) + climbStairs(n - 2)};
然后来个有些人不知道的，递归的常见优化思路：
解法2：记忆化递归
const climbStairs = function (n: number): number {if (n <= 2) return nlet memory = new Array(n + 1).fill(0)memory[1] = 1memory[2] = 2recur(n, memory)return recur(n, memory)};const recur = function (n: number, mem: number[]): number {if (mem[n] == 0)mem[n] = recur(n - 1, mem) + recur(n - 2, mem)return mem[n]}
接下来是个标准的动态规划的思想
解法3：动态规划
const climbStairs = function (n: number): number {let dp = new Array(n + 1)dp[1] = 1dp[2] = 2for (let i = 3; i <= n; i++)dp[i] = dp[i - 1] + dp[i - 2]return dp[n]}
最后是一个时间和空间都很好的做法，本质上是对 滚动数组 的优化：
解法4：优化空间复杂度
const climbStairs = function (n: number): number {if (n <= 2) return nlet first = 1, second = 2for (let i = 3; i <= n; i++) {second = first + secondfirst = second - first}return second};
26. 打家劫舍
题目：198. 打家劫舍
我的题解
动态规划的思想：
将复杂的原问题拆解成若干个简单的子问题每个子问题仅仅解决 1 次，并保存它们的解最后推导出原问题的解
可以用动态规划解决问题具备的特点：
最优子结构：通过求解子问题的最优解，可以获得原问题的最优解无后效性：未来与过去无关
动态规划经验：
尝试为 dp 数组赋予一个合理的含义尝试找到出 dp[i] 与 dp[i-1] 的关系
这一步的难度往往取决于第一步。
标准的动态规划
const rob = function (nums: number[]): number {// 处理特殊情况if (nums.length == 1) return nums[0]if (nums.length == 2) return Math.max(nums[0], nums[1])// dp[i] 偷窃第 i 号房屋的最高金额let dp = new Array(nums.length)dp[0] = nums[0]dp[1] = Math.max(nums[0], nums[1])for (let i = 2; i < nums.length; i++)// 偷窃第 i 家的最高金额 = // max{ 偷窃第 i -1 家的最大值, 偷窃第 i -2 家的最大值 + nums[i] }dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i])return dp[nums.length - 1]}
27. 三角形的最小路径和
题目：120. 三角形最小路径和
我的题解：动态规范、递归
我发现这种题目，如果明确告诉你使用什么方法，大多是比较好做的
如果做题前不知道属于什么方法，难度就上升了很多。。
解法1：从上往下的动态规划
这种做法比较恶心，需要考虑的边界情况不少，对于我这个 dp 入门选手，首先是写出了这种做法
public int minimumTotal(List<List<Integer>> triangle) {int m = triangle.size(), n = triangle.get(triangle.size() - 1).size();// 特殊情况if (m == 1)return triangle.get(0).get(0);if (m == 2)return triangle.get(0).get(0) + Math.min(triangle.get(1).get(0), triangle.get(1).get(1));// dp[i][j] 矩阵 i, j 位置的三角形的最小路径和int[][] dp = new int[m][n];dp[0][0] = triangle.get(0).get(0);dp[1][0] = dp[0][0] + triangle.get(1).get(0);dp[1][1] = dp[0][0] + triangle.get(1).get(1);for (int i = 2; i < m; i++) {for (int j = 0; j <= i; j++) {int curNum = triangle.get(i).get(j);// 首元素特殊处理if (j == 0) {dp[i][j] = dp[i - 1][j] + curNum;continue;}// 尾元素特殊处理if (j == i) {dp[i][j] = dp[i - 1][j - 1] + curNum;continue;}dp[i][j] = curNum + Math.min(dp[i - 1][j - 1], dp[i - 1][j]);}}int min = Integer.MAX_VALUE;for (int i = 0; i < m; i++)min = Math.min(min, dp[m - 1][i]);return min;}
解法2：从下往上的动态规划，这是评论区大佬们的思路膜拜一下 > 以后考虑思路要开阔，多方面都可以考虑一下，说不定有惊喜
public int minimumTotal(List<List<Integer>> triangle) {// 加1可以不用初始化最后一层int[][] dp = new int[triangle.size() + 1][triangle.size() + 1];for (int i = triangle.size() - 1; i >= 0; i--) {List<Integer> curTr = triangle.get(i);for (int j = 0; j < curTr.size(); j++)dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + curTr.get(j);}return dp[0][0];}
对解法2的优化：使用一维数组
public int minimumTotal1(List<List<Integer>> triangle) {// 只需要记录每一层的最小值即可int[] dp = new int[triangle.size() + 1];for (int i = triangle.size() - 1; i >= 0; i--) {List<Integer> curTr = triangle.get(i);for (int j = 0; j < curTr.size(); j++)// 这里的dp[j] 使用的时候默认是上一层的，赋值之后变成当前层dp[j] = Math.min(dp[j], dp[j + 1]) + curTr.get(j);}return dp[0];}
解法3：递归（超时） > 很多题目，递归不一定是最优解，却也有可能是最优解，但是无论如何，可以多多锻炼自己的递归思维
class Solution {public int minimumTotal(List<List<Integer>> triangle) {return dfs(triangle, 0, 0);}private int dfs(List<List<Integer>> triangle, int i, int j) {if (i == triangle.size()) return 0;return Math.min(dfs(triangle, i + 1, j), dfs(triangle, i + 1, j + 1)) + triangle.get(i).get(j);}}
对解法3的优化：记忆化搜索 > 这个方法必须熟悉，可以强行把递归优化成不错的效率，应该是所有递归都能优化吧？
class Solution1 {Integer[][] memo;public int minimumTotal(List<List<Integer>> triangle) {memo = new Integer[triangle.size()][triangle.size()];return dfs(triangle, 0, 0);}private int dfs(List<List<Integer>> triangle, int i, int j) {if (i == triangle.size()) return 0;if (memo[i][j] != null) return memo[i][j];return memo[i][j] = Math.min(dfs(triangle, i + 1, j), dfs(triangle, i + 1, j + 1)) + triangle.get(i).get(j);}}
位运算
28. 2的幂
题目：231. 2 的幂
我的题解
解法1：先来个比较容易的想到的模拟思路
>Math.pow的时间复杂度其实不低，应该尽量减少这种计算
public boolean isPowerOfTwo(int n) {int i = 0;while (Math.pow(2, i) <= n) {if (Math.pow(2, i) == n)return true;i++;}return false;}
所以可以将上面的代码优化一下（其实没有太多区别）
public boolean isPowerOfTwo0(int n) {int i = 0;double num = 1;while (num <= n) {if ((num = Math.pow(2, i)) == n)return true;i++;}return false;}
解法2：位运算 位运算中有个技巧可以直接记住：n & n-1可以消去最后一位的1 同时，如果 n 为 2 的幂，它的二进制中必然只有一个 1
举例：n = 6 (不为 2 的幂，二进制中有多个 1)n 二进制为：110n - 1 二进制为：101n & n - 1 == 100n = 4 (为 2 的幂, 二进制中只有一个 1)n 二进制为：100n - 1 二进制为：011n & n - 1 == 000
public boolean isPowerOfTwo(int n) {if (n <= 0) return false;return (n & (n - 1)) == 0;}
29. 位1的个数
题目：191. 位1的个数
我的题解
思路1：常规模拟
注意循环结束条件得是n != 0而不能是n > 0注意 Java 中要使用>>>进行无符号右移
public int hammingWeight(int n) {int count = 0;while (n != 0) {if ((n & 1) == 1)count++;n >>>= 1;}return count;}
思路2：使用位运算n & (n - 1)n & (n - 1)可以用来去掉 n 的二进制位最后一个 1
因此很适合用来判断是否是 2 的幂，因为 2 的幂的二进制中只会有 1 个 1
n = 10n 的二进制 1010n - 1 的二进制 1001n & (n - 1) 的二进制 1000public int hammingWeight(int n) {int count = 0;while (n != 0) {n &= (n - 1);count++;}return count;}
思路3：转成二进制字符串进行操作
转成二进制字符串后思路就很多了，但是不建议用，毕竟还是逃避了原问题的考察点
public int hammingWeight(int n) {String binStr = Integer.toBinaryString(n);int count = 0;for (int i = 0; i < binStr.length(); i++)if (binStr.charAt(i) == '1')count++;return count;}
30. 颠倒二进制位
题目：190. 颠倒二进制位
我的题解：API、位运算
调 API 的做法：
public class Solution {public int reverseBits(int n) {return Integer.reverse(n); }}
使用位运算的做法：
public class Solution {public int reverseBits(int n) {int res = 0;int i = 32;while (i-- > 0) {res <<= 1;res += (n & 1);n >>= 1;}return res;}}
31. 只出现一次的数字
我的题解：位运算
^异或常见知识：
交换律：a ^ b ^ c<=>a ^ c ^ b任何数于 0 异或 为 任何数0 ^ n => n相同的数异或为 0n ^ n => 0
function singleNumber(nums: number[]): number {let res = 0for (let num of nums)res ^= numreturn res};
如果觉得《LeetCode《算法入门》刷题笔记（31 题全）》对你有帮助，请点赞、收藏，并留下你的观点哦！
