月度归档： 2022年5月

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

示例 1:

输入: [7,5,6,4]
输出: 5

限制：

0 <= 数组长度 <= 50000

归并，基本思路李姐

归并过程可以把代码的注释打开看下，以实际数据来解释说明下

    归并数组： [7, 6, 5, 4, 3]   [32, 11, 8, 2, 1]
    idxL:0
    idxR:3
    2
    idxL:1
    idxR:3
    2
    idxL:2
    idxR:3
    2
    idxL:3
    idxR:3
    2
    idxL:4
    idxR:3
    2
    归并结果： [32, 11, 8, 7, 6, 5, 4, 3, 2, 1]
    -----

以上数组A[7, 6, 5, 4, 3]、B[32, 11, 8, 2, 1]

1. 合并的时候，A的第0个7小于B的第0个32，结果第一位插入32，第二位11同样，第三位8同样
2. A下标0的数字7大于B下标3的数字2，此时7和后面的[2, 1]形成逆序对，逆序对个数加2
3. 6同样和后面的[2, 1]形成逆序对，逆序对个数加2
4. [5, 4, 3]也一样，逆序对分别加2
5. 而在这之前的A数组内部的逆序对，在最开始之前的时候做归并排序

    归并数组： [7]   [5]
    idxL:0
    idxR:0
    1
    归并结果： [7, 5]
    -----

以及归并数组： [7, 5] [6]和归并数组： [4] [3]，再将这两个合并归并数组： [7, 6, 5] [4, 3]，得到结果[7, 6, 5, 4, 3]，在这个过程中已经计算过了

class Solution {
    int count = 0;
    public int reversePairs(int[] nums) {
        sort(nums);
        return count;
    }

    public int[] sort(int[] nums){
        if (nums.length<2){
            return nums;
        }
        int[] right = new int[nums.length/2];
        int[] left = new int[nums.length - right.length];
        System.arraycopy(nums,0,left,0,left.length);
        System.arraycopy(nums,left.length,right,0,right.length);
        left = sort(left);
        right = sort(right);
        return mergeArray(left,right);
    }

    public int[] mergeArray(int[] left, int[] right) {
        if (right.length==0){
            return left;
        }
//        System.out.println("归并数组： "+Arrays.toString(left) +"   "+ Arrays.toString(right));
        int[] arr = new int[left.length + right.length];
        int idx = -1;
        int idxL = 0;
        int idxR = 0;
        while (++idx < arr.length){
            if (idxL<left.length && (idxR>= right.length || left[idxL] > right[idxR])){
                arr[idx] = left[idxL];
                idxL++;
                count += right.length-idxR;
//                System.out.println(right.length-idxR);
            }else{
                arr[idx] = right[idxR];
                idxR++;
            }
        }
//        System.out.println("归并结果： "+Arrays.toString(arr));
//        System.out.println("-----");
        return arr;
    }
}

在《英雄联盟》的世界中，有一个叫 “提莫” 的英雄。他的攻击可以让敌方英雄艾希（编者注：寒冰射手）进入中毒状态。

当提莫攻击艾希，艾希的中毒状态正好持续 duration 秒。

正式地讲，提莫在 t 发起发起攻击意味着艾希在时间区间 [t, t + duration - 1]（含 t 和 t + duration - 1）处于中毒状态。如果提莫在中毒影响结束 前 再次攻击，中毒状态计时器将会 重置 ，在新的攻击之后，中毒影响将会在 duration 秒后结束。

给你一个 非递减 的整数数组 timeSeries ，其中 timeSeries[i] 表示提莫在 timeSeries[i] 秒时对艾希发起攻击，以及一个表示中毒持续时间的整数 duration 。

返回艾希处于中毒状态的 总 秒数。

示例 1：

输入：timeSeries = [1,4], duration = 2
输出：4
解释：提莫攻击对艾希的影响如下：
- 第 1 秒，提莫攻击艾希并使其立即中毒。中毒状态会维持 2 秒，即第 1 秒和第 2 秒。
- 第 4 秒，提莫再次攻击艾希，艾希中毒状态又持续 2 秒，即第 4 秒和第 5 秒。
艾希在第 1、2、4、5 秒处于中毒状态，所以总中毒秒数是 4 。

示例 2：

