给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

示例 1：

输入：nums = [3,0,1]
输出：2
解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。

示例 2：

输入：nums = [0,1]
输出：2
解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。

示例 3：

输入：nums = [9,6,4,2,3,5,7,0,1]
输出：8
解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。

示例 4：

输入：nums = [0]
输出：1
解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字，因为它没有出现在 nums 中。

提示：

• n == nums.length
• 1 <= n <= 104
• 0 <= nums[i] <= n
• nums 中的所有数字都 独一无二

进阶：你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?

异或、求和 & 【看起来没人用的其实也能用的 原地交换 ！！】

都知道的异或、求和先贴下、其他还有哈希表，重构数组遍历等等，没啥好说的了，大家都看很多遍了

异或

class Solution {
    public int missingNumber(int[] nums) {
        int num = 0;
        for (int i = 0; i < nums.length; i++) {
            num ^= nums[i];
            num ^= i;
        }
        num ^= nums.length;
        return num;
    }
}

求和

class Solution {

    public int missingNumber(int[] nums) {
        int num = 0;
        for (int i = 0; i < nums.length; i++) {
            num -= nums[i];
            num += i;
        }
        num += nums.length;
        return num;
    }

}

丢失数字之类的还有一种会用到原地交换的解法

这里我们其实也可以尝试下。大促晚值班摸鱼，来玩点花样

原地交换

跟官方题解写一样缺少乐趣，毕竟是简单题，能玩的花样一遍都比较多，

拿官方例题来分析下，第一行对应为数组下标，第二行数原始数组，

1. 如果nums[i] == nums.length原地交换会越界，那么我就声明一个变量用来保存存放在这个位置的数字，这样我们就可以顺利使用原地交换了，毕竟要求时间O(n),空间O(1)

• 其实你也可以声明一个长度为nums.length+1的数组来处理，这样可以省事，不过空间就不是O(1)了

2. 原来第n位上的数字不存在，那就在代码里用-1表示，图里用x表示
3. 从0下标开始交换，把0交换给n，此时记录丢失数字为0 ,missing = 0;
4. 后面从下标1开始交换，一直交换这些比较简单省略，直到到下标1上的值为x了，记录当前丢失数字missing = 1;
5. 后面继续交换，直到最后下标8上的值为x,记录missing = 8;
6. 结束

同时，看下剑指offer03的数组中的重复数字这题，试着用原地交换的方法来理解下，或许对你能有帮助
【原地交换】图解，看个明白

原地交换代码

class Solution {

    public int missingNumber(int[] nums) {
        //丢失的
        int misssing = nums.length;
        //额外占用的第nums.length下标位
        int n = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i]==nums.length){
                n = nums[i];
                nums[i] = -1;
            }
            while (nums[i] != -1 && nums[i] != i ){
                swap(nums,i,nums[i]);
                if (nums[i]==nums.length){
                    n = nums[i];
                    nums[i] = -1;
                }
            }
            if (nums[i]==-1){
                misssing = i;
            }
        }
        return misssing;
    }
    
    public void swap(int[] nums, int x, int y){
        int tmp = nums[x];
        nums[x] = nums[y];
        nums[y] = tmp;
    }

}

我们从二叉树的根节点 root 开始进行深度优先搜索。

在遍历中的每个节点处，我们输出 D 条短划线（其中 D 是该节点的深度），然后输出该节点的值。（如果节点的深度为 D，则其直接子节点的深度为 D + 1。根节点的深度为 0）。

如果节点只有一个子节点，那么保证该子节点为左子节点。

给出遍历输出 S，还原树并返回其根节点 root。

示例 1：

输入："1-2--3--4-5--6--7"
输出：[1,2,5,3,4,6,7]

示例 2：

输入："1-2--3---4-5--6---7"
输出：[1,2,5,3,null,6,null,4,null,7]

示例 3：

输入："1-401--349---90--88"
输出：[1,401,null,349,88,90]

提示：

