soyo的跨机房部署、同城双活、异地多活、9个9高可用博客yuque笔记同步site

@Service
public class UserCacheService {
    private static final Map<Long, String> userCache = new HashMap<>();

    public void put(Long id, String name) {
        userCache.put(id, name); // HashMap 非线程安全
    }

    public String get(Long id) {
        return userCache.get(id);
    }
}

import org.springframework.beans.factory.FactoryBean;
import org.springframework.stereotype.Component;
import redis.clients.jedis.JedisPool;
import redis.clients.jedis.JedisPoolConfig;

@Component("redisClient")
public class RedisClientFactoryBean implements FactoryBean<JedisPool> {

    // 模拟配置，可以改成 @Value 注入 application.properties 里的值
    private String host = "localhost";
    private int port = 6379;

    @Override
    public JedisPool getObject() throws Exception {
        System.out.println("初始化 Redis 连接池...");
        JedisPoolConfig config = new JedisPoolConfig();
        config.setMaxTotal(10);
        return new JedisPool(config, host, port);
    }

    @Override
    public Class<?> getObjectType() {
        return JedisPool.class;
    }

    @Override
    public boolean isSingleton() {
        return true;
    }
}

import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.stereotype.Service;
import redis.clients.jedis.Jedis;
import redis.clients.jedis.JedisPool;

@Service
public class RedisService {

    @Autowired
    private JedisPool jedisPool; // 注意：注入的就是 getObject() 返回的 JedisPool

    public String get(String key) {
        try (Jedis jedis = jedisPool.getResource()) {
            return jedis.get(key);
        }
    }

    public void set(String key, String value) {
        try (Jedis jedis = jedisPool.getResource()) {
            jedis.set(key, value);
        }
    }
}

class Solution {
    public int maxSubArray(int[] nums) {
        if(nums.length == 1) return nums[0];
       int []preSum = getPreSum(nums); 
       //找最大的和，那么就找最小前缀和 不断更新
       //System.out.println(Arrays.toString(preSum));
       int minPreSum=0;
       int res=Integer.MIN_VALUE;;
       for(int i=1;i<=nums.length;i++){
          res = Math.max(res,preSum[i]-minPreSum);
          minPreSum = Math.min(preSum[i],minPreSum);
       }
       return res;
    }
    public int[] getPreSum(int []nums){
        int []res =new int[nums.length+1];
        res[0]=0;
        for(int i=1;i<=nums.length;i++){
            res[i]=nums[i-1]+res[i-1];
        }
        return res;
    }
}

class Solution {
    public int search(int[] nums, int target) {
        int l = 0;
        int r = nums.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            //如果 nums[mid] >= nums[l]，说明左半边有序,否则右半边有序
            //例如 [4,5,6,7,0,1,2]，如果 mid 在前半段，那 [l...mid] 一定是升序。
            //第一个if就起到寻找 有序区间的作用
            if (nums[mid] >= nums[l]) {
                //判断是否在这个左的单调区间内
                // l.......mid
                if (target >= nums[l] && target <= nums[mid]) {
                    r = mid - 1;
                } else
                    l = mid + 1;
            }
            
            else {
                //判断是否在这个右的单调区间内
                //// mid.......r
                if (target <= nums[r] && target >= nums[mid]) {
                    l = mid + 1;
                } else
                    r = mid - 1;
            }
        }
        return -1;
    }
}

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1=m-1;
        int p2=n-1;
        int p3=m+n-1;
        //  1 2 3 6 , 3 4 5
        while(p1>=0&&p2>=0){
            if(nums1[p1]>=nums2[p2]){
              nums1[p3]=nums1[p1];
              p1--;
            }
            else {
                nums1[p3]=nums2[p2];
                p2--;
            }
            p3--;
        }
        while(p2>=0){
            nums1[p3]=nums2[p2];
            p3--;
            p2--;
        }
        while(p1>=0){
            nums1[p3]=nums1[p1];
            p3--;
            p1--;
        }

    }
}

