＜每日一题每日刷题＞LeetCode题目汇总Ⅲ

admin管理员组

文章数量:823469

＜每日一题 / 每日刷题＞LeetCode题目汇总Ⅲ

＜每日一题 / 每日刷题＞LeetCode题目汇总Ⅰ

＜每日一题 / 每日刷题＞LeetCode题目汇总Ⅱ

三月份了，来一边听拉赫玛尼诺夫一边刷题吧！

多刷题还是很有用的，对比了一下自己现在写的和上学期写的代码，就看到差距了。几个月前，连《两数之和》都不会做，甚至for循环都忘了怎么写。

说真的，这些算法题确实挺有意思的不是吗？希望你我都能享受其中，获得乐趣与成长。

---

文章目录

• 2021-03-14
• • 1.单词搜索
  • 2.全排列 II
  • 3.二进制矩阵中的最短路径
  • 4.二叉树的所有路径
• 2021-03-15
• • 1. 螺旋矩阵（每日一题）
  • 2. 螺旋矩阵 II
  • 3. Beans
• 2021-03-16
• • 1. 查找集群内的「关键连接」
• 2021-03-17
• • 1. 分割等和子集
• 2021-03-18
• • 1. 不同路径
• 2021-03-19
• • 1. 不同路径 II
  • 2. 不同路径Ⅲ
  • 3. 将有序数组转换为二叉搜索树
• 2021-03-20
• • 1.最小路径和
• 2021-03-21
• • 1.矩阵置零（每日一题）
• 2021-03-22
• • 1. 二叉搜索树的第k大节点
• 2021-03-23
• • 1. 不同的二叉搜索树
• 2021-03-24
• • 1. 验证二叉搜索树
• 2021-03-25
• • 1. 删除排序链表中的重复元素
  • 2. 删除排序链表中的重复元素 II（每日一题）
• 2021-03-26
• • 1. 有序链表转换二叉搜索树
• 2021-03-27
• • 1. 删除二叉搜索树中的节点
  • 2. 将二叉搜索树变平衡
  • 3. 二叉搜索树的最近公共祖先
• 2021-03-28
• • 1. 二叉搜索树迭代器（每日一题）
• 2021-03-29
• • 1. 合并二叉树
  • 2. 把二叉搜索树转换成累加树
• 2021-03-30
• • 1. 搜索二维矩阵（每日一题）
• 2021-03-31
• • 1. 二叉搜索树节点最小距离
• 2021-04-01
• • 1. 链表相交
• 2021-04-02
• • 1. 重排链表
• 2021-04-03
• • 1. 链表的中间结点
• 2021-04-04
• • 1. 二进制链表转整数
• 2021-04-05
• • 1. 合并K个有序链表
• 2021-04-06
• • 1. 交换链表中的节点
• 2021-04-08
• • 1. 合并两个链表
• 2020-04-13
• • 1. 分隔链表
• 2020-04-14
• • 1. 链表组件
• 2021-04-15
• • 1. 给单链表加一
• 2021-04-16
• • 1. 回文链表
• 2021-04-18
• • 1. 两数相加 II
• 2021-04-19
• • 1. 链表中的下一个最大节点
  • 2. 从链表节点中删去总和值为零的连续节点
  • 3. 移除重复节点

2021-03-14

1.单词搜索

    private int m, n;public boolean exist(char[][] board, String word) {m = board.length;n = board[0].length;boolean[][] visited = new boolean[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (dfs(board, i, j, visited, 0, word)) {return true;}}}return false;}private boolean dfs(char[][] board, int r, int c, boolean[][] visited, int cur, String word) {if (cur == word.length()) {return true;}if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] != word.charAt(cur) || visited[r][c]) {return false;}visited[r][c] = true;if (dfs(board, r + 1, c, visited, cur + 1, word) || dfs(board, r - 1, c, visited, cur + 1, word) || dfs(board, r, c + 1, visited, cur + 1, word) || dfs(board, r, c - 1, visited, cur + 1, word)) {return true;}visited[r][c] = false;return false;}