• 原始树中的节点数介于 1 和 1000 之间。
• 每个节点的值介于 1 和 10 ^ 9 之间。

栈辅助基本思路实现【联动 剑指 Offer 37. 序列化二叉树】

可以配合剑指 Offer 37. 序列化二叉树 一起做了加深理解，把这题的解法，加上自行再实现个序列化的方法就可以拿去做这一题了

借助辅助栈的基本思路，比较好理解，不过性能上略差

1. 按照-分割字符串
2. 第一个字符就是根节点
3. 后面的节点的层属由这个字符串的前面有多少个分割出来的空字符串决定
4. 由于是用-分割了，原来的两个相邻层级之间不存在空字符串分割了，所以下面代码中int level = 1;从1开始，而不是从0

class Solution {
    String[] strArr;
    public TreeNode recoverFromPreorder(String traversal) {
        if (null == traversal || traversal.length() ==0){
            return null;
        }
        //拆出来。
        strArr = traversal.split("-");
        //第一个数字是根节点
        TreeNode root = new TreeNode(Integer.parseInt(strArr[0]));
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        stack.add(root);
        int idx = 0;
        while (++idx< strArr.length){
            int level = 1;
            //判断下一个数字的深度
            while (strArr[idx].length()==0){
                idx++;
                level++;
            }
            //从栈顶弹出多余的
            while (stack.size() > level){
                stack.pollLast();
            }
            //构建节点
            TreeNode node = new TreeNode(Integer.parseInt(strArr[idx]));
            //由于序列化的时候是先序遍历，先尝试塞到左节点，如果左节点已经存在，则塞到右节点
            if (stack.peekLast().left == null){
                stack.peekLast().left = node;
            }else{
                stack.peekLast().right = node;
            }
            //当前节点处理完毕，将当前节点压入栈
            stack.addLast(node);
        }
        return root;
    }
}

请实现两个函数，分别用来序列化和反序列化二叉树。

你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

提示：输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

示例：

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

注意：本题与主站 297 题相同：https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/

Java层序遍历【联动 1028. 从先序遍历还原二叉树】

就我们在力扣上做二叉树相关的题目的时候，例子说明中常用到的[1,2,3,null,null,4,5]这种写法，
两边方括号可以直接省略，
序列化

1. 按层遍历，用逗号分割
2. 空节点用自定义字符串表示
3. 先广度优先搜索序列化成字符串，如果当前节点是空节点，用自定义字符串表示，且不再加入遍历用到的Queue
4. 最后记得删掉多加的一个逗号

反序列化

1. 依旧类似广度优先搜索
2. 字符串按照逗号分割得到每个节点的信息
3. 从头结点开始往下拼装，用一个Queue保存上一层的节点内容
4. 因为会遇到空节点，Queue中需要拼接上去的上层节点的时候需要先从Queue中找到最先的那个不是空节点的节点
5. 先拼左子节点再拼右子节点，因为右子节点可能没有，所以需要额外判断下字符串分割得到的数组越界的情况

其他方案

1. 当然也可以选择中序遍历+前序遍历 或者中序遍历+后序遍历这样的处理办法，但是序列化获得的字符串相应的应该会变大
2. 或者也可以直接参考【1028】从先序遍历还原二叉树 这题的方法，自行再写个序列化字符串的方法来完成本题
3. 也许你可以直接看下力扣官方的一个功能Playground ，对，就是顶上那个小铃铛图标左边那个光标带加号里的代码

本题层序遍历代码

public class Codec {
    
