作者： CheungQ

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

示例 1：

输入：nums = [1,2,0]
输出：3

示例 2：

输入：nums = [3,4,-1,1]
输出：2

示例 3：

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

提示：

• 1 <= nums.length <= 5 * 105
• -231 <= nums[i] <= 231 - 1

题解

如果不限条件的话，额外申请一个hash表，遍历数组，记录每个在遍历过程中遇到的数字，遍历完成后，再从1开始自增到hash中查询，第一个查不到的即为结果。

代码简单

class SolutionByHashSet {
        Set<Integer> set;
        public int firstMissingPositive(int[] nums) {
            set = new HashSet<>();
            for (int num : nums) {
                if (num>=0 && num<=num){
                    set.add(num);
                }
            }
            for (int i = 1; i <= nums.length; i++) {
                if (!set.contains(i)){
                    return i;
                }
            }
            return nums.length+1;
        }
    }

但是题目要求，常数级别额外空间，就需要再想想了，题目提供的是数组，而数组组和连续正数相关的话，自然会想到数组索引下标，那么依次遍历，把对应的值放到对应下标位置上是不是可行呢？不过不同的是，把数字1放在下标0的位置，数字2，放在下标1的位置……这样的方法。

拿用例想一下试试【3,4,-1,1】

• 下标0位置得到数字3，那么3应该把他放到下标2的位置，所以两个下标上面的值进行交换得到新的数组【-1,4,3,1】
• 此时下标0位置的值为-1，-1这个值找不到对应的下标下标上去放置，那么我们再去处理下标1位置的值
• 到了下标1之后，这个位置的值是4，把它和对应下标3位置的值交换，得到新的排序【-1,1,3,4】。
• 此时下标1位置的值为1，继续把这个值和对应下标0的位置值交换，新的数组排序是【1,-1,3,4】
• 此时下标1位置的值为-1，那么去处理下一个下标位置上的值，后面略过，因为对应位置的值都是对应的

最终再从头开始遍历一遍判断对应下标置上的值是否是+1的数字

代码

class Solution {
    public int firstMissingPositive(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            while (nums[i]!= i+1){
                //终止条件
                //当前位置上的值再不能对应到nums的索引0到nums.length-1上
                //即，nums[i]的值在1-nums.length之间，包含区间
                if (nums[i] < 1 || nums[i]>nums.length){
                    break;
                }
                //有重复值
                if (nums[i] == nums[nums[i]-1]){
                    break;
                }
                swap(nums,i,nums[i]-1);
                //当前位置的值等于对应值，即nums[i]== i+1这个发生在交换之后
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i]!= i+1){
                return i+1;
            }
        }
        return nums.length+1;
    }


    private void swap(int[] nums, int index1, int index2){
        int tmp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = tmp;
    }
}

最后提交的时候还是漏了一个里面有重复值的情况。于是再次加了个

if (nums[i] == nums[nums[i]-1]){
    break;
}

给定一个字符串 s 和一个整数 k，从字符串开头算起，每 2k 个字符反转前 k 个字符。

• 如果剩余字符少于 k 个，则将剩余字符全部反转。
• 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例 1：

输入：s = "abcdefg", k = 2
输出："bacdfeg"

示例 2：

输入：s = "abcd", k = 2
输出："bacd"

提示：

• 1 <= s.length <= 104
• s 仅由小写英文组成
• 1 <= k <= 104

题解

8月20日每日一题，简单

转换成char数组，然后从下标0开始，往后k个，一次分段内翻转，一次调过不动作，如此循环。

最后一个循环如果需要翻转，且往后k个位置数组越界了，则取数组最后下标

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {


    public String reverseStr(String s, int k) {
        k--;
        char[] chars = s.toCharArray();
        boolean ifSkip = false;
        for (int i = 0; i < s.length(); i += k+1) {
            if (ifSkip){
                ifSkip = false;
            }else{
                ifSkip = true;
                reverseSubStr(chars,i, Math.min(i + k, chars.length - 1));
            }
        }
        return new String(chars);
    }


    public void reverseSubStr(char[] s,int left, int right){
        char tmp;
        while (left < right){
            tmp = s[left];
            s[left++] = s[right];
            s[right--] = tmp;
        }
    }

}
//leetcode submit region end(Prohibit modification and deletion)