2.全排列 II

    public List<List<Integer>> permuteUnique(int[] nums) {Arrays.sort(nums);List<List<Integer>> res = new ArrayList();List<Integer> list = new ArrayList();boolean[] visited = new boolean[nums.length];dfs(nums, res, list, visited, 0);return res;}private void dfs(int[] nums, List<List<Integer>> res, List<Integer> list, boolean[] visited, int cur) {if (cur == nums.length) {res.add(new ArrayList(list));return;}for (int i = 0; i < nums.length; i++) {if (visited[i]|| (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1])) {continue;}list.add(nums[i]);visited[i] = true;dfs(nums, res, list, visited, cur + 1);visited[i] = false;list.remove(cur);}}

3.二进制矩阵中的最短路径

class Solution {int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, -1}, {1, 1}, {-1, 1}, {-1, -1}};int n;public int shortestPathBinaryMatrix(int[][] grid) {n = grid.length;if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1) {return -1;}grid[0][0] = 1;Queue<int[]> queue = new LinkedList<>();queue.offer(new int[]{0, 0});while (!queue.isEmpty()) {int[] point = queue.poll();int pre = grid[point[0]][point[1]];for (int[] dir : dirs) {int x = point[0] + dir[0];int y = point[1] + dir[1];if (x < 0 || x >= n || y < 0 || y >= n || grid[x][y] != 0) {continue;}queue.offer(new int[]{x, y});grid[x][y] = pre + 1;}} return grid[n - 1][n - 1] == 0 ? -1 : grid[n - 1][n - 1];}
}

4.二叉树的所有路径

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {private List<String> ans;public List<String> binaryTreePaths(TreeNode root) {ans = new ArrayList<>();if (root == null) {return ans;}List<Integer> vals = new ArrayList<>();dfs(root, vals);return ans;}// private void dfs(TreeNode root, String str) {//     if (root == null) //这两行可代替下面的两个if。//         return;//     str += root.val;//     if (root.left == null && root.right == null) //         ans.add(str);//     dfs(root.left, str + "->");//     dfs(root.right, str + "->");// }private void dfs(TreeNode root, List<Integer> vals) {if (root == null) {return;}vals.add(root.val);if (root.left == null && root.right == null) {ans.add(buildPath(vals));}dfs(root.left, vals);dfs(root.right, vals);vals.remove(vals.size() - 1);}private String buildPath(List<Integer> vals) {StringBuilder sb = new StringBuilder();for (int i = 0; i < vals.size(); i++) {sb.append(vals.get(i));if (i != vals.size() - 1) {sb.append("->");}}return new String(sb);}
}

2021-03-15

1. 螺旋矩阵（每日一题）

看了一圈评论区和题解，感觉我自己写的代码还是挺优美的嘛，多容易看懂，哈哈。

感觉代码和音乐也挺像，整洁、工整、有秩序的代码块是有美感的。

class Solution {List<Integer> res;int m, n;int dir = 0;boolean[][] vis;public List<Integer> spiralOrder(int[][] matrix) {m = matrix.length;n = matrix[0].length;res = new ArrayList<>();vis = new boolean[m][n];for (int i = 0; i < m / 2 + 1; i++) {spiralOrder(matrix, i, i);}return res;}private void spiralOrder(int[][] matrix, int i, int j) {if (i < 0 || i >= m || j < 0 || j >= n || vis[i][j]) {dir = (dir + 1) % 4;return;}vis[i][j] = true;res.add(matrix[i][j]);if (dir == 0) {spiralOrder(matrix, i, j + 1);} if (dir == 1) {spiralOrder(matrix, i + 1, j);} if (dir == 2) {spiralOrder(matrix, i, j - 1);} if (dir == 3) {spiralOrder(matrix, i - 1, j);}}
}

2. 螺旋矩阵 II

class Solution {int dir = 0;boolean[][] vis;int cnt;int len;public int[][] generateMatrix(int n) {len = n;vis = new boolean[n][n];int[][] matrix = new int[n][n];for (int i = 0; i < n / 2 + 1; i++) {spiralOrder(matrix, i, i);}return matrix;}private void spiralOrder(int[][] matrix, int i, int j) {if (i < 0 || i >= len || j < 0 || j >= len || vis[i][j]) {dir = (dir + 1) % 4;return;}vis[i][j] = true;matrix[i][j] = ++cnt;if (dir == 0) {spiralOrder(matrix, i, j + 1);} if (dir == 1) {spiralOrder(matrix, i + 1, j);} if (dir == 2) {spiralOrder(matrix, i, j - 1);} if (dir == 3) {spiralOrder(matrix, i - 1, j);}}
}