    private String NULL = "N";

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null){
            return "";
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        StringBuffer sb = new StringBuffer();
        while (!queue.isEmpty()){
            TreeNode node = queue.poll();
            sb.append(node == null?NULL:node.val).append(",");
            if (node != null){
                queue.offer(node.left);
            }
            if (node != null){
                queue.offer(node.right);
            }
        }
        sb.delete(sb.length()-1,sb.length());
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data.length()==0){
            return null;
        }
        String[] arr = data.split(",");
        TreeNode root = new TreeNode(Integer.parseInt(arr[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int idx = 0;
        while (++idx < arr.length){
            while (!queue.isEmpty() && queue.peek()==null){
                queue.poll();
            }
            TreeNode curr = queue.poll();
            TreeNode left = arr[idx].equals(NULL)?null:new TreeNode(Integer.parseInt(arr[idx]));
            queue.offer(left);
            curr.left = left;
            if (idx+1 < arr.length){
                idx++;
                TreeNode right = arr[idx].equals(NULL)?null:new TreeNode(Integer.parseInt(arr[idx]));
                curr.right = right;
                queue.offer(right);
            }
        }

        return root;
    }
}

给出一个单词数组 words ，其中每个单词都由小写英文字母组成。

如果我们可以 不改变其他字符的顺序 ，在 wordA 的任何地方添加 恰好一个 字母使其变成 wordB ，那么我们认为 wordA 是 wordB 的 前身 。

• 例如，"abc" 是 "abac" 的 前身 ，而 "cba" 不是 "bcad" 的 前身

词链是单词 [word_1, word_2, ..., word_k] 组成的序列，k >= 1，其中 word1 是 word2 的前身，word2 是 word3 的前身，依此类推。一个单词通常是 k == 1 的 单词链 。

从给定单词列表 words 中选择单词组成词链，返回 词链的 最长可能长度 。
 

示例 1：

输入：words = ["a","b","ba","bca","bda","bdca"]
输出：4
解释：最长单词链之一为 ["a","ba","bda","bdca"]

示例 2:

输入：words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]
输出：5
解释：所有的单词都可以放入单词链 ["xb", "xbc", "cxbc", "pcxbc", "pcxbcf"].

示例 3:

输入：words = ["abcd","dbqca"]
输出：1
解释：字链["abcd"]是最长的字链之一。
["abcd"，"dbqca"]不是一个有效的单词链，因为字母的顺序被改变了。

提示：

• 1 <= words.length <= 1000
• 1 <= words[i].length <= 16
• words[i] 仅由小写英文字母组成。

凑合还行，java，我也不知道叫啥了，试试使用并发类？

勉强97.26%

双指针判断前身字符串，
哈希表把字符串按长度整理好
当前字符串和长度加1的字符串集合对比，
然后从最短的一组开始尝试作为起始点，每次取到最长长度后取最大值

代码

class Solution {
    public int longestStrChain(String[] words) {
        HashMap<Integer, List<String>> hashMap = new HashMap<>();

        int minLength = 1000;
        int maxLength = 0;
        for (String word : words) {
            minLength = Math.min(minLength,word.length());
            maxLength = Math.max(maxLength,word.length());
            if (!hashMap.containsKey(word.length())){
                hashMap.put(word.length(),new ArrayList<>());
            }
            hashMap.get(word.length()).add(word);
        }
        int res = 1;
        for (int currentLength = minLength; res+currentLength <= maxLength; currentLength++) {
            int l = currentLength;
            int chainL = 1;
            List<String> stringList = hashMap.get(l);
            HashSet<String> nextStrings = new HashSet<>();
            l++;

            while (hashMap.containsKey(l)){
                List<String> nextList = hashMap.get(l);
                for (String str1 : stringList) {
                    for (String str2 : nextList) {
                        if (isBefore(str1,str2)){
                            nextStrings.add(str2);
                        }
                    }
                }
                if (nextStrings.size()>0){
                    chainL++;
                }else{
                    break;
                }
                l++;
                stringList = new ArrayList<>(nextStrings);
                nextStrings.clear();
            }
            res = Math.max(chainL,res);
        }

        return res;
    }

    /**
     * 双指针
     */
    private boolean isBefore(String str1, String str2){
        int idx1 = 0;
        int idx2 = 0;
        //头对齐
        if (str1.charAt(0)!= str2.charAt(0)){
            idx2 = 1;
        }
        while (idx1 < str1.length() && idx2< str2.length()){
            while (idx2< str2.length() && str1.charAt(idx1) != str2.charAt(idx2)){
                idx2++;
            }
            if (idx2< str2.length() && str1.charAt(idx1) == str2.charAt(idx2)){
                idx2++;
                idx1++;
            }
        }
        return idx1 == str1.length();
    }
}