class Solution {
    public int maxProfit(int[] prices) {
        int res=0;
        //肯定是得选最低价的天买入
        int minPrice =Integer.MAX_VALUE;
        for(int i=0;i<prices.length;i++){
            res=Math.max(res,prices[i]-minPrice);
            minPrice=Math.min(minPrice,prices[i]);
        }
        return res;
    }
}

import java.util.*;

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        int m = matrix.length;        // 行数
        int n = matrix[0].length;     // 列数

        // 定义四个边界
        int up = 0, down = m - 1;
        int left = 0, right = n - 1;

        List<Integer> res = new ArrayList<>();

        // 循环条件：还没有遍历完整个矩阵
        while (left <= right && up <= down) {

            // 1. 从左到右，遍历上边界
            for (int i = left; i <= right && res.size() < m * n; i++) {
                res.add(matrix[up][i]);
            }

            // 2. 从上到下，遍历右边界（注意不包含 corner）
            for (int i = up + 1; i <= down - 1 && res.size() < m * n; i++) {
                res.add(matrix[i][right]);
            }

            // 3. 从右到左，遍历下边界
            for (int i = right; i >= left && res.size() < m * n; i--) {
                res.add(matrix[down][i]);
            }

            // 4. 从下到上，遍历左边界（注意不包含 corner）
            for (int i = down - 1; i >= up + 1 && res.size() < m * n; i--) {
                res.add(matrix[i][left]);
            }

            // 缩小边界，进入下一圈
            left++;
            right--;
            up++;
            down--;
        }

        return res;
    }
}

class Solution {
    public int[][] merge(int[][] intervals) {
        //排序
        //把情况进行一个合并
        //[2,5]
        //   [4,6]

        Arrays.sort(intervals,(iv1,iv2)->(iv1[0]-iv2[0]));
        List<int []> temp=new ArrayList<>();
        for(int []interval:intervals){
            int size=temp.size();
            //存在交集
            //执行合并逻辑
            //[  ]
            //  [    ]
            if(size>0&&interval[0]<=temp.get(size-1)[1]){
                temp.get(size-1)[1]=Math.max(interval[1],temp.get(size-1)[1]);
            }
            //无法合并就加入
            else temp.add(interval);


        }
        return temp.toArray(new int[temp.size()][2]);
    }
}

class Solution {
    public int trap(int[] height) {
        int leftMax=0;
        int rightMax=0;
        int r=height.length-1;
        int l=0;
        int res=0;
        while(l<r){
            leftMax=Math.max(leftMax,height[l]);
            rightMax=Math.max(rightMax,height[r]);
            //哪边小先计算哪边，因为木桶效应，装水取决于短的那边
            int water= leftMax<rightMax? leftMax-height[l++]:rightMax-height[r--];
            res+=water;
        }
        return res;
    }
}

class Solution {
    public double findMedianSortedArrays(int[] A, int[] B) {
        int m = A.length, n = B.length;
        // 保证在短数组上二分
        if (m > n) return findMedianSortedArrays(B, A);

        int left = 0, right = m;
        int halfLen = (m + n + 1) / 2;

        while (left <= right) {
            int i = (left + right) / 2;       // A 的划分位置
            int j = halfLen - i;              // B 的划分位置

            int A_left = (i == 0) ? Integer.MIN_VALUE : A[i-1];
            int A_right = (i == m) ? Integer.MAX_VALUE : A[i];
            int B_left = (j == 0) ? Integer.MIN_VALUE : B[j-1];
            int B_right = (j == n) ? Integer.MAX_VALUE : B[j];

            if (A_left <= B_right && B_left <= A_right) {
                // 找到正确划分
                int maxLeft = Math.max(A_left, B_left);
                if ((m + n) % 2 == 1) return maxLeft;
                int minRight = Math.min(A_right, B_right);
                return (maxLeft + minRight) / 2.0;
            } 
            else if (A_left > B_right) right = i - 1; // i 太大
            else left = i + 1;                        // i 太小
        }
        return 0.0;
    }
}