3. Beans

Beans

    private static int beans(int[][] beans) {int m = beans.length;int[] dp = new int[m + 1];for (int i = 0; i < m; ++i) {int[] nums = beans[i];dp[i + 1] = rob(nums);}return rob(dp);}private static int rob(int[] nums) {if (nums.length == 0) {return 0;}int len = nums.length;int[] dp = new int[len + 1];dp[0] = 0;dp[1] = nums[0];for (int i = 2; i <= len; i++) {dp[i] = Math.max(dp[i - 1], nums[i - 1] + dp[i - 2]);}return dp[len];}public static void main(String[] args) {int res = beans(new int[][]{{11, 0, 7, 5, 13, 9},{78, 4, 81, 6, 22, 4},{1, 40, 9, 34, 16, 10},{11, 22, 0, 33, 39, 6}});System.out.println(res);}

2021-03-16

1. 查找集群内的「关键连接」

    List<List<Integer>> res;HashMap<Integer, List<Integer>> map;int[] ids;public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {res = new ArrayList<>();map = new HashMap<>();ids = new int[n];buildMap(map, connections);Arrays.fill(ids, -1);dfs(0, -1, 100);return res;}private int dfs(int cur, int par, int curId) {ids[cur] = curId;for (int neighbor : map.get(cur)) {if (neighbor == par) {continue;} else if (ids[neighbor] == -1) {ids[cur] = Math.min(ids[cur], dfs(neighbor, cur, curId + 1));} else {ids[cur] = Math.min(ids[cur], ids[neighbor]);}}if (ids[cur] == curId && cur != 0) {res.add(Arrays.asList(par, cur));}return ids[cur];}private void buildMap(HashMap<Integer, List<Integer>> map, List<List<Integer>> connections) {for (List<Integer> c : connections) {mapputeIfAbsent(c.get(0), k -> new ArrayList<>()).add(c.get(1));mapputeIfAbsent(c.get(1), k -> new ArrayList<>()).add(c.get(0));}}

2021-03-17

1. 分割等和子集

    public boolean canPartition(int[] nums) {int sum = 0;for (int num : nums) {sum += num;}if (sum % 2 != 0) {return false;}    int target = sum / 2;boolean[][] dp = new boolean[nums.length + 1][target + 1];dp[0][0] = true;for (int i = 1; i <= nums.length; i++) {for (int j = 1; j <= target; j++) {if (j >= nums[i - 1]) {dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];} else {dp[i][j] = dp[i - 1][j];}}}return dp[nums.length][target];}

2021-03-18

1. 不同路径

    public int uniquePaths(int m, int n) {int[][] dp = new int[m][n];init(dp, m, n);for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}return dp[m - 1][n - 1];}private void init(int[][] dp, int m, int n) {for (int i = 0; i < m; i++) {dp[i][0] = 1;}for (int i = 0; i < n; i++) {dp[0][i] = 1;}}

2021-03-19

1. 不同路径 II

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m = obstacleGrid.length;int n = obstacleGrid[0].length;int[][] dp = new int[m][n];init(dp, m, n, obstacleGrid);for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {if (obstacleGrid[i][j] == 1) {continue;}if (obstacleGrid[i - 1][j] == 1 && obstacleGrid[i][j] == 1) {dp[i][j] = 0;} else if (obstacleGrid[i - 1][j] == 1) {dp[i][j] = dp[i][j - 1];} else if (obstacleGrid[i][j - 1] == 1) {dp[i][j] = dp[i - 1][j];} else {dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}}return dp[m - 1][n - 1];}private void init(int[][] dp, int m, int n, int[][] obstacleGrid) {for (int i = 0; i < m; i++) {if (obstacleGrid[i][0] == 1) {break;}dp[i][0] = 1;}for (int j = 0; j < n; j++) {if (obstacleGrid[0][j] == 1) {break;}dp[0][j] = 1;}}

