ARTS_WEEK21

public ListNode mergeKLists(ListNode[] lists) {

        PriorityQueue<Integer> queue = new PriorityQueue<>(Integer::compareTo);

        //这里因为我是一次性将所有的元素加入到queue中
        // 第一 queue的插入复杂度是 (logn) n代表queue中的元素个数
        // 假设总元素有n个 时间复杂度就是 log1+log2...+logn约等于 nlogn
        //所以 总体 时间复杂度是 O(nlogn)

        //此地方可以优化
        //优化方式:
        //一直保持优先队列里面有k个元素 （k是list长度）
        //如何保持？
        //优先队列中先添加 所有list的头结点，然后弹出最小一个 插入其再拿出下一个
        for (int i = 0; i < lists.length; i++) {
            while (lists[i]!=null){
                queue.add(lists[i].val);
                lists[i] = lists[i].next;
            }
        }

        if (queue.isEmpty())return null;

        ListNode preHead = new ListNode(-1);
        ListNode head = preHead;
        while (!queue.isEmpty()){
            head.next = new ListNode(queue.poll());
            head = head.next;
        }
        return preHead.next;
    }

public ListNode mergeKLists1(ListNode[] lists) {


        if (lists.length==0)return null;

        PriorityQueue<ListNode> priorityQueue = new PriorityQueue<>(Comparator.comparing(listNode -> listNode.val));

        //这里不能使用这样的操作，因为可能 ListNode[] length不为0
        // 但是 ListNode本身为空
//        priorityQueue.addAll(Arrays.asList(lists));

        for (ListNode list : lists) {
            priorityQueue.add(list);
        }


        ListNode preHead = new ListNode(0);
        ListNode head = preHead;

        while (!priorityQueue.isEmpty()){
            ListNode listNode = priorityQueue.poll();
            head.next = listNode;
            head = head.next;

            if (listNode.next!=null){
                priorityQueue.add(listNode.next);
            }
        }

        return preHead.next;

    }

public int reversePairs(int[] nums) {
        int length = nums.length;
        int res = 0;
        for (int i = 0; i < length; i++) {
            for (int j = i; j < length; j++) {
                if (nums[i]>nums[j]){
                    res++;
                }
            }
        }
        return res;
    }

public int reversePairs1(int[] nums) {

        int[] arr = new int[nums.length];

        System.arraycopy(nums,0,arr,0,nums.length);

        int[] temp = new int[nums.length];

        return margeSort(arr,0,nums.length-1,temp);

    }

    /**
     * [left...right] 两闭区间 求其逆序数
     * @param arr
     * @param left
     * @param right
     * @param temp
     * @return
     */
    private int margeSort(int[] arr, int left, int right, int[] temp) {

        if (left==right)return 0;

        int mid = left + (right-left)/2;
        int leftCount = margeSort(arr, left, mid, temp);
        int rightCount = margeSort(arr, mid + 1, right, temp);

        //归并优化
        if (arr[mid+1]>=arr[mid]){
            return leftCount+rightCount;
        }
        int count = reverseCount(arr,left,mid,right,temp);

        return leftCount+rightCount+count;
    }

    /**
     * 归并 [left...mid] [mid+1...right] 两个有序区间的逆序对
     * @param arr
     * @param left
     * @param mid
     * @param right
     * @param temp
     * @return
     */
    private int reverseCount(int[] arr, int left, int mid, int right, int[] temp) {

        //拷贝 arr 的[left...right] 区间元素到 temp中，方便对比排序
        System.arraycopy(arr,left,temp,left,right-left+1);

        int count = 0;

        int i = left;//左边数组 初始位置
        int j = mid+1;//右边数组 初始位置

        for (int k = left; k <= right; k++) {

            //判断两个边界
            //由于每次计算完后 都会++操作
            //就所以边界的计算是要在 两数组中 最右区间下标+1的位置判断
            if (i==mid+1){
                arr[k] = temp[j++];
            }else if (j==right+1){
                arr[k] = temp[i++];
            }else if (temp[i]<=temp[j]){
                arr[k]=temp[i];
                i++;
            }else {
                arr[k] = temp[j];
                j++;
                //说明右边数组的j位置 小于 左边所有的元素
                count += (mid-i+1);
            }
        }
        return count;
    }

