[数据结构与算法]力扣day08

31.下一个排列

思路很简单，题解也是一样的思路，先从后往前找到nums[j]>nums[j-1]，再在j到nums.length-1之中找到最小的那个nums[k]>nums[j-1]，交换顺序，j到nums.length再重新排序

    public void nextPermutation(int[] nums) {
        int n = nums.length;
        int k = n - 1;
        while (k - 1 >= 0 && nums[k - 1] >= nums[k]) k--;
        if (k == 0) {
            reverse(nums, 0, n - 1);
        } else {
            int u = k;
            while (u + 1 < n && nums[u + 1] > nums[k - 1]) u++;
            swap(nums, k - 1, u);
            reverse(nums, k, n - 1);
        }
    }
    void reverse(int[] nums, int a, int b) {
        int l = a, r = b;
        while (l < r) {
            swap(nums, l++, r--);
        }
    }
    void swap(int[] nums, int a, int b) {
        int c = nums[a];
        nums[a] = nums[b];
        nums[b] = c;
    }

32. 最长有效括号

这个括号()()是对的，(())也算对的，刚开始没读懂

  public static int longestValidParentheses(String s) {
        int max = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(-1);//方便计算最大值
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    max = Math.max(max, i - stack.peek());
                }
            }
        }
        return max;
    }

33. 搜索旋转排序数组

暴力法，复杂度O（n)

    public int search(int[] nums, int target) {
        int index = -1;
        for(int i=0; i<nums.length; i++){
            if(nums[i]==target){
                return i;
            }
        }
        return index;
    }

进阶，二分法

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

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

双指针问题。。哦不，要求复杂度为O(logn)，所以是二分查找问题
双指针：

public int[] searchRange(int[] nums, int target) {
        if(nums.length==0) {
            return new int[]{-1,-1};
        }
        //设置双指针
        int left=0,right=nums.length-1;
        int f1=0,f2=0;
        int[] res={-1,-1};
        while (left<=right){
            if(nums[left]==target&&f1==0){
                f1=1;
                res[0]=left;
            }else if(f1==0){
                left++;
            }
            if(nums[right]==target&&f2==0){
                f2=1;
                res[1]=right;
            }else if(f2==0){
                right--;
            }
            if(f1==1&&f2==1){
                break;
            }
        }
        return res;
    }

二分查找：

   public int[] searchRange(int[] nums, int target) {
        int find = searchRangeHelper(nums,target);
        if (find==-1){
            return new int[]{-1,-1};
        }
        int left =find-1;
        int right =find+1;
        while(left>=0 && nums[left]==target){
            left--;
        }
        while(right<nums.length && nums[right]==target){
            right++;
        }
        return new int[]{left+1,right-1};
    }
    private int searchRangeHelper(int[] nums,int target){
        int low =0;
        int high =nums.length-1;
        while(low<=high){
            int mid =low+(high-low)/2;
            int midValue =nums[mid];

            if(midValue>target){
                high =mid-1;
            }else if (midValue<target){
                low =mid+1;
            }else {
                return mid;
            }
        }
        return -1;
    }

36.有效的数独

题目还好理解，就是每一行每一列和每3x3个黑粗线分割的小方格里面数字都不能重复
这个大佬的代码很好理解，仿佛回到了中学时代

 public boolean isValidSudoku(char[][] board) {
        // 判断9行
        for(int i = 0; i < 9; i++){
            int[] judge = new int[9];
            for(int j = 0; j < 9; j++){
                int now = board[i][j] - '0';
                if(now >= 1 && now <= 9){
                    if(judge[now-1] != 0) return false;
                    judge[now-1] = 1;
                }
            }
        }
        // 判断9列
        for(int i = 0; i < 9; i++){
            int[] judge = new int[9];
            for(int j = 0; j < 9; j++){
                int now = board[j][i] - '0';
                if(now >= 1 && now <= 9){
                    if(judge[now-1] != 0) return false;
                    judge[now-1] = 1;
                }
            }
        }
        // 判断9块儿
        for(int sign = 0; sign < 9; sign++){
            int[] judge = new int[9];
            int f_i = (sign % 3) * 3;
            int f_j = (sign / 3) * 3;
            for(int i = f_i; i < f_i + 3; i++){
                for(int j = f_j; j < f_j + 3; j++){
                        int now = board[i][j] - '0';
                        if(now >= 1 && now <= 9){
                        if(judge[now-1] != 0) return false;
                        judge[now-1] = 1;
                    }
                }
            }
        }
        return true;
    }

我觉得这样刷下去做题没什么必要，后面还是挑一些能学会算法的刷一下，哎为了明年找个好实习，后面可以再补回来