2. 不同路径Ⅲ

    int res;int m, n;boolean[][] vis;public int uniquePathsIII(int[][] grid) {res = 0;m = grid.length;n = grid[0].length;vis = new boolean[m][n];int a = 0, b = 0, dist = 1;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == 1) {a = i;b = j;} else if (grid[i][j] == 0) {dist++;}}}System.out.println(dist);dfs(grid, a, b, dist);return res;}private void dfs(int[][] grid, int x, int y, int dist) {if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == -1 || vis[x][y]) {return;}if (grid[x][y] == 2 && dist == 0) {res++;}vis[x][y] = true;dfs(grid, x + 1, y, dist - 1);dfs(grid, x - 1, y, dist - 1);dfs(grid, x, y - 1, dist - 1);dfs(grid, x, y + 1, dist - 1);vis[x][y] = false;return;}

3. 将有序数组转换为二叉搜索树

很久没做树、链表之类的题目了，做题思路都忘了挺多。

    public TreeNode sortedArrayToBST(int[] nums) {return buildTree(nums, 0, nums.length - 1);}private TreeNode buildTree(int[] nums, int l, int r) {if (l > r) {return null;}int m = l + (r - l) / 2;TreeNode root = new TreeNode(nums[m]);root.left = buildTree(nums, l, m - 1);root.right = buildTree(nums, m + 1, r);return root;}

2021-03-20

1.最小路径和

    int m, n;public int minPathSum(int[][] grid) {m = grid.length;n = grid[0].length;int[][] dp = new int[m + 1][n + 1];for (int i = 0; i <= m; i++) {dp[i][0] = Integer.MAX_VALUE;}for (int j = 0; j <= n; j++) {dp[0][j] = Integer.MAX_VALUE;}for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (i == 1 && j == 1) {dp[i][j] = grid[i - 1][j - 1];continue;}dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];}}return dp[m][n];}

2021-03-21

1.矩阵置零（每日一题）

    public void setZeroes(int[][] matrix) {int m = matrix.length;int n = matrix[0].length;boolean[] x = new boolean[m];boolean[] y = new boolean[n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (matrix[i][j] == 0) {x[i] = true;y[j] = true;}}}for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (x[i] || y[j]) {matrix[i][j] = 0;}}}}

空间复杂度O(m+n)

    public void setZeroes(int[][] matrix) {int m = matrix.length;int n = matrix[0].length;boolean row = false, col = false;for (int i = 0; i < m; i++) {if (matrix[i][0] == 0) {col = true;}}for (int i = 0; i < n; i++) {if (matrix[0][i] == 0) {row = true;}}for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {if (matrix[i][j] == 0) {matrix[i][0] = 0;matrix[0][j] = 0;}}}for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {if (matrix[i][0] == 0 || matrix[0][j] == 0) {matrix[i][j] = 0;}}}if (row) {for (int i = 0; i < n; i++) {matrix[0][i] = 0;}}if (col) {for (int i = 0; i < m; i++) {matrix[i][0] = 0;}}}

O(1)

2021-03-22

1. 二叉搜索树的第k大节点

    int ans;int cnt;public int kthLargest(TreeNode root, int k) {ans = 0;cnt = 0;dfs(root, k);return ans;}private void dfs(TreeNode root, int k) {if (root == null) {return;}dfs(root.right, k);cnt++;if (cnt == k) {ans = root.val;return;}dfs(root.left, k);}

对cnt和k或root.val的大小关系不确定的话，可以在中间的位置打印一下，防止出错。

2021-03-23

1. 不同的二叉搜索树

    public int numTrees(int n) {int[] dp  = new int[n + 1];dp[0] = 1;dp[1] = 1;for (int i = 2; i <= n; i++) {for (int j = 1; j <= i; j++) {dp[i] += dp[j - 1] * dp[i - j];}}return dp[n];}

2021-03-24

1. 验证二叉搜索树

    long pre = Long.MIN_VALUE;boolean flag = true;public boolean isValidBST(TreeNode root) {dfs(root);return flag;}private void dfs(TreeNode root) {if (root == null) {return;}dfs(root.left);if (root.val <= pre) {flag = false;return;}pre = root.val;dfs(root.right);}