class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length;

        // 第一步：从右向左找到第一个小于右侧相邻数字的数 nums[i]
        int i = n - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }

        // 如果找到了，进入第二步；否则跳过第二步，反转整个数组
        if (i >= 0) {
            // 第二步：从右向左找到 nums[i] 右边最小的大于 nums[i] 的数 nums[j]
            int j = n - 1;
            while (nums[j] <= nums[i]) {
                j--;
            }
            // 交换 nums[i] 和 nums[j]
            swap(nums, i, j);
        }

        // 第三步：反转 [i+1, n-1]（如果上面跳过第二步，此时 i = -1）
        reverse(nums, i + 1, n - 1);
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    private void reverse(int[] nums, int left, int right) {
        while (left < right) {
            swap(nums, left++, right--);
        }
    }
}

作者：灵茶山艾府
链接：https://leetcode.cn/problems/next-permutation/solutions/3621022/jiao-ni-cong-ling-kai-shi-si-kao-zhe-ti-9qfrq/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
    public int firstMissingPositive(int[] nums) {
        //先把元素交换到正确的位置上
        for (int i = 0; i < nums.length; i++) {
            //while循环在干什么？ 在寻找i这个位置上对的人！！！！ 
            //即 i 上应该坐着 i+1 即 nums[i] == nums[nums[i]-1】 => i = nums[i] - 1
            while (nums[i] > 0 
                   && nums[i] <= nums.length 
                   && nums[i] != nums[nums[i] - 1]) {
                
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
                
            }
        }
        //System.out.println(Arrays.toString(nums));
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return nums.length + 1;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        //[3,9,20,15,7]
        //[9,3,15,20,7]

        //1.从前序遍历里确定根节点
        //2.然后确立根节点在中序遍历的位置 index
        //3.切分中序数组，切出来左子树，右子树 eg：[9,3,15,20,7] -> [9] [15,20,7] [0,leftSize) leftSize [leftSize-1,n)
        // 4.切分前序数组，切出来左子树，右子树 eg：[3,9,20,15,7] -> [1,1+leftSize) [1+leftSize,n)
        //5.递归,求出left,right
        //6. return TreeNode (preOrder[0],left,right)
        int n = preorder.length;
        if (n == 0) {
            return null;
        }
        //
        int leftSize = getLeftSize(inorder, preorder[0]);
        int[] pre1 = Arrays.copyOfRange(preorder, 1, 1 + leftSize);
        int[] pre2 = Arrays.copyOfRange(preorder, 1 + leftSize, n);
        //[0 leftSize-1] [leftSize+1 n]
        int[] in1 = Arrays.copyOfRange(inorder, 0, leftSize);
        int[] in2 = Arrays.copyOfRange(inorder, 1 + leftSize, n);
        TreeNode left = buildTree(pre1, in1);
        TreeNode right = buildTree(pre2, in2);
        return new TreeNode(preorder[0], left, right);
    }

    public int getLeftSize(int[] order, int x) {
        for (int i = 0;; i++) {
            if (order[i] == x) {
                return i;
            }
        }
    }
}

               []                      (startIndex=0)
       /         |          \
     [1]        [2]        [3]         (分别选择 1,2,3)

    /   \        / \         \
[1,2] [1,3]  [2,3]  ···     ···        (继续往右走)

   /
[1,2,3]                         (完整路径)

class Solution {
    List<Integer> path = new ArrayList<>();
    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> subsets(int[] nums) {
        if (nums.length == 0) {
            return res;
        }
        dfs(nums, 0);
        return res;

    }
    //startIndex 的作用是控制
    //     startIndex 的本质是：
    
    // 限制递归的选择范围（只能往后，不回头）。
    
