初始时有 n 个灯泡处于关闭状态。第一轮，你将会打开所有灯泡。接下来的第二轮，你将会每两个灯泡关闭第二个。

第三轮，你每三个灯泡就切换第三个灯泡的开关（即，打开变关闭，关闭变打开）。第 i 轮，你每 i 个灯泡就切换第 i 个灯泡的开关。直到第 n 轮，你只需要切换最后一个灯泡的开关。

找出并返回 n 轮后有多少个亮着的灯泡。

示例 1：

输入：n = 3
输出：1 
解释：
初始时, 灯泡状态 [关闭, 关闭, 关闭].
第一轮后, 灯泡状态 [开启, 开启, 开启].
第二轮后, 灯泡状态 [开启, 关闭, 开启].
第三轮后, 灯泡状态 [开启, 关闭, 关闭]. 

你应该返回 1，因为只有一个灯泡还亮着。

示例 2：

输入：n = 0
输出：0

示例 3：

输入：n = 1
输出：1

提示：

• 0 <= n <= 109

1. 1 个开着 1*2 个关着
2. 1 个开着 2*2 个关着
3. 1 个开着 3*2 个关着
4. 后续省略

class Solution {
    public int bulbSwitch(int n) {
        if (n < 1){
            return n;
        }
        int count = 0;
        int idx = -1;
        while (true){
            if (++idx < n){
                count++;
            }else{
                break;
            }
            if (idx+(count * 2) < n){
                idx += count*2;
            }else{
                break;
            }
        }
        return count;
    }
}

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

例如：

给定二叉树 [3,9,20,null,null,15,7]，

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3 。

提示：

1. 节点总数 <= 10000

注意：本题与主站 104 题相同：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

深搜模板直接套用

1. dfs()方法返回当前节点下的最大深度
2. 如果当前节点有值，深度加1
3. 递归左右节点，返回左右节点的最大深度
4. 左右节点的最大深度中返回较大的那个

class Solution {

    public int maxDepth(TreeNode root) {
        if (root==null){
            return 0;
        }
        return dfs(root,0);
    }

    public int dfs(TreeNode node, int deep){
        if (node==null){
            return deep;
        }
        deep++;
        int left = dfs(node.left,deep);
        int right = dfs(node.right,deep);

        return Math.max(left,right);
    }
}

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

示例 1：

输入：nums = [3,4,3,3]
输出：4

示例 2：

输入：nums = [9,1,7,9,7,9,7]
输出：1

限制：

• 1 <= nums.length <= 10000
• 1 <= nums[i] < 2^31

凑合，记录下没啥参考意义

class Solution {
    public int singleNumber(int[] nums) {
        int[] arrCount = new int[32];
        for (int num : nums) {
            int idx = 32;
            while (--idx>=0 && num > 0){
                arrCount[idx] += num%2;
                num >>= 1;
            }
        }
        int res = 0;
        for (int count : arrCount) {
            res <<= 1;
            res += count%3;
        }
        return res;
    }
}

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

示例 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;
    }
}