/**
 * @author 86153
 * @data 2021/7/23 12:42
 */
public class Question95 {
    public List<TreeNode> generateTrees(int n){
        return getAns(1,n);
    }

    public List<TreeNode> getAns(int start,int  end){
        ArrayList<TreeNode> ans = new ArrayList<>();
        // 该情况说明节点无左子树或者右子树
        if(start>end){
            ans.add(null);
            return ans;
        }
        if(start==end){
            TreeNode treeNode = new TreeNode(start);
            ans.add(treeNode);
            return ans;
        }

        //第一个for：所有的元素做根节点的情况（包括已经进入递归后，也可能根节点有多种情况)
        for(int i=start;i<=end;i++){
            // 递归得到所有的拼接情况
            List<TreeNode> leftTreeNodes = getAns(start,i-1);
            List<TreeNode> rightTreeNodes = getAns(i + 1, end);
            // 遍历得到所有的节点
            for (TreeNode leftTreeNode : leftTreeNodes) {
                for (TreeNode rightTreeNode : rightTreeNodes) {
                    TreeNode root = new TreeNode(i);
                    root.left=leftTreeNode;
                    root.right=rightTreeNode;
                    ans.add(root);
                }
            }
        }
        return ans;
    }
}

/**
 * @author 86153
 * @data 2021/7/28 19:44
 */
public class Question863 {
    public List<Integer> ans=new ArrayList<>();
    public HashMap<Integer,TreeNode> parents=new HashMap<>();
    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
        generateMap(root,null);
        recursion(target,null,0,k);
        return ans;
    }
    // 生成 key:二叉树节点值 -- value: 该节点值的父节点TreeNode

    public void generateMap(TreeNode root,TreeNode from){
        if(root==null){
            return;
        }
        parents.put(root.val,from);
        generateMap(root.left,root);
        generateMap(root.right,root);
    }
    // 回溯节点from
    public void recursion(TreeNode node,TreeNode from,int depth,int k){
        // 递归结束条件
        if(node==null){
            return ;
        }
        // 如果深度为K,则结果集添加该值
        if(depth==k){
            ans.add(node.val);
        }
        // 如果目前节点的左节点不是来自递归调用的节点，则往左节点递归
        if(node.left!=from){
            recursion(node.left,node,depth+1,k);
        }
        // 如果目前节点的右节点不是来自递归调用的节点，则往右节点递归
        if(node.right!=from){
            recursion(node.right,node,depth+1,k);
        }
        // 如果目前节点的父节点不是来自递归调用的节点，则向父节点递归
        if(parents.get(node.val)!=from){
            recursion(parents.get(node.val),node,depth+1,k);
        }
    }
}

// 用二维数组存储方向
    static final int[][] directions={{-1,0},{0,1},{1,0},{0,-1}};
    // 标记数组
    static boolean[][] visited;
    public static 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++){
                // 只要返回值为false, 则状态重置 depth重置为0
                if(dfs(board,word,i,j,0)){
                    return true;
                }
            }
        }
        return false;
    }
    public static boolean dfs(char[][] board,String word,int i,int j,int depth){
        if(depth==word.length()-1){
            return board[i][j]==word.charAt(depth);
        }
        if(board[i][j]==word.charAt(depth)){
            visited[i][j]=true;
            for (int[] direction : directions) {
                int changeX=direction[0]+i;
                int changeY=direction[1]+j;
                if(condition(board,changeX,changeY) && !visited[changeX][changeY]){
                    if(dfs(board,word,changeX,changeY,depth+1)){
                        return true;
                    }
                }
            }
            //四个方向遍历完成之后 标记重置
            visited[i][j]=false;
        }
        return false;
    }
    public static boolean condition(char[][] board,int i,int j){
        return i>=0 && i<board.length && j>=0 && j<board[0].length;
    }