    // 保证子集不重复（避免 [2,1] 这种情况）。
    public void dfs(int[] nums, int startIndex) {
        res.add(new ArrayList<>(path));
        for (int i = startIndex; i < nums.length; i++) {
            path.add(nums[i]);
            dfs(nums, i + 1);
            path.remove(path.size() - 1);
        }
    }
}

class Solution {
    public int[] searchRange(int[] nums, int target) {
        //二分查找
        int leftBorder=leftBorder(nums,target);
        int rightBorder=rightBorder(nums,target);
        if(leftBorder==-1&&rightBorder==-1){
           return new int[]{leftBorder,rightBorder};
        }
        else 
        return new int[]{leftBorder+1,rightBorder-1};
        
    }
    public int leftBorder(int []nums,int target){
        int left=0;
        int right=nums.length-1;//左闭右闭
        int leftBorder=-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(nums[mid]==target){
               right=mid-1;
               leftBorder=right;
            }
            else if(nums[mid]<target){
                left=mid+1;
            }
            else if(nums[mid]>target){
                right=mid-1;
            }
        }
        return leftBorder;
    }
    public int rightBorder(int []nums,int target){
        int left=0;
        int right=nums.length-1;//左闭右闭
        int rightBorder=-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(nums[mid]==target){
               left=mid+1;
               rightBorder=left;
            }
            else if(nums[mid]<target){
                left=mid+1;
            }
            else if(nums[mid]>target){
                right=mid-1;
            }
        }
        return rightBorder;
    }
}

class Solution {
    List<Integer> path = new ArrayList<>();
    List<List<Integer>> res = new ArrayList<>();
    int sum =0;//用来记录cur和
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        dfs(candidates,target,0);
        return res;
    }
    public void dfs(int []candidates,int target,int startIndex){
        if(sum == target){
            res.add(new ArrayList<>(path));
            return ;
        }
        for(int i=startIndex;i<candidates.length;i++){
            if(sum > target) break;
            sum += candidates[i];
            path.add(candidates[i]);
            //这里的i表示 每个数可以重复选取
            dfs(candidates,target,i);
            sum -= path.remove(path.size()-1);
        }
    }
}

class Solution {
    int res = Integer.MAX_VALUE;
    int sum = 0;
    int n, m;
    int[][] dir = {{0,1},{1,0}}; // 只需要右和下

    public int minPathSum(int[][] grid) {
        n = grid.length;
        m = grid[0].length;
        dfs(grid, 0, 0, 0);
        return res;
    }

    public void dfs(int[][] grid, int x, int y, int currentSum) {
        if(x >= n || y >= m) return; // 越界
        currentSum += grid[x][y];
        if(x == n-1 && y == m-1) {
            res = Math.min(res, currentSum);
            return;
        }
        dfs(grid, x+1, y, currentSum); // 下
        dfs(grid, x, y+1, currentSum); // 右
    }
}

public int minPathSum(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;

        int[][] dp = new int[n][m];         // dp[i][j] = 到 (i,j) 的最小路径和
        String[][] path = new String[n][m]; // path[i][j] = 到 (i,j) 的路径字符串

        dp[0][0] = grid[0][0];
        path[0][0] = "(0,0)";

        // 初始化第一列
        for (int i = 1; i < n; i++) {
            dp[i][0] = dp[i-1][0] + grid[i][0];
            path[i][0] = path[i-1][0] + " -> (" + i + "," + 0 + ")";
        }

        // 初始化第一行
        for (int j = 1; j < m; j++) {
            dp[0][j] = dp[0][j-1] + grid[0][j];
            path[0][j] = path[0][j-1] + " -> (" + 0 + "," + j + ")";
        }

        // 填表
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                //下走 还是 左走
                if (dp[i-1][j] < dp[i][j-1]) {
                    dp[i][j] = dp[i-1][j] + grid[i][j];
                    path[i][j] = path[i-1][j] + " -> (" + i + "," + j + ")";
                } else {
                    dp[i][j] = dp[i][j-1] + grid[i][j];
                    path[i][j] = path[i][j-1] + " -> (" + i + "," + j + ")";
                }
            }
        }

        System.out.println("Path: " + path[n-1][m-1]);
        return dp[n-1][m-1];
    }

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        //去重
        for (int i : nums) {
            set.add(i);
        }
        //
        int res = 0;
        for (int x : set) {
            //已经找过的 就不要再找了
            if (set.contains(x - 1))
                continue;

            //寻找以x为开头的连续序列
            //x x+1 x+1+1 ....
            int cnt = 1;
            int nextX = x + 1;
            while (set.contains(nextX)) {
                nextX++;
                cnt++;
            }
            res = Math.max(res, cnt);
        }
        return res;
    }
}

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length - 1;
        int m = matrix[0].length - 1;
        //先交换行 上下倒置 第一行 和 第n 行 第二行 和 第 n-1行
        for (int i = 0; i <= n/2; i++) {
            int[] temp = matrix[i];
            matrix[i] = matrix[n - i];
            matrix[n - i] = temp;
        }
        //倒置 [i][j] 和 [j][i] 交换 对角想交换
        for (int i = 0; i <= n; i++) {
            for (int j = i + 1; j <= m; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
    }
}

