1. 找到可行解范围
2. 猜答案
3. 检验条件
4. 调整搜索范围
287. Find the Duplicate Number
Guess a duplicate number i and verify whether it is the final result or not
The number could be in the range of [1,n] so we made one guess and decide
larger or smaller based on the number of element smaller than this value
Binary Search on value. The search space is 1~~n, we deduce that the duplicate number is Value and count the number of element smaller than the suggested value . Reduce the search space every round
public class Solution {
public int findDuplicate(int[] nums) {
int len = nums.length;
int low = 1;
int high = len - 1;
while(low < high){
int mid = low + (high - low)/2;
int cnt = 0;
for(int val: nums){
if(val <= mid)cnt++;
}
if(cnt <= mid){
low = mid + 1;
}
else{
high = mid;
}
}
return high;
}
}
230. Kth Smallest Element in a BST
充分利用搜索二叉树的特性 左边的全部小于根结点 右边全部大于根结点 通过统计左子树的结点个数 判断第K个应该在哪 是左子树还是右子树还是就是根本身. A better way is to edit the node structure that compute the number of nodes it has.
public class Solution {
public int kthSmallest(TreeNode root, int k) {
int numLeft = countNodes(root.left);
if(k <= numLeft)return kthSmallest(root.left,k);
else if(k > numLeft + 1){
return kthSmallest(root.right,k - numLeft - 1);
}
//if put in a else statement would be TLE???
return root.val;
}
public int countNodes(TreeNode root){
if(root == null)return 0;
return 1 + countNodes(root.left) + countNodes(root.right);
}
}
besides using binary search we can also apply the In-Order Traversal Here ,which takes O(N) (visit node one time) use stack or recursion is ok
209. Minimum Size Subarray Sum
二分法只是优化了双指针其中拓展j的思路 利用了prefix数组是sorted的性质 Since we cannot sort the original array but we can change the array to represent the sum of element until index i as an new array "sum". And for each index i we search the leftmost element that satisfied the target. 以及注意Sum array的index是怎么分布的！注意填补循环的时候注意index 最好直接用.length
public class Solution {
public int minSubArrayLen(int s, int[] nums) {
if(nums == null || nums.length == 0)return 0;
int n = nums.length;
int[] sums = new int[n+1];
int minLen = Integer.MAX_VALUE;
for(int i = 1;i < sums.length;i++){
sums[i] = nums[i-1] + sums[i-1];
}
for(int i = 0;i <= n;i++){
int j = binarySearch(i+1,n,s+sums[i],sums);
if(j == sums.length)break;
minLen = Math.min(minLen,j - i);
}
return minLen == Integer.MAX_VALUE ? 0 : minLen;
}
public int binarySearch(int low,int high,int target,int[] sum){
while(low <= high){
int mid = low + (high - low)/2;
int val = sum[mid];
if(val < target){
low = mid + 1;
}
else{
high = mid - 1;
}
}
return low;
}
}
还可以用two pointer做 O(N)
public class Solution {
/**
* @param nums: an array of integers
* @param s: an integer
* @return: an integer representing the minimum size of subarray
* Two Pointer 做法 因为都是正数 所以前移动指针j直到满足条件后 前移指针i一步 j不用从头开始 这类虽然是sub array sum但是并不需要计算Prefix Sum数组
*/
public int minimumSize(int[] nums, int s) {
if(nums == null || nums.length == 0)return -1;
int n = nums.length;
int rangeSum = 0;
int res = Integer.MAX_VALUE;
int j = 0;
for(int i = 0;i < n;i++){
while(j < n && rangeSum < s){
rangeSum += nums[j];
j++;
}
if(rangeSum >= s){
res = Math.min(res,j - i);
}
//move out nums[i]
rangeSum -= nums[i];
}
if(res == Integer.MAX_VALUE)return -1;
return res;
}
}
302. Smallest Rectangle Enclosing Black Pixels
一开始看到第一个想到的是用DFS然后记录 实际上根本不用检查所有的格子 只要利用好所给的坐标就好 在行上向左右扫射 扫到最左和最右 判断该点有没有“1”不是看本身是不是1 而是看它所在的列有没有1（单独列出一个函数）这里写函数有一定技巧 比如我们可以用一个Boolean变量记录 是行还是列！