为啥我一开始要k–呢，因为下面每次遍历子分段边界的问题。

另外每次for循环的时候会差一个，所以额外需要再加1。

当然也可以每次移动2k个位置。然后运用双指针，把开头和到k位置的字符翻转

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。

返回同样按升序排列的结果链表。

示例 1：

输入：head = [1,1,2]
输出：[1,2]

示例 2：

输入：head = [1,1,2,3,3]
输出：[1,2,3]

提示：

• 链表中节点数目在范围 [0, 300] 内
• -100 <= Node.val <= 100
• 题目数据保证链表已经按升序排列

题解

//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode current = head;
        while (current!=null && current.next != null){
            if (current.val == current.next.val){
                current.next = current.next.next;
            }else{
                current = current.next;
            }
        }
        return head;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

示例 2：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提示：

• 1 <= nums.length <= 8
• -10 <= nums[i] <= 10

题解

回溯，同LeetCode刷题【剑指 Offer 38】字符串的排列

代码

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    List<List<Integer>> res;
    int[] nums;
    HashSet<Integer> samIndex;
    public List<List<Integer>> permuteUnique(int[] nums) {
        res = new ArrayList<>();
        samIndex = new HashSet<>();
        this.nums = nums;
        dfs(new ArrayList<>());
        return res;
    }


    private void dfs(List<Integer> list){
        if (list.size()==nums.length){
            res.add(new ArrayList<>(list));
            return;
        }
        HashSet<Integer> sameNum = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (samIndex.contains(i)){
                continue;
            }
            int num = nums[i];
            if (sameNum.contains(num)) {
                continue;
            }
            samIndex.add(i);
            sameNum.add(num);
            list.add(num);
            dfs(list);
            samIndex.remove(i);
            list.remove(list.size() - 1);
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• nums 中的所有元素 互不相同

题解

作为算法中常用的一个方法，根据已知推导未知，我们可以这样处理。

要求长度为n的数组的子集一下子不好看出来，那么可以先从简单的情况开始处理，然后处理多加了一个元素的情况，处理后再依次增加处理直到达到了数组原来的长度n的情况。首先假定一个数组【1,2,3,4】

当数组为空的时候只有一种情况[[]]

当数组长度为1的时候[[],[1]]

当数组长度为2的时候[[],[1],[2],[1,2]]

当数组长度为3的时候[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

当数组长度为4的时候[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3],[4],[1,4],[2,4],[1,2,4],[3,4],[1,3,4],[2,3,4],[1,2,3,4]]

这样就很好理解了，每增加一个元素，即表示在原来的结果基础上又增加了额外一个选项，所以，对原来的结果进行遍历，分别加上新加上的选项，而新加的选项是可以不选的，原来的结果也要保留。这样就很明显了，代码：

import java.util.ArrayList;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        res.add(new ArrayList<>());
        for (int i = 0; i < nums.length; i++) {
            //根据已知求未知，
            //当nums数组中有i个元素的时候，
            // 其结果集等于原来的i-1个元素的时候的结果集中的元素分别加上i，
            // 把i-1个元素的结果集和i个元素的结果集合并
            List<List<Integer>> tmp = new ArrayList<>();
            for (List<Integer> re : res) {
                List<Integer> reCopy = new ArrayList<>(re);
                reCopy.add(nums[i] );
                tmp.add(reCopy);
            }
            res.addAll(tmp);
        }
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

状态枚举。emm假装自己是二进制运算

import java.util.ArrayList;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        res = new ArrayList<>();
        res.add(new ArrayList<>());
        numsArr = nums;
        statusArr = new boolean[nums.length];
        while (!finished){
            doPlus();
        }
        return res;
    }

    boolean[] statusArr;
    boolean finished = false;
    int[] numsArr;
    List<List<Integer>> res;
    public void doPlus(){
        boolean step = true;
        for (int i = statusArr.length - 1; i >= 0 && step; i--) {
            if (!statusArr[i]){
                statusArr[i]=true;
                step = false;
            }else{
                statusArr[i]=false;
            }
        }
        List<Integer> tmp = new ArrayList<>();
        for (int i = 0; i < statusArr.length; i++) {
            if (statusArr[i]){
                tmp.add(numsArr[i]);
            }
        }
        res.add(tmp);
        if (tmp.size()==numsArr.length){
            finished = true;
        }
    }

}
//leetcode submit region end(Prohibit modification and deletion)