class Solution {
    int area = 0;
    int res = 0;

    public int maxAreaOfIsland(int[][] grid) {
        //bfs or dfs

        //dfs
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                area = 0;
                dfs(grid, i, j);
                res = Math.max(res, area);
            }
        }
        return res;
    }

    public void dfs(int[][] grid, int x, int y) {
        if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length) {
            return;
        }
        if (grid[x][y] != 1) {
            return;
        }
        if (grid[x][y] == 1)
            area++;
        grid[x][y] = -1;

        dfs(grid, x + 1, y);
        dfs(grid, x, y + 1);
        dfs(grid, x, y - 1);
        dfs(grid, x - 1, y);
    }
}

// [-无穷 ...3 4 .... -无穷]
// 那么4的右侧一定有山峰
// mid = indexof(3)
if (nums[mid] < nums[mid + 1]) {
    l = mid + 1;
}
// [-无穷 ...4 3 .... -无穷]
// mid = indexof(3)
// 那么4的左侧一定有山峰
else {
    r = mid - 1;
}

class Solution {
    public int findPeakElement(int[] nums) {
        if (nums.length == 1)
            return 0;
        //两端
        if (nums[nums.length - 1] > nums[nums.length - 2]) {
            return nums.length - 1;
        }
        if (nums[0] > nums[1]) {
            return 0;
        }
        //二分法
        int l = 0;
        int r = nums.length - 1;
        while (l <= r) {
            int mid = (r + l) / 2;
            // [-无穷 ...3 4 .... -无穷]
            // 那么4的右侧一定有山峰
            // mid = indexof(3)
            if (nums[mid] < nums[mid + 1]) {
                l = mid + 1;
            }
            // [-无穷 ...4 3 .... -无穷]
            // mid = indexof(3)
            // 那么4的左侧一定有山峰
            else {
                r = mid - 1;
            }
        }
        return l;
    }
}

class Solution {
    public void moveZeroes(int[] nums) {
        //双指针
        int i0 = 0;// i0表示指向
        for (; i0 < nums.length; i0++) {
            if (nums[i0] == 0) {
                break;
            }
        }
        //[1,2,0,5,6,0,1]
        //
        for (int i = i0 + 1; i < nums.length; i++) {
            // 非0 元素与0元素交换
            if (nums[i] != 0) {
                // i0 i交换
                int temp = nums[i];
                nums[i] = nums[i0];
                nums[i0] = temp;
                // 交换过了 i0++
                i0++;
            }
        }
    }
}

class Solution {
    public int findMin(int[] nums) {
        //
        int l = 0;
        int r = nums.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            // [3,4,5,1,2]  5 > 2 最小值在右边
            // 为什么不能和nums[0] 比较? 因为无法区分 [1 2 3 4 5] [3,4,5,1,2] 这两种情况
            if (nums[mid] > nums[nums.length - 1]) {
                l = mid +1;
            } else {
                //[1 2 3 4 5] 最小值在右边
                r = mid -1;
            }
        }
        
