剑指offer（第二版）刷题记录

03、数组中重复的数字

方法一：使用Set

class Solution {public int findRepeatNumber(int[] nums) {Set<Integer> set = new HashSet<>();int flag = -1;for (int num : nums) {if (!set.add(num)){ //添加成功返回true，否失败返回falseflag = num;break;}}return flag;}}

方法二：原地交换

利用条件：在一个长度为 n 的数组 nums 里的所有数字都在 0 ~ n-1 的范围内。

class Solution {public int findRepeatNumber(int[] nums) {int index = 0;while (index < nums.length){if (nums[index] == index){ //数字已在对应索引位置，无需交换index++;continue;}if (nums[nums[index]] == nums[index]){ //找到一组重复的值return nums[index];}//将此数字交换至对应索引位置int temp = nums[index];nums[index] = nums[temp];nums[temp] = temp;}return -1;}}

04、二维数组中的查找

方法一：直接遍历查找

class Solution {public boolean findNumberIn2DArray(int[][] matrix, int target) {for (int[] row : matrix){for (int val : row){if (val == target){return true;}}}return false;}}

方法二：二分查找

对每一行进行二分查找。

class Solution {public boolean findNumberIn2DArray(int[][] matrix, int target) {for (int[] row : matrix) { int index = search(row, target);//对每一行进行二分查找if (index >= 0){ //找到的话返回对应的下标，没找到返回-1return true;}}return false;}//二分查找public int search(int[] nums, int target){int left = 0, right = nums.length - 1;while (left <= right){int mid = (left + right) / 2;int num = nums[mid];if (num == target){return mid;}else if (num < target){left = mid + 1; //向右查找}else {right = mid - 1; //向左查找}}return -1;}}

方法三：Z 字形查找

class Solution {public boolean findNumberIn2DArray(int[][] matrix, int target) {//判断数组是否合法if (matrix.length == 0 || matrix == null){return false;}int m = matrix.length, n = matrix[0].length;int x = 0, y = n - 1; //矩阵的右上角开始查找while (x < m && y >=0){ //左下角为边界if (matrix[x][y] == target){ //找到return true;}else if (matrix[x][y] < target){ //每一行都是升序的，这一行左边的元素不用找了x++;}else { //每一列都是升序的，这一列下边的元素不用找了y--;}}return false;}}

05、替换空格

方法一：使用可变长字符串StringBuilder

class Solution {public String replaceSpace(String s) {StringBuilder sb = new StringBuilder();int len = s.length();for (int i = 0; i < len; i++) {if (s.charAt(i) == ' '){sb.append("%20");}else {sb.append(s.charAt(i));}}return sb.toString();}}

06、从尾到头打印链表

方法一：使用集合（也可以使用栈）

class Solution {public int[] reversePrint(ListNode head) {if (head == null){return new int[0];}List<Integer> list = new ArrayList<>();ListNode temp = head;while (temp != null){list.add(temp.val);temp = temp.next;}int[] arr = new int[list.size()];int index = arr.length - 1;for (int value : list){arr[index--] = value;}return arr;}}

07、重建二叉树

方法一：分治算法

class Solution {int[] preOrder;//前序遍历的数据Map<Integer, Integer> map = new HashMap<>();//存放中序遍历的节点值和对应的下标public TreeNode buildTree(int[] preorder, int[] inorder) { this.preOrder = preorder;for (int i = 0; i < inorder.length; i++) {map.put(inorder[i], i);}return recur(0, 0, inorder.length - 1);}public TreeNode recur(int root, int left, int right) {if (left > right){ //停止递归return null;}TreeNode node = new TreeNode(preOrder[root]); //建立根节点int rootIndex = map.get(preOrder[root]); //找到根节点在中序遍历数组中的下标node.left = recur(root + 1, left, rootIndex - 1); //向左递归，left～right为左子树的的范围//root + rootIndex - left + 1 ： 跟节点索引+左子树长度+1node.right = recur(root + rootIndex - left + 1, rootIndex + 1, right); //向右递归，left～right为右子树的的范围return node; // 回溯返回根节点}}

09、用两个栈实现队列

方法一：双栈

class CQueue {LinkedList<Integer> inStack;LinkedList<Integer> outStack;public CQueue() {inStack = new LinkedList<Integer>();outStack = new LinkedList<Integer>();}public void appendTail(int value) {inStack.addLast(value);}public int deleteHead() {if (!outStack.isEmpty()){return outStack.removeLast();//outStack中有元素，直接弹出最上面的元素}if (inStack.isEmpty()){//inStack和outStack中都没有元素，返回-1return -1;}else {//inStack中有元素，弹出一次入outStack，再弹出outStack最上面的元素while (!inStack.isEmpty()){outStack.addLast(inStack.removeLast());}return outStack.removeLast();}}}

10- I、斐波那契数列

方法一：动态规划

用三个变量来代替前两项和当前项。

边计算边取模。

class Solution {public int fib(int n) {int a = 0, b = 1, sum = 0;for (int i = 0; i < n; i++) {sum = (a + b) % 1000000007;a = b;b = sum;}return a;}}

10- II. 青蛙跳台阶问题

方法一：动态规划

当最后一步剩下一个台阶时共f(n-1)种情况；当最后一步剩下两个台阶时共f(n-2)种情况。所以一共f(n-1)+f(n-2)种情况。类似于斐波那契数列。

class Solution {public int numWays(int n) {int a = 1, b = 1, sum = 0;for (int i = 0; i < n; i++) {sum = (a + b) % 1000000007;a = b;b = sum;}return a;}}

11、旋转数组的最小数字

方法一：二分查找

class Solution {public int minArray(int[] numbers) {int left = 0, right = numbers.length - 1, mid;while (left <= right){mid = (left + right) / 2;if (numbers[mid] < numbers[right]){ //向左查找right = mid;}else if (numbers[mid] > numbers[right]){ //向右查找left = mid + 1;}else {right--;//缩小范围}}return numbers[left];}}

12、矩阵中的路径

方法一：dfs+剪枝

class Solution {public boolean exist(char[][] board, String word) {char[] words = word.toCharArray();for (int i = 0; i < board.length; i++) {for (int j = 0; j < board[0].length; j++) {if (dfs(board, words, i, j, 0)){return true;}}}return false;}//dfspublic boolean dfs(char[][] board, char[] words, int i, int j, int index){//如果超了边界或者匹配失败if (i < 0 || i > board.length - 1 || j < 0 || j > board[0].length - 1 || board[i][j] != words[index]){return false;}//匹配到了字符串的最后if (index == words.length - 1){return true;}board[i][j] = '\0';//标记，'\0'是为了不和字符重复//向四个方向递归boolean flag = dfs(board, words, i + 1, j, index + 1) || dfs(board, words, i, j + 1, index + 1) || dfs(board, words, i - 1, j, index + 1) || dfs(board, words, i, j - 1, index + 1);board[i][j] = words[index];//剪纸回溯return flag;}}

13、机器人的运动范围

方法一：dfs

class Solution {int m, n, k;boolean[][] visited;//标记位置是否已经访问public int movingCount(int m, int n, int k) {this.m = m;this.n = n;this.k = k;this.visited = new boolean[m][n];return dfs(0, 0, 0, 0);}/** * @param x ：纵坐标的数位和 * @param y ：横坐标的数位和 */public int dfs(int i, int j, int x, int y){//当到达边界，x+y大于k，被标记过时，返回if (i >= m || j >= n || x + y > k || visited[i][j]){return 0;}visited[i][j] = true;//标记已经访问int x2 = (i + 1) % 10 == 0 ? x - 8 : x + 1;//向下走一步后纵坐标的位数和int y2 = (j + 1) % 10 == 0 ? y - 8 : y + 1;//向右走一步后横坐标的位数和return 1 + dfs(i + 1, j, x2, y) + dfs(i, j + 1, x, y2);//向下和向右递归}}

方法二：bfs

class Solution {public int movingCount(int m, int n, int k) {boolean[][] visited = new boolean[m][n];//标记位置是否已经访问，没有赋值默认全是falseint res = 0;Queue<int[]> queue = new LinkedList<>();queue.offer(new int[]{0, 0, 0, 0});while (!queue.isEmpty()){int[] val = queue.poll();int i = val[0], j = val[1], x = val[2], y = val[3];//当到达边界，x+y大于k，被标记过时，返回if (i >= m || j >= n || x + y > k || visited[i][j]){continue;}visited[i][j] = true;res++;int x2 = (i + 1) % 10 == 0 ? x - 8 : x + 1;//向下走一步后纵坐标的位数和int y2 = (j + 1) % 10 == 0 ? y - 8 : y + 1;//向右走一步后横坐标的位数和queue.offer(new int[]{i + 1, j, x2, y});queue.offer(new int[]{i, j + 1, x ,y2});}return res;}}

14- I、剪绳子

方法一：数学推导、贪心

以下数学推导总体分为两步：① 当所有绳段长度相等时，乘积最大。② 最优的绳段长度为 3 。

class Solution {public int cuttingRope(int n) {if (n <= 3){ //当绳子长度小于等于3时，直接剪出一段长度为1的绳子return n - 1;}else {//按每段绳子长度为3来分int x = n / 3;int y = n % 3;if (y == 0){ //剩下长度为0时，为3的x次方return (int)Math.pow(3, x);}else if (y == 1){ //剩下长度为1时，把最后的1+3换成2+2return (int)Math.pow(3, x - 1) * 2 * 2;}else{ //剩下长度为2时，直接在最后*2return (int)Math.pow(3, x) * 2;}}}}

方法二：动态规划

转移方程：dp[i]=max(j×(i−j),j×dp[i−j])

class Solution {public int cuttingRope(int n) {if (n <= 3) { //当绳子长度小于等于3时，直接剪出一段长度为1的绳子return n - 1;}int[] dp = new int[n + 1];dp[2] = 1; //初始化前三项for (int i = 3; i <= n; i++) { //i为绳子的长度int curMax = 0;for (int j = 1; j < i; j++) { //剪去绳子的长度curMax = Math.max(curMax, Math.max(j * (i - j), j * dp[i - j]));}dp[i] = curMax;}return dp[n];}}

14- II、剪绳子II

方法一：循环求余

class Solution {public int cuttingRope(int n) {if (n <= 3){ //当绳子长度小于等于3时，直接剪出一段长度为1的绳子return n - 1;}long res = 1;//最后的乘积if (n % 3 == 1){res = 4;n -= 4;}else if (n % 3 == 2){res = 2;n -= 2;}while (n > 0){res = res * 3 % 1000000007;n -= 3;}return (int)res;}}

15、二进制中 1 的个数

方法一：位运算

class Solution {// you need to treat n as an unsigned valuepublic int hammingWeight(int n) {int count = 0;while (n != 0){count += 1 & n;n >>>= 1; //>>>表示无符号右移}return count;}}

方法二：巧用 n&(n-1)

n-1：二进制数字 n 最右边的 1 变成 0 ，此 1 右边的 0 都变成 1 。

n&(n-1)：二进制数字 n最右边的 1 变成 0 ，其余不变。

class Solution {// you need to treat n as an unsigned valuepublic int hammingWeight(int n) {int count = 0;while (n != 0){n &= n-1;//消去数字n最右边的1count++;//消除一个，总数加一}return count;}}

16、数值的整数次方

方法一：快速幂

class Solution {public double myPow(double x, int n) {if (x == 0){ //直接返回0，防止后面1/x时报错return 0;}long m = n;//防止遇见n=-2147483648时n=-n报错，先存入long类型中double res = 1.0;if (m < 0){ //当n<0的情况m = -m;x = 1 / x;}while (m > 0){if ((m & 1) == 1){res *= x;}x *= x;//更新xm >>= 1;//更新m右移}return res;}}

17、打印从 1 到最大的 n 位数

方法一：普通解法

class Solution {public int[] printNumbers(int n) {int len = (int)Math.pow(10, n) - 1; //数组的长度为10的n次方-1int[] arr = new int[len];for (int i = 0; i < len; i++) {arr[i] = i + 1;}return arr;}}

方法二：dfs+全排列+大数

class Solution {char[] num;//存放数组中每个数的每位的字符int[] ans;//需要返回的数组int count = 0;//下标int n;public int[] printNumbers(int n) {this.n = n;num = new char[n];ans = new int[(int) (Math.pow(10, n) - 1)];dfs(0);return ans;}private void dfs(int n) {if (n == this.n) {String tmp = String.valueOf(num); //char数组转字符串int curNum = Integer.parseInt(tmp);//字符串转数组，可以去除最前面的0if (curNum!=0) { //去掉值为0的数ans[count++] = curNum;}return;}for (char i = '0'; i <= '9'; i++) {num[n] = i;//固定每一位的值dfs(n + 1);//固定下一位的值}}}

18、删除链表的节点

方法一：

class Solution {public ListNode deleteNode(ListNode head, int val) {if (head.val == val){ //如果要删除的是head，直接返回head.nextreturn head.next;}ListNode temp = head;while (temp.next != null){if (temp.next.val == val){temp.next = temp.next.next;}else {temp = temp.next;}}return head;}}

21、调整数组顺序使奇数位于偶数前面

方法一：双指针

class Solution {public int[] exchange(int[] nums) { int left = 0, right = nums.length - 1; int temp = 0; while (left < right){ //left=right时退出循环 while (left < right && nums[left] % 2 == 1){//左边指针找一个偶数 left++; } while (left < right && nums[right] % 2 == 0){//右边指针找一个奇数 right--; } //交换 temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; } return nums;}}

22、链表中倒数第 k 个节点

方法一：顺序查找

先计算链表的长度n，在遍历到第n-k个节点处，返回该节点。

class Solution {public ListNode getKthFromEnd(ListNode head, int k) {int len = listLen(head);ListNode temp = head;for (int i = 0; i < len - k; i++) {temp = temp.next;}return temp;}//计算链表的长度public int listLen(ListNode head){int len = 0;ListNode temp = head;while (temp != null){len++;temp = temp.next;}return len;}}

方法二：快慢指针

快指针比慢指针多k个节点。

class Solution {public ListNode getKthFromEnd(ListNode head, int k) {ListNode fast = head, slow = head;for (int i = 0; i < k; i++) {fast = fast.next;}while (fast != null){fast = fast.next;slow = slow.next;}return slow;}}

24、反转链表

方法一：迭代+双指针

class Solution {public ListNode reverseList(ListNode head) {ListNode pre = null, cur = head;ListNode temp;while (cur != null){temp = cur.next; //暂存后继节点cur.nextcur.next = pre; //修改next引用指向pre = cur; //更新precur = temp; //更新cur}return pre;}}

方法二：递归

class Solution {ListNode head2;//反转后链表的头节点public ListNode reverseList(ListNode head) {dfs(head, null);return head2;}public void dfs(ListNode cur, ListNode pre){if (cur == null){ //终止条件head2 = pre; //链表的最后一个节点为头节点return;}dfs(cur.next, cur); //往后递归cur.next = pre; //反转指向}}

25、合并两个排序的链表

方法一：迭代

class Solution {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {ListNode head = new ListNode();ListNode temp = head;while (l1 != null || l2 != null){if (l1 == null){temp.next = l2;l2 = l2.next;}else if (l2 == null){temp.next = l1;l1 = l1.next;}else if (l1.val <= l2.val){temp.next = l1;l1 = l1.next;}else {temp.next = l2;l2 = l2.next;}temp = temp.next;}return head.next;}}

方法二：递归

class Solution {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {if (l1 == null){return l2;}else if (l2 == null){return l1;}else if (l1.val <= l2.val){l1.next = mergeTwoLists(l1.next, l2);return l1;}else {l2.next = mergeTwoLists(l1, l2.next);return l2;}}}

26、树的子结构

方法一：

class Solution {public boolean isSubStructure(TreeNode root, TreeNode subRoot) {boolean dfs = dfs(root, subRoot);return dfs;}public boolean dfs(TreeNode root, TreeNode subRoot){if (root == null || subRoot == null){return false;}return check(root, subRoot) || dfs(root.left, subRoot) || dfs(root.right, subRoot);}//查看root是否包含subRoot的结构public boolean check(TreeNode root, TreeNode subRoot){if (subRoot == null){ //如果subRoot为空了，说明匹配成功了return true;}if (root == null || root.val != subRoot.val){ //如果root为空，或者值不想等了，说明匹配失败return false;}return check(root.left, subRoot.left) && check(root.right, subRoot.right);//匹配左右节点}}

27、二叉树的镜像

方法一：递归

class Solution {public TreeNode mirrorTree(TreeNode root) {if(root == null) return null;TreeNode tmp = root.left;root.left = mirrorTree(root.right);root.right = mirrorTree(tmp);return root;}}

方法二：栈

class Solution {public TreeNode mirrorTree(TreeNode root) {if (root == null){return null;}Stack<TreeNode> stack = new Stack<TreeNode>();stack.push(root); //跟节点入栈while (!stack.isEmpty()){ //栈空了停止循环TreeNode node = stack.pop();//让该节点的左右字节点入栈if (node.left != null){stack.push(node.left);}if (node.right != null){stack.push(node.right);}//交换左右子节点TreeNode temp = node.left;node.left = node.right;node.right = temp;}return root;}}

28、对称的二叉树

class Solution {public boolean isSymmetric(TreeNode root) {if (root == null){return true;}return check(root.left, root.right);}public boolean check(TreeNode root1, TreeNode root2){if (root1 == null && root2 == null){ //匹配成功return true;}else if (root1 == null || root2 == null || root1.val != root2.val){ //匹配失败return false;}else {return check(root1.left, root2.right) && check(root1.right, root2.left);}}}

29、顺时针打印矩阵

方法一：

class Solution {public int[] spiralOrder(int[][] matrix) {if (matrix == null || matrix.length == 0){return new int[0];}int l = 0, r = matrix[0].length - 1, t = 0, b = matrix.length - 1;//矩阵的左、右、上、下边界int[] arr = new int[(r + 1) * (b + 1)];int index = 0;while (true){for (int i = l; i <= r; i++) { //从左向右打印arr[index++] = matrix[t][i];}if (++t > b){ //边界内缩1；若边界相遇则打印完毕break;}for (int i = t; i <= b; i++) { //从上向下打印arr[index++] = matrix[i][r];}if (--r < l){break;}for (int i = r; i >= l; i--) { //从右向左打印arr[index++] = matrix[b][i];}if (t > --b){break;}for (int i = b; i >= t; i--) { //从下向上打印arr[index++] = matrix[i][l];}if (r < ++l){break;}}return arr;}}

30、包含 min 函数的栈

方法一：使用栈+优先队列

class MinStack {Stack<Integer> stack;Queue<Integer> queue;//优先队列/** initialize your data structure here. */public MinStack() {stack = new Stack<Integer>();queue = new PriorityQueue<Integer>();}public void push(int x) {stack.push(x);queue.add(x);}public void pop() {int val = stack.pop();queue.remove(val);}public int top() {return stack.peek();}public int min() {return queue.peek();}}

方法二：双栈

栈A中存储所有元素。

栈B中存储A中所有非严格降序的元素。

class MinStack {Stack<Integer> A, B;public MinStack() {A = new Stack<Integer>();B = new Stack<Integer>();}public void push(int x) {A.push(x);if(B.empty() || x <= B.peek()){ //B中只压入比A栈顶小或者相等的元素B.push(x);}}public void pop() {int val = A.pop();if(val == B.peek()){ //A中该元素出栈了，B也出栈B.pop();}}public int top() {return A.peek();}public int min() {return B.peek();}}

31、栈的压入、弹出序列

方法一：自己写的，效率较低

class Solution {public boolean validateStackSequences(int[] pushed, int[] popped) {Stack<Integer> stack = new Stack<>();int index1 = 0, index2 = 0;while (index1 < pushed.length){if (pushed[index1] == popped[index2]){ //要入栈的数正好是要弹出的数index1++;index2++;}else if (!stack.isEmpty() && stack.peek() == popped[index2]){ //需要弹出栈顶的元素stack.pop();index2++;}else { //入栈stack.push(pushed[index1]);index1++;}}//把栈中剩下的元素一次弹出比较for (int i = 0; i < stack.size(); i++) {int val = stack.pop();if (val != popped[index2]){return false;}index2++;}return true;}}

方法二：官方答案，感觉效率更慢

class Solution {public boolean validateStackSequences(int[] pushed, int[] popped) {Stack<Integer> stack = new Stack<>();int index = 0;for (int value : pushed){stack.push(value); //入栈while (!stack.isEmpty() && stack.peek() == popped[index]){ //循环判断与出栈stack.pop();index++;}}return stack.isEmpty(); //最后看栈是不是为空}}

32 – I、从上到下打印二叉树

方法一：bfs

class Solution {public int[] levelOrder(TreeNode root) {if (root == null){return new int[0];}Queue<TreeNode> queue = new LinkedList<>();List<Integer> list = new ArrayList<>();queue.offer(root);while (!queue.isEmpty()){TreeNode node = queue.poll();list.add(node.val);if (node.left != null){queue.offer(node.left);}if (node.right != null){queue.offer(node.right);}}int[] arr = new int[list.size()];int index = 0;for (int val : list){arr[index++] = val;}return arr;}}

32 – II、从上到下打印二叉树 II

方法一：bfs

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {if (root == null){return new ArrayList<>();}Queue<TreeNode> queue = new LinkedList<>();List<List<Integer>> list = new ArrayList<>();queue.offer(root);while (!queue.isEmpty()){List<Integer> temp = new ArrayList<>();int len = queue.size();//queue.size()会变化，先赋值给lenfor (int i = 0; i < len; i++) { //此时queue中的所有元素为当前层的元素TreeNode node = queue.poll();temp.add(node.val);if (node.left != null){queue.offer(node.left);}if (node.right != null){queue.offer(node.right);}}list.add(temp);}return list;}}

32 – III、从上到下打印二叉树 III

方法一：bfs+双端队列

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {if (root == null){return new ArrayList<>();}Queue<TreeNode> queue = new LinkedList<>();List<List<Integer>> list = new ArrayList<>();queue.offer(root);while (!queue.isEmpty()){LinkedList<Integer> temp = new LinkedList<>(); //使用LinkedList作为双端队列使用int len = queue.size();for (int i = 0; i < len; i++) {TreeNode node = queue.poll();if (list.size() % 2 == 0){ //如果为偶数层，加入队列的尾部temp.addLast(node.val);}else { //如果为奇数层，加入队列的头部temp.addFirst(node.val);}if (node.left != null){queue.offer(node.left);}if (node.right != null){queue.offer(node.right);}}list.add(temp);}return list;}}

方法二：bfs+倒序

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {if (root == null){return new ArrayList<>();}Queue<TreeNode> queue = new LinkedList<>();List<List<Integer>> list = new ArrayList<>();queue.offer(root);while (!queue.isEmpty()){List<Integer> temp = new ArrayList<>();int len = queue.size();for (int i = 0; i < len; i++) {TreeNode node = queue.poll();temp.add(node.val);if (node.left != null){queue.offer(node.left);}if (node.right != null){queue.offer(node.right);}}if (list.size() % 2 == 1){Collections.reverse(temp); //奇数层进行反转}list.add(temp);}return list;}}

33、二叉搜索树的后序遍历序列

方法一：递归+分治

class Solution {public boolean verifyPostorder(int[] postorder) {return recur(postorder, 0, postorder.length - 1);}public boolean recur(int[] postorder, int i, int j){if (i >= j){ //递归结束return true;}int p = i;while (postorder[p] < postorder[j]){ //找到一个比头节点大的数p++;}int m = p; //把该数赋值给mwhile (postorder[p] > postorder[j]){ //找到一个小于等于头节点的数p++;}//如果p指导了j，说明m到j-1全都比头节点大，符合条件return p == j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1);}}

方法二：单调栈

class Solution {public boolean verifyPostorder(int[] postorder) {Stack<Integer> stack = new Stack<>();int root = Integer.MAX_VALUE;//倒序遍历for(int i = postorder.length - 1; i >= 0; i--) {if(postorder[i] > root) return false;//不满足二叉搜索树//发现递减序列while(!stack.isEmpty() && stack.peek() > postorder[i])root = stack.pop();//更新rootstack.add(postorder[i]);}return true;}}

34、二叉树中和为某一值的路径

方法一：回溯法

class Solution {LinkedList<List<Integer>> lists = new LinkedList<>();//保存最后结果LinkedList<Integer> list = new LinkedList<>();//保存当前的路径public List<List<Integer>> pathSum(TreeNode root, int target) {dfs(root, target);return lists;}public void dfs(TreeNode node, int sum){if (node == null){return;}list.add(node.val);//记录当前节点//判断当前节点是不是叶子节点，并且路径满足条件if (sum == node.val && node.left == null && node.right == null){lists.add(new LinkedList(list));list.removeLast(); //回溯return;}sum -= node.val;//更新sumdfs(node.left, sum); //向左递归dfs(node.right, sum); //向右递归list.removeLast(); //回溯}}

35、复杂链表的复制

方法一：哈希表

class Solution {Map<Node, Node> map = new HashMap<>();//存放链表的节点和复制链表的节点public Node copyRandomList(Node head) { if (head == null){ return null; } if (!map.containsKey(head)){ //如果该节点还没有创造 Node headnew = new Node(head.val); map.put(head, headnew); headnew.next = copyRandomList(head.next); headnew.random = copyRandomList(head.random); } return map.get(head);//该节点已经创造过}}

方法二：拼接+拆分

class Solution {public Node copyRandomList(Node head) { if (head == null){ return null; } Node cur = head; //1.复制各节点，并构建拼接链表 while (cur != null){ Node temp = new Node(cur.val); temp.next = cur.next; cur.next = temp; cur = cur.next.next; } //2.构建各新节点的 random 指向 cur = head; while (cur != null) {if (cur.random != null){cur.next.random = cur.random.next;}cur = cur.next.next; } //3.拆分两链表 Node res = head.next; Node pre = head; cur = head.next; while (cur.next != null){ pre.next = pre.next.next; cur.next = cur.next.next; pre = pre.next; cur = cur.next; } pre.next = null;//单独处理原链表尾节点 return res;//返回新链表头节点}}

36、二叉搜索树与双向链表

方法一：中序遍历

class Solution {Node pre, head;public Node treeToDoublyList(Node root) {if (root == null){return null;}mixDfs(root);//最后处理头和尾节点，形成循环双向链表head.left = pre;pre.right = head;//此时pre已经指向链表尾部return head;}//中序遍历public void mixDfs(Node curNode){if (curNode == null){return;}mixDfs(curNode.left);if (pre != null){ //如果pre不是空pre.right = curNode;}else { //否则，把当前节点为头节点head = curNode;}curNode.left = pre;pre = curNode;//更新premixDfs(curNode.right);}}

37、序列化二叉树

方法一：BFS

class Codec {public String serialize(TreeNode root) {if(root == null) {return "[]";}StringBuilder sb = new StringBuilder("[");Queue<TreeNode> queue = new LinkedList<>();queue.add(root);while(!queue.isEmpty()) {TreeNode node = queue.poll();if(node != null) { //如果节点不为空sb.append(node.val + ",");queue.add(node.left);queue.add(node.right);}else { //如果节点为空sb.append("null,");}}sb.deleteCharAt(sb.length() - 1);//删除最后一个逗号sb.append("]");return sb.toString();}public TreeNode deserialize(String data) {if(data.equals("[]")) {return null;}String[] vals = data.substring(1, data.length() - 1).split(",");//去掉首位的括号，并根据逗号隔开TreeNode root = new TreeNode(Integer.parseInt(vals[0]));//字符串转数字Queue<TreeNode> queue = new LinkedList<>();queue.add(root);int index = 1;while(!queue.isEmpty()) {TreeNode node = queue.poll();if(!vals[index].equals("null")) {node.left = new TreeNode(Integer.parseInt(vals[index]));queue.add(node.left);}index++;if(!vals[index].equals("null")) {node.right = new TreeNode(Integer.parseInt(vals[index]));queue.add(node.right);}index++;}return root;}}

38、字符串的排列

方法一：全排列+回溯+剪枝

class Solution {List<String> list = new LinkedList<>();//存放排列好的字符串char[] chars;//存放字符串的每一个字符public String[] permutation(String s) {chars = s.toCharArray();dfs(0);return list.toArray(new String[list.size()]);//把集合转成数组}public void dfs(int index){if (index == chars.length - 1){ //找到一个排列list.add(String.valueOf(chars));//字符数组转成字符串return;}//防止同一层的元素重复Set<Character> set = new HashSet<>();//让每一个字符都作为这一层的字符for (int i = index; i < chars.length; i++) {if (set.contains(chars[i])){ //存在重复元素，剪枝continue;}set.add(chars[i]);swap(i, index);//将第i个元素固定在index位置dfs(index + 1);//处理下一层swap(i, index);//回溯}}//交换public void swap(int x, int y){char temp = chars[x];chars[x] = chars[y];chars[y] = temp;}}

39、数组中出现次数超过一半的数字

方法一：哈希表

class Solution {public int majorityElement(int[] nums) {int len = nums.length;Map<Integer, Integer> map = new HashMap<Integer, Integer>();for (int i = 0; i < len; i++) {int val = map.getOrDefault(nums[i], 0);//边添加边判断if (val + 1 > len / 2){return nums[i];}else {map.put(nums[i], val + 1);}}return -1;}}

方法二：排序

class Solution {public int majorityElement(int[] nums) {Arrays.sort(nums);return nums[nums.length / 2];//排序后数组中间那个数一定是结果}}

方法三；摩尔投票法

class Solution {public int majorityElement(int[] nums) {int res = 0, votes = 0;for (int num : nums){if (votes == 0){ //票数抵消了，假设当前数为众数res = num;}if (num == res){ //相同票数+1votes += 1;}else { //否则-1votes -= 1;}}return res;}}

40、最小的 k 个数

方法一：排序

class Solution {public int[] getLeastNumbers(int[] arr, int k) {Arrays.sort(arr);return Arrays.copyOf(arr, k);}}

方法二：优先队列

class Solution {public int[] getLeastNumbers(int[] arr, int k) {int[] nums = new int[k];PriorityQueue<Integer> queue = new PriorityQueue<>();for (int i = 0; i < arr.length; i++) {queue.offer(arr[i]);}for (int i = 0; i < k; i++) {nums[i] = queue.poll();}return nums;}}

方法三：快速排序

class Solution {public int[] getLeastNumbers(int[] arr, int k) {quickSort(arr, 0, arr.length - 1);//快速排序return Arrays.copyOf(arr, k);}//快速排序public void quickSort(int[] arr, int l, int r){if (l >= r){ //子数组长度为1时停止递归return;}int i = l, j = r;//哨兵划分（以 arr[l] 作为基准数）while (i < j){while (i < j && arr[j] >= arr[l]){ //右边找一个小于哨兵的数j--;}while (j < j && arr[i] <= arr[l]){ //左边找一个大于哨兵的数i++;}swap(arr, i, j);//交换}swap(arr, i, l);//与哨兵交换quickSort(arr, l, i - 1);quickSort(arr, i + 1, r);}//交换public void swap(int[] arr, int i, int j){int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}

方法四：快速排序+数组划分

若 k < i，则前k小的数组在 i 左边，递归左子数组。

若 k > i，则前k小的数组在 i 右边，递归右子数组。

若 k = i，则前k小的数组已经找到，直接返回。

class Solution {public int[] getLeastNumbers(int[] arr, int k) {if (k >= arr.length){ //特殊情况，直接返回return arr;}return quickSort(arr, 0, arr.length - 1, k);//快速排序}//快速排序public int[] quickSort(int[] arr, int l, int r, int k){int i = l, j = r;//哨兵划分（以 arr[l] 作为基准数）while (i < j){while (i < j && arr[j] >= arr[l]){ //右边找一个小于哨兵的数j--;}while (j < j && arr[i] <= arr[l]){ //左边找一个大于哨兵的数i++;}swap(arr, i, j);//交换}swap(arr, i, l);//与哨兵交换if (i > k){ //向左找return quickSort(arr, l, i - 1, k);}else if (i < k){ //向右找return quickSort(arr, i + 1, r, k);}else { //找到return Arrays.copyOf(arr, k);}}//交换public void swap(int[] arr, int i, int j){int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}

41、数据流中的中位数

方法一：优先队列、大顶堆、小顶堆

class MedianFinder {Queue<Integer> A;Queue<Integer> B;/** initialize your data structure here. */public MedianFinder() {A = new PriorityQueue<>();//小顶堆，从小到大排B = new PriorityQueue<>((x, y) -> (y - x));//大顶堆，从大到小排}public void addNum(int num) {if (A.size() == B.size()){ //如果A和B大小相同，添加进B中，再从B中拿出一个最大的放入A中B.add(num);A.add(B.poll());}else { //否则，放入A中，再从A中拿出一个最小的放入B中A.add(num);B.add(A.poll());}}public double findMedian() {if (A.size() == B.size()){ //结果为A和B顶的元素的平均值return (double) (A.peek() + B.peek()) / 2;}else { //结果为A顶的元素return (double)A.peek();}}}

42、连续子数组的最大和

方法一：动态规划

class Solution {public int maxSubArray(int[] nums) {int res = nums[0];//nums中可能只有一个元素for (int i = 1; i < nums.length; i++) {if (nums[i - 1] > 0){ //如果上一个元素为负的，则不加nums[i] += nums[i - 1];}res = Math.max(res, nums[i]);//最大结果}return res;}}

43、1～n 整数中 1 出现的次数

方法一：

当 cur=0 时，此时1出现的次数为 high * digit ；

当 cur=1 时，此时1出现的次数为 high * digit + low + 1 ；

当 cur 为其他数时，此时1出现的次数为 (high + 1) * digit ；

class Solution {public int countDigitOne(int n) {int count = 0;int high = n / 10, cur = n % 10, low = 0, digit = 1;while (high != 0 || cur != 0){ //如果high和cur都为0时，说明已经越过最高位，因此跳出if (cur == 0){ //当cur为0时count += high * digit;}else if (cur == 1){ //当cur为1时count += high * digit + low + 1;}else { //当cur为其他时count += (high + 1) * digit;}//更新low += cur * digit;cur = high % 10;high /= 10;digit *= 10;}return count;}}

44、数字序列中某一位的数字

方法一：（太难了）

1. 确定所求数位的所在数字的位数。

2. 确定所求数位所在的数字。

3. 确定所求数位在 num 的哪一数位。

class Solution {public int findNthDigit(int n) {int digit = 1;//数位（这个数字有多少位）long start = 1;//数位开始的数字long count = 9;//这个数位有多少数字//1.确定所求数位的所在数字的位数while (n > count) {n -= count;//更新digit += 1;//加一start *= 10;//乘10count = digit * start * 9;//digit * start * 9}//2.确定所求数位所在的数字long num = start + (n - 1) / digit;//3.确定所求数位在 num 的哪一数位return Long.toString(num).charAt((n - 1) % digit) - '0';}}

45、把数组排成最小的数

方法一：内置函数

class Solution {public String minNumber(int[] nums) {int len = nums.length;String[] str = new String[len];for (int i = 0; i < len; i++) {str[i] = String.valueOf(nums[i]);}//重新定义排序规则，把字符串进行排序Arrays.sort(str, (x, y) -> (x + y).compareTo(y + x));StringBuilder sb = new StringBuilder();for (String s : str){sb.append(s);}return sb.toString();}}

方法二：快速排序

class Solution {public String minNumber(int[] nums) {int len = nums.length;String[] str = new String[len];for (int i = 0; i < len; i++) {str[i] = String.valueOf(nums[i]);}//重新定义排序规则，把字符串进行排序quickSort(str, 0, len - 1);StringBuilder sb = new StringBuilder();for (String s : str){sb.append(s);}return sb.toString();}//快速排序public void quickSort(String[] str, int l, int r){if (l >= r){return;}int i = l, j = r;while (i < j){//注意快速排序这里是右边先动while (i < j && (str[j] + str[l]).compareTo(str[l] + str[j]) >= 0){j--;}while (i < j && (str[i] + str[l]).compareTo(str[l] + str[i]) <= 0){i++;}swap(str, i, j);}swap(str, i, l);quickSort(str, l, i - 1);quickSort(str, i + 1, r);}public void swap(String[] str, int i, int j){String temp = str[i];str[i] = str[j];str[j] = temp;}}

46、把数字翻译成字符串

方法一：动态规划

空间优化：使用a和b代替动态规划的数组。

class Solution {public int translateNum(int num) {String str = String.valueOf(num);int a = 1, b = 1;//作为dp[1]和dp[0]for (int i = 2; i <= str.length(); i++) {String temp = str.substring(i - 2, i);int c = 0;//temp.compareTo:首先逐个字符比较ascll码值，一样的话比较字符串长度。if (temp.compareTo("10") >= 0 && temp.compareTo("25") <= 0){ //在[10, 25]范围，dp[i] = dp[i - 1] + dp[i - 2]c = a + b;}else { //否则，dp[i] = dp[i - 1]c = a;}//更新b = a;a = c;}return a;}}

47、 礼物的最大价值

方法一：动态规划

class Solution {public int maxValue(int[][] grid) {int m = grid.length, n = grid[0].length;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (i == 0 && j == 0){//左上角continue;}else if (i == 0 && j != 0){//最上边grid[i][j] += grid[i][j - 1];}else if (i != 0 && j == 0){//最左边grid[i][j] += grid[i - 1][j];}else {//其他情况grid[i][j] += Math.max(grid[i][j - 1], grid[i - 1][j]);}}}return grid[m - 1][n - 1];}}

方法二：动态规划优化

当矩阵特别大时，可先初始化矩阵第一行和第一列，再开始遍历递推。

class Solution {public int maxValue(int[][] grid) {int m = grid.length, n = grid[0].length;// 初始化第一列for (int i = 1; i < m; i++) {grid[i][0] += grid[i - 1][0];}// 初始化第一行for (int j = 1; j < n; j++) {grid[0][j] += grid[0][j - 1];}for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {grid[i][j] += Math.max(grid[i][j - 1], grid[i - 1][j]);}}return grid[m - 1][n - 1];}}

48、最长不含重复字符的子字符串

方法一：动态规划（太难了）

dp[i] 表示以第 i 个字符为结尾的 “最长不重复子字符串” 的长度。

空间优化：用 temp 代替 dp 数组。

class Solution {public int lengthOfLongestSubstring(String s) {Map<Character, Integer> map = new HashMap<>();int res = 0, temp = 0;for(int j = 0; j < s.length(); j++) {int i = map.getOrDefault(s.charAt(j), -1); // 获取索引iif (temp >= j - i){ //该字符在dp[i - 1]的范围内，dp[i] = j - itemp = j - i;}else { //该字符不在dp[i - 1]的范围内，dp[i] = dp[i - 1] + 1temp = temp + 1;}res = Math.max(res, temp); //更新最大值map.put(s.charAt(j), j); //更新哈希表，把最近相同字符的索引放进去}return res;}}

49、丑数

方法一：动态规划

dp[i] = min(a * 2, b * 3, c * 4);

class Solution {public int nthUglyNumber(int n) {int a = 1, b = 1, c = 1;//前面某个丑数的下标int[] dp = new int[n + 1];dp[1] = 1;//1为第一个丑数for (int i = 2; i <= n; i++) {int n1 = dp[a] * 2, n2 = dp[b] * 3, n3 = dp[c] * 5;//当前丑数一定为前面某个丑数乘2或3或5。dp[i] = Math.min(Math.min(n1, n2), n3);//取最小值//取的那个值，那么这个值就不会再用了，下标加一if (dp[i] == n1) a++;if (dp[i] == n2) b++;if (dp[i] == n3) c++;}return dp[n];}}

50、第一个只出现一次的字符

方法一：哈希表

class Solution {public char firstUniqChar(String s) { Map<Character, Integer> map = new HashMap<>();for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);map.put(c, map.getOrDefault(c, 0) + 1);}for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);if (map.get(c) == 1){return c;}}return ' ';}}