public int numberOfSubarrays(int[] nums, int k) {

        int left=0,right=0,ood=0,n=nums.length,res = 0;

        while (right < n ) {

            if ((nums[right++]&1)==1){
                ood++;
            }

            if (ood==k){

                //查找右边第一个奇数距离right的距离
                int tempRight = right;
                while (right<n&&(nums[right]&1)==0){
                    right++;
                }
                //右边第一个奇数距离right的距离
                int rightEventCont = right-tempRight;

                //查找左边第一个奇数距离left的距离
                int leftEventCont = 0;
                while (left<n&&(nums[left]&1)==0){
                    left++;
                    leftEventCont++;
                }
                res +=((leftEventCont+1)*(rightEventCont+1));

                ood--;
                left++;
            }
        }

        return res;

    }

public int numberOfSubarrays1(int[] nums, int k) {

        int res = 0;
        int count = 0;
        int[] oddCount = new int[nums.length+1];
        oddCount[0] =1;

        for (int num : nums) {
            count+= (num&1);
            oddCount[count]++;
            if (count>=k){
                res+=oddCount[count-k];
            }
        }

        return res;
    }

public List<List<Integer>> permute(int[] nums) {

        // 排列组合 本质上是一个树形的结构

        // 排列组合就是去遍历整棵树，
        // 但是用到了 回溯算法,回溯算法的关键是 要状态重置

        //利用了 两个个结构
        // dfs本质上利用了 方法栈
        // 每一个小的结果中使用到了 stack栈 来做回溯状态变更

        List<List<Integer>> res  = new ArrayList<>();
        int len = nums.length;
        if (len==0)return res;

        boolean[] use = new boolean[len];
        int path = 0;//层数
        Deque<Integer> stack = new ArrayDeque<Integer>();
        dfs(nums,len,path,use,stack,res);
        return res;
    }

public List<Integer> rightSideView(TreeNode root) {

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        ArrayList<Integer> res = new ArrayList<>();
        while (!queue.isEmpty()){
            int size = queue.size();
            TreeNode lastNode = null;
            for (int i = 0; i < size; i++) {
                TreeNode poll = queue.poll();
                if (poll!=null){
                    queue.add(poll.left);
                    queue.add(poll.right);
                    lastNode = poll;
                }
            }
            if (lastNode!=null){
                res.add(lastNode.val);
            }else {
                return res;
            }
        }
        return res;
    }

public int waysToChange(int n) {
        int [] coin = {25,10,5,1};
        int[][] dp = new int[5][n+1];
        for (int i = 1; i <= 4; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= 4; i++) {
            for (int j = 1; j <= n; j++) {

                if (j-coin[i-1]>=0){
                    //都可以选
                    // f(i,j) = f(i-1,j)+f(i,j-coin[i]);
                    dp[i][j] = (dp[i-1][j]+dp[i][j-coin[i-1]])%1000000007;
                }else {
                    //只能不选
                    dp[i][j] = dp[i-1][j]%1000000007;
                }

            }
        }
        return dp[4][n];
    }

 public int waysToChange1(int n) {
        int [] coins = {25,10,5,1};
        int[] dp = new int[n+1];
        dp[0] = 1;
        for (int coin : coins) {

            for (int i = 1; i <= n; i++) {
                if (i-coin>=0){
                    dp[i] = (dp[i]+dp[i-coin])%1000000007;
                }
            }
        }
        return dp[n];
    }

public int numIslands(char[][] grid) {

        if (grid.length==0)return 0;

        int n = grid.length;
        int m = grid[0].length;

        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                ans += grid[i][j]-'0';
                dfs(grid,i,j,n,m);
            }
        }
        return ans;
    }

    private int[] movex=  {0,1,0,-1};
    private int[] movey = {-1,0,1,0};

    private void dfs(char[][] grid, int i, int j, int n, int m) {
        if (i<0||i>=n||j<0||j>=m||grid[i][j]=='0'){
            return;
        }
        grid[i][j]='0';
        dfs(grid,i+movex[0],j+movey[0],n,m);
        dfs(grid,i+movex[1],j+movey[1],n,m);
        dfs(grid,i+movex[2],j+movey[2],n,m);
        dfs(grid,i+movex[3],j+movey[3],n,m);
    }

// MQTT的连接设置
options = new MqttConnectOptions();
// 设置是否清空session,这里如果设置为false表示服务器会保留客户端的连接记录，这里设置为true表示每次连接到服务器都以新的身份连接
options.setCleanSession(false);