        return nums[l];
    }
}

class Solution {
    int offset = -1;
    boolean[][] visited;

    public boolean exist(char[][] board, String word) {
        visited = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (dfs(board, i, j, word, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean dfs(char[][] board, int x, int y, String word, int offset) {
        if (x < 0 || y < 0 || x >= board.length || y >= board[0].length) {
            return false;
        }
        if (visited[x][y])
            return false;
        
        if (board[x][y] != word.charAt(offset)) {
            return false;
        }
        if (offset == word.length() - 1)
            return true;

        visited[x][y] = true;

        boolean found = dfs(board, x, y + 1, word, offset + 1) ||
                dfs(board, x + 1, y, word, offset + 1) ||
                dfs(board, x, y - 1, word, offset + 1) ||
                dfs(board, x - 1, y, word, offset + 1);
        //回溯
        visited[x][y] = false;
        return found;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode smlDummy = new ListNode();
        ListNode bigDummy = new ListNode();
        ListNode smlCur = smlDummy;
        ListNode bigCur = bigDummy;
        ListNode cur = head;
        while(cur!=null){
            if(cur.val < x){
                smlCur.next = cur;
                smlCur = smlCur.next;
            }
            else {
                bigCur.next = cur;
                bigCur = bigCur.next;
            }
            cur = cur.next;
        }
        smlCur.next = bigDummy.next;
        //重点
        bigCur.next = null;
        return smlDummy.next;
    }
}

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        //逆旋转旋转45
        int i = matrix.length - 1;
        int j = 0;
        while(i >= 0 && j < matrix[0].length){
            if(matrix[i][j] > target){
                //向左变小
                i--;
            }
            else if(matrix[i][j] < target){
                //向右变大
                j++;
            }
            else return true;
        }
        return false;
        
        
    }
}

class Solution {
    public int maxProduct(int[] nums) {
        int res = Integer.MIN_VALUE;
        for(int i = 0; i < nums.length; i++){
            int sub = 1;
            for(int j = i; j < nums.length; j++){
                sub = sub * nums[j];
                res = Math.max(res, sub);
            }
        }
        return res;
    }
}

class Solution {
    public int maxProduct(int[] nums) {
        int res = Integer.MIN_VALUE;
        //当前最大值，最小值
        int curMax = 1;
        int curMin = 1;
        for (int i = 0; i < nums.length; i++) {
            //如果为负数，就会触发 最大值变成最小值 最小值变成最大值
            //  1 2 -5 curMax = 2 curMin = 1
            //  curMax = 1 curMin = 2
            // curMax = -5 curMin = -10 
            if (nums[i] < 0) {
                int temp = curMax;
                curMax = curMin;
                curMin = temp;
            }
            curMax = Math.max(curMax * nums[i], nums[i]);
            curMin = Math.min(curMin * nums[i], nums[i]);
            if(nums[i] == 0){
                System.out.println("---0-");
                System.out.println(curMax);
                System.out.println(curMin);
                System.out.println("---0-");
            } 
            System.out.println(curMax);
            System.out.println(curMin);
            res = Math.max(curMax, res);
        }
        return res;
    }
}

class Solution {
    public int maxProduct(int[] nums) {
        int res = Integer.MIN_VALUE;
        //当前最大值，最小值
        int curMax = 1;
        int curMin = 1;
        //结果集的起始
        int start = 0, bestStart = 0, bestEnd = 0;

        for (int i = 0; i < nums.length; i++) {
            //如果为负数，就会触发 最大值变成最小值 最小值变成最大值
            //  1 2 -5 curMax = 2 curMin = 1
            //  curMax = 1 curMin = 2
            // curMax = -5 curMin = -10 
            if (nums[i] < 0) {
                int temp = curMax;
                curMax = curMin;
                curMin = temp;
            }
            if (curMax * nums[i] < nums[i]) {
                curMax = nums[i];
                start = i;
            } 
            else curMax = curMax * nums[i];
            
            curMin = Math.min(curMin * nums[i], nums[i]);
            
            if (res < curMax) {
                res = curMax;
                bestStart = start;
                bestEnd = i;
            }
        }
        System.out.println(Arrays.toString(Arrays.copyOfRange(nums, bestStart, bestEnd + 1)));
        return res;
    }
}

class Solution {
    public boolean canJump(int[] nums) {
        //i 是 人的位置，k 是路（即人能最远到达的地方），路就决定了 人能到达的位置 
        if(nums.length <= 1) return true;
        int k = 0;
        for(int i = 0; i <= k; i++){
            k = Math.max(k, nums[i] + i);
            if(k >= nums.length - 1){
                return true;
            }
        }
        return false;
    }
}

class Solution {
    public boolean canJump(int[] nums) {
        //
        if(nums.length <= 1){
            return true;
        }
        // 2 3 1 1 4
        // k表示 当前能跳到的最远位置
        int k = 0;
        for(int i = 0; i < nums.length; i++){
            if(i > k) return false;
            k = Math.max(k, i + nums[i]);
            System.out.println("当前下标：" + i + "最远位置：" + k);
        }
        return true;
    }
}

class Solution {
    public int jump(int[] nums) {
        if(nums.length <= 1) return nums.length - 1;
        //表示 走到i的所需的最小跳跃数
        int n = nums.length;
        int []dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 0; i < nums.length; i++){
            //状态方程
            int k = i + nums[i];
            if( k > nums.length - 1){
                k = nums.length - 1;
            }
            
            dp[k] = Math.min(dp[k], dp[i] + 1);
            for(int j = i + 1; j < k + 1; j++){
                dp[j] = Math.min(dp[k], dp[j]);
            }
            //Arrays.fill(dp,, dp[k]);
            System.out.println(Arrays.toString(dp));

        }
        //System.out.println(Arrays.toString(dp));
        return dp[n - 1];
    }
}

