Common

经典算法

堆排序

构建大根堆(升序排序)或者小根堆(降序排序).
总体思路:

1. 构建大根堆, 从最后一个非叶子节点(2*length-1)开始处理, (叶子节点没有子节点了, 所以从最后一个非叶子节点开始)
2. 将第一个元素(最大元素)与最后一个元素交换
3. 将前面元素再进行调整, 保证还是一个大根堆
4. 重复2.3步骤知道数组有序

调整算法思路:

1. 先比较左右子树的大小, index指向最大的那个

2. 然后比较index和根节点, 如果index>根节点, 那么交换index和根节点的位置, 否则退出循环, 已经是一个大根堆.保证这三个节点是一个大根堆, 然后再处理下面的元素(经过交换后, 根节点可能还比子节点小, 让根节点一直下沉), i指向根节点(根节点经过交换后可能在左子树或者在右子树上)

   //Heap sort
    public static void heapSort(int[] nums){
        //首先构造大根堆, 从最后一个非叶子节点开始,length/2-1
        for (int i=nums.length/2-1;i>=0;i--){
            adjust(nums,i,nums.length);
        }
        //将大根堆的第一个元素(最大元素)于最后一个元素交换, 然后对前n-1个元素再进行调整
        for (int i=nums.length-1;i>0;i--){
            int temp=nums[i];
            nums[i]=nums[0];
            nums[0]=temp;
            adjust(nums,0, i);
        }
    }
    //Heap_sort's adjust function
    public  static void adjust(int[] nums,int i,int length){
        int temp=nums[i];//先用一个临时变量保存根节点
        for (int index=2*i+1;index<length;index=index*2+1){//index指向左子树
            if (index+1<length&&nums[index+1]>nums[index]){//比较左右节点的大小
                index++;   //右子树更大, index*2+2, 指向右子树
            }
            if (nums[index]>t){//子树比父节点更大
                nums[i]=nums[index];
                i=index;
            }else {
                break;
            }
        }
        //最后进行赋值, 优化
        nums[i]=temp;
    }

   42.接雨水

   
   方法一:
   先找到中间最高的柱子, 然后分别从两边向最高的柱子遍历. 最高柱子左边的柱子一定比它矮, 那么只记录左边柱子的最大值, 遍历到第i个柱子的时候, 与它左边最高的柱子比较, 如果比左边最高柱子矮, 那么表示可以接到水, 那么就用最高柱子-第i个柱子, 加到总数中, 否则那么第i个柱子就是左边最高的柱子. 同样的右边的遍历规则也是如此

   class Solution {
    public int trap(int[] height) {
        int max_height=0,index=0;
        int sum=0;
        //求出中间的最大高度
        for (int i=0;i<height.length;i++) {
            if (height[i]>max_height){
                max_height=height[i];
                index=i;
            }
        }
        //从左往右遍历
        int temp=0;
        for (int i=0;i<index;i++){
            if (height[i]>temp){
                temp=height[i];
            }else {
                sum+=temp-height[i];
            }
        }
        temp=0;
        for (int i=height.length-1;i>index;i--){
            if (height[i]>temp){
                temp=height[i];
            }else {
                sum+=temp-height[i];
            }
        }
        return sum;
    }
   }

   方法二:
   利用栈, 如下图所示
   
   如果第i个柱子比栈顶的柱子高, 那么说明栈顶的柱子可能接到水, 将其出栈, 然后再观察栈顶的柱子,如果没有柱子了, 说明左边没有比第一次出栈的柱子高了, 那么这个柱子一定比第一次出栈的柱子高或者同样高, 那么算出栈顶柱子与第i个柱子的距离, 界限高度=两者谁的高度最小(木桶效应)-栈顶的柱子高度, 距离*界限高度 将其加入总和之中. 重复

   Stack<Integer> s = new Stack<>();
   int i=0,sum=0;
   while (i<height.length){
    //如果遍历到的柱子比栈顶的柱子高, 那么他们中间就可以储存水
    while(!s.isEmpty()&&height[i]>height[s.peek()]){
        int index_temp=s.pop();//将栈顶元素出栈
        //如果左边没有了元素,表示不能接水
        if(s.isEmpty()){
            break;
        }
        int left=s.peek();
        int distance=i-left-1;//
        sum+=distance*(Math.min(height[left],height[i])-height[index_temp]);
    }
    s.push(i++);
   }
   return sum;