给定一棵二叉搜索树和其中的一个节点 p ，找到该节点在树中的中序后继。如果节点没有中序后继，请返回 null 。

节点 p 的后继是值比 p.val 大的节点中键值最小的节点，即按中序遍历的顺序节点 p 的下一个节点。

示例 1：

输入：root = [2,1,3], p = 1
输出：2
解释：这里 1 的中序后继是 2。请注意 p 和返回值都应是 TreeNode 类型。

示例 2：

输入：root = [5,3,6,2,4,null,null,1], p = 6
输出：null
解释：因为给出的节点没有中序后继，所以答案就返回 null 了。

提示：

• 树中节点的数目在范围 [1, 104] 内。
• -105 <= Node.val <= 105
• 树中各节点的值均保证唯一。

注意：本题与主站 285 题相同： https://leetcode-cn.com/problems/inorder-successor-in-bst/

题解

一看题目，二叉搜索树、中序后继这两个关键词，那么好说直接先上个中序遍历，记录下上一次访问的节点，如果上次的节点是目标节点，则当前访问到的节点就是这个节点的中序后继节点。

如果想要优化则需要对状态严格判断下需要中断的条件，容易疏漏，和这题思路一样。LeetCode刷题【面试题04.06】 后继者。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    TreeNode target;
    TreeNode lastVisited;
    TreeNode follower;

    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        target = p;
        dfs(root);
        return follower;
    }

    private void dfs(TreeNode root){
        if (root == null || follower!=null) {
            return;
        }
        dfs(root.left);
        //中序
        if (follower==null && lastVisited!= null && lastVisited.val == target.val){
            follower = root;
        }
        lastVisited = root;
        dfs(root.right);
    }
}

那么再看下，本题中给出的是确定的一棵二叉搜索树，根据二叉搜索树的特性，左节点比根节点小，根节点比右节点小。可以根据这个条件来查找目标节点p。

找到p之后就需要再找到他的后继节点，分两种情况

• 假如p节点有右子节点，从p节点的右子节点开始往下找出最大的节点，即从右子树上最左边的节点。
• 假如p节点在某个节点的左子树上，那么他的后继节点也可能是这个左子树的根节点，即最后一次往左子树上寻找p节点的时候的那个节点。
• 右子节点的判定需要在左子树的判断优先级之上，因为BST的特性左子树上节点最小也比根节点小。

所以，代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    TreeNode lastBigger;
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        return dfs(root,p);
    }

    private TreeNode search(TreeNode root, TreeNode p){
        if (root.val == p.val){
            //如果有右子树，找出右子树中最大的
            if (root.right != null){
                TreeNode node = root.right;
                while (node.left != null){
                    node = node.left;
                }
                return node;
            }else{
                //如果没有右子树,则找到之前记录的比他大的后继节点中最小的
                return lastBigger;
            }
        }else{
            if (root.val > p.val){
                //这个节点比p节点大，记录下来
                lastBigger = root;
                return dfs(root.left,p);
            }else{
                return dfs(root.right,p);
            }
        }
    }

}
//leetcode submit region end(Prohibit modification and deletion)

序列化是将数据结构或对象转换为一系列位的过程，以便它可以存储在文件或内存缓冲区中，或通过网络连接链路传输，以便稍后在同一个或另一个计算机环境中重建。

设计一个算法来序列化和反序列化 二叉搜索树 。 对序列化/反序列化算法的工作方式没有限制。 您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序列化为最初的二叉搜索树。

编码的字符串应尽可能紧凑。