class Solution {
    public int jump(int[] nums) {
        int steps = 0;      // 总跳跃次数
        int end = 0;        // 当前这一步能跳到的最远边界
        int farthest = 0;   // 下一步能跳到的最远位置

        // 注意：最后一个位置不需要再跳，所以循环到 n-2
        for (int i = 0; i < nums.length - 1; i++) {
            // 更新下一步的最远可达位置
            farthest = Math.max(farthest, i + nums[i]);

            // 如果到达当前步的边界，就必须跳一次
            if (i == end) {
                steps++;
                end = farthest;  // 更新下一跳的边界
            }
        }
        return steps;
    }
}

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int[] newNums = Arrays.copyOfRange(nums, 0, nums.length);
        Arrays.sort(newNums);
        int l = 0;
        int r = -1;
        for(int i = 0;i < newNums.length; i++){
            if(newNums[i] != nums[i]){
                l = i;
                break;
            }
        }
        for(int i = newNums.length - 1;i >= 0; i--){
            if(newNums[i] != nums[i]){
                r = i;
                break;
            }
        }
        return r - l + 1 > 0? r - l + 1: 0;
    }
}

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int[] newNums = Arrays.copyOfRange(nums, 0, nums.length);
        sort(newNums);
        //System.out.println(Arrays.toString(newNums));
        int l = 0;
        int r = -1;
        for(int i = 0;i < newNums.length; i++){
            if(newNums[i] != nums[i]){
                l = i;
                break;
            }
        }
        for(int i = newNums.length - 1;i >= 0; i--){
            if(newNums[i] != nums[i]){
                r = i;
                break;
            }
        }
        return r - l + 1 > 0? r - l + 1: 0;
    }
    public void sort(int []nums){
        int MAX = 100000;
        int[] counter = new int[MAX * 2 + 4];
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for(int i: nums){
            min = Math.min(i, min);
            max = Math.max(i, max);
            counter[i + MAX]++;
        }
        int idx = 0;
        for(int i = min; i <= max; i++){
            int count = counter[i + MAX];
            while(count > 0){
                nums[idx] = i;
                count--;
                idx++;
            }
        }
    }
}