54.螺旋矩阵

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        int row_length=matrix.length;
        int col_length=matrix[0].length;
        boolean[][] flag=new boolean[row_length][col_length];
        int direction=0;//方向标志
        int i=0,j=0;
        List<Integer> list=new ArrayList<>();
        while(!flag[i][j]){
            list.add(matrix[i][j]);
            flag[i][j]=true;
            switch (direction){
                case 0:
                    if(j+1>=col_length||flag[i][j+1]==true){ //超过右边界, 或者下一个元素遍历过
                        direction=(direction+1)%4;
                        i++;
                    }else{
                        j++;
                    }
                    break;
                case 1:
                    if(i+1>=row_length||flag[i+1][j]==true){ 
                        direction=(direction+1)%4;
                        j--;
                    }else{
                        i++;
                    }
                    break;
                case 2:
                    if(j-1<0||flag[i][j-1]==true){ 
                        direction=(direction+1)%4;
                        i--;
                    }else{
                        j--;
                    }
                    break;
                case 3:
                    if(i-1<0||flag[i-1][j]==true){ 
                        direction=(direction+1)%4;
                        j++;
                    }else{
                        i--;
                    }
                    break;
            }
            if(i<0||j<0||i>=row_length||j>=col_length||flag[i][j]==true){
                break;
            }
        }
        return list;
    }
}

704.二分查找

class Solution {
    public int search(int[] nums, int target) {
        int left=0,right=nums.length-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(nums[mid]==target){
                return mid;
            }else if(nums[mid]>target){
                right=mid-1;
            }else{
                left=mid+1;
            }
        }
        return -1;
    }
}

注意循环中的判断条件, 有等号

415.字符串相加

class Solution {
    public String addStrings(String num1, String num2) {
        StringBuilder sb = new StringBuilder();
        int carry = 0, i = num1.length()-1, j = num2.length()-1;
        while(i >= 0 || j >= 0 || carry != 0){
            //这里i和j要判断是否大于等于0, 因为他们其中之一可能会小于0.
            if(i>=0) carry += num1.charAt(i--)-'0';
            if(j>=0) carry += num2.charAt(j--)-'0';
            sb.append(carry%10);
            carry /= 10;
        }
        return sb.reverse().toString();
    }
}

69.x的平方根

利用二分法, 对于结果的整数部分k, 满足k2<=x, 那么我们就可以利用二分法来找结果, 如果mid2>x, 那么下界就等于mid, 反之同样的到里, 知道上界和下界的差值小于1, 算法结束, 因为一个数的平方根只会在两个相邻的整数之间

class Solution {
    public int mySqrt(int x) {
        if(x==1){
            return 1;
        }
        int right=x;
        int left=0;
        while(right-left>1){
            int mid=left+(right-left)/2;
            if(mid>x/mid){
                //注意这里
                right=mid;
            }else{
                //注意这里
                left=mid;
            }
        }
        return left;
    }
}

4.寻找两个正序数字的中位数

就是找第k个大的数
主要思路：要找到第 k (k>1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较
这里的 “/“ 表示整除
nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个
nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个
取 pivot = min(pivot1, pivot2)，两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个
这样 pivot 本身最大也只能是第 k-1 小的元素
如果 pivot = pivot1，那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 “删除”，剩下的作为新的 nums1 数组
如果 pivot = pivot2，那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 “删除”，剩下的作为新的 nums2 数组
* 由于我们 “删除” 了一些元素（这些元素都比第 k 小的元素要小），因此需要修改 k 的值，减去删除的数的个数

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length1 = nums1.length, length2 = nums2.length;
        int totalLength = length1 + length2;
        //如果是奇数, 那么求得的是一个数
        if (totalLength % 2 == 1) {
            int midIndex = totalLength / 2;
            //下标从0开始, 所以是要+1, 第1大, 第2大...的=数
            double median = getKthElement(nums1, nums2, midIndex + 1);
            return median;
        } else {
            int midIndex1 = totalLength / 2 - 1, midIndex2 = totalLength / 2;
            double median = (getKthElement(nums1, nums2, midIndex1 + 1) + getKthElement(nums1, nums2, midIndex2 + 1)) / 2.0;
            return median;
        }
    }
    //求第K大的数
    public int getKthElement(int[] nums1, int[] nums2, int k) {
        int length1 = nums1.length, length2 = nums2.length;
        int index1 = 0, index2 = 0;
        int kthElement = 0;
        while (true) {
            // 边界情况
            //如果nums1到头了, 说明nums2中的元素都比nums1大, 去nums2中寻找
            if (index1 == length1) {
                return nums2[index2 + k - 1];
            }
            if (index2 == length2) {
                return nums1[index1 + k - 1];
            }
            if (k == 1) {
                //求第1大的元素, 那么直接返回两个数组较小的首位元素
                return Math.min(nums1[index1], nums2[index2]);
            }
            // 正常情况
            int half = k / 2;
            int newIndex1 = Math.min(index1 + half, length1) - 1;
            int newIndex2 = Math.min(index2 + half, length2) - 1;
            int pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2];
            if (pivot1 <= pivot2) {
                //nums1前面的(newIndex1-index1+1)个元素不可能是第K大的元素, 所以k减去相应的数目.
                k -= (newIndex1 - index1 + 1);
                index1 = newIndex1 + 1;
            } else {
                k -= (newIndex2 - index2 + 1);
                index2 = newIndex2 + 1;
            }
        }
    }
}

8.字符串转换整数(atoi)