输入：timeSeries = [1,2], duration = 2
输出：3
解释：提莫攻击对艾希的影响如下：
- 第 1 秒，提莫攻击艾希并使其立即中毒。中毒状态会维持 2 秒，即第 1 秒和第 2 秒。
- 第 2 秒，提莫再次攻击艾希，并重置中毒计时器，艾希中毒状态需要持续 2 秒，即第 2 秒和第 3 秒。
艾希在第 1、2、3 秒处于中毒状态，所以总中毒秒数是 3 。

提示：

• 1 <= timeSeries.length <= 104
• 0 <= timeSeries[i], duration <= 107
• timeSeries 按 非递减 顺序排列

模拟分析一下【 本次的结束时间 – max ( 本次开始时间， 上次结束时间 ) 】

两种情况如下见图

1. 当前的结束时间在下次的开始时间之后，中间有重复部分，需要减去
2. 当前的结束时间在下次的开始时间之前，只需加上对应的duration即可

 0 1 2 3 4 5 6 7 8 9 10
 - - -
     - - -
             - - -

综合两种情况的分析，需要加上的时长为

本次的结束时间 - max( 本次开始时间， 上次结束时间 )

class Solution {
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        int ans = 0;
        int last = timeSeries[0];
        for (int timeSery : timeSeries) {
            ans += timeSery + duration - Math.max(last,timeSery);
            last = timeSery + duration;
        }
        return ans;
    }
}

给定一棵 N 叉树的根节点 root ，计算这棵树的直径长度。

N 叉树的直径指的是树中任意两个节点间路径中 最长 路径的长度。这条路径可能经过根节点，也可能不经过根节点。

（N 叉树的输入序列以层序遍历的形式给出，每组子节点用 null 分隔）

示例 1：

输入：root = [1,null,3,2,4,null,5,6]
输出：3
解释：直径如图中红线所示。

示例 2：

输入：root = [1,null,2,null,3,4,null,5,null,6]
输出：4

示例 3：

输入: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出: 7

提示：

• N 叉树的深度小于或等于 1000 。
• 节点的总个数在 [0, 10^4] 间。

深度优先搜索算法

深度优先搜索算法，类似的题目有，
剑指 Offer 68 – II. 二叉树的最近公共祖先

1740. 找到二叉树中的距离

基本都一样的题目。多做几遍练练手加深印象

class Solution {

    int max = 0;

    public int diameter(Node root) {
        dfs(root,0);
        return max;
    }


    public int dfs(Node node,int deep){
        if (node == null){
            return deep - 1;
        }
        int childMaxDeep = deep;
        int max1 = 0;
        int max2 = 0;
        for (Node child : node.children){
            int childDeep = dfs(child,deep+1);
            childMaxDeep = Math.max(childMaxDeep,childDeep);
            if (childDeep>max1){
                max2 = max1;
                max1 = childDeep;
            }else if (childDeep>max2){
                max2 = childDeep;
            }
        }
        max = Math.max(max, max1+max2-deep-deep);
        return childMaxDeep;
    }
}

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

示例：

输入：S = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。

提示：

• S的长度在[1, 500]之间。
• S只包含小写字母 'a' 到 'z' 。

基本思考思路及实现

好像和官方题解想得一样，还是说下自己的思考过程吧

1. 从前面找到一个字符，往后找到他最后出现的位置，这时候想到了可能需要双指针？或者从后往前找这个字符第一次出现的位置，不过好像有点复杂，
2. 于是又想到了可以用哈希表记录下每个字符出现的最后位置，但是这时候又一个想法，是不是可以同时记下这个字符第一次出现的位置，这样就知道了这个字符需要对应的最小区间，但是如何和其他字符对应的区间是个问题，遂放弃，不过也许应该有办法
3. 那么有了前面得到的最后位置之后我们就把找当前字符最后出现位置的操作变成了O(1)复杂度
4. 继续下一个字符，判断他出现的最后位置，如果比之前那个小的话，就不用管，如果比之前那个大的话，说明这两个字符对应的最小区间需要扩大了
5. 如果找到了某个字符出现最后位置就是当前对应的区间的结束位置的话，那么说明可以形成符合题意的区间了，记录长度

class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> list = new ArrayList<>();
        int[] map = new int[26];
        int idx = -1;
        while (++idx < s.length()){
            map[s.charAt(idx) - 'a'] = idx;
        }
        int begin = 0;
        idx = -1;
        int lastPostion = -1;
        while (++idx < s.length()){
            lastPostion = Math.max(lastPostion,map[s.charAt(idx)-'a']);
            if (idx == lastPostion){
                list.add(idx - begin + 1);
                begin = idx+1;
            }
        }
        return list;
    }
}