class Solution {
    public int leastInterval(char[] tasks, int n) {
        //贪心：很容易想到就是 先安排出现次数最多的任务，然后让这个任务之间的间隔刚好为N
        Map<Character,Integer> counter = new HashMap();
        for(char c: tasks){
            counter.put(c, counter.getOrDefault(c, 0) + 1);
        }
        int max = 0;
        char cMax = '*';
        for(char c: counter.keySet()){
            if(counter.get(c) > max) {
                cMax = c;
                max = counter.get(c);
            }
        }
        int bucketCnt = max;
        int cntOflastBucket = 0;
        for(char c: counter.keySet()){
            if(counter.get(c) == max) cntOflastBucket++;
        }
        //第一种情况：槽够用
        //eg：A：4 B：4 C：1 D: 1 n = 2 
        //A B C
        //A B D
        //A B *
        //A B
        //则 完成时间不能等于 长度

        //第二种情况：槽不够用
        //eg：A：4 B：4 C：4 D: 2 n = 2 
        //A B C D
        //A B C D
        //A B C 
        //A B C
        //则 完成时间等于 长度
        return Math.max((bucketCnt - 1) * (n + 1) + cntOflastBucket, tasks.length);
    }
}

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        for(int i = 0; i < nums.length; i++){
            System.out.println(i);
            System.out.println(nums[i] +"::::::::::::" + nums[nums[i] - 1]);
            while(nums[i] <= nums.length && nums[i] != nums[nums[i] - 1]){
                System.out.println(Arrays.toString(nums));
                System.out.println(i + ":::"+ (nums[i] -1));
                swap(nums, i, nums[i] - 1);
            }
        }
        //System.out.println(Arrays.toString(nums));
        List<Integer> res = new ArrayList();
        // 1 2 3
        for(int i = 0; i < nums.length; i++){
            if(nums[i] != i + 1)
                res.add(i + 1);
        }
        return res;
    }
    public void swap(int []nums, int i,int j){
        int temp  = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
//eg：[2,2,1] nums[i] == nums[nums[i] - 1] 表示当前数字是否在正确位置上，每次就会正确交换一次，这样子每个数字只会被遍历一次
// 0
// 2::::::::::::2
// 1
// 2::::::::::::2
// 2
// 1::::::::::::2
// [2, 2, 1]
// 2:::0

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        //先排序再插队
        //排序
        Arrays.sort(people,
            (a, b) -> {
                return  a[0] == b[0] ? a[1] - b[1] : b[0] - a[0];  
            }
        );
        List<int[]> res = new ArrayList();

        for(int []p: people) {
            System.out.println(Arrays.toString(p));
            //插队
            res.add(p[1], p);
        }
         System.out.println("////////////");
        for(int []p: res) {
            System.out.println(Arrays.toString(p));
        }
        return res.toArray(new int[people.length][2]);
    }
}

import java.util.*;

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] ans = new int[nums.length];
        Map<Integer, Integer> front = new HashMap<>();
        Map<Integer, Integer> back = new HashMap<>();

        // 前缀积
        for (int i = 0; i < nums.length; i++) {
            front.put(i, front.getOrDefault(i - 1, 1) * nums[i]);
        }

        // 后缀积
        for (int i = nums.length - 1; i >= 0; i--) {
            back.put(i, back.getOrDefault(i + 1, 1) * nums[i]);
        }

        // 最终结果
        for (int i = 0; i < nums.length; i++) {
            int left = front.getOrDefault(i - 1, 1);
            int right = back.getOrDefault(i + 1, 1);
            ans[i] = left * right;
        }

        return ans;
    }
}