2021-03-25

1. 删除排序链表中的重复元素

法1：

    public ListNode deleteDuplicates(ListNode head) {if (head == null || head.next == null) {return head;}ListNode dummy = new ListNode(-1);dummy.next = head;ListNode pre = dummy.next;ListNode cur = pre.next;while (cur != null) {if (cur.val != pre.val) {pre.next = cur;pre = pre.next;} else {pre.next = null;}cur = cur.next;}return dummy.next;}

其实不需要设置虚拟头结点，因为不存在删掉头结点的情况。惯性思维用了dummyhead那套思路，结果在这里出问题了。

    public ListNode deleteDuplicates(ListNode head) {if (head == null || head.next == null) {return head;}ListNode pre = head;ListNode cur = pre.next;while (cur != null) {if (cur.val != pre.val) {pre.next = cur;pre = pre.next;} else {pre.next = null;}cur = cur.next;}return head;}

法2：哈希表

    public ListNode deleteDuplicates(ListNode head) {if (head == null || head.next == null) {return head;}HashSet<Integer> set = new HashSet<>();ListNode cur = head;ListNode dummy = new ListNode(-1);ListNode ptr = dummy;while (cur != null) {if (set.add(cur.val)) {ptr.next = cur;ptr = ptr.next;} else {ptr.next= null;}cur = cur.next;}return dummy.next;}

但这样做没啥好处，时间没减少，空间还增加了。

2. 删除排序链表中的重复元素 II（每日一题）

    public ListNode deleteDuplicates(ListNode head) {if (head == null || head.next == null) {return head;}ListNode dummy = new ListNode(-1);dummy.next = head;ListNode cur = dummy;while (cur.next != null && cur.next.next != null) {if (cur.next.val == cur.next.next.val) {int val = cur.next.val;while (cur.next != null && val == cur.next.val) {cur.next = cur.next.next;}} else {cur = cur.next;}          }return dummy.next;}

2021-03-26

1. 有序链表转换二叉搜索树

    public TreeNode sortedListToBST(ListNode head) {return buildTree(head, null);}private TreeNode buildTree(ListNode l, ListNode r) {if (l == r) {return null;}ListNode mid = getMidNode(l, r);TreeNode root = new TreeNode(mid.val);root.left = buildTree(l, mid);root.right = buildTree(mid.next, r);return root;}private ListNode getMidNode(ListNode head, ListNode tail) {ListNode f = head;ListNode s = head;while (f != tail && f.next != tail) {f = f.next.next;s = s.next;}return s;}

2021-03-27

1. 删除二叉搜索树中的节点

    public TreeNode deleteNode(TreeNode root, int key) {if (root == null) {return null;}if (key < root.val) {root.left = deleteNode(root.left, key);} else if (key > root.val) {root.right = deleteNode(root.right, key);} else {if (root.left == null) {return root.right;} if (root.right == null) {return root.left;}TreeNode minNode = getMin(root.right);root.val = minNode.val;root.right = deleteNode(root.right, minNode.val);}return root;}private TreeNode getMin(TreeNode node) {while (node.left != null) {node = node.left;}return node;}

2. 将二叉搜索树变平衡

    List<Integer> list;public TreeNode balanceBST(TreeNode root) {list = new ArrayList<>();dfs(root);return buildTree(0, list.size() - 1);}private void dfs(TreeNode root) {if (root == null) {return;}dfs(root.left);list.add(root.val);dfs(root.right);}private TreeNode buildTree(int l, int r) {if (l > r) {return null;}int m = l + (r - l) / 2;TreeNode root = new TreeNode(list.get(m));root.left = buildTree(l, m - 1);root.right = buildTree(m + 1, r);return root;}

3. 二叉搜索树的最近公共祖先

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {return lca(root, p, q);   }private TreeNode lca(TreeNode root, TreeNode p, TreeNode q) {if (root.val < p.val && root.val < q.val) {return lca(root.right, p, q);} else if (root.val > p.val && root.val > q.val) {return lca(root.left, p, q);} else {return root;}}

2021-03-28

