Easy难度
771. Jewels and Stones
- 题目: 给出两个字符串A 和 B, 在B中找出在A中也出现过的字符
- 思路: 新建一个HashSet,先遍历A，把所有字符放到set里，再遍历B并判断字符是否在set中出现。
// 02.14class Solution { public int numJewelsInStones(String J, String S) { if (J == null || J.length() == 0) { return 0; } int count = 0; HashSet set = new HashSet<>(); for (Character c : J.toCharArray()) { set.add(c); } for (Character c : S.toCharArray()) { if (set.contains(c)) { count++; } } return count; }}复制代码 461. Hamming Distance 题目: 给出两个整数,找出两个整数变为二进制格式时有几个bit位不同 思路: 直接异或操作找不同？Yes，异或操作的结果是相同为为0，不同位为1，将异或后得到的数字中所有的1相加就是Hamming距离
class Solution { public int hammingDistance(int x, int y) { int xor = x ^ y, count = 0; for (int i = 0; i < 32; i++) { // 右移操作等价于除以2^n count += (xor >> i) & 1; // n & 1 如果以1结尾，得到1, 如果以0结尾，得到0 } return count; }}复制代码 Similar question:
-
- Number of 1 Bits
- 题目:求一个整数二进制中
1出现的次数 - 思路:
public class Solution { // you need to treat n as an unsigned value public int hammingWeight(int n) { int count = 0; // 这里也可以用另一个判断条件 while (n != 0) for (int i = 0; i < 32; i++) { count += n & 1; n = n >>> 1; } return count; }}复制代码 -
- Counting Bits
- 题目: 给出一个整数n,求出在[0,n]范围内的每个整数二进制表示中
1出现的次数 - 思路: 观察规律,[2^1， 2^2], [2^2, 2^3]的前半部分是[2^1,2^2], 后半部分是[2^1,2^2]+1
0 0000 0-------------1 0001 1-------------2 0010 13 0011 2-------------4 0100 15 0101 26 0110 27 0111 3-------------8 1000 19 1001 210 1010 211 1011 312 1100 213 1101 314 1110 315 1111 4复制代码
public int[] countBits(int num) { int[] f = new int[num + 1]; for (int i=1; i<=num; i++) { f[i] = f[i >> 1] + (i & 1); //用一个dp数组来存已经判断过的信息 } return f;}复制代码 617. Merge Two Binary Trees
- 题目: 将两个二叉树合并为一个二叉树
- 思路: 注意必须是将树的节点合并而不只是值合并
// 02.14class Solution { public TreeNode mergeTrees(TreeNode t1, TreeNode t2) { if (t1 == null) { return t2; } if (t2 == null) { return t1; } TreeNode root = new TreeNode(t1.val + t2.val); root.left = mergeTrees(t1.left, t2.left); root.right = mergeTrees(t1.right, t2.right); return root; }}复制代码 104. Maximum Depth of Binary Tree
// 02.14class Solution { public int maxDepth(TreeNode root) { if (root == null) { return 0; } int left = maxDepth(root.left); int right = maxDepth(root.right); return Math.max(left, right) + 1; }}复制代码 110. Balanced Binary Tree
- 思路: 每一层都求一次深度,如果左右子树的深度差值超过1，就是非平衡的二叉树
// 02.14class Solution { public boolean isBalanced(TreeNode root) { if (root == null) { return true; } int left = maxDepth(root.left); int right = maxDepth(root.right); if (Math.abs(left - right) > 1) { return false; } return isBalanced(root.left) && isBalanced(root.right); } private int maxDepth(TreeNode root) { if (root == null) { return 0; } int left = maxDepth(root.left); int right = maxDepth(root.right); return Math.max(left, right) + 1; }}复制代码 136. Single Number
- 题目: 给出一个数组,其中只有一个元素出现一次，其他所有的元素都出现了两次,请找出只出现一次的元素
- 思路: 使用异或的特性,相同位相加得到0,不同位相加得到1
// 02.14// 利用 A XOR A = 0的特点，保证class Solution { public int singleNumber(int[] nums) { int res = 0; for (int num : nums) { res = res ^ num; } return res; }}复制代码 137. Single Number II
- 题目: 给出一个数组,其中只有一个元素出现一次，其他所有的元素都出现了三次,请找出只出现一次的元素
260. Single Number III[M]
- 题目: 给出一个数组，里面有两个元素只出现一次，其他元素都出现了两次，找到只出现一次的元素
- 思路: 调用两次异或操作，第一次将两个出现一次的元素分到两个不同的组, 第二次调用找出这两个元素
public class Solution { public int[] singleNumber(int[] nums) { // Pass 1 : // Get the XOR of the two numbers we need to find int diff = 0; for (int num : nums) { diff ^= num; } // Get its last set bit diff &= -diff; // Pass 2 : int[] rets = { 0, 0}; // this array stores the two numbers we will return for (int num : nums) { if ((num & diff) == 0) // the bit is not set { rets[0] ^= num; } else // the bit is set { rets[1] ^= num; } } return rets; }}复制代码 Missing Number
- 题目: 给出一个数组其中元素的范围是0, 1, 2, ..., n 求出缺少的那个数字
- 思路: 利用异或特性,i和nums[i]的取值范围除一个missing number之外都相同
- 变形: 如果是排好序的数组直接用二分法，比较中间值的下标和元素值，如果下标比元素值,左边的元素少,missin number在左边,反之在右边。
public int missingNumber(int[] nums) { //xor int res = nums.length; // 这里需要将res初始值设定为n，而不是0, 如果设定为0的话,0会出现三次 for(int i=0; i 287. Find the Duplicate Number
226. Invert Binary Tree
- 问题: 将一个二叉树的左右子树颠倒
- 思路: DC算法，左换右，左左换右右，右右换左左
// 02.17 class Solution { public TreeNode invertTree(TreeNode root) { // bottom-up 解法 if (root == null) { return null; } TreeNode left = invertTree(root.left); TreeNode right = invertTree(root.right); root.left = right; root.right = left; return root; }}复制代码 101. Symmetric Tree
- 问题: 判断一棵二叉树是否是中心对称的
- 思路: 左子树的左节点要和右子树的右节点中心对称
class Solution { public boolean isSymmetric(TreeNode root) { if (root == null) { return true; } return helper(root.left, root.right); } public boolean helper(TreeNode left, TreeNode right) { if (left == null || right == null) { return left == right; } if (left.val != right.val) { return false; } // 这里必须要继续判断当前节点的子节点是否满足条件 return helper(left.right, right.left) && helper(left.left, right.right); }}复制代码 283. Move Zeroes
- 问题: 给出一个数组，将数组中所有的
0移动到数组的最后，并保持原来非零元素的相对顺序 - 思路: 同向双指针, 交换第一个
0元素和第一个非零元素 - 样例:
Input: [0,1,0,3,12]Output: [1,3,12,0,0]复制代码
// 02.17class Solution { public void moveZeroes(int[] nums) { int n = nums.length; int left = 0; int right = 0; while (left < n && right < n) { while (right < n && nums[right] == 0) { right++; } // 这里要保证left指针在right指针的前面 while (left < right && nums[left] != 0) { left++; } if (left < n && right < n) { swap(nums, left, right); left++; right++; } } } private void swap(int[] nums, int i, int j) { int swap = nums[i]; nums[i] = nums[j]; nums[j] = swap; }}class Solution { public void moveZeroes(int[] nums) { int n = nums.length; int left = 0, right = 0; wihle (right < n) { if (nums[right] != n) { //当left 和 right指向了同一个元素时，可以自己和自己swap，这样保证了left一定指向一个0元素，right指向一个非零元素 swap(nums, left, right); left++; } right++; } } private void swap(int[] A, int i, int j) { int swap = A[i]; A[i] = A[j]; A[j] = swap; }}复制代码 448. Find All Numbers Disappeared in an Array
- 题目: 给出一个数组，每个元素的取值范围是[1,n] n是数组的长度,每个元素可以出现两次或者一次，找出[1,n]中的哪些元素没有在数组中出现
- 思路: 利用性质(1): 每个元素的取值范围是[1,n]，可以看做是一个数组的index, 将其作为数组的标记nums[index] = -nums[index]
class Solution { public List findDisappearedNumbers(int[] nums) { List res = new ArrayList<>(); for (int i = 0; i < nums.length; i++) { int index = Math.abs(nums[i]) - 1; if (nums[index] > 0) { nums[index] = -nums[index]; } } for (int i = 0; i < nums.length; i++) { if (nums[i] > 0) { res.add(i + 1); // 注意这里要将index转换为元素时需要进行 +1 操作 } } return res; }}复制代码 Similar Question:
- 41. First Missing Positive[Hard]
- 题目: 给出一个整数型元素, 数组内的元素取值可以是正或负数, 返回缺失的最小的正整数 要求O(n)时间复杂度和O(1)空间复杂度
- 思路: 因为是要求缺失的最小整数,其实也限定了一个取值的范围必须要从小到大, 因为不能使用额外空间，就直接使用给出的input数组作为我们的范围，取值范围就是[1,n] n是给出数组的长度, 接下来我们要做的就是将input当中已经出现过的取值范围在[1,n]之中的元素标记出来,做法是将出现过的元素对应的index取负值，类似448中的思路, 但是需要注意数组越界的情况，需要限定
num <= nums.length - 讲解视频： https://www.youtube.com/watch?v=8DqewGsVNkI
// 02.17 02.18class Solution { public int firstMissingPositive(int[] nums) { if (nums == null || nums.length == 0) { return 1; } int n = nums.length; // 先将负数和零单独标记出来 for (int i = 0; i < n; i++) { if (nums[i] <= 0) { nums[i] = Integer.MAX_VALUE; } } for (int i = 0; i < n; i++) { int index = Math.abs(nums[i]); if (index <= n) { nums[index - 1] = -Math.abs(nums[index - 1]); } } for (int i = 0; i < n; i++) { if (nums[i] > 0) { return i + 1; } } return n + 1; // 这里返回的应该是 n + 1 }} }}复制代码 206. Reverse Linked List
class Solution { public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode curr = head; while (curr != null) { ListNode next = curr.next; curr.next = prev; prev = curr; curr = next; } return prev; }}// 02.23 递归实现-先走到链表最后然后向前指class Solution { public ListNode reverseList(ListNode head) { if (head == null || head.next == null) { return head; } ListNode curr = head; ListNode next = head.next; curr.next = null; ListNode newHead = reverseList(next); next.next = curr; return newHead; }}复制代码 Similar Question:
- 92. Reverse Linked List II
- 题目: 翻转一个链表中m到n的元素,
1 <= m <= n - 思路:用一个变量计数? 分段处理,在m之前直接顺序遍历,在m到n之间需要reverse
//02.17 宝典的解法-没看懂public class Solution { public ListNode reverseBetween(ListNode head, int m, int n) { if (m == n) { return head; } ListNode dummy = new ListNode(0); dummy.next = head; ListNode prev = dummy; ListNode cur = head; for (int i = 0; i < m - 1; i++) { prev = prev.next; cur = cur.next; } for (int i = 0; i < n - m; i++) { ListNode next = cur.next; cur.next = next.next; next.next = prev.next; prev.next = next; } return dummy.next; }}//02.17 自己根据basketwang的代码改写的//核心思路就是将mNode依次插入到nNode的后面直到mNode和nNode重合class Solution { public ListNode reverseBetween(ListNode head, int m, int n) { if (m == n) { return head; } ListNode dummy = new ListNode(0); dummy.next = head; ListNode prevM = dummy; ListNode mNode = head; ListNode nNode = head; for (int i = 0; i < m - 1; i++) { prevM = prevM.next; mNode = mNode.next; nNode = nNode.next; } for (int i = 0; i < n - m; i++) { nNode = nNode.next; } while (mNode != nNode) { prevM.next = mNode.next; mNode.next = nNode.next; nNode.next = mNode; mNode = prevM.next; } return dummy.next; }}复制代码 - 143. Reorder List
- 题目: Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
- 思路: 先将后半段的链表倒序，然后双指针遍历，将后半段的链表节点依次插入到前半段的链表中
class Solution { public void reorderList(ListNode head) { if (head == null || head.next == null) { return; } ListNode fast = head; ListNode slow = head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; } ListNode tail = reverseList(slow.next); slow.next = null; merge(head, tail); } private ListNode reverseList(ListNode head) { ListNode prev = null; ListNode curr = head; while (curr != null) { ListNode next = curr.next; curr.next = prev; prev = curr; curr = next; } return prev; } private void merge(ListNode l1, ListNode l2) { int index = 0; ListNode dummy = new ListNode(0); ListNode curr = dummy; while (l1 != null && l2 != null) { if (index % 2 == 0) { curr.next = l1; l1 = l1.next; } else { curr.next = l2; l2 = l2.next; } curr = curr.next; index++; } if (l1 == null) { curr.next = l2; } if (l2 == null) { curr.next = l1; } }}复制代码 169. Majority Element
- 问题:给出一个数组，找出出现次数超过一半的元素
- 思路:这个元素的出现次数之和一定大于其它所有元素的和, 需要用两个变量来存, 一个存出现次数，一个存元素数值。
class Solution { public int majorityElement(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int res = nums[0]; int count = 1; for (int i = 1; i < nums.length; i++) { if (res != nums[i]) { if (count > 0) { count--; } else { res = nums[i]; count++; } } else { count++; } } return res; }}复制代码 ** 538. Convert BST to Greater Tree**
- 问题: 给出一个BST, 将BST中的每个节点值加上所有比它大的节点值之和
- 思路: 后序遍历 并用一个变量来存当前所有遍历过的节点的累加和
class Solution { int sumVal = 0; public TreeNode convertBST(TreeNode root) { if (root == null) { return null; } root.right = convertBST(root.right); sumVal += root.val; // 先更新sumVal为当前节点值 + 累计sumVal root.val = sumVal; // 再直接更新root.val 为sumVal root.left = convertBST(root.left); return root; }}复制代码 121.Best Time to Buy and Sell Stock
- 问题: 只允许买卖一次，求最大收益
// 02.18class Solution { public int maxProfit(int[] prices) { if (prices == null || prices.length == 0) { return 0; } int min = prices[0]; int maxProfit = 0; for (int i = 0; i < prices.length; i++) { if (prices[i] < min) { min = prices[i]; continue; } maxProfit = Math.max(maxProfit, prices[i] - min); } return maxProfit; }}复制代码 - Follow Up:
- 参考总结: https://blog.csdn.net/Dr_Unknown/article/details/51939121
- 122. Best Time to Buy and Sell Stock II
- 问题: 不限制交易次数买卖股票,求最大收益
- 思路: 从头遍历数组,如果当天股票价格大于前一天就卖, 贪心算法
// 02.18class Solution { public int maxProfit(int[] prices) { if (prices == null || prices.length == 0) { return 0; } int maxProfit = 0; for (int i = 1; i < prices.length; i++) { if (prices[i] - prices[i - 1] > 0) { maxProfit += prices[i] - prices[i - 1]; } } return maxProfit; }}复制代码 - 123. Best Time to Buy and Sell Stock III
- 问题: 只允许买卖两次，求最大收益
- 思路: 用动态规划，以第i天作为分界，判断在第i天之前做一次交易的最大收益和第i天之后做一次交易的最大收益,最后遍历两个数组求和
// 02.18public class Solution { public int maxProfit(int[] prices) { if (prices.length < 2) return 0; int n = prices.length; int[] preProfit = new int[n]; int[] postProfit = new int[n]; int curMin = prices[0]; for (int i = 1; i < n; i++) { curMin = Math.min(curMin, prices[i]); preProfit[i] = Math.max(preProfit[i - 1], prices[i] - curMin);//第i天卖出 } int curMax = prices[n - 1]; for (int i = n - 2; i >= 0; i--) { //从后往前遍历 如果当天的收益大于之前的最大收益,就更新收益的数组 curMax = Math.max(curMax, prices[i]); postProfit[i] = Math.max(postProfit[i + 1], curMax - prices[i]);//第i天买入 } int maxProfit = 0; for (int i = 0; i < n; i++) { maxProfit = Math.max(maxProfit, preProfit[i] + postProfit[i]); } return maxProfit; }复制代码 - Best Time to Buy and Sell Stock IV 没看懂 跳过
- 问题: 最多进行k次交易, 求最大收益, k作为一个变给出
- 思路: 如果k > n / 2, 直接按照买股票II来做,贪心只要当天比前一天股价高就卖 定义localMax 和 globalMax 两个二维数组？ 为什么？
localMax必须在当前位置结束globalMax记录可能的不连续性
public class Solution { public int maxProfit(int k, int[] prices) { if (prices == null || prices.length == 0) { return 0; } int n = prices.length; if (k >= n / 2) { int profit = 0; for (int i = 1; i < n; i++) { int diff = prices[i] - prices[i - 1]; if (diff > 0) { profit += diff; } } return profit; } int[][] localMax = new int[n][k + 1]; int[][] globalMax = new int[n][k + 1]; for (int i = 1; i < n; i++) { int diff = prices[i] - prices[i - 1]; for (int j = 1; j <= k && j * 2 <= i + 1; j++) { localMax[i][j] = Math.max(localMax[i - 1][j], globalMax[i - 1][j - 1]) + diff; globalMax[i][j] = Math.max(localMax[i][j], globalMax[i - 1][j]); } } return globalMax[n - 1][k]; }}复制代码 53. Maximum Subarray
- 问题: 给出一个数组, 找出数组中和最大的子数组
- 思路: 定义一个
localMax和一个globalMax,localMax是连续的子数组区间Math.Max(localMax + nums[i], nums[i])
class Solution { public int maxSubArray(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int cur = nums[0]; int max = nums[0]; for (int i = 1; i < nums.length; i++) { cur = Math.max(cur + nums[i], nums[i]); // localMax更新必须要考虑当前位置的元素 max = Math.max(cur, max); // globalMax的更新只需要比较自身和localMax两个值即可 } return max; }}复制代码 - Follow Up:
- 152. Maximum Product Subarray
- 问题: 给出一个数组,求其中乘积最大的子数组
- 思路: 由于存在负负得正,需要同时记录
localMax和localMin两个local变量和一个globalMax变量
//02.18 必须注意初始化为nums[0]class Solution { public int maxProduct(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int localMax = nums[0]; int localMin = nums[0]; int globalMax = nums[0]; for (int i = 1; i < nums.length; i++) { //必须要在比较之前先用新的变量将localMax * nums[i] 和 localMin * nums[i]存起来，否则比较的时候不同步 int currMax = localMax * nums[i]; int currMin = localMin * nums[i]; localMax = Math.max(Math.max(currMax, currMin), nums[i]); // 这里会出现localMin使用更新后的localMax的结果, 需要保证localMax和localMin的同步 localMin = Math.min(Math.min(currMax, currMin), nums[i]); globalMax = Math.max(localMax, globalMax); } return globalMax; }}复制代码 - 42. Maximum SubarrayII
- 问题: 给出一个数组,找出两个不重叠的子数组使其和最大
- 思路: 需要找到的是两个子数组, 如何进行切割 每个位置都可以作为切割点
//02.18public class Solution { public int maxTwoSubArrays(ArrayList nums) { if (nums == null || nums.size() == 0) { return 0; } int n = nums.size(); int[] left = new int[n]; int[] right = new int[n]; int localMax = nums.get(0); int max = nums.get(0); left[0] = nums.get(0); for (int i = 1; i < n; i++) { localMax = Math.max(nums.get(i), nums.get(i) + localMax); max = Math.max(max, localMax); left[i] = max; } localMax = nums.get(n - 1); max = nums.get(n - 1); right[n - 1] = nums.get(n - 1); for (int i = n - 2; i >= 0; i--) { localMax = Math.max(nums.get(i), nums.get(i) + localMax); max = Math.max(max, localMax); right[i] = max; } int res = Integer.MIN_VALUE; for (int i = 0; i < n - 1; i++) { res = Math.max(res, left[i] + right[i + 1]); // 为什么要用right[i + 1]?? } return res; }}复制代码 - Maximum Subarray III
- 问题: 给出一个整数数组,找出k个不重叠且和最大的子数组
- 思路:
字典序最大的子序列
// 02.14public class Main { public static void main(String[] args) { Scanner input = new Scanner(System.in); String str = input.nextLine(); char[] res = str.toCharArray(); ArrayList arr = new ArrayList<>(); arr.add(res[res.length-1]); for (int i = res.length-1; i > 0; i--){ if ( arr.get(arr.size()-1) <= res[i-1]){ arr.add(res[i-1]); } } StringBuilder sb = new StringBuilder(); for (int i = 0; i < arr.size(); i++){ sb.append(arr.get(i)); } System.out.println(sb.reverse().toString()); }}复制代码 160.Intersection of Two Linked List
- 问题: 给出两个链表，它们的后半段是相交的，也就是后半段完全一致,求出交点的起始位置
- 思路: 由于后半段一致,当第一次同时走到相同的节点是就是第一个交点,关键问题是前半段的长度不一致，如果从同一起点来做就可以做到同步到达交点
// 02.18public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode currA = headA; ListNode currB = headB; int lenA = 0; int lenB = 0; while (currA != null) { currA = currA.next; lenA++; } while (currB != null) { currB = currB.next; lenB++; } while (lenA - lenB > 0) { headA = headA.next; lenA--; } while (lenB - lenA > 0) { headB = headB.next; lenB--; } while (headA != headB) { headA = headA.next; headB = headB.next; } return headA; }}//两次遍历利用差值来直接 a + b + cpublic class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA == null || headB == null) { return null; } ListNode a = headA; ListNode b = headB; while (a != b) { a = a == null ? headB : a.next; b = b == null ? headA : b.next; } return a; }}复制代码 438.Find All Anagrams in a String
- 问题: 给出两个字符串s和p, 找出
- 思路: 滑动窗口,窗口的长度为
p.length()并设定一个辅助变量diff来记录当前窗口内的所有字符与p字符串的比较结果
class Solution { public List findAnagrams(String s, String p) { ArrayList res = new ArrayList<>(); if (s.length() == 0 || p.length() == 0 || s.length() < p.length()) { return new ArrayList (); } // store the characters we need for finding next anagram int[] chars = new int[26]; for (Character c : p.toCharArray()) { chars[c - 'a']++; } int matched = 0; int plength = p.length(); int slength = s.length(); int left = 0; // point to String s int right = 0; // point to String p while (right < slength) { if (chars[s.charAt(right) - 'a'] >= 1) { matched++; } if (matched == plength) { res.add(left); } chars[s.charAt(right) - 'a']--; right++; if (right - left == plength) { // 当前left位置的字符在p中也出现过,走到下一步时会被推出当前窗口,所以matched需要减一 if (chars[s.charAt(left) - 'a'] >= 0) { matched--; } // 当前left向前走之后,需要匹配的元素多了一个,需要将chars中的记录+1 chars[s.charAt(left) - 'a']++; left++; } } return res; }}复制代码 - Similar Question:
- 242.Valid Anagram
- 问题: 给出两个字符串s和t，判断t是否是s的Anagram
- 思路: 先比较长度,长度不一致一定是false，再用一个数组存s中的所有出现的字符
class Solution { public boolean isAnagram(String s, String t) { int[] alphabet = new int[26]; for (int i = 0; i < s.length(); i++) alphabet[s.charAt(i) - 'a']++; for (int i = 0; i < t.length(); i++) alphabet[t.charAt(i) - 'a']--; for (int i : alphabet) if (i != 0) return false; return true; }}复制代码 581. Shortest Unsorted Continuous Subarray
Medium
94. Binary Tree Inorder Traversal
// 02.15class Solution { public List inorderTraversal(TreeNode root) { List list = new ArrayList (); Stack stack = new Stack (); TreeNode cur = root; while(cur!=null || !stack.empty()){ while(cur!=null){ stack.add(cur); cur = cur.left; } cur = stack.pop(); list.add(cur.val); cur = cur.right; } return list; }}复制代码 ** 95. Unique Binary Search Trees II**
- 问题:
- 思路:
230. Kth Smallest Element in a BST[M]
- 题目: 找到一个BST当中第K大的数值
- 思路: 中序遍历倒计时
class Solution { private static int number = 0; private static int count = 0; public int kthSmallest(TreeNode root, int k) { count = k; helper(root); return number; } public void helper(TreeNode n) { if (n.left != null) helper(n.left); count--; if (count == 0) { number = n.val; return; } if (n.right != null) helper(n.right); }}复制代码 - 思路: 利用BST的特性,中序遍历
// 02.14class Solution { public int kthSmallest(TreeNode root, int k) { Stack stack = new Stack<>(); TreeNode cur = root; while (cur != null || !stack.isEmpty()) { while (cur != null) { stack.add(cur); cur = cur.left; } cur = stack.pop(); k--; if (k == 0) { return cur.val; } cur = cur.right; } return -1; }}复制代码 285.Inorder Successor in BST
- 问题: 找出一个node 的中序遍历的下一个节点
- 思路: 直接inorde traversal
// 02.15class Solution { public TreeNode inorderSuccessor(TreeNode root, TreeNode p) { Stack stack = new Stack (); TreeNode cur = root; boolean found = false; while(cur!=null || !stack.empty()){ while(cur!=null){ stack.add(cur); cur = cur.left; } cur = stack.pop(); if (found == true) { return cur; } if (cur == p) { found = true; } cur = cur.right; } return null; }}复制代码 510.Inorder Successor in BST II
- 问题: 找出BST中某个节点的下一个相邻节点，只给出parent, left, right指针而不给出root节点
- 思路: 分类讨论不同Successor
- Case 1: 当前节点的右子节点存在,那么successor就是右子树的最左节点
- Case 2: 如果当前节点的右子树不存在，向上找parent,直到找到一个比当前节点大的parent node就是succsssor, 如果找不到最后会返回
null也就是root.parent
class Solution { public Node inorderSuccessor(Node x) { if (x.right == null) { Node result = x.parent; while (result != null && result.val < x.val) { result = result.parent; } return result; } else { Node result = x.right; while (result.left != null) { result = result.left; } return result; } }}复制代码 333. Largest BST Subtree
- 问题: 找出一个二叉树中包含最多节点的BST子树
- 思路: 先要找最大的子树, 再保证是一个BST
复制代码
98. Validate Binary Search Tree
- 问题: 确定一个二叉树是否是一个BST
- 思路: Inorder 顺序遍历必须要是递增的, 设一个
pre指针, 初始值为null，每次遍历到新的节点是进行更新
//02.15public boolean isValidBST(TreeNode root) { if (root == null) return true; Stack stack = new Stack<>(); TreeNode pre = null; while (root != null || !stack.isEmpty()) { while (root != null) { stack.push(root); root = root.left; } root = stack.pop(); if(pre != null && root.val <= pre.val) return false; pre = root; root = root.right; } return true;}复制代码 215. Kth Largest Elements in an Array
- 题目: 给出一个数组，找到数组中第k大的数值
- 思路: 根据快排的partition分类思路,先找一个pivot值，然后将比pivot值大的数放在右边,比pivot小的数字都放在左边,每次分好之后,判断一下pivot所在的位置是否等于k,如果等于，那么直接返回pivot值,如果k <= right + 1, 说明第k大的数一定在pivot左边,递归调用partition判断左半部分,如果k > right + 1, 判断右半部分。
public class Solution { public int findKthLargest(int[] nums, int k) { return partition(nums, k, 0, nums.length - 1); } private int partition(int[] nums, int k, int start, int end){ int pivot = nums[start]; int left = start; int right = end; while(left <= right){ while(left <= right && nums[left] >= pivot) left++; while(left <= right && nums[right] <= pivot) right--; if(left < right) swap(nums, left, right); } swap(nums, start, right); if(k == right + 1) return nums[right]; if(k > right + 1){ return partition(nums, k, right + 1, end); } else { return partition(nums, k, start, right - 1); } }287. Find the Duplicate Number private void swap(int[] nums, int a, int b){ int temp = nums[a]; nums[a] = nums[b]; nums[b] = temp; }}复制代码 follow up: 378. Kth Smallest Element in a Sorted Matrix
- 题目: 给出一个n * n的二维数组,每一行和每一列都是递增的，但是不保证蛇形有序, 求出这个数组中第K大的数值
- 思路1: 直接遍历所有元素并用最大堆维护前K小的元素,当pq.size() > k的时候将pq中的Top元素poll出来
- 思路2: 使用二分查找,不是简单的查找某个元素是否存在而是需要找出比某一个值小的元素的个数，定义一个
countLessEqualNumsfunction, 自己定义的target
// 02.17class Solution { // matrix is n * n public int kthSmallest(int[][] matrix, int k) { int start = matrix[0][0]; int end = matrix[matrix.length - 1][matrix[0].length - 1]; while (start <= end) { // count the numbers that is smaller than or equal to the mid int mid = start + (end - start) / 2; // 这个mid值一定存在么？ int count = countLessEqualNums(mid, matrix); if (count < k) { start = mid + 1; } else { end = mid - 1; } } return start; } private int countLessEqualNums(int target, int[][] matrix) { int i = 0; int j = matrix[0].length - 1; int start = matrix[i][j]; int result = 0; while (i < matrix.length && j >= 0) { if (matrix[i][j] > target) { j--; } else { result += j + 1; i++; } } return result; }}复制代码 similar questions:
- 74.Search in 2D Matrix
- 题目: 给出一个二维的数组,判断一个特定target值是否在数组中存在
- 思路: 因为每一行都是递增的且每一行的最后一个元素总小于当前行的下一行的首元素,所以整个二维数组可以看做一个有序的一维数组, 一维转二维 [mid/cols]得到行数 [mid%cols]得到列数
- 思路2: 和Search in 2D Matrix II 同样解法
public class Solution { /** * @param matrix, a list of lists of integers * @param target, an integer * @return a boolean, indicate whether matrix contains target */ public boolean searchMatrix(int[][] matrix, int target) { // write your code here if(matrix == null || matrix.length == 0 || matrix[0].length == 0){ return false; } int row = matrix.length; int column = matrix[0].length; int start = 0, end = row * column - 1; while(start <= end){ int mid = start + (end - start) / 2; int number = matrix[mid / column][mid % column]; if(number == target){ return true; }else if(number > target){ end = mid - 1; }else{ start = mid + 1; } } return false; }}复制代码 - Search in 2D Matrix II
- 问题:给出一个二维数组，每一行都是递增的，每一列都是递增的，但不保证蛇形有序，问数组中是否存在一个特定的值
- 思路: 看到有序排列就要使用Binary Search， Binary Search的核心是找到比较的区间, 起点是左下角的元素, 如果查找的元素大于
[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30]]复制代码
class Solution { public boolean searchMatrix(int[][] matrix, int target) { if (matrix == null || matrix.length == 0) { return false; } int col = 0; int row = matrix.length - 1; while (row >= 0 && col < matrix[0].length) { if (target == matrix[row][col]) { return true; } else if (target < matrix[row][col]) { row--; } else if (target > matrix[row][col]) { col++; } } return false; }}复制代码 - 703. Kth Largest Element in a Stream
- 问题: 给出一个不断增加的字节流，写一个函数返回当前第K大的数字
- 思路: 维持一个Min Heap来保存前K大的元素，如果新加入的数字大于当前的第K大,则更新当前的第K大,如果小于当前的第K大则不做任何更新
class KthLargest { final PriorityQueue q; final int k; public KthLargest(int k, int[] nums) { this.k = k; q = new PriorityQueue (k); for (int a :nums) { add(a); //这里直接调用add() 而不是pq中默认的add()方法 } } public int add(int val) { q.offer(val); if (q.size() > k) { q.poll(); } return q.peek(); }}* **329.Longest Increasing Path in a Matrix*** 题目: 找出一个二维数组中一条最长的递增路径，并返回路径的长度* 思路: 直接DFS + memo来判断每一个位置作为路径的最小的元素（即路径的起点)能够得到的最长路径的长度 ```java// 02.16public static final int[][] dirs = { { 0, 1}, { 1, 0}, { 0, -1}, {-1, 0}};public int longestIncreasingPath(int[][] matrix) { if(matrix.length == 0) return 0; int m = matrix.length, n = matrix[0].length; int[][] cache = new int[m][n]; int max = 1; for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { int len = dfs(matrix, i, j, m, n, cache); max = Math.max(max, len); } } return max;}public int dfs(int[][] matrix, int i, int j, int m, int n, int[][] cache) { if(cache[i][j] != 0) return cache[i][j]; int max = 1; for(int[] dir: dirs) { int x = i + dir[0], y = j + dir[1]; // matrix[i][j] 是当前节点的值, 而matrix[x][y]是周围的neighbor节点的值 if(x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] <= matrix[i][j]) continue; int len = 1 + dfs(matrix, x, y, m, n, cache); max = Math.max(max, len); }https://leetcode.com/problems/third-maximum-number/ cache[i][j] = max; return max;}复制代码 414. Third Maximum Number
- 题目: 给出一个数组，找到数组中第三大的数字
- 思路: 用三个变量分别存最大，第二大，第三大的数字, 遍历数组并及时更新
class Solution { public int thirdMax(int[] nums) { long firstMax = Long.MIN_VALUE,secondMax = Long.MIN_VALUE,thirdMax = Long.MIN_VALUE; // 为了解决[1,2,-2147483648]这种corner case for (int i = 0; i < nums.length; i++) { if(nums[i]> firstMax) { thirdMax = secondMax; secondMax = firstMax; firstMax = nums[i]; }else if(nums[i]> secondMax && nums[i] < firstMax) { thirdMax = secondMax; secondMax = nums[i]; }else if( nums[i] > thirdMax && nums[i] < secondMax) { thirdMax = nums[i]; } } return (int)(thirdMax == Long.MIN_VALUE ? firstMax: thirdMax); }}复制代码