示例 1：

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

示例 2：

输入：root = []
输出：[]

提示：

• 树中节点数范围是 [0, 104]
• 0 <= Node.val <= 104
• 题目数据 保证 输入的树是一棵二叉搜索树。

注意：不要使用类成员/全局/静态变量来存储状态。 你的序列化和反序列化算法应该是无状态的。

题解

因为这是一棵搜索树，利用前序遍历的特性就可以，还原过程和之前的LeetCode刷题【1008】前序遍历构造二叉搜索树样

import java.util.ArrayList;
import java.util.List;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    List<Integer> list;

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        list = new ArrayList<>();
        dfs(root);
        return listToString();
    }

    //先序遍历记录内容
    public void dfs(TreeNode root){
        if (root == null) {
            return;
        }
        list.add(root.val);
        dfs(root.left);
        dfs(root.right);
    }

    public String listToString(){
        if (list.size()==0){
            return "";
        }
        StringBuilder str = new StringBuilder(""+list.get(0));
        for (int i = 1; i < list.size(); i++) {
            str.append(",").append(list.get(i));
        }
        return str.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data==null || data.length()==0){
            return null;
        }
        list = new ArrayList<>();
        String[] arr = data.split(",");
        for (String num : arr) {
            list.add(Integer.parseInt(num));
        }
        return deserializeByPreOrder(0,arr.length-1);
    }

    public TreeNode deserializeByPreOrder(int left, int right){
        if (left>right){
            return null;
        }
        TreeNode node = new TreeNode(list.get(left));
        if (left==right){
            return node;
        }
        //找到比node大的那个值为右子树的根节点
        int rightBegin = left;
        left++;
        while (rightBegin<=right && list.get(rightBegin) <= node.val){
            rightBegin++;
        }
        node.left = deserializeByPreOrder(left,rightBegin-1);
        node.right = deserializeByPreOrder(rightBegin,right);
        return node;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// String tree = ser.serialize(root);
// TreeNode ans = deser.deserialize(tree);
// return ans;
//leetcode submit region end(Prohibit modification and deletion)

因为是二叉搜索树，有着明显的大小值有序的特性。

如果换成是普通的二叉树，可以用BFS的方式序列化处理。null节点使用特殊非数字的字符替代即可或者直接留空可以，解析的时候同样按“,”逗号分割，如果得到的是空字符串则表示null。

还有一个通用二叉树的思路，比如有二叉树如下

             5
           /   \
          4     7
         /     / \
         2   6   8
          \
          3

按照结构序列化如下，使用“[”“]”“,”来分割表示

5[4[,2[,3]],],7[6,8]]

借助栈的先进后出的特性，来实现，分析过程如下

• 读取到5，构建一个val为5的node节点入栈，此时栈内元素【5】
• 读取到4，继续构建入栈，此时栈内元素【4,5】
• 读取到一个空节点，构建个空节点入栈，此时栈内元素【null,4,5】
• 读取到2，构建一个2节点入栈，此时栈内元素【2,null,4,5】
• 读取到一个空节点，构建一个空节点入栈，此时栈内元素【null,2,null,4,5】
• 读取到3，构建个3节点入栈，此时栈内元素【3,null,2,null,4,5】
• 接下来是关键，遇到了“]”字符，取出栈顶两个元素，依次分别为取出后栈顶元素的右节点和左节点，即3节点为2节点的右子节点，null节点为2节点的左子节点。此时栈内元素【2,null,4,5】，2下面挂靠了null和3节点
• 接下来又遇到了“]”字符，同样取出栈顶两个元素，挂靠到对应节点下面，即2节点挂到4节点的右子节点位置，null节点挂在4节点的左子节点位置，此时栈内元素【4,5】
• 之后继续遇到了7，创建节点并入栈。【7,4,5】
• 又分别遇到了6和7，继续入栈。【8,6,7,4,5】
• 再次遇到“]”，把弹出放在7节点下。此时栈内剩下【7,4,5】
• 再次遇到“]”，把7、4节点弹出放在5节点下
• 最终结束二叉树构建完成