你正在参与祖玛游戏的一个变种。

在这个祖玛游戏变体中，桌面上有 一排 彩球，每个球的颜色可能是：红色 'R'、黄色 'Y'、蓝色 'B'、绿色 'G' 或白色 'W' 。你的手中也有一些彩球。

你的目标是 清空 桌面上所有的球。每一回合：

• 从你手上的彩球中选出 任意一颗 ，然后将其插入桌面上那一排球中：两球之间或这一排球的任一端。
• 接着，如果有出现 三个或者三个以上 且 颜色相同 的球相连的话，就把它们移除掉。
  • 如果这种移除操作同样导致出现三个或者三个以上且颜色相同的球相连，则可以继续移除这些球，直到不再满足移除条件。
• 如果桌面上所有球都被移除，则认为你赢得本场游戏。
• 重复这个过程，直到你赢了游戏或者手中没有更多的球。

给你一个字符串 board ，表示桌面上最开始的那排球。另给你一个字符串 hand ，表示手里的彩球。请你按上述操作步骤移除掉桌上所有球，计算并返回所需的 最少 球数。如果不能移除桌上所有的球，返回 -1 。

示例 1：

输入：board = "WRRBBW", hand = "RB"
输出：-1
解释：无法移除桌面上的所有球。可以得到的最好局面是：
- 插入一个 'R' ，使桌面变为 WRRRBBW 。WRRRBBW -> WBBW
- 插入一个 'B' ，使桌面变为 WBBBW 。WBBBW -> WW
桌面上还剩着球，没有其他球可以插入。

示例 2：

输入：board = "WWRRBBWW", hand = "WRBRW"
输出：2
解释：要想清空桌面上的球，可以按下述步骤：
- 插入一个 'R' ，使桌面变为 WWRRRBBWW 。WWRRRBBWW -> WWBBWW
- 插入一个 'B' ，使桌面变为 WWBBBWW 。WWBBBWW -> WWWW -> empty
只需从手中出 2 个球就可以清空桌面。

示例 3：

输入：board = "G", hand = "GGGGG"
输出：2
解释：要想清空桌面上的球，可以按下述步骤：
- 插入一个 'G' ，使桌面变为 GG 。
- 插入一个 'G' ，使桌面变为 GGG 。GGG -> empty
只需从手中出 2 个球就可以清空桌面。

示例 4：

输入：board = "RBYYBBRRB", hand = "YRBGB"
输出：3
解释：要想清空桌面上的球，可以按下述步骤：
- 插入一个 'Y' ，使桌面变为 RBYYYBBRRB 。RBYYYBBRRB -> RBBBRRB -> RRRB -> B
- 插入一个 'B' ，使桌面变为 BB 。
- 插入一个 'B' ，使桌面变为 BBB 。BBB -> empty
只需从手中出 3 个球就可以清空桌面。

提示：

• 1 <= board.length <= 16
• 1 <= hand.length <= 5
• board 和 hand 由字符 'R'、'Y'、'B'、'G' 和 'W' 组成
• 桌面上一开始的球中，不会有三个及三个以上颜色相同且连着的球

深度优先搜索方法，board 结尾借个空格好处理点

上班摸鱼，凑合摸了一个小时多，水平有限

深度优先搜索，

删除连续相同颜色的，我在结尾添加了一个空格，代码稍微好写点具体参见reductionChars方法，不过这个还是写的不太完美，需要递归处理，应该有不用递归的写法的，回头再尝试

具体还是看代码吧，有一些注解，应该能看看吧

class Solution {
    HashSet<String> visited = new HashSet<>();

    int min = 100;

    public int findMinStep(String board, String hand) {
        //借个空结尾代码好处理点
        board = board+" ";
        boolean[] handUsed = new boolean[hand.length()];
        char[] boardChars = board.toCharArray();
        dfs(boardChars,hand,handUsed);
        //如果是100表示不能全消除
        return min==100?-1:min;
    }