class Solution {
    public int myAtoi(String s) {
        char[] arr=s.toLowerCase().toCharArray();
        int i=0;
        for(;i<arr.length;i++) {
            if(arr[i]!=' ') {
                break;
            }
        }
        boolean flag=false;
        if(i==arr.length||(arr[i]>='a'&&arr[i]<='z')||arr[i]=='.') {
            return 0;
        }
        if(arr[i]=='-') {
            flag=true;
            i++;
        }else if(arr[i]=='+'){
            flag=false;
            i++;
        }
        int sum=0;
        //sum=sum*10+digit>Integer.MAX_VALUE
        //sum>(Integer.MAX_VALUE-digit)/10,循环终止
        for(;i<arr.length&&arr[i]>='0'&&arr[i]<='9';i++) {
            if(sum>(Integer.MAX_VALUE-(arr[i]-'0'))/10) {
                if(flag) {
                    return Integer.MIN_VALUE;
                }else {
                    return Integer.MAX_VALUE;
                }
            }else {
                sum=sum*10+(arr[i]-'0');
            }
        }
        return flag? -sum:sum;
    }
}

41.缺失的第一个正数

如果没有第二行的限制, 其实很简单, 但是有了限制, 先否定了排序,因为时间复杂度, 然后否定了哈希数组或者其他的数组, 所以只能利用原来的数组进行操作.
长度为N的数组, 没有出现的最小正整数只可能出现在[1,N+1]中, 因为[1,N]都出现了, 那么最小的正整数就是N+1, 如果[1,N]有没出现的, 那么最小的正整数就是在[1,N]中了.
遍历元素的算法如下:

• 先将数组中小于0的元素设为N+1的数
• 再将数组中<=N的数 对应下标-1(数组从0开始)的数置为负数, 表示遍历的数出现过, 如果此位置的数已经是负数, 那么不动它

• 从头遍历数组, 如果该数大于0, 那么表示不存在该下标, 那么就返回下标+1, 如果都小于0, 那么返回N+1

  class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            if (nums[i] <= 0) {
                nums[i] = n + 1;
            }
        }
        for (int i = 0; i < n; ++i) {
            int num = Math.abs(nums[i]);
            if (num <= n) {
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return n + 1;
    }
  }

  31.下一个排序

  
  下一个排列就是比当前排列大的最小排列组合.
  为了达到目标, 将左边的较小数与左边的较大数交换, 此时的排列比原排列大, 还要满足, 较小数尽可能的靠右, 较大数尽可能的小, 只比较小数大, 这样才能保证变大地幅度最小, 也就是前面说地最小排列.
  从后往前找较小值, 如果a[i]此时[a[i+1],a[n-1] ]为降序(因为 a[i]<a[i+1] ), 可以证明, 然后将其区间升序, 保证上升的幅度最小.

  class Solution {
    public void nextPermutation(int[] nums) {
        //先找最左的较小数, 从右往左找
        int left=0,right=nums.length-1,cur=nums.length-2;
        for (;cur>=0;cur--){
            if (nums[cur+1]>nums[cur]){
                left=cur;
                break;
            }
        }
        //如果存在, 否则说明数组为降序, 直接将其变为升序即可
        if (cur>=0){
            //在(left,n-1]中从后往前找到第一个比num[left]大的数, 即右边的较大数
            while(nums[right]<=nums[left]){
                right--;
            }
            //交换nums[left],nums[right]
            int temp=nums[left];
            nums[left]=nums[right];
            nums[right]=temp;
            //将(left,n-1]的数变为升序
            left++;
            right= nums.length-1;
        }
        while(left<right){
            int temp=nums[left];
            nums[left]=nums[right];
            nums[right]=temp;
            left++;
            right--;
        }
    }
  }

  151.颠倒字符串中的单词

  
  先去除字符串前后的空格，去除字符串中间的空格，将字符串整体翻装， 将单词反转

  class Solution {
    public String reverseWords(String s) {
        //去掉其中的多余空格
        s=s.trim();
        //正则表达式表示一个或者多个空格
        s=s.replaceAll("[\s]+"," ");
        char[] arr=s.toCharArray();
        //将整个字符串翻装
        revers(arr,0,arr.length-1);
        int cur=0;
        while(cur<arr.length){
            int k=cur;
            //将单词翻转
            while(k+1<arr.length&&arr[k+1]!=' '){
                k++;
            }
            revers(arr,cur,k);
            cur=k+2;
        }
        return new String(arr);
    }
    public void revers(char[] arr,int l,int r){
        while(l<r){
            char temp=arr[l];
            arr[l]=arr[r];
            arr[r]=temp;
            l++;
            r--;
        }
    }
  }

  239.滑动窗口最大值

  
  本来就是用的BF来解的, 每次算出窗口中的最大值, 但是超时了, 所以困难提题不能想的这么简单.
  利用到的是单调队列, 即队列中的数是单调递增或者递减的, 那么队列头上的值就是最大的值

