public int searchFloor(int[] nums, int target){
int lo = 0, hi = nums.length-1;
while(lo < hi){
int mid = lo + (hi-lo)/2;
if(nums[mid] >= target) hi = mid;
else lo = mid + 1;
}
return nums[hi] != target ? -1 : hi;
}
public int searchCeiling(int[] nums, int target){
int lo = 0, hi = nums.length-1;
while(lo + 1< hi){
int mid = lo + (hi-lo)/2;
if(nums[mid] <= target) lo = mid;
else hi = mid-1;
}
if(nums[hi] == target) return hi;
return nums[lo] == target? lo:-1;
}
300. Longest Increasing Subsequence
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length+1];
if(nums.length==0) return 0;
int len = 1;dp[1] = nums[0];
for(int i = 1; i < nums.length; i++){
//find left most position that store number bigger or equal
//floorSearch
int idx = floorBinarySearch(dp,1,len,nums[i]);
dp[idx] = nums[i];
len = Math.max(idx,len);
}
return len;
}
public int floorBinarySearch(int[] dp,int lo,int hi, int n){
while(lo < hi){
int mid = lo + (hi-lo)/2;
if(dp[mid] >= n) hi = mid;
else lo = mid + 1;
}
if(dp[hi] < n) return hi+1;
return hi;
}
18. 230. Kth Smallest Element in a BST
while(root!=null){
int left = leftCount(root.left);
if(left == k-1) return root.val;
else if( left < k-1){root = root.right;k=k-left-1;}
else if (left > k-1){root = root.left;}
}
return 0;
}
public int leftCount(TreeNode root){
if(root == null) return 0;
return leftCount(root.left) + leftCount(root.right) +1;
}
19.378. Kth Smallest Element in a Sorted Matrix
1.Use heap to do it
class Node implements Comparable<Node>{
int x ;
int y;
int val;
public Node(int x, int y,int val){
this.x = x;this.y = y;this.val = val;
}
public int compareTo(Node n){
return Integer.compare(this.val,n.val);
}
}
public int kthSmallest(int[][] matrix, int k) {
int m = matrix.length;
if(m == 0) return 0;
int n = matrix[0].length;
PriorityQueue<Node> minHeap = new PriorityQueue<>();
for(int i = 0;i < n; i++){
Node node = new Node(0,i,matrix[0][i]);
minHeap.offer(node);
}
while(--k>0){
Node node = minHeap.poll();
if(node.x+1< m){
minHeap.offer(new Node(node.x+1,node.y,matrix[node.x+1][node.y]));
}
}
return minHeap.poll().val;
}
2. Binary Search
Because the loop invariant is
left<=Solution<=right. The moment it quits the loop, we also know another condition is true: left>=right.left<=Solution<=right and left>=right means left==Solution==right. class Solution
{
public:
int kthSmallest(vector<vector<int>>& matrix, int k)
{
int n = matrix.size();
int le = matrix[0][0], ri = matrix[n - 1][n - 1];
int mid = 0;
while (le < ri)
{
mid = le + (ri-le)/2;
int num = 0;
for (int i = 0; i < n; i++)
{
int pos = upper_bound(matrix[i].begin(), matrix[i].end(), mid) - matrix[i].begin();
num += pos;
}
if (num < k)
{
le = mid + 1;
}
else
{
ri = mid;
}
}
return le;
}
};
174 Dungeon Game
1. pick a simple path through the dungeon to obtain an upperbound
2.use a small number which is impossible to come back alive from as lowerbound
3.Binary search looking for the smallest starting health which we survive from.
Invariant we maintain is lowerbound dies and upperbound survives
public:
int calculateMinimumHP(vector<vector<int> > &dungeon) {
int N = dungeon.size();
int M = dungeon[0].size();
// just pick a simple path through the dungeon to obtain an upperbound
int lowerbound = 0;
int upperbound = 1;
for (int i = 0; i < M; i++) {
int val = dungeon[0][i];
if (val < 0) upperbound += (-val);
}
for (int i = 0; i < N; i++) {
int val = dungeon[i][M - 1];
if (val < 0) upperbound += (-val);
}
// A number so small impossible to come back alive from
static const int64_t dead = numeric_limits<int64_t>::min() / 3;
// Binary search looking for the smallest starting health which we
// survive from. Invariant we maintain is lowerbound dies and
// upperbound survives
while (lowerbound < upperbound - 1) {
int mid = (upperbound - lowerbound) / 2 + lowerbound;
// create a buffer N + 1 and M + 1 size so we have sentinal values
// padding the first row and column.
auto cur_health = vector<vector<int64_t> >(N + 1);
for (int n = 0; n <= N; n++) {
cur_health[n].resize(M + 1, dead);
}
// Seed in our starting health
cur_health[0][1] = cur_health[1][0] = mid;
for (int n = 1; n <= N; n++) {
for (int m = 1; m <= M; m++) {
cur_health[n][m] = max(cur_health[n-1][m], cur_health[n][m-1]) + dungeon[n-1][m-1];
if (cur_health[n][m] < 1) {
// Once we are dead, ensure we stay dead
cur_health[n][m] = dead;
}
}
}
// If we have positive health at the end we survived!
if (cur_health[N][M] > 0) {
upperbound = mid;
} else {
lowerbound = mid;
}
}
return upperbound;
}
}; public int hIndex(int[] citations) {
int lo = 0, n =citations.length ,hi = n-1, mid =0,max = 0;
while(lo <= hi){
mid = lo + (hi - lo)/2;
if(citations[mid]==n-mid){
return n-mid;
}else if(citations[mid]>n-mid){
max = Math.max(max,n-mid);
hi = mid - 1;
}else{
max = Math.max(max,citations[mid]);
lo = mid + 1;
}
}
return max;
}
436. Find Right Interval
find smallest i2.end > i1.start
sort< start,index>, and binary search on it to find the right start
find smallest i2.end > i1.start
sort< start,index>, and binary search on it to find the right start
public int[] findRightInterval(Interval[] intervals) {
int n = intervals.length;
int[] ans = new int[n];
if(n == 0) return ans;
//record index
TreeMap<Integer,Integer> map = new TreeMap<>();
for(int i = 0; i < n; i++) map.put(intervals[i].start,i);
for(int i = 0; i < n; i++){
Map.Entry e = map.ceilingEntry(intervals[i].end);
if(e!=null){
ans[i] =(int) e.getValue();
}else{
ans[i] = -1;
}
}
return ans;
}
270. Closest Binary Search Tree Value
public int closestValue(TreeNode root, double target) {
int ret = root.val;
while(root != null){
if(Math.abs(target - root.val) < Math.abs(target - ret)){
ret = root.val;
}
root = root.val > target? root.left: root.right;
}
return ret;
} public int arrangeCoins(int n) {
if(n <= 0) return 0;
long lo = 1, hi = n;
while(lo + 1< hi){
long mid = lo + (hi - lo) / 2;
if((1+mid)*mid/2 == n) return (int)mid;
else if ((1+mid)*mid/2 < n) lo = mid;
else hi = mid;
}
if((1+hi)*hi/2 <= n) return (int)hi;
return (int) lo;
}
354. Russian Doll Envelopes
Smallest Rectangle Enclosing Black Pixels
363. Max Sum of Rectangle No Larger Than K
https://leetcode.com/problems/max-sum-of-sub-matrix-no-larger-than-k/
没有评论:
发表评论