    public void dfs(char[] chars, String hand , boolean[] handUsed){
        if (chars.length==1){
            //统计用了几个
            int usedCount = 0;
            for (boolean used : handUsed) {
                if (used){
                    usedCount++;
                }
            }
            min = Math.min(min,usedCount);
            return ;
        }
        //剪枝已经处理过的情况
        if (visited.contains(new String(chars))){
            return ;
        }
        //记录下当前情况已经处理过
        visited.add(new String(chars));
        //从handUsed所有在handUsed中没有标记的已用过的位置中取一个字符
        for (int idx = 0; idx < handUsed.length; idx++) {
            if (handUsed[idx]){
                continue;
            }
            //标记已使用
            handUsed[idx] = true;
            //构造所有可能的组合情况
            List<char[]> list = insertChar(chars,hand.charAt(idx));
            for (char[] charArr : list) {
                //继续递归
                dfs(reductionChars(charArr),hand,handUsed);
            }
            //回溯标记未使用
            handUsed[idx] = false;
        }
    }

    /**
     * 往`char[] chars` 数组中所有能插入的位置插入一个新的字符`c`
     * 如果原来的被 插入位置和当前插入字符相同，只插入到后面一个位置
     * @param chars
     * @param c
     * @return
     */
    public List<char[]> insertChar(char[] chars, char c){
        List<char[]> list = new ArrayList<>();
        int idx = -1;
        while (++idx < chars.length){
            while (chars[idx]==c){
                idx++;
            }
            char[] newChars = new char[chars.length+1];
            System.arraycopy(chars,0,newChars,0,idx);
            System.arraycopy(chars,idx,newChars,idx+1,chars.length-idx);
            newChars[idx] = c;
            list.add(newChars);
        }
        return list;
    }

    /**
     * 删除字符串数组中连续出现次数大于等于3的区段内容
     * @param chars
     * @return
     */
    public char[] reductionChars(char[] chars){
        //记录下当前的长度
        int length = chars.length;
        int idx = 0;
        char lastChar = chars[0];
        int lastCharCount = 1;
        while (++idx < chars.length){
            if (chars[idx] == lastChar){
                lastCharCount++;
            }else{
                //当前字符和前一个不同
                if (lastCharCount>=3){
                    //从当前位置往前删除掉lastCharCount个
                    char[] newChars = new char[chars.length-lastCharCount];
                    System.arraycopy(chars,0,newChars,0,idx-lastCharCount);
                    System.arraycopy(chars,idx,newChars,idx-lastCharCount,chars.length-idx);
                    chars = newChars;
                    idx -= lastCharCount;
                }
                lastChar = chars[idx];
                lastCharCount = 1;
            }
        }
        //如果没有能处理删除掉的字符则直接返回
        //如果长度发生了变化，尝试再处理一次，防止   WWRRRWW 变成了 WWWW后还要再处理一次的情况
        return length == chars.length?chars:reductionChars(chars);
    }
}

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。

若队列为空，pop_front 和 max_value 需要返回 -1

示例 1：

输入: 
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]

示例 2：

输入: 
["MaxQueue","pop_front","max_value"]
[[],[],[]]
输出: [null,-1,-1]

限制：

• 1 <= push_back,pop_front,max_value的总操作数 <= 10000
• 1 <= value <= 10^5

双队列空间换时间

1. 一个queue用来保存正常顺序的队列Queue<Integer> queue
2. 另一个双端队列Deque<Integer> deque ,从队尾插入的时候时候需要从队列尾部往前删除比自己小的值，直到遇到一个大于等于当前需要插入的值的时候停止
3. 这样这个双端队列deque从队头读取的时候，能保证，对头元素是当前所有插入的值中的最大值
4. 当从queue中删除头部的元素的时候，对比下deque中队首的元素是否是当前被从queue中删除的那个，如果是的话，则同时删除双端队列deque的队首元素
5. 这样双端队列deque删除队首元素的时候，下一个小于等于当前删除的队首元素的，且位置是位于当前queue队首那个元素到结尾这个区间内的最大元素，那么符合题意的设计就完成了

class MaxQueue {

    Queue<Integer> queue;

    Deque<Integer> deque;

    public MaxQueue() {
        queue = new ArrayDeque<>();
        deque = new ArrayDeque<>();
    }
    
    public int max_value() {
        if (queue.isEmpty()){
            return -1;
        }
        return deque.peekFirst();
    }
    
    public void push_back(int value) {
        queue.add(value);
        while (!deque.isEmpty() && deque.peekLast() < value){
            deque.pollLast();
        }
        deque.offer(value);
    }
    
    public int pop_front() {
        if (queue.isEmpty()){
            return -1;
        }
        if (queue.peek().equals(deque.peekFirst())){
            deque.pollFirst();
        }
        return queue.poll();
    }
}