其中利用到的单调队列, 其实并没有维护窗口中的全部元素, 而是维护了可能成为最大值的元素
新元素入队时, 与队尾的元素比较, 如果比队尾的元素大, 那么将队尾的元素出队, 这个元素与新入队的元素相比, 不可能成为最大的元素, 直到队尾的元素比新元素大或者等于新元素, 将新元素插到队尾.
窗口滑动后元素出队时, 就与队首元素比较, 因为队列是个单调队列, 队首元素是最大的元素, 如果移除的元素是队首的元素, 那么就将队首的元素出队, 如果与队首元素不相等, 那么就不用管.

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] result=new int[nums.length-k+1];
        deque deque = new deque();
        for (int i=0;i<k;i++){        //先将前k个元素入队
            deque.push(nums[i]);
        }
        result[0]=deque.peek();        //求出前k个元素的最大值
        for (int i=1;i+k-1<nums.length;i++){    //处理后面的元素
            deque.poll(nums[i-1]);        //将窗口移除的元素出队
            deque.push(nums[i+k-1]);    //将窗口新增的元素入队
            result[i]=deque.peek();        //返回队列中最大的值
        }
        return result;
    }
    class  deque{
        Deque<Integer> deque=new LinkedList<>();
        /*
            出队操作, 如果窗口移除的元素值等于队列头的值, 那么移除队列的值
         */
        public void poll(int val){
            if (!deque.isEmpty()&&deque.peek()==val){
                deque.poll();
            }
        }
        /*
            入队操作, 如果窗口新加入的值大于队列入口的值, 那么将入口元素弹出, 直到入口的元素大于新元素, 将其入队
         */
        void push(int val){
            while (!deque.isEmpty()&&deque.getLast()<val){
                deque.pollLast();
            }
            deque.addLast(val);
        }
        /*
            队列头的元素是最大的元素, 返回最大的元素
         */
        int peek(){
           return deque.peek();
        }
    }
}

76.最小覆盖子串

本题利用滑动窗口解决. left指向窗口的左边界, right指向窗口的右边界, 每次只移动一边.

1. 首先利用一个哈希表map_t表示字符串t中的字符, 键为字符, 值为字符出现的个数.
2. 用一个哈希表保存字符串s中的字符, 处理字符串s, 如果右指针指向的字符map_t中存在, 那么map_s中对应的元素个数加一, 这样一直移动右指针, 直到map_s中包含map_t中的全部元素, 且个数不能小于map_t中的个数, 此时右指针到左指针中包含了t字符串中的所有字符, 那么收缩左指针

