ARTS_WEEK17

/**
     * 关键点 求解最大公约数
     *
     * @param deck
     * @return
     */
    public boolean hasGroupsSizeX(int[] deck) {

        int[] countor = new int[10000];

        for (int i : deck) {
            countor[i]++;
        }

        int x = countor[deck[0]];

        for (int i = 0; i < countor.length; i++) {
            int count = countor[i];
            if (count == 1) return false;

            if (count >= 2) {
                x = gcd(x, count);
                if (x == 1) return false;
            }
        }
        return true;
    }

    public boolean hasGroupsSizeX1(int[] deck) {

        int[] countor = new int[10000];

        for (int i : deck) {
            countor[i]++;
        }

        int x = countor[deck[0]];

        System.out.println(Arrays.stream(countor).reduce(this::gcd).getAsInt());
        //每两个数字都 gcd一下，所以只要最终结果 大于等2就说明有解
        return Arrays.stream(countor).reduce(this::gcd).getAsInt() >= 2;

    }


    private int gcd(int x, int y) {

        if (y == 0) return x;

        return gcd(y, x % y);
    }

    public static void main(String[] args) {
        Week17EHasGroupsSizeX914 groupsSizeX = new Week17EHasGroupsSizeX914();
        groupsSizeX.hasGroupsSizeX1(new int[]{2,3,4,4,3,2,1});
    }

/**
     * 动态规划
     * @param nums
     * @return
     */
    public int massage(int[] nums) {
        return dp(nums, nums.length - 1);
    }

    //递归的方式
    private int dp(int[] nums, int n) {
        if (n < 0) {
            return 0;
        }
        return Math.max(dp(nums, n - 2) + nums[n], dp(nums, n - 1));
    }

    //使用数组缓存
    public int massage1(int[] nums) {

        int n = nums.length;
        if (n == 0) return 0;
        if (n == 1) return nums[0];

        int[] dp = new int[n];

        //前两个的最优解
        dp[0] = nums[0];
        dp[1] = Math.max(nums[1], nums[0]);

        for (int i = 2; i < n; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }

        return dp[n - 1];
    }

    //只缓存两个数字
    public int massage2(int[] nums) {

        int n = nums.length;
        if (n == 0) return 0;
        if (n == 1) return nums[0];

        int a = 0, b = 0;

        for (int i = 0; i < n; i++) {
            int c = Math.max(b, nums[i] + a);
            a = b;
            b = c;
        }

        return b;
    }

public ListNode middleNode(ListNode head) {

        //双指针方式
        ListNode slow = head;
        ListNode fast = head;

        while (fast!=null&&fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

public int numRookCaptures(char[][] board) {
        int n = board.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                char c = board[i][j];
                //找到车
                if (c == 'R') {
                    int up = j, down = j;
                    int left = i, right = i;

                    int count = 0;

                    //向上查找
                    while (up >= 0) {
                        char upNum = board[i][up];
                        if (upNum == 'p') {
                            count++;
                            break;
                        } else if (upNum == '.' || upNum == c) {
                            up--;

                        } else {
                            break;
                        }
                    }
                    //向下查找
                    while (down < n) {
                        char downNum = board[i][down];
                        if (downNum == 'p') {
                            count++;
                            break;
                        } else if (downNum == '.' || downNum == c) {
                            down++;
                        } else {
                            break;
                        }

                    }
                    //向左查找
                    while (left >= 0) {
                        char leftNum = board[left][j];
                        if (leftNum == 'p') {
                            count++;
                            break;
                        } else if (leftNum == '.' || leftNum == c) {
                            left--;

                        } else {
                            break;
                        }
                    }

                    //向右查找
                    while (right < n) {
                        char rightNum = board[right][j];
                        if (rightNum == 'p') {
                            count++;
                            break;
                        } else if (rightNum == '.' || rightNum == c) {
                            right++;
                        } else {
                            break;
                        }
                    }
                    return count;
                }
            }

        }

        return 0;
    }

    public int numRookCaptures1(char[][] board) {

        int n = board.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {

                if (board[i][j] == 'R') {
                    int res = 0;
                    for (int[] direction : directions) {
                        if (burnout(board, i, j, direction)) {
                            res++;
                        }
                    }
                    return res;
                }
            }
        }


        return 0;
    }

    private boolean burnout(char[][] board, int x, int y, int[] direction) {
        int i = x;
        int j = y;

        while (isArea(i, j)) {
            char c = board[i][j];
            if (c == 'B') break;

            if (c == 'P') return true;

            i += direction[0];
            j += direction[1];
        }
        return false;
    }

    private boolean isArea(int i, int j) {
        return i >= 0 && i < 8 && j >= 0 && j < 8;
    }