以及一些碎碎念

当res+currentLength <= maxLength的时候，如果不停止的话，后面算到的res值只会越来越小
如果用currentLength < maxLength判断的话就会变成击败5%了

当然还有个地方能优化

if (isBefore(str1,str2)){
    nextStrings.add(str2);
    hashMap.get(l).remove(str2);
}

算过的字符串就完全可以删掉了以后不用再算了，可以删除掉
但是会引发

java.util.ConcurrentModificationException

所以原来哈希表要换成

HashMap<Integer, CopyOnWriteArrayList<String>> hashMap

不过好像没啥提升，看起来这边的瓶颈不在这里
但是删掉处理过的字符串之后即使是用 currentLength < maxLength 也能击败94%了

给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

进阶：不要 使用任何内置的库函数，如  sqrt 。

示例 1：

输入：num = 16
输出：true

示例 2：

输入：num = 14
输出：false

提示：

• 1 <= num <= 2^31 - 1

两分

r = 46341,你是int 别往外找了、别往外找了、别往外找了、别往外找了、别往外找了

class Solution {
    public boolean isPerfectSquare(int num) {
        int l = 0;
        int r = 46341;
        while (l<r){
            int mid = l + ((r - l) >> 1);
            int tmp = mid * mid;
            if (tmp == num){
                return true;
            }
            if (tmp < num){
                l = mid + 1;
            }else{
                r = mid - 1;
            }

        }
        return l*l == num;
    }
}

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

例如，

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

• void addNum(int num) – 从数据流中添加一个整数到数据结构中。
• double findMedian() – 返回目前所有元素的中位数。

示例 1：

输入：
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
输出：[null,null,null,1.50000,null,2.00000]

示例 2：

输入：
["MedianFinder","addNum","findMedian","addNum","findMedian"]
[[],[2],[],[3],[]]
输出：[null,null,2.00000,null,2.50000]

限制：

• 最多会对 addNum、findMedian 进行 50000 次调用。

注意：本题与主站 295 题相同：https://leetcode-cn.com/problems/find-median-from-data-stream/

【双薯片桶算法】又见薯片桶

本来其实看到困难题有点多想，不过回想了下之前做的这题，我的题解剑指 Offer 09. 用两个栈实现队列（简单） ， 再想想这题，好像….也没那么复杂了

借一次之前的图

我们需要的其实是一个队列。但是和之前不同的是这次是有序的，我们要从这个有序队列中取中间那个值。

这样，我们把原来的两个栈换成两个堆，一个大顶堆，一个小顶堆，那么对应这上面这个图

1. 左边一个大顶堆，堆顶是最大值
2. 右边一个小顶堆，堆顶是最小值
3. 每插入一个值的时候判断下是应该往左边的插还是往右边插，小于等于左边的最大值，就往左边插，大于等于右边的最小值，就往右边插，只要做一个判断即可
4. 插入之后对两个堆做一下平衡，保证左边堆的数量等于右边堆的数量，或者等于右边堆的数量加1，就如同上面的两个薯片桶从左往右倒一个，或者从右往左倒一个
5. 不同于之前的栈维护的队列，堆附带自动排序的属性，所以你可以认为把一个数字插入其中一个堆里的时候，可以自动将他排序到对应的正确位置，这是一个比较智能的薯片桶

代码

class MedianFinder {

    PriorityQueue<Integer> left;
    PriorityQueue<Integer> right;

    /** initialize your data structure here. */
    public MedianFinder() {
        left = new PriorityQueue<>((a,b)-> b-a);
        right = new PriorityQueue<>();
    }
    
    public void addNum(int num) {
        if (left.size()==0||num<=left.peek()){
            left.offer(num);
        }else{
            right.offer(num);
        }
        if (left.size() - right.size()>1){
            right.offer(left.poll());
        }else if (right.size() > left.size()){
            left.offer(right.poll());
        }
    }
    