3. 收缩左指针, 如果left<=right, 且map_s包含了map_t中的所有元素, 那么left++, 向右移动, 此时还需要几个变量来保存最小的窗口, 以及最小的窗口时left和right的值, 与最小值比较. left向右移动, 直到map_s不包含map_t中的元素, 然后右回到了第2步, 继续向右寻找能全部包含字符串t中的窗口

   class Solution {
    HashMap<Character, Integer> map_t = new HashMap<>();    //map_t来保存t的字符以及每个字符的个数
    HashMap<Character, Integer> map_s = new HashMap<>();
    public String minWindow(String s, String t) {
        //将t中de字符放入map_t中
        for (int i=0;i<t.length();i++){
            if (map_t.containsKey(t.charAt(i))){
                map_t.put(t.charAt(i),map_t.get(t.charAt(i))+1);
            }else{
                map_t.put(t.charAt(i),1);
            }
        }
        int left=0,right=-1,min_window=Integer.MAX_VALUE;//记录最小的子串长度
        int min_left=-1,min_right=-1;   //记录最小字串的位置
        while (right<s.length()){
            right++;
            if (right<s.length()&&map_t.containsKey(s.charAt(right))){  //map_t中包含此字符
                map_s.put(s.charAt(right),map_s.getOrDefault(s.charAt(right),0)+1);//有就个数加一,没有就添加
            }
            while (check()&&left<=right){  //如果map_s中包含了map_t中所有的字符,个数也一样, 那么收缩左边界
                if (right-left+1<min_window){
                    min_window=right-left+1;
                    min_right=right;
                    min_left=left;
                }
                if (map_t.containsKey(s.charAt(left))){ //如果map_t中包含左边界去除的元素,那么map_s中元素的值的对应减1
                    map_s.put(s.charAt(left),map_s.getOrDefault(s.charAt(left),0)-1);
                }
                left++;
            }
        }
        return min_window==Integer.MAX_VALUE? "":s.substring(min_left,min_right+1);
    }
    public boolean check(){        //检查map_s中是否包含map_t中所有的字符
        Iterator<Map.Entry<Character, Integer>> iterator = map_t.entrySet().iterator();
        while(iterator.hasNext()){
            Map.Entry<Character,Integer> entry = iterator.next();
            Character key = entry.getKey();
            Integer value=entry.getValue();
            if (map_s.getOrDefault(key,0)<value){    //如果map_s的某一个字符的个数小于map_t对应字符的个数, 那么返回错误
                return false;
            }
        }
        return true;
    }
   }

   下面的代码更加简介, 没有用到哈希表保存, 而是利用了数组, 将字符作为索引

   public class Solution {
    public String minWindow(String s, String t) {
        char[] cs = s.toCharArray();
        char[] ct = t.toCharArray();
        int[] a = new int[128];
        //字符对应数组的下标
        for(int ch : ct){
            a[ch]--;
        }
        int left = 0,right = 0,len=0;
        String res = "";
        while (right < s.length()){
            //右边界指向的字符对应的下标数+1, 表示右边界字符存入数组中,对应的数+1
            a[cs[right]]++;
            //如果a[cs[right]]<=0, 说明t中包含此字符
            if(a[cs[right]] <= 0){
                len++;
            }  
            while (len == t.length() && a[cs[left]] > 0){
                a[cs[left++]]--;
            }
            if(len == t.length()){
                if(res == "") 
                    res = s.substring(left,right+1);
                else if(res.length() > right-left+1){
                    res = s.substring(left,right+1);
                }
            }
            right++;
        }
        return res;
    }
   }

   20.有效的括号

   

   class Solution {
    public boolean isValid(String s) {
        int n = s.length();
        if (n % 2 == 1) {
            return false;
        }
        Map<Character, Character> pairs = new HashMap<Character, Character>() {{
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }};
        Deque<Character> stack = new LinkedList<Character>();
        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            if (pairs.containsKey(ch)) {
                if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
                    return false;
                }
                stack.pop();
            } else {
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }
   }

   1.两数之和
   
   利用哈希表降低复杂度, 将target-nums[i]放到哈希表中.

   class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; ++i) {
            if (hashtable.containsKey(target - nums[i])) {
                return new int[]{hashtable.get(target - nums[i]), i};
            }
            hashtable.put(nums[i], i);
        }
        return new int[0];
    }
   }

   15.三数之和

   
   先将数组排序, 然后利用双指针, 遍历, 还有一个外循环控制从左往右找到所有的三元组.

   class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        //首先对数组进行排序,利用希尔排序
        for(int gap=nums.length/2;gap>0;gap/=2){
            for(int i=gap;i<nums.length;i++){
                int temp=nums[i];
                while(i-gap>=0&&nums[i-gap]>temp){
                    nums[i]=nums[i-gap];
                    i-=gap;
                }
                nums[i]=temp;
            }
        }
        List<List<Integer>> list1=new ArrayList<>();
        //利用双指针
        for(int i=0;i<nums.length-1;i++){            //下标从左往右
            for(int l=i+1,r=nums.length-1;l<r;){
                if(nums[i]+nums[l]+nums[r]==0){
                    List<Integer> list2=new ArrayList<>();
                    list2.add(nums[i]);
                    list2.add(nums[l]);
                    list2.add(nums[r]);
                    list1.add(list2);
                    l++;
                    r--;
                }else if(nums[i]+nums[l]+nums[r]>0){
                    r--;
                }else{
                    l++;
                }
            }
        }
        return list1;
    }
   }

   215.数组中的第K个最大元素

   
   普通做法是, 利用快速排序, 将数组降序排好序, 返回下标为k-1的元素.
   但是快速排序的实质是将一个元素归位, 对于降序排序, 它的左边元素都比它大, 它右边的元素都比它小, 此时它的下标已经确定了为i, 我们只是关心第K大的元素, 它左边或者右边的元素并不关心, 如果i大于K-1, 说明它不是第K大的元素, 而是第i+1大的元素, 比K小, 所以要在它的左边去找, 左边的元素都比它大, 所以放弃右边的元素, 这样能加速找到.
   注意第9行加上了等于

   class Solution {
    int result=0;
    public int findKthLargest(int[] nums, int k) {
        fun(nums, 0, nums.length - 1, k);
        return result;
    }
    public void fun(int[] nums,int left,int right,int k){
        if (left<=right){
            int l=left,r=right;
            int temp=nums[l];
            //将大于nums[l]的元素和小于nums[l]的元素分别放到它的左右边, 利用快速排序的思想
            while (l<r){
                while(l<r&&nums[r]<=temp){      //降序排列
                    r--;
                }
                nums[l]=nums[r];
                while (l<r&&nums[l]>=temp){
                    l++;
                }
                nums[r]=nums[l];
            }
            nums[l]=temp;
            //如果nums[l]就是第k大的元素, 那么直接返回
            if (k-1==l){
                result=nums[l];
                return ;
            }else if(k-1>l){//如果第k大的元素在nums[l]的右边, 那么就到右边寻找
                fun(nums,l+1,right,k);
            }else {
                fun(nums,left,l-1,k);
            }
        }
    }
   }

   3.无重复字符的最长子串

   

   class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 哈希集合，记录每个字符是否出现过
        Set<Character> occ = new HashSet<Character>();
        int n = s.length();
        // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        int rk = -1, ans = 0;
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                // 左指针向右移动一格，移除一个字符
                occ.remove(s.charAt(i - 1));
            }
            while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
                // 不断地移动右指针
                occ.add(s.charAt(rk + 1));
                ++rk;
            }
            // 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = Math.max(ans, rk - i + 1);
        }
        return ans;
    }
   }

   155.最小栈

   
   两种方法， 一种是使用辅助栈， 栈中保存最小的元素， 第二种是将最小值一起保存在一个栈中。

   //第一种方法
   class MinStack {
    Stack<Integer> min_stack=new Stack<>();
    Stack<Integer> stack=new Stack<>();
    public MinStack() {
        min_stack.push(Integer.MAX_VALUE);
    }
    public void push(int val) {
        stack.push(val);
        min_stack.push(Math.min(min_stack.peek(),val));
    }
    public void pop() {
        stack.pop();
        min_stack.pop();
    }
    public int top() {
        return stack.peek();
    }
    public int getMin() {
        return min_stack.peek();
    }
   }
   //第二张方法
   class MinStack {
    Stack<Integer> stack=new Stack<>();
    /** initialize your data structure here. */
    public MinStack() {
    }
    public void push(int val) {
        if(stack.isEmpty()){
            stack.push(val);
            stack.push(val);
        }else{
            int temp=stack.peek();
            stack.push(val);
            if(temp<val)
                stack.push(temp);
            else
                stack.push(val);
        }
    }
    public void pop() {
        stack.pop();
        stack.pop();
    }
    public int top() {
        return stack.get(stack.size()-2);
    }
    public int getMin() {
        return stack.peek();
    }
   }

   32.最长有效括号

   
   先用栈处理一边字符串, 将其中的无效括号设为1, 有效括号设为0, 然后从中寻找最长连续0

   class Solution {
    public int longestValidParentheses(String s) {
       Stack<Integer> stack = new Stack<>();
        int[] flag = new int[s.length()];
        for (int i = 0; i < s.length(); i++) {
            //只将左括号入栈
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                //如果栈中为空, 那么此右括号无效
                if (stack.isEmpty()) {
                    flag[i] = 1;
                    //否则栈中只有左括号, 出栈一个左括号
                } else {
                    stack.pop();
                }
            }
        }
        //如果栈中还有括号, 那么都为无效的括号
        while (!stack.isEmpty()) {
            flag[stack.pop()] = 1;
        }
        int max_length = 0;
        int length = 0;
        for (int i = 0; i < flag.length; i++) {
            if (flag[i] == 1) {
                length = 0;
                continue;
            }
            length++;
            max_length = Math.max(length, max_length);
        }
        return max_length;
   }

   43.字符串相乘

   

   class Solution {
    public String multiply(String num1, String num2) {
        if(num1.equals("0")||num2.equals("0")){
            return "0";
        }
        int length_1=num1.length();
        int length_2=num2.length();
        String ans="0";
        for (int i=length_1-1;i>=0;i--){
            StringBuilder sub_sb = new StringBuilder();
            int carry=0;
            //需要将后面补零, 也就是将前面补零.
            for(int j=length_1-1;j>i;j--){
                sub_sb.append(0);
            }
            int int_num1=num1.charAt(i)-'0';
            for (int j=length_2-1;j>=0;j--){
                int int_num2=num2.charAt(j)-'0';
                int sub_result=int_num1*int_num2+carry;
                sub_sb.append(sub_result%10);
                carry=sub_result/10;
            }
            if (carry!=0){
                sub_sb.append(carry);
            }
            ans=addString(ans,sub_sb.reverse().toString());
        }
        return ans;
    }
    //将相乘后的字符串相加
    public String addString(String num1,String num2){
        int i=num1.length()-1,j=num2.length()-1,caryy=0;
        StringBuilder sb = new StringBuilder();
        while (i>=0||j>=0||caryy!=0){
            int x= i>=0? num1.charAt(i)-'0':0;
            int y= j>=0? num2.charAt(j)-'0':0;
            int result=x+y+caryy;
            sb.append(result%10);
            caryy=result/10;
            i--;
            j--;
        }
        return sb.reverse().toString();
    }
   }

   165.比较版本号

   
   先分割, 然后利用Integer.valueOf方法将每一组转为整数比较, 注意读题, 每个修改号都可以转为32位整数

   class Solution {
    public int compareVersion(String version1, String version2) {   
        String[] strings1 = version1.split("\\.");
        String[] strings2 = version2.split("\\.");
        int i=0;
        while (i<strings1.length&&i<strings2.length){
            int temp1=Integer.valueOf(strings1[i]);
            int temp2=Integer.valueOf(strings2[i]);
            if(temp1>temp2){
                return 1;
            }else if (temp1<temp2){
                return -1;
            }
            i++;
        }
        //string1已经遍历完成
        if(i==strings1.length){
            for (;i<strings2.length;i++) {
                if (Integer.valueOf(strings2[i])!=0){
                    return -1;
                }
            }
        }else {
            for (;i<strings1.length;i++) {
                if (Integer.valueOf(strings1[i])!=0){
                    return 1;
                }
            }
        }
        return 0;
    }
   }

   470.用Rand7()实现Rand10()

   

   class Solution extends SolBase {
    public int rand10() {
        //思路：使用ran7在[0，6]直接选一个数 使用ran7在[0，5]之间选一个数
        int a=rand7();int b=rand7();
        while(a==7) a=rand7();//a不能为7 必须为[0，6]这样才能保证奇偶都是1/2概率
        while(b>5) b=rand7();//b不能为5以上 因为一会可能要加5
        return ((a&1)==0? 0:5 )+b;//判断a奇偶性1/2 * b取值[0，5]之间1/5=1/10
    }
   }

   169.多数元素

   
   多数元素超过了n/2, 就从头开始遍历, 如果与target元素一样, 那么count+1, 否则count-1, 如果减到了0, 那么target等于下一个元素, 遍历完之后, target就指向多数元素.
   这种过程可以抽象为 大乱斗, 有很多的国家参加, 遇到自己的人, 人数+1, 如果遇到不是自己的人, 那么人数就-1, 默认一换一, 那么厮杀过后, 剩下的肯定是多数元素.

   class Solution {
    public int majorityElement(int[] nums) {
        int target=nums[0];
        int count=1;
        for(int i=1;i<nums.length;i++){
            if(nums[i]==target){
                count++;
            }else{
                count--;
                if(count==0){
                    target=nums[i+1];
                }
            }
        }
        return target;
    }
   }

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

   

   class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] result=new int[2];
        result[0]=-1;
        result[1]=-1;
        // //基础解法，从头开始遍历
        // for(int i=0;i<nums.length;i++){
        //     if(nums[i]==target){
        //         if(result[0]==-1){
        //             result[0]=i;
        //             result[1]=i;
        //         }else{
        //             result[1]=i;
        //         }
        //     }
        // }
        // return result;
        /**
            进阶，时间复杂度为O（logn）考虑二分法解决，查找左右边界
         */
        //true表示左边界
        result[0]=fun(nums,target,true);
        result[1]=fun(nums,target,false);
        return result;
    }
    public int fun(int[] nums,int target,boolean flag){
        int res=-1;
        int l=0,r=nums.length-1;
        while(l<=r){
            int mid=l+(r-l)/2;
            if(target>nums[mid]){
                l=mid+1;
            }else if(target<nums[mid]){
                r=mid-1;
            }else{
                res=mid;
                if(flag==true){//如果找到目标数, 如果是左边界, 那么往左继续查找
                    r=mid-1;
                }else{
                    l=mid+1;
                }
            }
        }
        return res;
    }
   }

   14.最长公共前缀

   

   public static String longestCommonPrefix(String[] strs) {
     //初始值等于第一个
     String s=strs[0];
     for(String string:strs){
         //如果遍历的字符串不以初始值开始, 那么初始值就从末尾减少一个, 直至以初始值开头
         while(!string.startsWith(s)){
             s=s.substring(0,s.length()-1);
         }
         if (!string.startsWith(s))
             break;
     }
     return s;
   }

   48.旋转图像

   

   class Solution {
      public void rotate(int[][] matrix) {
        //先水平反转
        for (int i=0;i<matrix.length/2;i++){
            for (int j=0;j<matrix[0].length;j++){
                int temp=matrix[i][j];
                matrix[i][j]=matrix[matrix.length-i-1][j];
                matrix[matrix.length-i-1][j]=temp;
            }
        }
        //然后对角线反转
        for (int i=0;i<matrix.length;i++){
            for (int j=0;j<i;j++){
                int temp=matrix[i][j];
                matrix[i][j]=matrix[j][i];
                matrix[j][i]=temp;
            }
        }
    }
   }

   128.最长连续序列

   
   时间复杂度是O（n），使用Array.sort()肯定是不行的，其利用的是快速排序和归并排序，时间复杂度都是nlogn，不符合。
   对于题目对时间复杂度有要求的，那么就用空间去换取时间，反之亦然。
   这里使用HashSet来保存其中的数组，注意第三行先要将nums数组转换为包装类，再转为set
   遍历到一个元素，那么就判断x，x+1，x+2……是否连续，这样复杂度还是O（n2），如果已知了x,x+1,x+2…x+y连续，当遍历到一个元素的时候，却重新从x+1，x+2…x+y开始匹配，得到的结果肯定没有从x开始枚举的结果好，所以当遇到一个元素m，如果m-1在set中不存在，则从m开始枚举，也就是说当m是连续数组中的第一个数时，才开始枚举。外层的复杂度为O（n），只有当一个数是连续序列中的第一个数时才进入内循环，所以每个数只会进入内存循环一次，因为如果一个数是某个连续序列中的数（不是首个元素），那么这个数跳过了。

   class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = Arrays.stream(nums).boxed().collect(Collectors.toSet());
        int max_length=0;
        for (Integer integer : set) {
            if (!set.contains(integer-1)){
                int temp=integer;
                int length=1;
                while (set.contains(temp+1)){
                    temp++;
                    length++;
                }
                max_length=Math.max(length,max_length);
            }
        }
        return max_length;
    }
   }

   153.寻找旋转排序数组中的最小值

   
   数组是旋转过的, 题目是要求O(logn)的时间复杂度, 那么就是二分法, 二分法对部分有序的数组同样有效的. 那么对于这道题, 要先找到无序的一半和有序的一半, 那么如何找到? 经过观察发现, 如果得到的中间元素比最右边的元素大, 那么说明右边时无序的, 左边是有序的, 这个可以很容易的发现, 那么找到了有序和无序的一半, 那么最小值在那一边, 一定是无序的那一边, 可以得到如下的算法, 注意第10行, right=mid, 返回的也是左边的元素

   class Solution {
    public int findMin(int[] nums) {
        int left=0,right=nums.length-1;
        while (left < right) {
            int mid=(left+right)/2;
            //表明中间的数比最右边的数大,那么右边是无序的,最小值在其中
            if (nums[mid]>nums[right]){
                 left=mid+1;
            }else {
                //可能当前元素nums[mid]就是最小的元素,不能是right=mid-1
                right=mid;
            }
        }
        return nums[left];
    }
   }

   227.基本计算器2

   
   用一个栈保存当前的结果, 如果是+那么就将后面的数字直接入栈, 如果是-那么就将num取反压栈, 如果是*|/那么就取栈顶元素与num相乘或者相除后入栈, 利用一个preSign来保存先前的一个符号, 根据先前的符号来决定num的

   class Solution {
    public int calculate(String s) {
        char[] chars = s.toCharArray();
        Stack<Integer> stack=new Stack<>();
        int num=0;
        char preSign='+';
        for (int i=0;i<chars.length;i++){
            //如果是一个数字, 那么就加上
            if (Character.isDigit(chars[i])){
                num=num*10+chars[i]-'0';
            }
            //如果是符号,或者是最后一位, 将前面的数字根据先前的符号压栈
            if (!Character.isDigit(chars[i])&&chars[i]!=' '||i== chars.length-1){
                switch (preSign){
                    case '+':
                        stack.push(num);
                        break;
                    case '-':
                        stack.push(-num);
                        break;
                    case '*':
                        //如果先前的符号是'*', 那么就将本位与栈顶元素相乘后入栈
                        stack.push(stack.pop()*num);
                        break;
                    case '/':
                        stack.push(stack.pop()/num);
                        break;
                }
                preSign=chars[i];
                num=0;
            }
        }
        int ans=0;
        while (!stack.isEmpty()){
            ans+=stack.pop();
        }
        return ans;
    }
   }

   468.验证IP地址

   

   class Solution {
    public String validIPAddress(String IP) {
        if (IP == null) {
            return "Neither";
        }
        String regex0 = "(\\d|[1-9]\\d|1\\d\\d|2[0-4]\\d|25[0-5])";
        String regexIPv4 = regex0 + "(\\." + regex0 + "){3}";
        String regex1 = "([\\da-fA-F]{1,4})";
        String regexIPv6 = regex1 + "(:" + regex1 + "){7}";
        String result = "Neither";
        if (IP.matches(regexIPv4)) {
            result = "IPv4";
        } else if (IP.matches(regexIPv6)) {
            result = "IPv6";
        }
        return result;
    }
   }

   "(\\d|[1-9]\\d|1\\d\\d|2[0-4]\\d|25[0-5])"依次匹配1位,2位,3位的子段
   String regexIPv4 = regex0 + "(\\." + regex0 + "){3}"有三个., 所以要分开写

   179.最大数

   
   自定义比较器, 比较s1+s2和s2+s1的大小

   class Solution {
    public String largestNumber(int[] nums) {
        int len_ = nums.length;
        String[] ss = new String[len_];
        for(int i=0; i<len_; i++){
            ss[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(ss,(o1,o2)->(o2 + o1).compareTo(o1 + o2));
        StringBuilder sb = new StringBuilder();
        for(String s : ss) sb.append(s);
        return sb.charAt(0) == '0' ? "0" : sb.toString();
    }
   }
   //自己写的
   public String largestNumber(int[] nums) {
    Integer[] integers = Arrays.stream(nums).boxed().toArray(Integer[]::new);
    Arrays.sort(integers,(i, j)->{
        String s1=String.valueOf(i);
        String s2=String.valueOf(j);
        int sum1=Integer.valueOf(s1+s2);
        int sum2=Integer.valueOf(s2+s1);
        return sum2-sum1;
    });
    StringBuilder stringBuilder = new StringBuilder();
    for (Integer num : integers) {
        stringBuilder.append(num);
    }
    return stringBuilder.charAt(0)=='0'? "0":stringBuilder.toString();
   }

   136. 只出现一次的数字