static final int[][] directions={{-1,0},{0,1},{1,0},{0,-1}};
    public static void solve(char[][] board){
        int m=board[0].length;
        int n=board.length;
        //前两个for循环用来查找边界为O的元素  并以边界为O的点扩散查找与之间接或者直接相邻的元素
        for(int i=0;i<m;i++){
            dfs(board,0,i);
            dfs(board,n-1,i);
        }
        for(int j=1;j<n-1;j++){
            dfs(board,j,0);
            dfs(board,j,m-1);
        }

        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(board[i][j]=='A'){
                    board[i][j]='O';
                }else if(board[i][j]=='O'){
                    board[i][j]='X';
                }
            }
        }
    }

    public static void dfs(char[][] board,int i,int j){
        if(condition(board,i,j)){
            return;
        }
        board[i][j]='A';
        for (int[] direction : directions) {
            int changeX=direction[0]+i;
            int changeY=direction[1]+j;
            dfs(board,changeX,changeY);
        }
    }

    public static boolean condition(char[][] board,int i,int j){
        return i<0 || i>=board[0].length || j<0 || j>=board.length || board[i][j]!='O';
    }

static int[][] directions={{-1,0},{0,1},{1,0},{0,-1}};
    public void solve(char[][] board){
        int m=board.length;
        // 列数
        int n=board[0].length;
        Queue<int[]> queue=new LinkedList<>();

        // 前两个for循环遍历边界的O元素 将其坐标加入队列
        for(int i=0;i<m;i++){
            if(board[i][0]=='O'){
                board[i][0]='A';
                queue.offer(new int[]{i,0});
            }
            if(board[i][n-1]=='O'){
                board[i][n-1]='A';
                queue.offer(new int[]{i,n-1});
            }
        }


        for(int j=1;j<n-1;j++){
            if(board[0][j]=='O'){
                board[0][j]='A';
                queue.offer(new int[]{0,j});
            }
            if(board[m-1][j]=='O'){
                board[m-1][j]='A';
                queue.offer(new int[]{m-1,j});
            }
        }

        // 队列抛出元素 每抛出一个元素  先广度搜索其四周的元素是否为O  如果是  将O先加入队列当中
        // 此处注意区分广度和深度的区别
        while(!queue.isEmpty()){
            int[] point = queue.poll();
            int x=point[0];
            int y=point[1];
            for (int[] direction : directions) {
                int changeX=direction[0]+x;
                int changeY=direction[1]+y;
                if(condition(board,changeX,changeY)){
                    continue;
                }
                board[changeX][changeY]='A';
                queue.offer(new int[]{changeX,changeY});
            }
        }
        // 循环遍历  将A-》O  O->X
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(board[i][j]=='A'){
                    board[i][j]='O';
                }else if(board[i][j]=='O'){
                    board[i][j]='X';
                }
            }
        }
    }
    public boolean condition(char[][] board,int x,int y){
        return x<0 || x>=board.length || y<0 || y>=board[0].length || board[x][y]!='O';
    }

static int[][] directions={{-1,0},{0,1},{1,0},{0,-1}};
public int maxAreaOfIsland(int[][] grid) {
    int maxNum=0;
    int num=0;  
    Queue<int[]> queue=new LinkedList<>();
    //行
    int m=grid.length;
    int n=grid[0].length;
    
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(grid[i][j]==1){
                queue.offer(new int[]{i,j});
                grid[i][j]=0;
                while(!queue.isEmpty()){
                    int[] poll = queue.poll();
                    num++;
                    int x=poll[0];
                    int y=poll[1];
                    for (int[] direction : directions) {
                        int changeX=direction[0]+x;
                        int changeY=direction[1]+y;
                        if(condition(grid,changeX,changeY)){
                            if(grid[changeX][changeY]==1){
                                queue.offer(new int[]{changeX,changeY});
                                grid[changeX][changeY]=0;
                            }
                        }
                    }
                }
            }
            maxNum=Math.max(num,maxNum);
            num=0;
        }
    }
    return maxNum;
}
public boolean condition(int[][] grid,int i,int j){
    return i>=0 && i<grid.length && j>=0 && j<grid[0].length;
}

