1、反转链表 1、题目描述 给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。
2、解题思路 由于递归反转链表的空间复杂度为 O(n)，故本题使用迭代的方式来完成反转链表 在遍历链表时，将当前节点的 next 指针指向前一个节点，由于单链表中的节点无法得知前一个节点，所以我们需要使用一个 prev 变量存储当前节点的前一个结点，同时，由于我们需要将当前节点的 next 指向前一个节点，那么为了防止当前节点后续节点丢失，所以我们需要用一个变量来保存当前节点的下一个节点。 3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 public ListNode reverseList (ListNode head) if (head == null || head.next == null ) return head; ListNode prev = null , cur = head; while (cur != null ) { ListNode next = cur.next; cur.next = prev; prev = cur; cur = next; } return prev; }
2、K 个一组反转链表 1、题目描述 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表，k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
1 2 输入：head = [1 ,2 ,3 ,4 ,5 ], k = 2 输出：[2 ,1 ,4 ,3 ,5 ]
1 2 输入：head = [1 ,2 ,3 ,4 ,5 ], k = 3 输出：[3 ,2 ,1 ,4 ,5 ]
2、解题思路 先反转以 head 为开头的前 k 个元素 然后以第 k + 1 个元素作为 head ，继续递归调用 reverseGroup 函数 将上述结果连接起来 如果剩下的元素不足 k 个，那么就保持不变 3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 public ListNode reverseKGroup (ListNode head, int k) if (head == null || head.next == null ) return head; ListNode begin = head, end = head; for (int i = 0 ;i < k;i++) { if (end == null ) return head; end = end.next; } ListNode newHead = reverseInRange(begin, end); begin.next = reverseKGroup(end, k); return newHead; } private ListNode reverseInRange (ListNode begin, ListNode end) if (begin == end || begin.next == end) return begin; ListNode prev = null , cur = begin; while (cur != end) { ListNode next = cur.next; cur.next = prev; prev = cur; cur = next; } return prev; }
3、两两交换链表中的节点 1、题目描述 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
1 2 输入：head = [1 ,2 ,3 ,4 ] 输出：[2 ,1 ,4 ,3 ]
2、解题思路 在这道题中，由于我们需要将相邻节点两两交换，那么最终得到的链表的头节点将会与题目所给的头节点不同，对于这种头节点会发生改变的问题，我们可以创建一个虚拟头节点，即 ListNode virtual = head.next 创建一个 ListNode 类型的变量 now ，我们记 now 与 now 之前的链表为已经翻转完毕的链表 创建一个 ListNode 类型的变量 left ，它表示 now 的下一个节点，同时创建一个 ListNode 类型的变量 right ，它表示 now 的下下个节点
接下来我们进行节点的交换，让 now.next = right ，然后 让 left.next = right.next ，最后让 right.next = left
这样做完之后，我们重新按照指针编排链表，就可以看到链表已经变为了 x -> 2 -> 1 -> 3 -> 4 ，然后我们更新 now 指针，将 now 移动到 left 的位置，然后重复上面的步骤即可。 最后返回 virtualHead.next 即可。 3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 public ListNode swapPairs (ListNode head) if (head == null || head.next == null ) return head; ListNode virtualHead = new ListNode(Integer.MAX_VALUE); virtualHead.next = head; ListNode now = virtualHead, left = null , right = null ; while (now.next != null && now.next.next != null ) { left = now.next; right = now.next.next; now.next = right; left.next = right.next; right.next = left; now = left; } return virtualHead.next; }
4、合并二叉树 1、题目描述 给你两棵二叉树： root1 和 root2 。
想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
1 2 输入：root1 = [1 ,3 ,2 ,5 ], root2 = [2 ,1 ,3 ,null ,4 ,null ,7 ] 输出：[3 ,4 ,5 ,5 ,4 ,null ,7 ]
1 2 输入：root1 = [1 ], root2 = [1 ,2 ] 输出：[2 ,2 ]
2、解题思路 递归 + 前序遍历来解决这个问题，其实这道题使用什么顺序的递归都没有问题 确定终止条件 当传入的树有一棵为空时，就应该结束递归
如果 root1 为空，那么合并的结果就是 root2 如果 root2 为空，那么合并的结果就是 root1 让 root2 的 val 合并到 root1 的 val 中 最后分别递归左右子树，让 root1 的左子树、右子树与 root2 的左子树、右子树合并 3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 public TreeNode mergeTrees (TreeNode root1, TreeNode root2) if (root1 == null ) return root2; if (root2 == null ) return root1; root1.val += root2.val; root1.left = mergeTrees(root1.left, root2.left); root1.right = mergeTrees(root1.right, root2.right); return root1; }
5、最长回文子串 1、题目描述 给你一个字符串 s，找到 s 中最长的回文子串。
1 2 3 输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。
2、解题思路 明确 dp 数组的含义 我们需要创建一个二维的 boolean 数组，它的长度和宽度均为 s.length() ，其中 dp[i][j] 表示子串 s[i, j] 是否为回文串
初始化 dp 数组 字符串中任意一个字符都可以看为一个回文字符串，即 dp[i][i] = true
状态转移方程 对于 dp[i][j] ，当 s.charAt(i) == s.charAt(j) 时，有 dp[i][j] = dp[i + 1][j - 1] ；
当 s.charAt(i) != s.charAt(j) 时，有 dp[i][j] = false ；
我们需要使用一个变量来保存最长回文子串 3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 public String longestPalindrome (String s) if (s == null || s.length() == 0 ) return "" ; int len = s.length(); if (len < 2 ) return s; boolean [][] dp = new boolean [len][len]; for (int i = 0 ;i < len;i++) { dp[i][i] = true ; } char [] charArray = s.toCharArray(); int maxLength = 1 ; String result = s.substring(0 , 1 ); for (int i = len - 1 ;i >= 0 ;i--) { for (int j = i + 1 ;j < len;j++) { if (charArray[i] == charArray[j]) { if (j == i + 1 ) { dp[i][j] = true ; } else { dp[i][j] = dp[i + 1 ][j - 1 ]; } } if (dp[i][j] && j - i + 1 > maxLength) { maxLength = j - i + 1 ; result = s.substring(i, j + 1 ); } } } return result; }
6、求最大公共前缀 1、题目描述 编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
1 2 输入：strs = ["flower" ,"flow" ,"flight" ] 输出："fl"
1 2 3 输入：strs = ["dog" ,"racecar" ,"car" ] 输出："" 解释：输入不存在公共前缀。
2、解题思路 我们以字符串数组中的第一个字符串为准，使用一个全局变量保存最长公共前缀长度的值，然后循环遍历字符串数组，然后获取第一个字符串与后续字符串的公共前缀长度，然后更新全局变量的值。 3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 public String longestCommonPrefix (String[] strs) if (strs == null || strs.length == 0 ) return "" ; if (strs.length == 1 ) return strs[0 ]; char [] firstCharArray = strs[0 ].toCharArray(); int longestCommonPrefixLength = Integer.MAX_VALUE; for (int i = 1 ;i < strs.length;i++) { char [] tempArray = strs[i].toCharArray(); int index = 0 ; while (index < firstCharArray.length && index < tempArray.length) { if (firstCharArray[index] != tempArray[index]) { break ; } index++; } longestCommonPrefixLength = Math.min(longestCommonPrefixLength, index); if (longestCommonPrefixLength == 0 ) { return "" ; } } return strs[0 ].substring(0 , longestCommonPrefixLength); }
7、链表排序 1、题目描述 给定链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
2、解题思路 按照归并排序的思路进行操作，使用快慢指针来寻找链表的中点
使用一个小顶堆，将链表节点依次加入到小顶堆中，然后再将节点逐个从堆中弹出。
3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 public ListNode sortList (ListNode head) if (head == null || head.next == null ) return head; PriorityQueue<ListNode> minHeap = new PriorityQueue<>((o1, o2) -> o1.val - o2.val); while (head != null ) { ListNode next = head.next; head.next = null ; minHeap.add(head); head = next; } ListNode result = new ListNode(); ListNode cur = result; while (minHeap.size() > 0 ) { cur.next = minHeap.poll(); cur = cur.next; } return result.next; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 public ListNode sortList (ListNode head) if (head == null || head.next == null ) return head; ListNode fast = head, slow = head; while (fast.next != null && fast.next.next != null ) { fast = fast.next.next; slow = slow.next; } ListNode temp = slow.next; slow.next = null ; ListNode left = sortList(head); ListNode right = sortList(temp); ListNode virtualHead = new ListNode(); ListNode cur = virtualHead; while (left != null && right != null ) { if (left.val < right.val) { cur.next = left; left = left.next; } else { cur.next = right; right = right.next; } cur = cur.next; } cur.next = (left == null ) ? right : left; return virtualHead.next; }
8、验证回文字符串 II 1、题目描述 给定一个非空字符串 s，最多 删除一个字符。判断是否能成为回文字符串。
2、解题思路 一个指针从头开始，一个指针从尾巴开始，当两个指针指向的字符不等时，此时我们再给它一次机会
创建一个方法，这个方法用于判断字符串下标范围处于 [left, right] 的那部分子串是否为严格的回文串 当 s.charAt(left) == s.charAt(right) 时，此时让左指针右移动，右指针左移 当 s.charAt(left) != s.charAt(right) 时，此时我们再给它一次机会，判断 s[left + 1,right] 或者 s[left, right - 1] 中是否有一个为回文串，如果有，那么返回 true ，否则返回 false 3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 public boolean validPalindrome (String s) if (s == null || s.length() <= 1 ) return true ; int left = 0 , right = s.length() - 1 ; while (left < right) { if (s.charAt(left) == s.charAt(right)) { left++; right--; } else { return isPalindrome(s, left + 1 , right) || isPalindrome(s, left, right - 1 ); } } return true ; } public boolean isPalindrome (String s, int left, int right) if (s == null || s.length() <= 1 || left >= right) return true ; while (left < right) { if (s.charAt(left) == s.charAt(right)) { left++; right--; } else { return false ; } } return true ; }
9、回文链表 1、题目描述 给定一个链表的头节点 head ，
如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。
1 2 输入: head = [1 ,2 ,3 ,3 ,2 ,1 ] 输出: true
1 2 输入: head = [1 ,2 ] 输出: false
2、解题思路 找到链表中点 反转后半部分链表 判断前半段链表和后半段链表是否相等 3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 public boolean isPalindrome (ListNode head) if (head == null || head.next == null ) return true ; ListNode slow = head, fast = head; while (fast.next != null && fast.next.next != null ) { fast = fast.next.next; slow = slow.next; } ListNode temp = slow.next; slow.next = null ; temp = reverseList(temp); slow.next = temp; fast = head; slow = temp; while (slow != null ) { if (slow.val != fast.val) { return false ; } slow = slow.next; fast = fast.next; } return true ; } private ListNode reverseList (ListNode node) if (node == null || node.next == null ) return node; ListNode prev = null , cur = node; while (cur != null ) { ListNode next = cur.next; cur.next = prev; prev = cur; cur = next; } return prev; }
10、有效的山脉数组 1、题目描述 给定一个整数数组 arr，如果它是有效的山脉数组就返回 true，否则返回 false。
让我们回顾一下，如果 arr 满足下述条件，那么它是一个山脉数组：
arr.length >= 3在 0 < i < arr.length - 1 条件下，存在 i 使得：arr[0] < arr[1] < ... arr[i-1] < arr[i]arr[i] > arr[i+1] > ... > arr[arr.length - 1] 2、解题思路 使用双指针，一个从左往右找最高点，一个从右往左找最高点，然后判断两个指针找到的最高点是不是同一个，如果是，返回 true，否则返回 false 3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 public boolean validMountainArray (int [] arr) if (arr == null || arr.length < 3 ) return false ; int left = 0 , right = arr.length - 1 ; while (left <= arr.length - 2 && arr[left] < arr[left + 1 ]) { left++; } while (right >= 1 && arr[right] < arr[right - 1 ]) { right--; } return left > 0 && right < arr.length - 1 && left == right; }
11、数组中的最长山脉 1、题目描述 把符合下列属性的数组 arr 称为 山脉数组 ：
arr.length >= 3在 0 < i < arr.length - 1 条件下，存在 i 使得：arr[0] < arr[1] < ... arr[i-1] < arr[i]arr[i] > arr[i+1] > ... > arr[arr.length - 1] 给出一个整数数组 arr，返回最长山脉子数组的长度。如果不存在山脉子数组，返回 0 。
示例一 1 2 3 输入：arr = [2 ,1 ,4 ,7 ,3 ,2 ,5 ] 输出：5 解释：最长的山脉子数组是 [1 ,4 ,7 ,3 ,2 ]，长度为 5 。
示例二 1 2 3 输入：arr = [2 ,2 ,2 ] 输出：0 解释：不存在山脉子数组。
2、解题思路 使用动态规划求解这道题，这道题其实与接雨水差不多 我们创建两个数组，即从左到右依次升高的数组，称为 increase ，其中 increase[i] 表示数组元素 arr[i] 左边小于它且连续的元素个数，比如说 [1,2,3,4,3,2,1] 中 increase[3] 的值为 3 ，它表示数组元素 4 左边有三个 递增且连续小于它的数 同理，我们创建一个从左往右依次递减的数组 decrease ，其中 decrease[i] 表示数组元素 arr[i] 右边小于它且连续的元素个数。 遍历数组中的元素，我们遍历的范围为 [1, len - 2] ，因为和接雨水差不多，第一个和最后一个元素不可能作为山峰的顶点存在。 当 increase[i] 与 decrease[i] 均不为 0 时，我们才计算 arr[i] 作为顶点的山脉长度，以 arr[i] 作为顶点的山脉长度 len 为 decrease[i] + increase[i] + 1 ，其中 1 表示 arr[i] 这个元素的固有长度。
当这两个值有一个为空时，直接值为 0 即可。
3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 public int longestMountain (int [] arr) if (arr == null || arr.length < 3 ) return 0 ; int len = arr.length; int [] increase = new int [len]; int [] decrease = new int [len]; for (int i = 1 ;i < len;i++) { if (arr[i - 1 ] < arr[i]) { increase[i] = increase[i - 1 ] + 1 ; } } for (int i = len - 2 ;i >= 0 ;i--) { if (arr[i] > arr[i + 1 ]) { decrease[i] = decrease[i + 1 ] + 1 ; } } int max = 0 ; for (int i = 1 ;i <= len - 2 ;i++) { int curSize = 0 ; if (increase[i] != 0 && decrease[i] != 0 ) { curSize = decrease[i] + increase[i] + 1 ; } max = Math.max(curSize, max); } return max; }
12、买卖股票的最佳时机 III 1、题目描述 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
1 2 3 4 输入：prices = [3 ,3 ,5 ,0 ,0 ,3 ,1 ,4 ] 输出：6 解释：在第 4 天（股票价格 = 0 ）的时候买入，在第 6 天（股票价格 = 3 ）的时候卖出，这笔交易所能获得利润 = 3 -0 = 3 。 随后，在第 7 天（股票价格 = 1 ）的时候买入，在第 8 天 （股票价格 = 4 ）的时候卖出，这笔交易所能获得利润 = 4 -1 = 3 。
1 2 3 4 5 输入：prices = [1 ,2 ,3 ,4 ,5 ] 输出：4 解释：在第 1 天（股票价格 = 1 ）的时候买入，在第 5 天 （股票价格 = 5 ）的时候卖出, 这笔交易所能获得利润 = 5 -1 = 4 。 注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。 因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
2、解题思路 dp[i][j] 中 i 表示第 i 天，j 为 [0 - 4] 五个状态，dp[i][j] 表示第 i 天状态 j 所剩的最大现金。
0 没有操作 第一次买入 第一次卖出 第二次买入 第二次卖出 达到 dp[i][1] 状态，有两个具体操作 操作一：第 i 天第一次买入股票，那么 dp[i][1] = dp[i - 1][0] - prices[i]
操作二：第 i 天没有操作，在第 i - 1 天已经买入了，那么 dp[i][1] = dp[i - 1][1]
达到 dp[i][2] 状态，有两个操作： 操作一：第 i 天卖出股票，此时 dp[i][2] = dp[i - 1][1] + prices[i]
操作二：第 i 天不操作，在第 i - 1 天已经卖出了，那么 dp[i][2] = dp[i - 1][2]
同理有 dp[i][3] = Math.max(dp[i - 1][3], dp[i][2] - prices[i])，dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i] 初始化 dp[0][0] = 0 ，dp[0][1] = -prices[0] ，dp[0][3] = -prices[0]
3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 public int maxProfit (int [] prices) if (prices == null || prices.length == 0 ) return 0 ; int length = prices.length; int [][] dp = new int [length][5 ]; dp[0 ][1 ] = -prices[0 ]; dp[0 ][3 ] = -prices[0 ]; for (int i = 1 ;i < length;i++) { dp[i][0 ] = dp[i - 1 ][0 ]; dp[i][1 ] = Math.max(dp[i - 1 ][1 ], dp[i - 1 ][0 ] - prices[i]); dp[i][2 ] = Math.max(dp[i - 1 ][2 ], dp[i - 1 ][1 ] + prices[i]); dp[i][3 ] = Math.max(dp[i - 1 ][3 ], dp[i - 1 ][2 ] - prices[i]); dp[i][4 ] = Math.max(dp[i - 1 ][4 ], dp[i - 1 ][3 ] + prices[i]); } return dp[length - 1 ][4 ]; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 public int maxProfit (int [] prices) if (prices == null || prices.length == 0 ) return 0 ; int length = prices.length; int [] dp = new int [5 ]; dp[1 ] = -prices[0 ]; dp[3 ] = -prices[0 ]; for (int i = 1 ;i < length;i++) { dp[1 ] = Math.max(dp[1 ], dp[0 ] - prices[i]); dp[2 ] = Math.max(dp[2 ], dp[1 ] + prices[i]); dp[3 ] = Math.max(dp[3 ], dp[2 ] - prices[i]); dp[4 ] = Math.max(dp[4 ], dp[3 ] + prices[i]); } return dp[4 ]; }
13、买卖股票的最佳时机 IV 1、题目描述 给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
1 2 3 输入：k = 2 , prices = [2 ,4 ,1 ] 输出：2 解释：在第 1 天 (股票价格 = 2 ) 的时候买入，在第 2 天 (股票价格 = 4 ) 的时候卖出，这笔交易所能获得利润 = 4 -2 = 2 。
1 2 3 4 输入：k = 2 , prices = [3 ,2 ,6 ,5 ,0 ,3 ] 输出：7 解释：在第 2 天 (股票价格 = 2 ) 的时候买入，在第 3 天 (股票价格 = 6 ) 的时候卖出, 这笔交易所能获得利润 = 6 -2 = 4 。 随后，在第 5 天 (股票价格 = 0 ) 的时候买入，在第 6 天 (股票价格 = 3 ) 的时候卖出, 这笔交易所能获得利润 = 3 -0 = 3 。
2、解题思路 我们可以按照上题的思路来解，初始化一个 prices.length 行 2 * k + 1 列的二维数组 初始化 dp 数组，当列数 j 满足 j % 2 == 1 时， dp[0][j] 初始化为 -prices[0] ，否则初始化为 0 状态转移数组，当列数 j 满足 j % 2 == 1 时，此时证明我们需要买入股票，此时 dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i])；当列数 j % 2 == 0 时，此时证明我们要卖出股票，此时 dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i]) 最后我们返回二维数组中最后一个元素，表示我们进行了 k 次交易后所能获取的最大收益。
3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 public int maxProfit (int k, int [] prices) if (prices == null || prices.length == 0 ) return 0 ; int len = prices.length; int [][] dp = new int [len][2 * k + 1 ]; for (int i = 1 ;i < 2 * k + 1 ;i += 2 ) { dp[0 ][i] = -prices[0 ]; } for (int i = 1 ;i < len;i++) { dp[i][0 ] = dp[i - 1 ][0 ]; for (int j = 1 ;j < 2 * k + 1 ;j++) { if (j % 2 == 1 ) { dp[i][j] = Math.max(dp[i - 1 ][j], dp[i - 1 ][j - 1 ] - prices[i]); } else { dp[i][j] = Math.max(dp[i - 1 ][j], dp[i - 1 ][j - 1 ] + prices[i]); } } } return dp[len - 1 ][2 * k]; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 public int maxProfit (int k, int [] prices) if (prices == null || prices.length == 0 ) return 0 ; int len = prices.length; int [] dp = new int [2 * k + 1 ]; for (int i = 1 ;i < 2 * k + 1 ;i += 2 ) { dp[i] = -prices[0 ]; } for (int i = 1 ;i < len;i++) { for (int j = 1 ;j < 2 * k + 1 ;j++) { if (j % 2 == 1 ) { dp[j] = Math.max(dp[j], dp[j - 1 ] - prices[i]); } else { dp[j] = Math.max(dp[j], dp[j - 1 ] + prices[i]); } } } return dp[2 * k]; }
14、圆圈中最后剩下的数字 1、题目描述 0,1,···,n-1 这 n 个数字排成一个圆圈，从数字 0 开始，每次从这个圆圈里删除第 m 个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。
例如，0、1、2、3、4 这 5 个数字组成一个圆圈，从数字 0 开始每次删除第 3 个数字，则删除的前 4 个数字依次是 2、0、4、1，因此最后剩下的数字是 3。
1 2 输入: n = 10 , m = 17 输出: 2
2、解题思路 构造环形链表解决这道题 使用一个 ArrayList 来模拟约瑟夫问题 创建一个 ArrayList，将 [0, n - 1] 放入到 ArrayList 中
使用公式计算出当前需要剔除出列表中的元素下标 index ，其中 index = (index + m - 1) % size ，其中 size 为当前列表中的元素个数
将列表中下标为 index 的元素剔除，反复执行 2 直到列表只剩下最后一个元素
返回最后一个元素即可
3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 public int lastRemaining (int n, int m) List<Integer> list = new ArrayList<>(); for (int i = 0 ;i < n;i++) { list.add(i); } int index = 0 ; while (list.size() > 1 ) { index = (index + m - 1 ) % list.size(); list.remove(index); } return list.get(0 ); }
15、使用队列实现栈 1、题目描述 请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：void push(int x) 将元素 x 压入栈顶。int pop() 移除并返回栈顶元素。int top() 返回栈顶元素。boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。 注意： 你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。 2、解题思路 这道题与使用两个栈实现队列不一样，当我们将一个队列的数据导入另外一个队列时，数据的顺序没有发生改变，这是因为队列是先进先出的数据结构。
如果使用两个队列来模拟栈，那么第一个栈是用于模拟栈，而第二个栈是用于临时存储元素的
向栈中加入元素
当我们要向栈中加入元素时，我们直接将新元素添加到队列二中，比如说我们要向栈中加入 3 ，然后如果此时队列一不为空，那么我们需要更新 top 指向的值为新加入的值，而后依次从队列一弹出元素，然后加入到队列二中，最后调换队列一和队列二，此时队列一中就模拟了栈的元素顺序。
如果加入元素后队列一为空，那么直接交换队列一和队列二的引用即可。
向栈中弹出元素 我们直接从队列一中弹出队首元素即可，然后我们需要更新一下 top 的值为队列的首部元素。
查看栈顶元素 top() 直接返回 top 值即可
查看队列是否为空 isEmpty() 直接查看当前队列一是否为空即可。
添加元素 如果此时队列为空，那么直接将元素加入到队列中
如果此时队列不为空，那么先将元素 x 从尾部加入到队列中，然后将 x 之前的所有元素依次从队列中弹出，然后按照顺序从尾部加入到队列中
弹出元素：直接弹出队列首部的元素即可 查看栈顶元素：直接返回队列首部元素即可 3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 class MyStack private Queue<Integer> firstQueue; private Queue<Integer> secondQueue; public MyStack () firstQueue = new LinkedList<>(); secondQueue = new LinkedList<>(); } public void push (int x) secondQueue.add(x); while (!firstQueue.isEmpty()) { secondQueue.add(firstQueue.poll()); } Queue<Integer> temp = firstQueue; firstQueue = secondQueue; secondQueue = temp; } public int pop () return firstQueue.poll(); } public int top () return firstQueue.peek(); } public boolean empty () return firstQueue.isEmpty(); } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 class MyStack private Queue<Integer> queue; public MyStack () queue = new LinkedList<>(); } public void push (int x) queue.add(x); if (queue.size() == 1 ) { return ; } int size = queue.size(); while (size > 1 ) { queue.add(queue.poll()); size--; } } public int pop () return queue.poll(); } public int top () return queue.peek(); } public boolean empty () return queue.isEmpty(); } }
16、最长无重复子串 1、题目描述 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度
1 2 3 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc" ，所以其长度为 3 。
1 2 3 输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b" ，所以其长度为 1 。
2、解题思路 当我们遍历到第 i 个字符时，我们设 dp[i] 表示以第 i 个位置为结尾的最长无重复子串的长度 dp[i] 取决于什么？它取决为以 i - 1 个字符为结尾最长无重复子串的长度与 char[i] 的上一次出现的位置，这两个条件我们需要求一个最大值，也就是离 i 更近的情况。我们使用一个哈希表来记录当前字符 char[i] 在字符串中上一次出现的位置
由于 dp[i] 只与 dp[i - 1] 有关，所以我们可以用一个变量来滚动更新即可。 3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 public int lengthOfLongestSubstring (String s) if (s == null || s.length() == 0 ) return 0 ; Map<Character, Integer> map = new HashMap<>(); int pre = -1 , cur = 0 , maxLength = 0 , len = s.length(); char [] array = s.toCharArray(); for (int i = 0 ;i < len;i++) { int index = map.getOrDefault(array[i], -1 ); pre = Math.max(index, pre); cur = i - pre; maxLength = Math.max(maxLength, cur); map.put(array[i], i); } return maxLength; }
17、对称二叉树 1、题目描述 给你一个二叉树的根节点 root ， 检查它是否轴对称。
1 2 输入：root = [1 ,2 ,2 ,3 ,4 ,4 ,3 ] 输出：true
2、解题思路 如果当前传入的 root 为空，那么直接返回 true 如果当前 root 的左右子树均为空，那么返回 true ，如果左右子树不全为空，那么返回 false 然后我们需要分别递归判断左子树的右子树和右子树的左子树是否对称，左子树的左子树和右子树的右子树是否对称 3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 public boolean isSymmetric (TreeNode root) if (root == null || (root.left == null && root.right == null )) return true ; return isSymmetric(root.left, root.right); } private boolean isSymmetric (TreeNode left, TreeNode right) if (left == null && right == null ) return true ; if (left == null && right != null ) return false ; if (left != null && right == null ) return false ; if (left.val != right.val) return false ; return isSymmetric(left.right, right.left) && isSymmetric(left.left, right.right); }
18、树的子结构 1、题目描述 输入两棵二叉树 A 和 B，判断 B 是不是 A 的子结构。(约定空树不是任意一个树的子结构)
B 是 A 的子结构， 即 A 中有出现和 B 相同的结构和节点值。
2、解题思路 如果 B 是 A 的子结构，那么必须满足以下三种情况其中之一
3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 public boolean isSubStructure (TreeNode A, TreeNode B) if (A == null || B == null ) return false ; return isSub(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B); } private boolean isSub (TreeNode A, TreeNode B) if (B == null ) return true ; if (A == null ) return false ; if (A.val != B.val) return false ; return isSub(A.left, B.left) && isSub(A.right, B.right); }
19、回文子串 1、题目描述 给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
1 2 3 输入：s = "aaa" 输出：6 解释：6 个回文子串: "a" , "a" , "a" , "aa" , "aa" , "aaa"
2、解题思路 我们定义一个二维的 dp 数组，其中 dp[i][j] 表示字符串 s[i, j] 是否为回文子串
每一个字符都是一个回文字符串
s.charAt(i) == s.charAt(j) ，如果此时 j - i == 1，那么 dp[i][j] = true ，此时我们就找到了一个回文子串，否则 dp[i][j] = dp[i + 1][j - 1]s.charAt(i) != s.charAt(j)，dp[i][j] = false由于 dp[i][j] 与 dp[i + 1][j - 1] 有关，所以对于 i ，我们需要从后往前遍历，而对于 j 我们需要正向遍历。
使用一个 result 变量统计结果，当 dp[i][j] = true 时，result +=1
3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 public int countSubstrings (String s) if (s == null || s.length() == 0 ) return 0 ; int len = s.length(); boolean [][] dp = new boolean [len][len]; int result = 0 ; for (int i = 0 ;i < len;i++) { dp[i][i] = true ; result++; } for (int i = len - 1 ;i >= 0 ;i--) { for (int j = i + 1 ;j < len;j++) { if (s.charAt(i) == s.charAt(j)) { if (j - i <= 1 ) { result++; dp[i][j] = true ; } else if (dp[i + 1 ][j - 1 ]) { result++; dp[i][j] = true ; } } } } return result; }
20、O(1) 时间插入、删除和获取随机元素 - 允许重复 1、题目描述 RandomizedCollection 是一种包含数字集合(可能是重复的)的数据结构。它应该支持插入和删除特定元素，以及删除随机元素。
实现 RandomizedCollection 类:
RandomizedCollection() 初始化空的 RandomizedCollection 对象。bool insert(int val) 将一个 val 项插入到集合中，即使该项已经存在。如果该项不存在，则返回 true ，否则返回 false 。bool remove(int val) 如果存在，从集合中移除一个 val 项。如果该项存在，则返回 true ，否则返回 false 。注意，如果 val 在集合中出现多次，我们只删除其中一个。int getRandom() 从当前的多个元素集合中返回一个随机元素。每个元素被返回的概率与集合中包含的相同值的数量 线性相关 。您必须实现类的函数，使每个函数的 平均 时间复杂度为 O(1) 。
注意： 生成测试用例时，只有在 RandomizedCollection 中 至少有一项 时，才会调用 getRandom 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 输入 ["RandomizedCollection" , "insert" , "insert" , "insert" , "getRandom" , "remove" , "getRandom" ] [[], [1 ], [1 ], [2 ], [], [1 ], []] 输出 [null , true , false , true , 2 , true , 1 ] 解释 RandomizedCollection collection = new RandomizedCollection(); collection.insert(1 ); collection.insert(1 ); collection.insert(2 ); collection.getRandom(); collection.remove(1 ); collection.getRandom();
2、解题思路 为了使得在 O(1) 时间内随机获取一个元素，我们可以讲数放在一个列表中，这样获取随机元素时，就可以通过随机生成下标，从而随机得到一个元素 但列表的随机删除不是 O(1) 的，但元素在列表中的顺序是无关紧要的，所以在删除元素时，我们可以讲被删除的元素与列表中的最后一个元素交换位置，然后就可以在 O(1) 时间内，从列表中删除元素 所以我们需要维护数值在列表中的下标集合，对于数组 num 来说，它在 nums 中的下标集合为 Set（num） 在删除时，我们找出 num 出现的其中一个下标 i ，并将 nums[i] 与 nums[nums.length - 1] 交换位置，随后讲 i 从 Set（num） 中移除，并将原有的 nums[nums.length - 1] 替换为 i 。 3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 class RandomizedCollection private Map<Integer, Set<Integer>> ids; private List<Integer> nums; public RandomizedCollection () ids = new HashMap<>(); nums = new ArrayList<>(); } public boolean insert (int val) nums.add(val); Set<Integer> indexSet = ids.getOrDefault(val, new HashSet<>()); indexSet.add(nums.size() - 1 ); ids.put(val, indexSet); return indexSet.size() == 1 ; } public boolean remove (int val) if (!ids.containsKey(val)) return false ; Set<Integer> indexSet = ids.get(val); int firstIndex = indexSet.iterator().next(); int lastNum = nums.get(nums.size() - 1 ); nums.set(firstIndex, lastNum); Set<Integer> lastNumIndexSet = ids.get(lastNum); indexSet.remove(firstIndex); lastNumIndexSet.remove(nums.size() - 1 ); if (firstIndex < nums.size() - 1 ) { lastNumIndexSet.add(firstIndex); } if (indexSet.isEmpty()) { ids.remove(val); } nums.remove(nums.size() - 1 ); return true ; } public int getRandom () return nums.get((int )(Math.random() * nums.size())); } }
21、岛屿数量 1、题目描述 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
1 2 3 4 5 6 7 输入：grid = [ ["1" ,"1" ,"1" ,"1" ,"0" ], ["1" ,"1" ,"0" ,"1" ,"0" ], ["1" ,"1" ,"0" ,"0" ,"0" ], ["0" ,"0" ,"0" ,"0" ,"0" ] ] 输出：1
1 2 3 4 5 6 7 输入：grid = [ ["1" ,"1" ,"0" ,"0" ,"0" ], ["1" ,"1" ,"0" ,"0" ,"0" ], ["0" ,"0" ,"1" ,"0" ,"0" ], ["0" ,"0" ,"0" ,"1" ,"1" ] ] 输出：3
2、解题思路
1 2 3 4 5 6 7 8 9 void traverse (TreeNode root) if (root == null ) { return ; } traverse(root.left); traverse(root.right); }
可以看到，二叉树的 DFS 有两个要素，即访问子节点 与判断终止条件
访问子节点：二叉树本身就是一个递归定义的节奏，它的左右子树也是一颗二叉树 判断终止条件：当前节点为空时，递归结束 对于网格的 DFS ，我们可以对照着二叉树的 DFS 写出它的两个要素：
相邻节点：一个网格一般来说有上下左右四个相邻节点，即格子 (r, c) 拥有 (r - 1, c) 、 (r + 1, c) 、 (r, c - 1) 和 (r, c + 1)
终止条件 当当前所处位置处于网格边界时，此时我们需要停止搜索，我们可以写出网格递归的框架代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 private void dfs (char [][] grid, int row, int column) if (!inArea(grid, row, column)) { return ; } if (grid[row][column] != '1' ) { return ; } grid[row][column] = 2 ; dfs(grid, row - 1 , column); dfs(grid, row + 1 , column); dfs(grid, row, column - 1 ); dfs(grid, row, column + 1 ); } private boolean inArea (char [][] grid, int row, int column) return (row > -1 && row < grid.length) && (column > -1 && column < grid[0 ].length); }
在这道题中，我们需要在所有值为 1 的陆地格子上进行遍历，当我们遍历到陆地格子时，将对应的值改为 2 ，这样当我们遇到 2 的时候，就知道这是遍历过的格子了。也就是说，每个格子可能取三个值：
0 —— 海洋格子 1 —— 陆地格子（未遍历过） 2 —— 陆地格子（已遍历过） 在代码中，我们在当前层处理逻辑中加入避免重复判断的语句：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 private void dfs (char [][] grid, int row, int column) if (!inArea(grid, row, column)) { return ; } if (grid[row][column] != '1' ) { return ; } grid[row][column] = 2 ; dfs(grid, row - 1 , column); dfs(grid, row + 1 , column); dfs(grid, row, column - 1 ); dfs(grid, row, column + 1 ); }
对于这道题，我们循环遍历 grid 数组，当我们发现有一个格子的值为 1 时，我们就让岛屿数量 +1，因为每一次 dfs 都会将同一个岛屿的所有陆地都值为 2 ，所以每遍历到一个 1 ，就证明找到了一个新岛屿 3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 class Solution private int result; public int numIslands (char [][] grid) if (grid == null || grid.length == 0 ) return 0 ; result = 0 ; for (int i = 0 ;i < grid.length;i++) { for (int j = 0 ;j < grid[0 ].length;j++) { if (grid[i][j] == '1' ) { dfs(grid, i, j); result++; } } } return result; } private void dfs (char [][] grid, int row, int column) if (!inArea(grid, row, column)) { return ; } if (grid[row][column] != '1' ) { return ; } grid[row][column] = 2 ; dfs(grid, row - 1 , column); dfs(grid, row + 1 , column); dfs(grid, row, column - 1 ); dfs(grid, row, column + 1 ); } private boolean inArea (char [][] grid, int row, int column) return (row > -1 && row < grid.length) && (column > -1 && column < grid[0 ].length); } }
22、缺失的第一个正数 1、题目描述 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
1 2 输入：nums = [3 ,4 ,-1 ,1 ] 输出：2
1 2 输入：nums = [7 ,8 ,9 ,11 ,12 ] 输出：1
2、解题思路 3、解题代码 23、全排列 1、题目描述 1 给定一个 没有重复 数字的序列，返回其所有可能的全排列。
1 2 输入: [1 ,2 ,3 ] 输出: [ [1 ,2 ,3 ], [1 ,3 ,2 ], [2 ,1 ,3 ], [2 ,3 ,1 ], [3 ,1 ,2 ], [3 ,2 ,1 ]]
2、解题思路 使用回溯算法解决这道题，我们使用一个 used 数组来标志 nums 中的某个元素已经被用过 在我们遍历到某个元素时，如果 used[i] 为 true ，那么直接跳过本次循环，在回溯时需要将 used[i] 置为 false 3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 class Solution List<List<Integer>> result = new ArrayList<>(); LinkedList<Integer> path = new LinkedList<>(); boolean [] used; public List<List<Integer>> permute(int [] nums) { if (nums == null || nums.length == 0 ) return result; used = new boolean [nums.length]; backtracking(nums); return result; } private void backtracking (int [] nums) if (nums.length == path.size()) { result.add(new ArrayList<>(path)); return ; } for (int i = 0 ;i < nums.length;i++) { if (used[i]) { continue ; } path.addLast(nums[i]); used[i] = true ; backtracking(nums); path.removeLast(); used[i] = false ; } } }
24、组合总和 1、题目描述 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
1 2 3 4 5 6 输入：candidates = [2 ,3 ,6 ,7 ], target = 7 输出：[[2 ,2 ,3 ],[7 ]] 解释： 2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。7 也是一个候选， 7 = 7 。仅有这两种组合。
2、解题思路 确定递归结束条件：当 path 中的和为 target 时，我们将当前结果 path 放入到最终结果中 每遍历到一个数组中的元素，我们都将其放入到 path 中，案后让 sum += nums[i] ，然后继续往下一层进行递归，然后我们需要撤销，让 sum -= nums[i] ，同时将 nums[i] 从 path 中移除。 3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 class Solution List<List<Integer>> result = new ArrayList<>(); LinkedList<Integer> path = new LinkedList<>(); public List<List<Integer>> combinationSum(int [] candidates, int target) { if (candidates == null || candidates.length == 0 ) return result; Arrays.sort(candidates); backtracking(candidates, 0 , target, 0 ); return result; } private void backtracking (int [] candidates, int startIndex, int target, int sum) if (sum == target) { result.add(new ArrayList<>(path)); return ; } for (int i = startIndex;i < candidates.length;i++) { if (sum + candidates[i] > target) break ; sum += candidates[i]; path.addLast(candidates[i]); backtracking(candidates, i, target, sum); path.removeLast(); sum -= candidates[i]; } } }
25、判断一棵二叉树是否为搜索二叉树和完全二叉树 1、题目描述 给定一棵二叉树，已知其中的节点没有重复值，请判断该二叉树是否为搜索二叉树 和完全二叉树 。
2、解题思路 判断二叉树是否为搜索二叉树，可以使用递归或者判断中序遍历序列来判断 判断一棵树是否为完全二叉树，可以使用层序遍历的方式来解答，在层序遍历中保存一个 pre 指针指向当前遍历节点 cur 的前一个节点，如果 pre 为空且当前遍历节点 cur 不为空，那么直接返回 false 我们不需要判断当前节点的左右节点是否存在，因为我们需要将二叉树中的 null 节点保存 3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 public boolean [] judgeIt (TreeNode root) { if (root == null || (root.left == null && root.right == null )) return new boolean [] {true , true }; boolean [] result = new boolean [2 ]; result[0 ] = isBST(root, null , null ); result[1 ] = isComplete(root); return result; } private boolean isBST (TreeNode root, Integer min, Integer max) if (root == null ) return true ; if (min != null && min >= root.val) return false ; if (max != null && max <= root.val) return false ; return isBST(root.left, min, root.val) && isBST(root.right, root.val, max); } private boolean isComplete (TreeNode root) if (root == null ) return false ; Queue<TreeNode> queue = new LinkedList<>(); TreeNode pre = root; queue.add(root); while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0 ;i < size;i++) { TreeNode cur = queue.poll(); if (pre == null && cur != null ) return false ; if (cur != null ) { queue.add(cur.left); queue.add(cur.right); } pre = cur; } } return true ; }
26、二叉树的直径 1、题目描述 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
1 2 3 4 5 6 7 给定二叉树： 1 / \ 2 3 / \ 4 5 输出：返回 3 , 它的长度是路径 [4 ,2 ,1 ,3 ] 或者 [5 ,2 ,1 ,3 ]。
2、解题思路 以某个点为中心的直径就是这个点左右子树的深度之和，使用一个 result 全局变量保存最大直径 创建一个方法，这个方法用于求解某棵树的深度，然后在方法中，我们要更新 result 的值 3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution int result; public int diameterOfBinaryTree (TreeNode root) result = 1 ; depth(root); return result - 1 ; } private int depth (TreeNode root) if (root == null ) return 0 ; if (root.left == null && root.right == null ) return 1 ; int left = depth(root.left); int right = depth(root.right); result = Math.max(result, left + right + 1 ); return Math.max(left, right) + 1 ; } }
27、最长公共前缀 1、题目描述 编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
1 2 输入：strs = ["flower" ,"flow" ,"flight" ] 输出："fl"
2、解题思路 我们以第一个字符串为基准，然后分别获取其他字符串与第一个字符串的公共前缀 然后使用一个变量来保存所有字符串的最长公共前缀长度，需要与 strs[i] 与 strs[0] 的最长公共前缀长度取最小值 3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 public String longestCommonPrefix (String[] strs) if (strs == null || strs.length == 0 ) return "" ; if (strs.length == 1 ) return strs[0 ]; char [] firstCharArray = strs[0 ].toCharArray(); int maxPrefixLen = Integer.MAX_VALUE; char [] tempCharArray = null ; int index = 0 ; for (int i = 1 ;i < strs.length;i++) { index = 0 ; tempCharArray = strs[i].toCharArray(); while (index < tempCharArray.length && index < firstCharArray.length) { if (firstCharArray[index] != tempCharArray[index]) { break ; } index++; } maxPrefixLen = Math.min(maxPrefixLen, index); if (maxPrefixLen == 0 ) return "" ; } return strs[0 ].substring(0 , maxPrefixLen); }
28、 逆序打印不可变链表 1、题目描述 给您一个不可变的链表，使用下列接口逆序打印每个节点的值：
ImmutableListNode : 描述不可变链表的接口，链表的头节点已给出。您 不能 直接访问 ImmutableListNode ）：
1 2 ImmutableListNode.printValue()：打印当前节点的值。 ImmutableListNode.getNext()：返回下一个节点。
输入只用来内部初始化链表。您不可以通过修改链表解决问题。也就是说，您只能通过上述 API 来操作链表。
1 2 输入：head = [1 ,2 ,3 ,4 ] 输出：[4 ,3 ,2 ,1 ]
2、解题思路 当当前结点存在 next 结点时，直接进行递归，将当前结点的 next 传入 当当前结点不存在 next 结点时，直接打印当前结点即可 3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution public void printLinkedListInReverse (ImmutableListNode head) if (head.getNext()!=null ){ printLinkedListInReverse(head.getNext()); } head.printValue(); } }
29、最接近 target 的值 1、题目描述 给出一个数组，在数组中找到两个数，使得它们的和最接近目标值但不超过目标值，返回它们的和
1 2 3 输入: target = 15 和 array = [1 ,3 ,5 ,11 ,7 ] 输出: 14 解释: 11 +3 =14
1 2 3 输入: target = 16 和 array = [1 ,3 ,5 ,11 ,7 ] 输出: 16 解释: 11 +5 =16
2、解题思路 使用双指针解决这道题，我们先将数组进行排序，然后右指针指向数组的最后一个元素，左指针指向第一个元素 我们使用一个变量 diff 来表示当前指针指向元素之和与 target 的差值，当 nums[left] + nums[right] <= target 时，我们更新 diff 的值，然后让 left++ 。 当 nums[right] > target 时，让 right– ，此时我们不更新 diff 的值 最后返回 target - diff 即可。 3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 public int closestTargetValue (int target, int [] array) if (array == null || array.length == 0 ) return -1 ; Arrays.sort(array); int left = 0 , right = array.length - 1 , diff = Integer.MAX_VALUE; while (left < right) { if (array[left] >= target) { break ; } if (array[left] + array[right] <= target) { diff = Math.min(diff, target - (array[left] + array[right])); left++; } else if (array[left] + array[right] > target) { right--; } } if (diff == Integer.MAX_VALUE) { return -1 ; } return target - diff; }
30、小于 n 的最大数 1、题目描述 给定一个数 n，如 23121，给定一组数 A，{2, 4, 9}，返回用 A 可以组成的小于 n 的最大数，A 不为空，答案 22999，
2、解题思路 使用贪心完成这道题，我们创建一个 flag 标识用于标识当前结果的前 n 位是否小于所给值得前 n 位，从最高位开始计算，flag 初始化为 false 我们使用两层循环来解决这个问题，如果此时 flag 为 true ，那么证明当前结果已经小于所给值，此时我们只需要当前结果剩下的位数中全部拼接上数组中的最大值即可。 比如说所给数为 100 ，数组为 {2,4,9} ，当 flag 为 true 时，我们直接组装两次 9 ，即返回 99
当所给值的某一位在数组中出现时，那么直接用数组中的那一个数 当所给书为 23121 ，所给数组为 {2,4,9} 时，由于所给的第一位在数组中有出现，所以直接用数组中的数
3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 public static String minValue (int [] nums, int value) Arrays.sort(nums); boolean flag = false ; String valueStr = String.valueOf(value); StringBuilder result = new StringBuilder(); for (int i = 0 ;i < valueStr.length();i++) { int current = valueStr.charAt(i) - '0' ; for (int j = 0 ;j < nums.length;j++) { if (flag) { result.append(nums[nums.length - 1 ]); break ; } else if (current == nums[j]) { result.append(nums[j]); break ; } else if (current < nums[j]) { if (j - 1 >= 0 ) { result.append(nums[j - 1 ]); } flag = true ; break ; } } } return result.toString(); }
31、盛最多水的容器 1、题目描述 给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
1 2 3 输入：[1 ,8 ,6 ,2 ,5 ,4 ,8 ,3 ,7 ] 输出：49 解释：图中垂直线代表输入数组 [1 ,8 ,6 ,2 ,5 ,4 ,8 ,3 ,7 ]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49 。
2、解题思路 使用双指针来解决这道题 我们初始化左指针和右指针，其中左指针初始化为 0 ，右指针指向数组最后一个元素，使用一个变量用于存储最大水量 计算当前能存储的水量，计算公式为 water = Math.min(nums[left], nums[right]) * (right - left)，然后判断当前水量是否大于最大水量，如果是，那么更新 判断 nums[left] 和 nums[right] 的关系，如果 nums[left] > nums[right] ，那么让 right 左移，以期找到一个更大的 right ，反之亦然 3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 public int maxArea (int [] height) if (height == null || height.length == 0 ) return 0 ; int left = 0 , right = height.length - 1 , maxWater = Integer.MIN_VALUE, curWater = 0 ; while (left < right) { curWater = Math.min(height[left], height[right]) * (right - left); maxWater = Math.max(curWater, maxWater); if (height[left] < height[right]) { left++; } else { right--; } } return maxWater == Integer.MIN_VALUE ? 0 : maxWater; }
32、删除排序链表中的重复元素 II 1、题目描述 给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
1 2 输入：head = [1 ,2 ,3 ,3 ,4 ,4 ,5 ] 输出：[1 ,2 ,5 ]
2、解题思路 由于链表是有序的，那么我们其实只需要用一次遍历即可解决这个问题 由于链表的头节点也可能是待删除元素，所以我们可以创建一个虚拟头节点 使用一个 cur 结点遍历链表，当发现 cur.next.val == cur.next.next.val 时，这个时候我们需要删除，此时证明 cur.next 和 cur.next.next 都是需要删除的结点，此时我们记录 cur.next.val 的值为 nextVal ，然后循环遍历，删除所有值为 nextVal 的结点 如果 cur.next.val != cur.next.next.val 时，直接让 cur 后移即可。 3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 public ListNode deleteDuplicates (ListNode head) if (head == null || head.next == null ) return head; ListNode virtualHead = new ListNode(Integer.MIN_VALUE, head); ListNode cur = virtualHead; while (cur.next != null && cur.next.next != null ) { if (cur.next.val == cur.next.next.val) { int nextVal = cur.next.val; while (cur.next != null && cur.next.val == nextVal) { cur.next = cur.next.next; } } else { cur = cur.next; } } return virtualHead.next; }
33、长度最小的子数组 1、题目描述 给定一个含有 n 个正整数的数组和一个正整数 target
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
1 2 3 输入：target = 7 , nums = [2 ,3 ,1 ,2 ,4 ,3 ] 输出：2 解释：子数组 [4 ,3 ] 是该条件下的长度最小的子数组。
2、解题思路 使用滑动窗口解决这个问题，我们使用一个 for 循环遍历数组，将 for 循环中的循环变量称为右边界 right，同时我们在数组最左边划定一个左边界 left ，称 [left, right] 为滑动窗口，而 [left, right] 中的和记为 sum 当 sum 小于 target 时，此时我们需要让 right 右移，扩充窗口的大小，从而让数组中的元素和符合题意 当 sum 大于等于 target 时，此时我们就找到了一个解，这个解实际上就是滑动窗口的大小 right - left + 1 ，我们将这个值与全局最优解作比较，选一个小的，然后我们需要保持右边界不动，并尝试缩小 left ，以此达到缩小窗口的目的，可以想一下，比如说当前窗口的元素为 [1, 2, 3] ，而 target 为 5 ，那么如果我们缩小窗口，那么 [2,3] 也是一个答案，且这个答案要比窗口缩小前来得好，所以这一步是一个筛选最优解的过程 3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 public int minSubArrayLen (int target, int [] nums) if (nums == null || nums.length == 0 ) return 0 ; int left = 0 ; int result = Integer.MAX_VALUE; int sum = 0 ; for (int right = 0 ;right < nums.length;right++) { sum += nums[right]; while (sum >= target) { result = Math.min(result, right - left + 1 ); sum -= nums[left]; left++; } } return result == Integer.MAX_VALUE ? 0 : result; }
34、二叉树的右视图 1、题目描述 给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
1 2 输入: [1 ,2 ,3 ,null ,5 ,null ,4 ] 输出: [1 ,3 ,4 ]
2、解题思路 除了使用 BFS 之外，还使用 DFS 解决这道题 我们按照 根节点 -> 右子树 -> 左子树 的顺序访问，可以保证每层都是最先访问最右边的结点，那么我们只需要在进入到树的新一层的时候，收集该层我们遍历到的第一个结点即可。 我们使用一个 depth 全局变量来表示我们当前遍历的深度，当 depth == result.size() 时，我们就可以进行收集。 3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 private List<Integer> result;public List<Integer> rightSideView (TreeNode root) result = new ArrayList<>(); dfs(root, 0 ); return result; } private void dfs (TreeNode root, int depth) if (root == null ) return ; if (depth == result.size()) { result.add(root.val); } depth++; dfs(root.right, depth); dfs(root.left, depth); }
35、简化路径 1、题目描述 给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 **绝对路径 ** （以 '/' 开头），请你将其转化为更加简洁的规范路径。
在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，’//‘）都被视为单个斜杠 ‘/‘ 。 对于此问题，任何其他格式的点（例如，’…’）均被视为文件/目录名称
请注意，返回的 规范路径 必须遵循下述格式：
始终以斜杠 '/' 开头。 两个目录名之间必须只有一个斜杠 '/' 。 最后一个目录名（如果存在）**不能 **以 '/' 结尾。 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。 返回简化后得到的 规范路径 。
示例一 1 2 3 输入：path = "/home/" 输出："/home" 解释：注意，最后一个目录名后面没有斜杠。
示例二 1 2 3 输入：path = "/../" 输出："/" 解释：从根目录向上一级是不可行的，因为根目录是你可以到达的最高级。
2、解题思路 将所给的字符串通过 split 函数进行分割，这里以 / 作为分割符，当我们进行分割后，我们会得到一个字符串列表，这个字符串列表中只存在以下几种元素 空字符串，当出现多个连续的 / 时，就会分割出空字符串 一个点 .：表示当前路径 对于空字符串和一个点的情况，我们实际上可以直接跳过，因为空字符串没有意义，而 . 代表当前目录
两个点 ..：表示上一个路径 只包含英文字母、数字或 _ 的目录名 对于两个点及目录名的情况，我们需要使用一个栈来维护路径中的每一个目录名。
当我们遇到 .. 时，需要将目录切换到上一级，因此只要栈不为空，我们就弹出栈顶的目录。当我们遇到目录名时，就直接将其压入栈中。
这样一来，我们只需要遍历字符串列表并进行上述操作即可，在所有操作完成后，我们将从栈底到栈顶的字符串用 / 链接，再加上最前面的 / 表示根目录，就可以得到简化后的路径。
3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 public String simplifyPath (String path) if (path == null || path.length() == 0 ) return "" ; String[] array = path.split("/" ); Deque<String> stack = new ArrayDeque<>(); for (String item : array) { if (".." .equals(item)) { if (!stack.isEmpty()) { stack.pollLast(); } } else if (item.length() > 0 && !("." .equals(item))) { stack.offerLast(item); } } StringBuilder result = new StringBuilder(); if (stack.isEmpty()) { result.append("/" ); } else { while (!stack.isEmpty()) { result.append("/" ).append(stack.pollFirst()); } } return result.toString(); }
36、全排列 II 1、题目描述 给定一个可包含重复数字的序列 nums ，**按任意顺序** 返回所有不重复的全排列。
1 2 3 4 5 输入：nums = [1 ,1 ,2 ] 输出： [[1 ,1 ,2 ], [1 ,2 ,1 ], [2 ,1 ,1 ]]
1 2 输入：nums = [1 ,2 ,3 ] 输出：[[1 ,2 ,3 ],[1 ,3 ,2 ],[2 ,1 ,3 ],[2 ,3 ,1 ],[3 ,1 ,2 ],[3 ,2 ,1 ]]
2、解题思路 与全排列的思路差不多，但我们要在进行递归时判断，当前 nums[i] 是否与 nums[i - 1] 相等，如果满足 i > 0 && nums[i] == nums[i - 1] && used[i - 1] ，那么直接跳过，因为这个数字在前面已经使用过 在进行全排列之前需要对数组进行排序。 3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 class Solution private List<List<Integer>> result = new ArrayList<>(); private LinkedList<Integer> path = new LinkedList<>(); boolean [] used; public List<List<Integer>> permuteUnique(int [] nums) { if (nums == null || nums.length == 0 ) return result; used = new boolean [nums.length]; Arrays.sort(nums); dfs(nums); return result; } private void dfs (int [] nums) if (nums.length == path.size()) { result.add(new ArrayList<>(path)); return ; } for (int i = 0 ;i < nums.length;i++) { if (i > 0 && nums[i - 1 ] == nums[i] && used[i - 1 ]) continue ; if (!used[i]) { path.addLast(nums[i]); used[i] = true ; dfs(nums); used[i] = false ; path.removeLast(); } } } }
37、 36 进制加法 1、题目描述 36 进制由 0-9，a-z，共 36 个字符表示。
要求按照加法规则计算出任意两个 36 进制正整数的和，如 1b + 2x = 48 （解释：47+105=152）
2、解题思路 这道题类似于大数相加，本质上就是 36 进制的大数相加。 我们从后往前遍历两个字符串，然后进行相加，最后将数组翻转即可 3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 private static int getInt (char ch) if (ch >= '0' && ch <= '9' ) { return ch - '0' ; } else { return ch - 'a' + 10 ; } } private static char getChar (int n) if (n <= 9 ) { return (char ) (n + '0' ); } else { return (char ) (n - 10 + 'a' ); } } public static String add36String (String num1, String num2) int carry = 0 ; int leftPoint = num1.length() - 1 , rightPoint = num2.length() - 1 ; int x = 0 , y = 0 ; StringBuilder result = new StringBuilder(); while (leftPoint >= 0 || rightPoint >= 0 || carry > 0 ) { x = (leftPoint >= 0 ) ? getInt(num1.charAt(leftPoint)) : 0 ; y = (rightPoint >= 0 ) ? getInt(num2.charAt(rightPoint)) : 0 ; int temp = x + y + carry; result.append(getChar(temp % 36 )); carry = temp / 36 ; leftPoint--; rightPoint--; } return result.reverse().toString(); }
38、掷骰子的 N 种方法 1、题目描述 这里有 n 个一样的骰子，每个骰子上都有 k 个面，分别标号为 1 到 k 。
给定三个整数 n , k 和 target ，返回可能的方式(从总共 kn 种方式中)滚动骰子的数量，使正面朝上的数字之和等于 target 。
答案可能很大，你需要对 10^9 + 7 取模 。
1 2 3 4 输入：n = 1 , k = 6 , target = 3 输出：1 解释：你扔一个有6 张脸的骰子。 得到3 的和只有一种方法。
1 2 3 4 输入：n = 2 , k = 6 , target = 7 输出：6 解释：你扔两个骰子，每个骰子有6 个面。 得到7 的和有6 种方法1 +6 2 +5 3 +4 4 +3 5 +2 6 +1 。
2、解题思路 使用动态规划解决这个问题，这个问题是一个背包问题 创建一个二维的 dp 数组，我们设 dp[i][j] 表示，用 i 个骰子掷出总和为 j 的方案数 对于前 i 个骰子而言，可能决策的方案有：第 i 个骰子的结果为 1 ，那么此时有 dp[i][j] = dp[i - 1][j - 1] 第 i 个骰子的结果为 2 ，那么此时有 dp[i][j] = dp[i - 1][j - 2] … 第 i 个骰子的结果为 m ，那么此时有 dp[i][j] = dp[i - 1][j - m] 而 dp[i][j] 为以上所有方案的总和
3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 public int numRollsToTarget (int n, int k, int target) int mod = (int )1e9 +7 ; int [][] dp = new int [n + 1 ][target + 1 ]; dp[0 ][0 ] = 1 ; for (int i = 1 ;i <= n;i++) { for (int j = 0 ;j <= target;j++) { for (int x = 1 ;x <= k;x++) { if (j >= x) { dp[i][j] += dp[i - 1 ][j - x]; dp[i][j] %= mod; } } } } return dp[n][target]; }
39、二叉树中的最大路径和 1、题目描述 路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
1 2 3 输入：root = [1 ,2 ,3 ] 输出：6 解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
1 2 3 输入：root = [-10 ,9 ,20 ,null ,null ,15 ,7 ] 输出：42 解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
2、解题思路 我自己为一个路径 我只和左子树合并成为一条路径 我只和右子树合并成为一条路径 我同时链接左子树和右子树的路径 3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution int pathSum = Integer.MIN_VALUE; public int maxPathSum (TreeNode root) dfs(root); return pathSum; } private int dfs (TreeNode root) if (root == null ) return 0 ; int left = dfs(root.left); int right = dfs(root.right); int res = Math.max(root.val, root.val + Math.max(left, right)); pathSum = Math.max(pathSum, Math.max(res, root.val + left + right)); return res; } }
40、单词拆分 1、题目描述 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意： 不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
1 2 3 输入: s = "leetcode" , wordDict = ["leet" , "code" ] 输出: true 解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
1 2 3 4 输入: s = "applepenapple" , wordDict = ["apple" , "pen" ] 输出: true 解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。 注意，你可以重复使用字典中的单词。
2、解题思路 使用动态规划解决这道题，我们令 dp[i] 表示 s[0, i - 1] 子串是否能被空格拆分为若干个字典中出现的单词。 状态转移方程：dp[i] = dp[j] && check(s[j, i - 1]) ，也就当 dp[j] = true 时，那我们只需要判断 s[j, i - 1] 是否也在 wordDict 中即可。 初始化 dp 数组，我们令 dp[0] = true 3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public boolean wordBreak (String s, List<String> wordDict) Set<String> wordSet = new HashSet<>(wordDict); int len = s.length(); boolean [] dp = new boolean [len + 1 ]; dp[0 ] = true ; for (int i = 1 ;i <= len;i++) { for (int j = 0 ;j < i;j++) { if (dp[j] && wordSet.contains(s.substring(j, i))) { dp[i] = true ; } } } return dp[len]; }
41、从根节点到叶节点的路径数字之和 1、题目描述 给定一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字：例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
计算从根节点到叶节点生成的 所有数字之和 ，叶节点 是指没有子节点的节点。
1 2 3 4 5 6 输入：root = [1 ,2 ,3 ] 输出：25 解释： 从根到叶子节点路径 1 ->2 代表数字 12 从根到叶子节点路径 1 ->3 代表数字 13 因此，数字总和 = 12 + 13 = 25
1 2 3 4 5 6 7 输入：root = [4 ,9 ,0 ,5 ,1 ] 输出：1026 解释： 从根到叶子节点路径 4 ->9 ->5 代表数字 495 从根到叶子节点路径 4 ->9 ->1 代表数字 491 从根到叶子节点路径 4 ->0 代表数字 40 因此，数字总和 = 495 + 491 + 40 = 1026
2、解题思路 使用深度优先算法解决这个问题，如果遇到一个叶子节点，那么将叶子节点对应的数加到数字之和中。 如果当前节点不是叶子节点，那么计算它子节点对应的数字，然后对子节点进行递归
3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 public int sumNumbers (TreeNode root) return process(root, 0 ); } private int process (TreeNode root, int value) if (root == null ) return 0 ; int sum = value * 10 + root.val; if (root.left == null && root.right == null ) { return sum; } else { return process(root.left, sum) + process(root.right, sum); } }
42、二叉树中和为某一值的路径 1、题目描述 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
1 2 输入：root = [5 ,4 ,8 ,11 ,null ,13 ,4 ,7 ,2 ,null ,null ,5 ,1 ], targetSum = 22 输出：[[5 ,4 ,11 ,2 ],[5 ,8 ,4 ,5 ]]
1 2 输入：root = [1 ,2 ,3 ], targetSum = 5 输出：[]
2、解题思路 使用回溯算法解决这道题，每当我们经过一个叶子节点，我们就让 target 的值减去对应 root 节点的值，这样当 root 为叶子节点且 target 的值为 0 时，此时就可以收集答案 配合前序遍历解决这道题 3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 public List<List<Integer>> pathSum(TreeNode root, int target) { List<List<Integer>> result = new ArrayList<>(); LinkedList<Integer> path = new LinkedList<>(); if (root == null ) return result; process(root, target, result, path); return result; } private void process (TreeNode root, int target, List<List<Integer>> result, LinkedList<Integer> path) if (root == null ) { return ; } target -= root.val; path.addLast(root.val); if (target == 0 && root.left == null && root.right == null ) { result.add(new ArrayList<>(path)); } process(root.left, target, result, path); process(root.right, target, result, path); target += root.val; path.removeLast(); }
43、最接近的三数之和 1、题目描述 给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
返回这三个数的和，假定每组输入只存在恰好一个解。
1 2 3 输入：nums = [-1 ,2 ,1 ,-4 ], target = 1 输出：2 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2 ) 。
1 2 输入：nums = [0 ,0 ,0 ], target = 1 输出：0
2、解题思路 这道题与三数之和类似，我们将数组排序后，先确定一个数的值，然后再在 [i + 1, end] 中使用双指针选出两个数 3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 public int threeSumClosest (int [] nums, int target) int result = nums[0 ] + nums[1 ] + nums[2 ]; int left = -1 , right = -1 , sum = 0 ; Arrays.sort(nums); for (int i = 0 ;i < nums.length - 2 ;i++) { left = i + 1 ; right = nums.length - 1 ; while (left < right) { sum = nums[i] + nums[left] + nums[right]; if (Math.abs(target - result) > Math.abs(target - sum)) { result = sum; } else if (sum > target) { right--; } else if (sum < target) { left++; } else { return result; } } } return result; }
44、删除字符串中的所有相邻重复项 1、题目描述 给出由小写字母组成的字符串 S，重复项删除操作 会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
1 2 3 4 输入："abbaca" 输出："ca" 解释： 例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca" ，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca" 。
2、解题思路 使用一个栈来解决这个问题，当遍历到的字符与栈顶字符相同时，直接弹出栈顶字符，否则将该字符入栈 最后自底而上收集栈中元素 3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 public String removeDuplicates (String s) if (s == null || s.length() == 0 ) return "" ; Deque<Character> stack = new ArrayDeque<>(); for (char ch : s.toCharArray()) { if (!stack.isEmpty() && stack.peekLast() == ch) { stack.pollLast(); } else { stack.addLast(ch); } } StringBuilder result = new StringBuilder(); while (!stack.isEmpty()) { result.append(stack.pollFirst()); } return result.toString(); }
45、柠檬水找零 1、题目描述 在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
注意，一开始你手头没有任何零钱。
给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
1 2 3 4 5 6 7 输入：bills = [5 ,5 ,5 ,10 ,20 ] 输出：true 解释： 前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。 第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。 第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。 由于所有客户都得到了正确的找零，所以我们输出 true 。
2、解题思路 我们需要维护三种金额的数量，5， 10 和 20，有以下三种情况
情况一：账单是 5，直接收下。 情况二：账单是 10，消耗一个 5，增加一个 10 情况三：账单是 20，优先消耗一个 10 和一个 5，如果不够，再消耗三个 5 由于 10 元只能给 20 找零，所以 5 元更通用。由于 20 元不可能花出去，所以我们只需要在代码中维护 5 元和 10 元的钱数即可，在一次找零后，如果发现 5 元和 10 元的钱数有一个小于 0 ，那么直接返回 false ，整个数组遍历完后，如果钱数均不小于 0 ，则返回 true
3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 public boolean lemonadeChange (int [] bills) int five = 0 , ten = 0 ; for (int bill : bills) { if (bill == 5 ) { five++; } else if (bill == 10 ) { five--; ten++; } else { if (ten > 0 ) { ten--; five--; } else { five -= 3 ; } } if (ten < 0 || five < 0 ) return false ; } return true ; }
46、最长有效括号 1、题目描述 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
1 2 3 输入：s = "(()" 输出：2 解释：最长有效括号子串是 "()"
1 2 3 输入：s = ")()())" 输出：4 解释：最长有效括号子串是 "()()"
2、解题思路 将 -1 入栈，用于处理边界条件 遍历字符串，如果遇到左括号时，就将左括号对应的索引值入栈 如果遇到右括号时，我们弹出栈顶元素表示匹配了当前右括号如果栈为空，那么说明当前的右括号为没有被匹配的右括号，我们将它的下标放入栈中来更新我们之前提到的最后一个没有被匹配的右括号的下标 如果栈不为空，那么使用当前右括号的下标减去栈顶元素即为以该右括号为结尾的最长有效括号的长度 需要注意的是，如果一开始栈为空，第一个字符为左括号的时候我们会将其放入栈中，这样就不满足提及的「最后一个没有被匹配的右括号的下标」，为了保持统一，我们在一开始的时候往栈中放入一个值为 −1 的元素。
3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 public int longestValidParentheses (String s) if (s == null || s.length() <= 1 ) return 0 ; Deque<Integer> stack = new ArrayDeque<>(); stack.addLast(-1 ); int maxLength = 0 ; for (int i = 0 ;i < s.length();i++) { if (s.charAt(i) == '(' ) { stack.addLast(i); } else { stack.removeLast(); if (stack.isEmpty()) { stack.addLast(i); } else { maxLength = Math.max(i - stack.peekLast(), maxLength); } } } return maxLength; }
47、下一个更大元素 II 1、题目描述 给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。
数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。
1 2 3 4 5 输入: nums = [1 ,2 ,1 ] 输出: [2 ,-1 ,2 ] 解释: 第一个 1 的下一个更大的数是 2 ； 数字 2 找不到下一个更大的数； 第二个 1 的下一个最大的数需要循环搜索，结果也是 2 。
1 2 输入: nums = [1 ,2 ,3 ,4 ,3 ] 输出: [2 ,3 ,4 ,-1 ,4 ]
2、解题思路 使用单调栈和循环数组来解决这个问题，当栈为空或者栈顶元素下标对应的值小于当前遍历到的值时，直接将当前元素的下标入栈，否则循环弹出栈顶小于当前值的下标，计算该下标对应的值 3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public int [] nextGreaterElements(int [] nums) { if (nums == null || nums.length == 0 ) return nums; Deque<Integer> stack = new ArrayDeque<>(); int [] result = new int [nums.length]; Arrays.fill(result, -1 ); int len = nums.length; for (int i = 0 ;i < 2 * len - 1 ;i++) { while (!stack.isEmpty() && nums[stack.peekLast()] < nums[i % len]) { result[stack.pollLast()] = nums[i % len]; } stack.addLast(i % len); } return result; }
48、二叉树最大宽度 1、题目描述 给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。
每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的 null 节点也计入长度）之间的长度。
1 2 3 4 5 6 7 8 9 10 输入: 1 / \ 3 2 / \ \ 5 3 9 输出: 4 解释: 最大值出现在树的第 3 层，宽度为 4 (5 ,3 ,null ,9 )。
1 2 3 4 5 6 7 8 9 10 输入: 1 / 3 / \ 5 3 输出: 2 解释: 最大值出现在树的第 3 层，宽度为 2 (5 ,3 )。
2、解题思路 使用层序遍历来解决这道题，我们使用一个双向队列来保存节点，同时以节点的值来记录节点在二叉树上的位置 那么每一层的宽度就可以这样计算，使用双端队列中最后一个元素的 val 减去第一个元素的 val ，得到的结果 + 1 就是本层的宽度。 如果 cur 的左子树不为空，那么将左子树的值置为 2 * cur.val + 1，然后加入到双端队列中 如果 cur 的右子树不为空，那么将右子树的值置为 2 * cur.val + 2，然后加入到队列中 我们也可以不改变节点 val 的值，可以通过自定义一个类来解决这个问题，然后使用 position 来保存位置即可。 1 2 3 4 class MyTreeNode TreeNode node; int position; }
3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 public int widthOfBinaryTree (TreeNode root) if (root == null ) return 0 ; if (root.left == null && root.right == null ) return 1 ; int max = 1 ; int current = 0 ; Deque<TreeNode> queue = new LinkedList<>(); root.val = 0 ; queue.add(root); while (!queue.isEmpty()) { int size = queue.size(); current = queue.peekLast().val - queue.peekFirst().val + 1 ; max = Math.max(current, max); for (int i = 0 ;i < size;i++) { TreeNode cur = queue.pollFirst(); if (cur.left != null ) { cur.left.val = 2 * cur.val + 1 ; queue.addLast(cur.left); } if (cur.right != null ) { cur.right.val = 2 * cur.val + 2 ; queue.addLast(cur.right); } } } return max; }
49、螺旋矩阵 1、题目描述 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
1 2 输入：matrix = [[1 ,2 ,3 ],[4 ,5 ,6 ],[7 ,8 ,9 ]] 输出：[1 ,2 ,3 ,6 ,9 ,8 ,7 ,4 ,5 ]
1 2 输入：matrix = [[1 ,2 ,3 ,4 ],[5 ,6 ,7 ,8 ],[9 ,10 ,11 ,12 ]] 输出：[1 ,2 ,3 ,4 ,8 ,12 ,11 ,10 ,9 ,5 ,6 ,7 ]
2、解题思路 我们可以将矩阵看为若干层，首先输出最外层的元素，然后输出次外层的元素，直到输出最内层的元素 对于每层，从左上方开始以顺时针遍历所有元素。假设当前层的左上角位于 （top, left），右下角位于（bottom，right），我们按照以下顺序遍历当前层元素 从左到右遍历元素，依次为（top，left）到（top，right） 从上到下遍历元素，依次为（top + 1，right）到（bottom，right） 如果此时 left < right 且 top < bottom ，则从右到左遍历下侧元素，依次为（bottom，right - 1）到（bottom，left - 1）以及从下到上遍历左侧元素，依次为（bottom，left）到（top + 1，left） 在遍历完一层元素后，收缩矩阵范围，令 left 与 top + 1，同时让 right 与 bottom - 1 3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 public List<Integer> spiralOrder (int [][] matrix) List<Integer> result = new ArrayList<>(); if (matrix == null || matrix.length == 0 ) return result; int row = matrix.length, column = matrix[0 ].length; int top = 0 , bottom = row - 1 , left = 0 , right = column - 1 ; while (left <= right && top <= bottom) { for (int i = left;i <= right;i++) { result.add(matrix[top][i]); } for (int i = top + 1 ;i <= bottom;i++) { result.add(matrix[i][right]); } if (left < right && top < bottom) { for (int i = right - 1 ;i > left;i--) { result.add(matrix[bottom][i]); } for (int i = bottom;i > top;i--) { result.add(matrix[i][left]); } } left++; top++; right--; bottom--; } return result; }
50、搜索旋转排序数组 1、题目描述 整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
1 2 输入：nums = [4 ,5 ,6 ,7 ,0 ,1 ,2 ], target = 0 输出：4
1 2 输入：nums = [4 ,5 ,6 ,7 ,0 ,1 ,2 ], target = 3 输出：-1
2、解题思路 使用二分查找解决这个问题，在循环中，我们计算判断 nums[mid] 与 target 值的关系 如果 nums[mid] == target ，那么直接返回 mid 如果 nums[0] <= nums[mid] ，此时代表 [0, mid] 不包含旋转，是一个完整的有序数组，当 nums[0] <= target <= nums[mid] 时，我们就可以让 right = mid - 1，否则我们需要在 [mid + 1, right] 中查找，也就是让 left = mid + 1 如果 nums[mid] <= nums[right] ，那么说明 [mid, right] 是有序数组，当 target 的值满足 nums[mid] <= target <= nums[right] 时，则我们应该将搜索范围缩小至 [mid + 1, right]，否则在 [left, mid - 1] 中寻找。 3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 public int search (int [] nums, int target) int left = 0 , right = nums.length - 1 , mid = -1 ; while (left <= right) { mid = left + ((right - left) >> 1 ); if (nums[mid] == target) { return mid; } if (nums[left] <= nums[mid]) { if (nums[left] <= target && target < nums[mid]) { right = mid - 1 ; } else { left = mid + 1 ; } } else { if (nums[mid] < target && target <= nums[right]) { left = mid + 1 ; } else { right = mid - 1 ; } } } return -1 ; }
51、鸡蛋掉落 1、题目描述 给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。
已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。
每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。
请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？
1 2 3 4 5 6 7 输入：k = 1 , n = 2 输出：2 解释： 鸡蛋从 1 楼掉落。如果它碎了，肯定能得出 f = 0 。 否则，鸡蛋从 2 楼掉落。如果它碎了，肯定能得出 f = 1 。 如果它没碎，那么肯定能得出 f = 2 。 因此，在最坏的情况下我们需要移动 2 次以确定 f 是多少。
2、解题思路 当我们只有一个鸡蛋时，此时我们别无他法，只能一层楼一层楼测试，也就是对 [1, n] 进行线性扫描，所以结果为 n 当我们有无限个鸡蛋时，这个时候我们可以使用二分查找法来解决这个问题，每次都将扫描的范围减半，所以结果为 log(n) 使用动态规划解决这个问题，假设有 k 个鸡蛋 n 层楼，我们创建一个二维的 dp 数组 dp[n + 1][k + 1] 确定 dp 数组的含义，其中 dp[i][j] 表示有 i 层楼 k 个鸡蛋时，确定 f 所需要的最小操作数 3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 ``` ## 52、多数元素 ### 1、题目描述 > 给定一个大小为 *n* 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 **大于** `⌊ n/2 ⌋` 的元素。 > > 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 > * 示例一 ```java 输入：[3 ,2 ,3 ] 输出：3
2、解题思路 维护一个候选众数 target 和它出现的次数 count ，初始化时 target 为任意值，而 count 为 0 遍历数组中的所有元素，对于每个元素 num ，在判断 num 之前，如果 count 等于 0 ，那么将 target 的值赋为 num ，随后判断 num：如果 num 与 target 的值相等，那么 count ++ 如果 num 与 target 的值不等，那么 count – 遍历完 nums 后，target 即为整个数组中的众数。 3、解题代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public int majorityElement (int [] nums) if (nums.length == 1 ) return nums[0 ]; int target = -1 , count = 0 ; for (int num : nums) { if (count == 0 ) { target = num; } if (num == target) { count++; } else { count--; } } return target; }