1. 二叉搜索树迭代器（每日一题）

class BSTIterator {private int idx;private List<Integer> list;public BSTIterator(TreeNode root) {idx = 0;list = new ArrayList<>();inOrder(root);}public int next() {return list.get(idx++);}public boolean hasNext() {return idx < list.size();}private void inOrder(TreeNode root) {if (root == null) {return;}inOrder(root.left);list.add(root.val);inOrder(root.right);}
}/*** Your BSTIterator object will be instantiated and called as such:* BSTIterator obj = new BSTIterator(root);* int param_1 = obj.next();* boolean param_2 = obj.hasNext();*/

2021-03-29

1. 合并二叉树

    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if (root1 == null && root2 == null) {return null;}if (root1 == null) {return root2;}if (root2 == null) {return root1;}root1.left = mergeTrees(root1.left, root2.left);root1.right = mergeTrees(root1.right, root2.right);root1.val = root1.val + root2.val;return root1;}

2. 把二叉搜索树转换成累加树

    int sum;public TreeNode convertBST(TreeNode root) {sum = 0;inOrder(root);return root;}private void inOrder(TreeNode root) {if (root == null) {return;}inOrder(root.right);sum += root.val;root.val = sum;inOrder(root.left);}

2021-03-30

1. 搜索二维矩阵（每日一题）

    int m, n;public boolean searchMatrix(int[][] matrix, int target) {m = matrix.length;n = matrix[0].length;return searchBST(matrix, target, 0, n - 1);}private boolean searchBST(int[][] matrix, int target, int r, int c) {while (r >= 0 && r < m && c >= 0 && c < n) {if (matrix[r][c] > target) {c--;} else if (matrix[r][c] < target) {r++;} else {return true;}}return false;}

2021-03-31

1. 二叉搜索树节点最小距离

    int res;int pre;public int minDiffInBST(TreeNode root) {res = Integer.MAX_VALUE;pre = Integer.MAX_VALUE;dfs(root);return res;}private void dfs(TreeNode root) {if (root == null) {return;}dfs(root.left);if (pre == Integer.MAX_VALUE) {pre = root.val;} else {res = Math.min(res, root.val - pre);pre = root.val;}dfs(root.right);}

2021-04-01

1. 链表相交

法1：

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode ptrA = headA;ListNode ptrB = headB;while (ptrA != ptrB) {if (ptrA != null) {ptrA = ptrA.next;} else {ptrA = headB;}if (ptrB != null) {ptrB = ptrB.next;} else {ptrB = headA;}}return ptrA;}

法2：

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode ptrA = headA;ListNode ptrB = headB;HashSet<ListNode> vis = new HashSet<>();while (ptrA != null) {vis.add(ptrA);ptrA = ptrA.next;}while (ptrB != null) {if (!vis.add(ptrB)) {return ptrB;}ptrB = ptrB.next;}return null;}

2021-04-02

1. 重排链表

    public void reorderList(ListNode head) {List<ListNode> list = new ArrayList<>();ListNode node = head;while (node != null) {list.add(node);node = node.next;}int l = 0, r = list.size() - 1;while (l < r) {list.get(l++).next = list.get(r);if (l == r) {break;}list.get(r--).next = list.get(l);}list.get(l).next = null;}

2021-04-03

1. 链表的中间结点

    public ListNode middleNode(ListNode head) {ListNode node = head;int len = 0;while (node != null) {len++;node = node.next;}node = head;for (int i = 0; i < len / 2; i++) {node = node.next;}return node;}

2021-04-04

1. 二进制链表转整数

法1：库函数

    public int getDecimalValue(ListNode head) {ListNode node = head;StringBuilder sb = new StringBuilder();while (node != null) {sb.append(node.val);node = node.next;}return Integer.parseInt(sb.toString(), 2);}

法2：位运算

    public int getDecimalValue(ListNode head) {ListNode node = head;int res = 0;while (node != null) {res = (res << 1) + node.val;node = node.next;}return res;}

2021-04-05