public int surfaceArea(int[][] grid) {
        //题目 ： n*n的底，n为grid的length
        int area = 0;
        int n = grid.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int high = grid[i][j];
                if (high > 0) {
                    area += high * 4 + 2;
                    area -= i > 0 ? Math.min(high, grid[i - 1][j]) * 2 : 0;
                    area -= j > 0 ? Math.min(high, grid[i][j - 1]) * 2 : 0;
                }
            }
        }
        return area;
    }

    public int maxDistance1(int[][] grid) {
        //多点BFS
        //但是要设置，遍历过得不能再遍历
        int n = grid.length;

        LinkedList<int[]> queue = new LinkedList<>();

        //将所有陆地加入队列
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    queue.addLast(new int[]{i, j});
                }
            }
        }
        //设置上下左右 陆地被包围的是个点
        int[] dx = new int[]{1, -1, 0, 0};
        int[] dy = new int[]{0, 0, 1, -1};

        int[] print = null;
        boolean hashOcean = false;
        //BFS遍历
        while (!queue.isEmpty()) {

            print = queue.poll();
            int x = print[0];
            int y = print[1];

            for (int i = 0; i < 4; i++) {
                int newx = x+dx[i];
                int newy = y+dy[i];

                //grid[newx][newy]!=0
                // 表示如果下一个节点 有值就说明被标记过
                if (newx<0||newx>=n||newy<0||newy>=n||grid[newx][newy]!=0){
                    continue;
                }
                hashOcean = true;
                grid[newx][newy] = grid[x][y]+1;
                queue.addLast(new int[]{newx,newy});
            }
        }
        if (!hashOcean||print==null)return -1;
        //-1是因为 第一个陆地是1 所以需要减去
        return grid[print[0]][print[1]]-1;
    }

public int minimumLengthEncoding(String[] words) {
        Trie trie = new Trie();
        int count = 0;

        //先要插入较长的
        Arrays.sort(words,(o1,o2)->o2.length()-o1.length());

        for (String word : words) {
            count+=trie.insert(word);
        }
        return count;
    }


    class Trie{
        private TrieNode root;
        boolean isNew = true;

        public Trie() {
            root = new TrieNode();
        }

        public int insert(String word){

            TrieNode curr = root;

            isNew = false;
            char[] chars = word.toCharArray();

            //倒着插入
            for (int i = chars.length-1; i >= 0; i--) {
                char aChar = chars[i];
                if (curr.children[aChar - 'a']==null){
                    isNew = true;
                    //是新单词
                    curr.children[aChar - 'a'] = new TrieNode();
                }
                curr = curr.children[aChar - 'a'];
            }
            return isNew?word.length()+1:0;
        }
    }

    class TrieNode{
        char val;
        TrieNode[] children = new TrieNode[26];
    }

Set<Integer> queue = new TreeSet<>(Integer::compareTo);

    /**
     * 方法一 使用set储存
     * @param root
     * @return
     */
    public int findSecondMinimumValue(TreeNode root) {
        dfs(root);
        int i = 0;
        int res = -1;
        for (Integer integer : queue) {
            if (i==1){
                res= integer;
            }
            i++;
        }
        return res;
    }

    private void dfs(TreeNode root) {
        if (root==null)return;
        dfs(root.left);
        dfs(root.right);
        queue.add(root.val);
    }

/**
     * 方法二
     * 拿出左边最小的与
     * 右边最小的
     * <p>
     * 然后找出两个里面大的那一个，如果相同就返回-1
     *
     * @param root
     * @return
     */
    public int findSecondMinimumValue1(TreeNode root) {

        return myfun(root, root.val);
    }

    /**
     * 1. left right的最小值也 > root.val 说明root.val是最小的值
     * 第二小就是 left right 中最小的值
     * 2. 其他情况 因为只有三个数 只需要取 left 与 right最大值
     *
     * @param root 当前检查的node
     * @param val root的val
     * @return
     */
    private int myfun(TreeNode root, int val) {

        if (root == null) return -1;

        //返回大于 val的
        if (root.val > val) {
            return root.val;
        }

        int l = myfun(root.left, val);
        int r = myfun(root.right, val);

        if (l > val && r > val) {
            return Math.min(l, r);
        }
        return Math.max(l, r);
    }

public int rob(int[] nums) {

        if (nums.length==0)return 0;
        if (nums.length==1)return nums[0];
        int a = 0,b = 0;

        for (int i = 0; i < nums.length; i++) {
            int c = Math.max(nums[i]+a,b);
            a= b;
            b=c;
        }
        return b;
    }

/**
     * 递归方式，动态规划
     * @param root
     * @return
     */
    public int rob(TreeNode root) {
        if (root==null)return 0;
        int nextCount = root.val;
        if (root.left!=null){
            nextCount +=(rob(root.left.left)+rob(root.left.right));
        }
        if (root.right!=null){
            nextCount +=(rob(root.right.left)+rob(root.right.right));
        }
        return Math.max(nextCount,rob(root.left)+rob(root.right));
    }


    private Map<TreeNode,Integer> cache = new HashMap<>();
    /**
     * 使用map 缓存
     * @param root
     * @return
     */
    public int rob1(TreeNode root) {
        if (root==null)return 0;

        if (cache.containsKey(root)){
            return cache.get(root);
        }

        int nextCount = root.val;
        if (root.left!=null){
            nextCount +=(rob(root.left.left)+rob(root.left.right));
        }
        if (root.right!=null){
            nextCount +=(rob(root.right.left)+rob(root.right.right));
        }
        int max = Math.max(nextCount, rob(root.left) + rob(root.right));
        cache.put(root,max);
        return max;
    }

    //只记录两个状态
    public int rob2(TreeNode root) {
        int[] res = robInternal(root);
        return Math.max(res[0],res[1]);
    }

    /**
     * 0 表示不选
     * 1 表示选中
     * @param root
     * @return
     */
    private int[] robInternal(TreeNode root) {
        if (root==null)return new int[2];
        int[] res = new int[2];
        int[] left = robInternal(root.left);
        int[] right = robInternal(root.right);

        res[0] = Math.max(left[0],left[1])+Math.max(right[0],right[1]);
        res[1] = root.val + left[0] + right[0];
        return res;
    }