每日5题Day7 - LeetCode 31 - 35

每一步向前都是向自己的梦想更近一步，坚持不懈，勇往直前！

第一题：31. 下一个排列 - 力扣（LeetCode）

注意这道题的处理逻辑，我们应该走最右边的数i开始，向左遍历找到小于他的数j，然后交换，一定要注意交换后右边序列（j所在位置的后一位）也要满足是升序（因为刚刚已经完成升序了，每次升一点，所有子序列就要满足是最小升序，如果看文字太抽象，请用[2,3,1]这个例子自行模拟）

class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        // 从右向左找到第一个降序的位置 i
        int i = n - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        // 如果找到了 i，从右向左找到第一个比 nums[i] 大的数字位置 j
        if (i >= 0) {
            int j = n - 1;
            while (j >= 0 && nums[j] <= nums[i]) {
                j--;
            }
            swap(nums, i, j); // 交换 nums[i] 和 nums[j]
        }
        // 将 i 右边的数字进行反转，使得右边变为最小的排列
        reverse(nums, i + 1, n - 1);
    }
    // 交换数组中的两个元素
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    // 反转数组中从 left 到 right 位置的元素
    private void reverse(int[] nums, int left, int right) {
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }
}

第二题：32. 最长有效括号 - 力扣（LeetCode）

class Solution {
    public int longestValidParentheses(String s) {
        // 一看到最长，要警觉，是不是可以使用dp了？
        // 用于记录最长有效括号子串的长度
        int maxans = 0;
        // 创建一个数组，用于记录以当前字符结尾的最长有效括号子串的长度
        int[] dp = new int[s.length()];
        for (int i = 1; i < s.length(); i++) {
            // 如果当前字符为右括号
            if (s.charAt(i) == ')') {
                // 如果前一个字符是左括号，形成了一对有效括号
                if (s.charAt(i - 1) == '(') {
                    // 更新以当前字符结尾的最长有效括号子串的长度
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                }
                // 如果前一个字符是右括号，需要判断是否能与之前的部分形成有效括号子串
                else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                    // 更新以当前字符结尾的最长有效括号子串的长度
                    dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                // 更新最长有效括号子串的长度
                maxans = Math.max(maxans, dp[i]);
            }
        }
        // 返回最长有效括号子串的长度
        return maxans;
    }
}

第三题：33. 搜索旋转排序数组 - 力扣（LeetCode）

class Solution {
    public int search(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1, mid = 0;
        while (lo <= hi) {
            mid = lo + (hi - lo) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            // 先根据 nums[mid] 与 nums[lo] 的关系判断 mid 是在左段还是右段
            if (nums[mid] >= nums[lo]) {
                // 再判断 target 是在 mid 的左边还是右边，从而调整左右边界 lo 和 hi
                if (target >= nums[lo] && target < nums[mid]) {
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            } else {
                if (target > nums[mid] && target <= nums[hi]) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
        }
        return -1;
    }
}

第四题：34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left = searchLeft(nums, target);
        int right = searchRight(nums, target);
        return new int[] { left, right };
    }
 
    public int searchLeft(int[] nums, int target) {
        // 寻找元素第一次出现的地方
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            // >= 的都要缩小 因为要找第一个元素
            if (nums[mid] >= target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        // right = left - 1
        // 如果存在答案 right是首选
        if (right >= 0 && right < nums.length && nums[right] == target) {
            return right;
        }
        if (left >= 0 && left < nums.length && nums[left] == target) {
            return left;
        }
        return -1;
    }
 
    public int searchRight(int[] nums, int target) {
        // 找最后一次出现
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            // <= 的都要更新 因为我们要找最后一个元素
            if (nums[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        // left = right + 1
        // 要找最后一次出现 如果有答案 优先找left
        if (left >= 0 && left < nums.length && nums[left] == target) {
            return left;
        }
        if (right >= 0 && right <= nums.length && nums[right] == target) {
            return right;
        }
        return -1;
    }
}

 第五题：35. 搜索插入位置 - 力扣（LeetCode）

class Solution {
    public int searchInsert(int[] nums, int target) {
        int n = nums.length;
        int left = 0, right = n - 1, ans = n;
        while (left <= right) {
            int mid = ((right - left) >> 1) + left;
            if (target <= nums[mid]) {
                //记录插入位置，其实和二分查找是一样的，不过多一个记录的过程
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}