模版

  1. //二分查找
  2. public static int binarySearch(int[] arr, int target) {
  3.     int left = 0;
  4.     int right = arr.length - 1;
  5.     while (left <= right) {
  6.         int mid = (left + right) >> 1 ;
  7.         if (target == arr[mid]) {
  8.             return mid;
  9.         }
  10.         if (arr[mid] > target) {
  11.             right = mid - 1;
  12.         } else {
  13.                left = mid + 1;
  14.         }
  15.     }
  16.     return -1;
  17. }
  18. //左区间查找
  19. //寻找左插入位置
  20. public int getLeft(int[] nums, int target) {
  21.     int left = 0;
  22.     int right = nums.length - 1;
  23.     while(left <= right) {
  24.         int mid = (left + right) >> 1;
  25.         if(nums[mid] >= target) {
  26.             right = mid - 1;
  27.         }else{
  28.             left = mid + 1;
  29.         }
  30.     }
  31.     return left;
  32. }

33 搜索旋转排序数组

  1. 输入：nums = [4,5,6,7,0,1,2], target = 0
  2. 输出：4
  1. class Solution {
  2.     public int search(int[] nums, int target) {
  3.         int n = nums.length;
  4.         if(n == 0) return -1;
  5.         if(n == 1) return target==nums[0]? 0: -1;
  6.         int l = 0;
  7.         int r = n-1;
  8.         while(l <= r) {
  9.             int mid = (l+r)>>1;
  10.             if(nums[mid] == target) return mid;
  11.             if(nums[mid] >= nums[0]) {
  12.                 if(target >= nums[0] && nums[mid] > target) {
  13.                     r = mid -1;
  14.                 }else{
  15.                     l = mid + 1;
  16.                 }
  17.             }else {
  18.                 if(target <= nums[n-1] && nums[mid] < target) {
  19.                     l = mid + 1;
  20.                 }else {
  21.                     r = mid - 1;
  22.                 }
  23.             }       
  24.         }
  25.         return -1;
  26.     }
  27. }

34 在排序数组中查找元素的第一个和最后一个位置

  1. 输入：nums = [5,7,7,8,8,10], target = 8
  1. class Solution {
  2.     int[] nums;
  3.     public int[] searchRange(int[] nums, int target) {
  4.         this.nums = nums;
  5.         int[] arr = new int[2];
  6.         arr[0] = -1;
  7.         arr[1] = -1;
  8.         if(nums.length == 0){
  9.             return arr;
  10.         } 
  11.         int res = get(target);
  12.         if(res > nums.length) return arr;
  13.         if(nums[res] == target ){
  14.             arr[0] = res;
  15.             arr[1] = get(target+1)-1;
  16.             return arr;
  17.         }
  19.         return arr;
  20.     }
  22.     public int get(int target){
  23.         int left = 0;
  24.         int right = nums.length-1;
  25.         while(left <= right) {
  26.             int mid = (left + right) >>1;
  27.             if(nums[mid] >= target) {
  28.                 right = mid - 1;
  29.             }else{
  30.                 left = mid + 1;
  31.             }
  32.         }
  33.         return left;
  34.     }
  35. }

69 X的平方根

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

class Solution {
    public int mySqrt(int x) {
        int left = 0;
        int right = x;
        int ans = -1;
        while(left <= right) {
            int mid = (left+right)>>1;
            if((long)mid * mid <= x) {
                left = mid + 1;
                ans = mid;
            }else {
                right = mid - 1;
            }
        }
        return ans;
    }
}

153 寻找旋转数组的最小值

输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

class Solution {
    public int findMin(int[] nums) {
        int low = 0;
        int high = nums.length - 1;
        while (low < high) {
            int pivot = low + (high - low) / 2;
            if (nums[pivot] < nums[high]) {
                high = pivot;
            } else {
                low = pivot + 1;
            }
        }
        return nums[low];
    }
}

162 寻找峰值

输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。

class Solution {
    public int findPeakElement(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = l + ((r - l) >> 1);
            if (nums[mid] < nums[mid+1]) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }
}

300 最长递增子序列

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

//dp
//dp[i] = max(dp[i], dp[j] + 1)
//dp[i]为每一位的最长递增数
class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        int res = 0;
        Arrays.fill(dp, 1);
        for(int i = 0; i < nums.length; i++) {
            for(int j = 0; j < i; j++) {
                if(nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                } 
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}
//dp+二分
//tails记录长度为i的序列的最大值
class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] tails = new int[nums.length];
        int res = 0;
        for(int num : nums) {
            int i = 0, j = res;
            while(i < j) {
                int mid = (i + j) / 2;
                if(tails[mid] < num){
                    i = mid + 1;
                }else{
                    j = mid
                }
            }
            tails[i] = num;
            if(res == j) res++;
        }
        return res;
    }
}

456 132模式

输入：nums = [3,1,4,2]
输出：true
解释：序列中有 1 个 132 模式的子序列： [1, 4, 2] 。

//单调栈
class Solution {
    public boolean find132pattern(int[] nums) {
       Deque<Integer> q = new ArrayDeque();
       int k = Integer.MIN_VALUE;
       for(int i = nums.length-1; i>=0; i--){
           if(nums[i] < k) return true;
           while(!q.isEmpty()&& q.peekLast() < nums[i]) {
               k = q.pollLast();
           }
           q.addLast(nums[i]);
       }
       return false;
    }

}