刷题记录

Problem: You have a number of envelopes with widths and heights given as a pair of integers  (w, h) . One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope. What is the maximum number of envelopes can you Russian doll? (put one inside other) Example: Given envelopes =  [[5,4],[6,4],[6,7],[2,3]] , the maximum number of envelopes you can Russian doll is  3  ([2,3] => [5,4] => [6,7]). Analysis: Two dimensional Longest increasing sub sequence. Convert this problem to 1D LIS. Sort the envelopes by width. So height becomes the 1D LIS. But if we have [3, 3], [3, 4], the former doll can not fit into the latter one. If there is a tie on width, sort height in desc order.  Time:  O(nlogn). Solution: class Solution { public int maxEnvelopes ( int [][] envelopes) { if (envelopes == null || envelopes . length == 0 || envelopes[ 0 ...

Problem: We are playing the Guess Game. The game is as follows: I pick a number from  1  to  n . You have to guess which number I picked. Every time you guess wrong, I'll tell you whether the number is higher or lower. You call a pre-defined API  guess(int num)  which returns 3 possible results ( -1 ,  1 , or  0 ): -1 : My number is lower 1 : My number is higher 0 : Congrats! You got it! Example: n = 10, I pick 6. Return 6. Analysis: The condition is very clear, so use double check template Solution: /* The guess API is defined in the parent class GuessGame. @param num, your guess @return -1 if my number is lower, 1 if my number is higher, otherwise return 0 int guess(int num); */ public class Solution extends GuessGame { public int guessNumber ( int n) { int left = 0 , right = n; while (left + 1 < right) { int mid = left + (right - left) / 2 ; ...

Problem: Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array. Example 1: Input: [1,3,5,6], 5 Output: 2 Example 2: Input: [1,3,5,6], 2 Output: 1 Example 3: Input: [1,3,5,6], 7 Output: 4 Example 4: Input: [1,3,5,6], 0 Output: 0 8/23/2018 update: 这道题不能取end的原因是，如果设end = mid - 1，那么end有可能为负。 ------------------ ------------------ ------------------ ------------------ ------------------ ------------------ -------------- Analysis: After trial for several times, the start = mid + 1 template wins and end should at nums.length Solution: class Solution { public int searchInsert ( int [] nums, int target) { int start = 0 , end = nums . length; while (start < end) { int mid = start + (end - start) / 2 ; if (nums[mid] == target) return mid; ...

Problem : Given a  n  x  n  matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix. Note that it is the kth smallest element in the sorted order, not the kth distinct element. Example: matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ], k = 8, return 13. 6/13/2018 update: Another and more efficient approach is using binary search. Very similar to quick select. If number of numbers less than and equal to mid is greater than k, we know that result is on left. class Solution { public int kthSmallest ( int [][] matrix, int k) { int m = matrix . length, n = matrix[ 0 ] . length; int lo = matrix[ 0 ][ 0 ], hi = matrix[m - 1 ][n - 1 ] + 1 ; while (lo < hi) { int mid = lo + (hi - lo) / 2 ; int count = 0 , j = n - 1 ; for ( int i = 0 ; i < m; i ++ ) { while (j >= 0 &...

用l + 1 < r再二次检查的模板。二次检查要遵循mid check。

Problem: Follow up  for "Find Minimum in Rotated Sorted Array": What if  duplicates  are allowed? Would this affect the run-time complexity? How and why? Analysis: 6/19/2018 update: Since we only compare nums[end], decrease end to remove duplicate. class Solution { public int findMin ( int [] nums) { int lo = 0 , hi = nums . length - 1 ; while (lo + 1 < hi) { int mid = lo + (hi - lo) / 2 ; if (nums[mid] > nums[hi]) { lo = mid; } else if (nums[mid] < nums[hi]){ hi = mid; } else { hi -- ; } } return nums[lo] < nums[hi] ? nums[lo] : nums[hi]; } } ---------------- ---------------- ---------------- ---------------- ---------------- ---------------- ---------------- ---------- 去除重复，保持二分法区间单调性。 参见 http://cqbbshuashua.blogspot.com/2018/01/search-in-rotated-sorted-array-ii.html ...

Problem: Given a target number and an integer array sorted in ascending order. Find the total number of occurrences of target in the array. Analysis: Use binary search to find lowerbound, and count from lowerbound up. Solution: public class Solution { /* * @param A: A an integer array sorted in ascending order * @param target: An integer * @return: An integer */ public int totalOccurrence ( int [] A , int target) { if ( A == null || A . length == 0 ) return 0 ; // write your code here int start = 0 , end = A . length - 1 , lower = - 1 , res = 0 ; while (start + 1 < end) { int mid = start + (end - start) / 2 ; if ( A [mid] >= target){ end = mid; } else { start = mid; } } if ( A [start] == target) lower = start; else if ( A [end] == target) lower = end; ...

Problem: Follow up  for "Search in Rotated Sorted Array": What if  duplicates  are allowed? Would this affect the run-time complexity? How and why? Analysis: 6/19/2018 update: If only compares with left, we can only increment left when there is duplicate. class Solution { public boolean search ( int [] nums, int target) { if (nums == null || nums . length == 0 ) return false; int left = 0 , right = nums . length - 1 ; while (left <= right) { int mid = left + (right - left) / 2 ; if (nums[mid] == target) return true; else if (nums[mid] > nums[left]) { if (target < nums[mid] && target >= nums[left]) right = mid - 1 ; else left = mid + 1 ; } else if (nums[mid] < nums[left]){ if (target > nums[mid] && target <= nums[r...

01/16/2018 update Solution with current chosen template. Longer but much safer. Note that when finding upper bound, check r index first. class Solution { public int [] searchRange ( int [] nums, int target) { if (nums . length == 0 ) { return new int []{ - 1 , - 1 }; } int start = - 1 , end = - 1 ; int low = 0 , high = nums . length - 1 ; while (low + 1 < high) { int mid = low + (high - low) / 2 ; if (nums[mid] >= target){ high = mid; } else { low = mid; } } if (nums[low] == target) start = low; else if (nums[high] == target) start = high; else return new int []{ - 1 , - 1 }; low = 0 ; high = nums . length - 1 ; while (low + 1 < high) { int mid = low + (high - low) / 2 ; if (nums[mid] <= ta...

Problem: You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad. Suppose you have  n  versions  [1, 2, ..., n]  and you want to find out the first bad one, which causes all the following ones to be bad. You are given an API  bool isBadVersion(version)  which will return whether  version  is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API. Analysis : Due to the nature of the bad version, if mid is not bad version, then the bad version must lie after mid.  Solution: /* The isBadVersion API is defined in the parent class VersionControl. boolean isBadVersion(int version); */ public class Solution extends VersionControl { public int firstBadVersion ...

01/17/2018 update Find the duplicate number 不适合使用start + 1< end模板。如果不好判断start 和end差距应该换模板。 第二种模板，可以把start = mid + 1加到满足的条件里面，所以最后退出的时候start就是结果。 01/16/2018 update 还是用九章总结的模板吧，更加统一，虽然start和end都要检查， 但是不容易出错。 int start = 0 , end = nums . length - 1 ; while (start + 1 < end) { int mid = start + (end - start) / 2 ; if (nums[mid] >= target){ end = mid; } else { start = mid; } } if (nums[start] == target) return start; else if (nums[end] == target) return end;  -------------------------------------------------------- int low = 0 , high = nums . length - 1; while (low < high) { int mid = low + (high - low) / 2 ; if (nums[mid] = target) { break ; } else if (nums[mid] > target){ high = mid; ...

Problem: Given an array where elements are sorted in ascending order, convert it to a height balanced BST. For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of  every  node never differ by more than 1. Example: Given the sorted array: [-10,-3,0,5,9], One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST: 0 / \ -3 9 / / -10 5 Analysis: Use binary search, nums[mid] is root, left and right are sub trees' mid. But condition has to be low < high, instead of regular template condition low + 1 < high. Because low == high is valid.  Solution: /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public TreeNode sortedArrayToBST(int[] nums) { if (nu...

6/11/2018 update: Why use R value instead of L when len is odd? Because cutR starts  with nums1.length, the mid point drops on right, so that the right part has more numbers. 这道题到道理懂，会实现。但是为什么这样实现还是一头雾水。为什么cutL要从length开始，二分条件是cutL <= cutR? -------------------------------------------------------------------------------------------------------------------------- 01/19/2018 Problem: There are two sorted arrays  nums1  and  nums2  of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). Example 1: nums1 = [1, 3] nums2 = [2] The median is 2.0 Example 2: nums1 = [1, 2] nums2 = [3, 4] The median is (2 + 3)/2 = 2.5 Analysis: L1 L2 nums1: 3 5 | 8 9 cut1: 2 nums2: 1 2 7 | 10 11 12 cut2: 3 R1 R2 nums3: 1 2 3 4 5 7 | 8 9 10 11 12 See the above table. If the cuts reach median, L1, L2, R1 and R2 satisfy the below conditions: L1 <= R2 R1 <= L2 Then use binar...

Problem: Given an array consisting of  n  integers, find the contiguous subarray whose  length is greater than or equal to   k  that has the maximum average value. And you need to output the maximum average value. Example 1: Input: [1,12,-5,-6,50,3], k = 4 Output: 12.75 Explanation: when length is 5, maximum average value is 10.8, when length is 6, maximum average value is 9.16667. Thus return 12.75. Note: 1 <=  k  <=  n  <= 10,000. Elements of the given array will be in range [-10,000, 10,000]. The answer with the calculation error less than 10 -5  will be accepted. Analysis: 6/20/2018 update: Use binary search to guess the average value. And make sure the error is within 0.00001. To compare the average, for instance, a1, a2, a3, a4 and b1, b2, b3, b4. If (a1-b1) + (a2-b2)  + (a3-b3) + (a4-b4) > 0, we can tell that a's average is greater than b. preSum is the sum that k away from current...

Problem: Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e.,  [0,1,2,4,5,6,7]  might become  [4,5,6,7,0,1,2] ). You are given a target value to search. If found in the array return its index, otherwise return  -1 . You may assume no duplicate exists in the array. Your algorithm's runtime complexity must be in the order of  O (log  n ). Example 1: Input: nums = [ 4,5,6,7,0,1,2] , target = 0 Output: 4 Example 2: Input: nums = [ 4,5,6,7,0,1,2] , target = 3 Output: -1 Analysis: 6/19/2018 update: If mid value is on upper part, it's easier to control going left. So that target has to on the upper part: target >= nums[left]. and target needs to be smaller than mid value, target < nums[mid]. Same thing applies to lower part. The left and right points are inclusive. So add == to condition. No need to use start + 1 < end template, since this problem finds the exact value. class So...