1. 合并K个有序链表

    public ListNode mergeKLists(ListNode[] lists) {if (lists.length == 0) {return null;}return mergeKLists(lists, 0, lists.length - 1);}private ListNode mergeKLists(ListNode[] lists, int l, int r) {if (l == r) {return lists[l]; }int m = l + (r - l) / 2;return mergeTwoLists(mergeKLists(lists, l, m), mergeKLists(lists, m + 1, r));}private ListNode mergeTwoLists(ListNode l1, ListNode l2) {ListNode node1 = l1, node2 = l2;ListNode merged = new ListNode(-1);ListNode cur = merged;while (node1 != null && node2 != null) {if (node1.val <= node2.val) {cur.next = node1;node1 = node1.next;} else {cur.next = node2;node2 = node2.next;}cur = cur.next;}if (node1 == null) {cur.next = node2;}if (node2 == null) {cur.next = node1;}return merged.next;}

2021-04-06

1. 交换链表中的节点

法1：容器

    public ListNode swapNodes(ListNode head, int k) {List<ListNode> list = new ArrayList<>();ListNode node = head;while (node != null) {list.add(node);node = node.next;}int tmp = list.get(k - 1).val;list.get(k - 1).val = list.get(list.size() - k).val;list.get(list.size() - k).val = tmp;return head;}

法2：快慢指针

    public ListNode swapNodes(ListNode head, int k) {ListNode dummy = new ListNode(-1);dummy.next = head;ListNode slow = dummy;ListNode fast = dummy;for (int i = 0; i < k; i++) {fast = fast.next;}ListNode pre = fast;while (fast != null) {fast = fast.next;slow = slow.next;}int tmp = pre.val;pre.val = slow.val;slow.val = tmp;return head;}

2021-04-08

1. 合并两个链表

    public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {ListNode node = list1;for (int i = 1; i < a; i++) {node = node.next;}ListNode tail = node.next;for (int i = 0; i < b - a + 1; i++) {tail = tail.next;}node.next = list2;while (list2.next != null) {list2 = list2.next;}list2.next = tail;return list1;}

2020-04-13

1. 分隔链表

    int idx;public ListNode[] splitListToParts(ListNode root, int k) {idx = 0;ListNode[] res = new ListNode[k];split(root, k, res);return res;}private void split(ListNode root, int k, ListNode[] res) {if (root == null) {return;}ListNode cur = root;int len = 0;while (cur != null) {len++;cur = cur.next;}int tmp = len % k;int dist = 0;if (tmp == 0) {dist = len / k;} else {dist = len / k + 1;}cur = root;for (int i = 1; i < dist; i++) {cur = cur.next;}ListNode newRoot = cur.next;cur.next = null;res[idx++] = root; split(newRoot, k - 1, res);}

2020-04-14

1. 链表组件

    public int numComponents(ListNode head, int[] G) {Set<Integer> set = new HashSet<>();for (int g : G) {set.add(g);}int res = 0;ListNode cur = head;while (cur != null) {if (set.contains(cur.val) && (cur.next == null || !set.contains(cur.next.val))) {res++;}cur = cur.next;}return res;}

2021-04-15

1. 给单链表加一

这是会员题，我没开会员，便在LeetCode的Playground 调试，挺好用的平台，不用自己在本地IDE上写一大堆准备代码，调试起来也很方便。

    public static void main(String[] args) throws IOException {BufferedReader in = new BufferedReader(new InputStreamReader(System.in));String line;while ((line = in.readLine()) != null) {ListNode node = Wrapper.stringToListNode(line);node = plusOne(node);Wrapper.prettyPrintLinkedList(node);}}public static ListNode plusOne(ListNode head) {ListNode dummy = new ListNode(0);dummy.next = head;plus(dummy, null);return dummy.val == 1 ? dummy : dummy.next;}private static void plus(ListNode head, ListNode tail) {ListNode cur = head;while (cur.next != tail) {cur = cur.next;}cur.val += 1;if (cur.val == 10) {cur.val = 0;tail = cur;plus(head, tail);}}

2021-04-16