static final int[][] directions={{-1,0},{0,1},{1,0},{0,-1}};
static int maxNum=0;
public static int maxAreaOfIsland(int[][] grid) {
    //行
    int m=grid.length;
    int n=grid[0].length;
    int num=0;
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(grid[i][j]==1){
                num = dfs(grid, i, j, num);
                //搜索完毕之后  最大值
                maxNum= Math.max(num, maxNum);
                num=0;
            }
        }
    }
    return maxNum;
}
public static int dfs(int[][] grid,int i,int j,int num){
    if(grid[i][j]==0){
        return num;
    }
    num++;
    grid[i][j]=0;
    for (int[] direction : directions) {
        int changeX=direction[0]+i;
        int changeY=direction[1]+j;
        if(condition(grid,changeX,changeY))
            num=dfs(grid,changeX,changeY,num);
    }
    return num;
}
public static boolean condition(int[][] grid,int x,int y){
    return x>=0 && x<grid.length && y>=0 && y<grid[0].length;
}

// 双指针 快指针走两步 慢指针走一步
public static boolean circularArrayLoop(int[] nums) {
    int slow, fast;
    for (int i = 0; i < nums.length; i++) {
        slow = fast = i;
        fast = next(nums, fast);
        // 反向或者是有0元素 则跳出循环
        while (nums[slow] * nums[fast] > 0 && nums[fast] * nums[next(nums, fast)] > 0) {
            // 快慢指针相遇 如果不是自身循环 则返回true；
            if (slow == fast) {
                if (slow != next(nums, slow)) {
                    return true;
                } else {
                    break;
                }
            }
            slow = next(nums, slow);
            fast = next(nums, next(nums, fast));
        }
        // 如果同方向遇到自身循环 将快慢指针经过的所有元素置为0
        // 如果遇到不同方向 则将快指针之前的所有元素(也有可能包含快指针对应的元素，看奇数个还是偶数个）置为0：
        int rep = i;
        while (nums[rep] * nums[next(nums, rep)] > 0) {
            int temp = rep;
            rep = next(nums, rep);
            nums[temp] = 0;
        }
        nums[rep]=0;
    }
    return false;
}

// 返回快指针所对应的下标
public static int next(int[] nums, int fast) {
    int n = nums.length;
    // 此写法可以应对 正负两种情况
    return (nums[fast] + fast) % n + n;
}

class Solution {   
    public boolean circularArrayLoop(int[] nums) {
        int n = nums.length;
        // 使用 vis 数组对每个下标进行标记
        // 如果下标为 i 的位置在第 idx 轮被标记，则有 vis[i] = idx
        int[] vis = new int[n];
        for (int start = 0, idx = 1; start < n; start++, idx++) {
            if (vis[start] != 0) continue;
            int cur = start;
            boolean flag = nums[cur] > 0;
            while (true) {
                int next = ((cur + nums[cur]) % n + n) % n;
                if (next == cur) break;
                if (vis[next] != 0) {
                    // 如果 next 点已经被标记过，并且不是在本轮被标记，那么往后的通路必然都被标记，且无环，跳出   
                    if (vis[next] != idx) break;
                    // 如果 next 点已被标记，并且是本来被标记，说明找到了环
                    else return true;
                }
                if (flag && nums[next] < 0) break;
                if (!flag && nums[next] > 0) break;
                vis[next] = idx;
                cur = next;
            }
        }
        return false;
    }
}

public int maxArea(int[] height) {
        int i=0,j=height.length-1,mul,max=0;
        while(i!=j){
            // 从两边开始比较 哪边的值小 哪边移动一个
            // 为什么小的可以移动：
            // 1.另一边如果下次移动过程当中遇到一个比该值大的元素，就算这两个元素相乘也比这次相乘要小（横轴距离变短，高度不变)
            // 2. 另一边如果下次移动过程当中遇到一个比该值小的元素，比该值小的这个元素与这个元素相乘也比那一次的乘积小（因为横轴小于等于这次横轴距离，且高度小于这次的高度）
            if(height[i]<height[j]){
                mul=height[i]*(j-i);
                max=mul>max?mul:max;
                i++;
            }else{
                mul=height[j]*(j-i);
                max=mul>max?mul:max;
                j--;
            }
        }
        return max;
    }