    public double findMedian() {
        if (left.size() == right.size()){
            return ((double) (left.peek() + right.peek()))/2;
        }else{
            return (double)left.peek();
        }
    }
}

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。

换句话说，第一个字符串的排列之一是第二个字符串的 子串 。

示例 1：

输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").

示例 2：

输入: s1= "ab" s2 = "eidboaoo"
输出: False

提示：

• 1 <= s1.length, s2.length <= 104
• s1 和 s2 仅包含小写字母

注意：本题与主站 567 题相同： https://leetcode-cn.com/problems/permutation-in-string/

滑动窗口基本思路

基本滑动窗口算法
挪一格，修改一下统计数量，然后对比两个数组内是否相同

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length()>s2.length()){
            return false;
        }
        
        int[] count = new int[26];
        int[] window = new int[26];
        int idx = -1;
        while (++idx < s1.length()){
            count[s1.charAt(idx)-'a']++;
            window[s2.charAt(idx)-'a']++;
        }
        if (Arrays.equals(count,window)){
            return true;
        }
        idx--;
        while (++idx < s2.length()){
            System.out.println( idx );
            window[s2.charAt( idx - s1.length() ) - 'a']--;
            window[s2.charAt( idx ) - 'a']++;
            if (Arrays.equals(count,window)){
                return true;
            }
        }
        return false;
    }

}

滑动窗口diffArr判断算法，判断26个字母数量是否为0，如果是都是0则代表能匹配

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length()>s2.length()){
            return false;
        }

        int[] diffArr = new int[26];
        int idx = -1;
        int diffCount = 0;
        while (++idx < s1.length()){
            diffArr[s1.charAt(idx)-'a']++;
            diffArr[s2.charAt(idx)-'a']--;
        }
        boolean flag = true;
        for (int i = 0; i < 26; i++) {
            if (diffArr[i]!=0){
                flag =false;
                break;
            }
        }
        if (flag){
            return true;
        }
        --idx;
        while (++idx < s2.length()){
            diffArr[s2.charAt(idx-s1.length())-'a']++;
            diffArr[s2.charAt(idx)-'a']--;
            flag = true;
            for (int i = 0; i < 26; i++) {
                if (diffArr[i]!=0){
                    flag =false;
                    break;
                }
            }
            if (flag){
                return true;
            }
        }
        return false;
    }

}

第二种滑动窗口的理解稍微绕个弯，每当diffArr中有一个不是0的，说明有一个差异点，
然后接下来窗口滑动过程中 需要在修改前判断

1. 这个值是不是0，如果是0，修改了之后diffCount需要加1，
2. 如果不是0.修改之后会不会变0.如果会变0，diffCount减1
3. 如果修改后不会变0，则diffCount不需要变更

if判断太多，效率甚至不如上一个遍历一下长度只有26的diffArr数组

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length()>s2.length()){
            return false;
        }

        int[] diffArr = new int[26];
        int idx = -1;
        int diffCount = 0;
        while (++idx < s1.length()){
            diffArr[s1.charAt(idx)-'a']++;
            diffArr[s2.charAt(idx)-'a']--;
        }
        int i = -1;
        while (++i<26){
            diffCount += diffArr[i]==0?0:1;
        }
        if (diffCount==0){
            return true;
        }

        --idx;
        while (++idx < s2.length()){
            int before = s2.charAt(idx-s1.length())-'a';
            int current = s2.charAt(idx)-'a';
            if (before == current){
                continue;
            }
            if (diffArr[before]==-1){
                diffCount--;
            }
            if (diffArr[before] == 0){
                diffCount++;
            }
            diffArr[before]++;

            if (diffArr[current]==1){
                diffCount--;
            }
            if (diffArr[current]==0){
                diffCount++;
            }
            diffArr[current]--;
            if (diffCount == 0){
                return true;
            }
        }
        return false;
    }

}