1. 回文链表

    public boolean isPalindrome(ListNode head) {if (head == null) {return true;}ListNode fast = head;ListNode slow = head;while (fast.next != null && fast.next.next != null) {fast = fast.next.next;slow = slow.next;}ListNode rightHead = reverseList(slow.next);while (rightHead != null) {if (head.val != rightHead.val) {return false;}head = head.next;rightHead = rightHead.next;}return true;}private ListNode reverseList(ListNode head) {ListNode prev = null;ListNode cur = head;while (cur != null) {ListNode nxt = cur.next;cur.next = prev;prev = cur;cur = nxt;}return prev;}

2021-04-18

1. 两数相加 II

法1：翻转法

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {l1 = reverseList(l1);l2 = reverseList(l2);return reverseList(addTwoReverseNumbers(l1, l2));}private ListNode reverseList(ListNode head) {ListNode prev = null;ListNode cur = head;while (cur != null) {ListNode nxt = cur.next;cur.next = prev;prev = cur;cur = nxt;}return prev;}private ListNode addTwoReverseNumbers(ListNode l1, ListNode l2) {ListNode dummy = new ListNode(-1);ListNode cur = dummy;int carry = 0;while (l1 != null || l2 != null) {int a = l1 == null ? 0 : l1.val;int b = l2 == null ? 0 : l2.val;int sum = a + b + carry;carry = sum / 10;cur.next = new ListNode(sum % 10);cur = cur.next;if (l1 != null) {l1 = l1.next;}if (l2 != null) {l2 = l2.next;}}if (carry == 1) {cur.next = new ListNode(1);}return dummy.next;}

法2：栈

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {Deque<ListNode> stack1 = new LinkedList<>();Deque<ListNode> stack2 = new LinkedList<>();while (l1 != null) {stack1.push(l1);l1 = l1.next;}while (l2 != null) {stack2.push(l2);l2 = l2.next;}ListNode res = null;ListNode cur = res;int carry = 0;        while (!stack1.isEmpty() || !stack2.isEmpty()) {int a = stack1.isEmpty() ? 0 : stack1.pop().val;int b = stack2.isEmpty() ? 0 : stack2.pop().val;int sum = a + b + carry;carry = sum / 10;cur = new ListNode(sum % 10);cur.next = res;res = cur;}if (carry == 1) {cur = new ListNode(1);cur.next = res;res = cur;}return res;}

2021-04-19

1. 链表中的下一个最大节点

    public int[] nextLargerNodes(ListNode head) {List<Integer> list = new ArrayList<>();while(head != null) {list.add(head.val);head = head.next;}int[] res = new int[list.size()];Deque<Integer> stack = new LinkedList<>();for (int i = 0; i < list.size(); i++) {while (!stack.isEmpty() && list.get(stack.peek()) < list.get(i)) {res[stack.peek()] = list.get(i);stack.pop();}stack.push(i);}return res;}public int[] nextLargerNodes1(ListNode head) {ListNode cur = head;int len = 0;while (cur != null) {len++;cur = cur.next;}int[] res = new int[len];for (int i = 0; i < len - 1; i++) {int curVal = head.val;head = head.next;cur = head;for (int j = i + 1; j < len; j++) {if (cur.val > curVal) {res[i] = cur.val;break;}cur = cur.next;}}return res;}

2. 从链表节点中删去总和值为零的连续节点

    public ListNode removeZeroSumSublists(ListNode head) {Map<Integer, ListNode> map = new HashMap<>();int sum = 0;ListNode dummy = new ListNode(0);dummy.next = head;ListNode cur = dummy;while (cur != null) {sum += cur.val;map.put(sum, cur);cur = cur.next;}sum = 0;cur = dummy;while (cur != null) {sum += cur.val;cur.next = map.get(sum).next;cur = cur.next;}return dummy.next;}

连续区间和，利用前缀和的特性把时间复杂度降到O(n)，好像华为机试第二题也可以用这种方法，当时没想起来。

3. 移除重复节点

    public ListNode removeDuplicateNodes(ListNode head) {if (head == null) {return null;}Set<Integer> vis = new HashSet<>();ListNode prev = head;vis.add(head.val);while (prev.next != null) {ListNode cur = prev.next;if (vis.add(cur.val)) {prev = cur;} else {prev.next = cur.next;}}return head;}

本文标签： ＜每日一题每日刷题＞LeetCode题目汇总Ⅲ