月度归档： 2021年8月

给定一个可包含重复数字的序列 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节点下
• 最终结束二叉树构建完成

给你一棵二叉树，它的根为 root 。请你删除 1 条边，使二叉树分裂成两棵子树，且它们子树和的乘积尽可能大。

由于答案可能会很大，请你将结果对 10^9 + 7 取模后再返回。

示例 1：

输入：root = [1,2,3,4,5,6]
输出：110
解释：删除红色的边，得到 2 棵子树，和分别为 11 和 10 。它们的乘积是 110 （11*10）

示例 2：

输入：root = [1,null,2,3,4,null,null,5,6]
输出：90
解释：移除红色的边，得到 2 棵子树，和分别是 15 和 6 。它们的乘积为 90 （15*6）

示例 3：

输入：root = [2,3,9,10,7,8,6,5,4,11,1]
输出：1025

示例 4：

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

提示：

• 每棵树最多有 50000 个节点，且至少有 2 个节点。
• 每个节点的值在 [1, 10000] 之间。

题解

1.求出二叉树总和

2.找到一个节点上的总和，最接近于树上总和的一半

3.求出面积即是结果

4.为啥是一半呢，看代码中间的注释

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    double sum = 0;
    double halfSum = 0;
    double nearHalf = 0;
    public int maxProduct(TreeNode root) {
        //两数之和固定，两数需要乘积最大化，则两个数应当无限接近，最优解为两数之和的一半
        //类似于一根固定长的绳子摆成矩形的两个相邻边，要求使矩形面积最大化，这是一个高中还是初中数学题来着
        //假设这条绳子长为 2x，分成两段
        // 一段长度为 x - t , 另一段的长度就为 x + t
        //（ x - t ）* （ x + t ） <= x^2
        // x^2 + x*t - x*t - t^2  <= x^2
        // x^2 - t^2 <= x^2
        // 有且只有当t = 0 的时候面积最大
        sum = dfs(root);
        halfSum = sum/2;
        dfsNearHalf(root);
        return (int)((sum-nearHalf)*nearHalf%1000000007);

    }


    private double dfsNearHalf(TreeNode node){
        if(node==null){
            return 0;
        }
        double tempSum = node.val + dfsNearHalf(node.left) + dfsNearHalf(node.right);
        nearHalf = Math.abs(nearHalf - halfSum) > Math.abs(tempSum-halfSum)?tempSum:nearHalf;
        return tempSum;
    }


    private double dfs(TreeNode node){
        if(node==null){
            return 0;
        }
        return node.val + dfs(node.left) + dfs(node.right);
    }
}
//leetcode submit region end(Prohibit modification and deletion)

其实也可以第一DFS之后把结果缓存起来，在然后遍历缓存起来的结果，找到最接近的那个，或者在第二次dfs的之后从缓存里取结果，而不是再算一次，但是这两种我都试了下。效率还没有再算一次的效率高。

给你一个字符串 s 表示一个学生的出勤记录，其中的每个字符用来标记当天的出勤情况（缺勤、迟到、到场）。记录中只含下面三种字符：

• 'A'：Absent，缺勤
• 'L'：Late，迟到
• 'P'：Present，到场

如果学生能够 同时 满足下面两个条件，则可以获得出勤奖励：

• 按 总出勤 计，学生缺勤（'A'）严格 少于两天。
• 学生 不会 存在 连续 3 天或 3 天以上的迟到（'L'）记录。

如果学生可以获得出勤奖励，返回 true ；否则，返回 false 。

示例 1：

输入：s = "PPALLP"
输出：true
解释：学生缺勤次数少于 2 次，且不存在 3 天或以上的连续迟到记录。

示例 2：

输入：s = "PPALLL"
输出：false
解释：学生最后三天连续迟到，所以不满足出勤奖励的条件。

提示：

• 1 <= s.length <= 1000
• s[i] 为 'A'、'L' 或 'P'

题解

8月17日每日一题

一次遍历。两个变量统计判断，没啥复杂的

public boolean checkRecord(String s) {
        if (s == null || s.length() <=1){
            return true;
        }
        // 'A'：Absent，缺勤
        // 'L'：Late，迟到
        // 'P'：Present，到场
        if (s.length()==2){
            return !(s.charAt(0)=='A'&& s.charAt(1)=='A');
        }

        int aCount = 0;
        int lCount = 0;
        //先把前两位的算下
        for (int i = 0; i < 2; i++) {
            if (s.charAt(i)=='A'){
                aCount++;
            }
            if (s.charAt(i)=='L'){
                lCount++;
            }else{
                lCount=0;
            }
        }
        //从第三天开始需要判断
        for (int i = 2; i < s.length(); i++) {
            if (s.charAt(i)=='A'){
                aCount++;
                //只要总缺勤天数达到了2，就说明不符合
                if (aCount >= 2){
                    return false;
                }
                //额。。。。这个，。。没上课的时候连续迟到也归零，
                //所以 LLA 的可以获得出勤奖励
                //而 LLL 的得不到出勤奖励
                lCount=0;
            }else if (s.charAt(i)=='L'){
                //如果当天迟到了，连续迟到天数加1，
                lCount++;
                if (lCount == 3){
                    //当连续迟到了3天，则不符合
                    return false;
                }
            }else{
                //如果当天没迟到，则连续迟到的记录归零
                lCount=0;
            }
        }
        return true;
    }

不过有点点点小问题。。我注解里写的

LLA 的可以获得出勤奖励，而 LLL 的得不到出勤奖励，第三天假如迟到的话不如直接缺勤…….emmmm

给你一棵二叉树的根节点 root ，树中有 n 个节点，每个节点都有一个不同于其他节点且处于 1 到 n 之间的值。

另给你一个由 n 个值组成的行程序列 voyage ，表示 预期 的二叉树 先序遍历 结果。

通过交换节点的左右子树，可以 翻转 该二叉树中的任意节点。例，翻转节点 1 的效果如下：

请翻转 最少 的树中节点，使二叉树的 先序遍历 与预期的遍历行程 voyage 相匹配 。 

如果可以，则返回 翻转的 所有节点的值的列表。你可以按任何顺序返回答案。如果不能，则返回列表 [-1]。

示例 1：

输入：root = [1,2], voyage = [2,1]
输出：[-1]
解释：翻转节点无法令先序遍历匹配预期行程。

示例 2：

输入：root = [1,2,3], voyage = [1,3,2]
输出：[1]
解释：交换节点 2 和 3 来翻转节点 1 ，先序遍历可以匹配预期行程。

示例 3：

输入：root = [1,2,3], voyage = [1,2,3]
输出：[]
解释：先序遍历已经匹配预期行程，所以不需要翻转节点。

提示：

• 树中的节点数目为 n
• n == voyage.length
• 1 <= n <= 100
• 1 <= Node.val, voyage[i] <= n
• 树中的所有值 互不相同
• voyage 中的所有值 互不相同

题解

还是考验的对先序遍历的理解，如果同时有左右子节点，左子树的遍历节点在右子树的遍历节点之前。

所以只要判断右子节点的是否出现在当前节点的下一个（有左子节点的情况下），这种情况是需要翻转当前节点的左右子节点的。

倘若只有一个子节点，这个子节点放在左边或者右边都不影响最终的遍历顺序。

//leetcode submit region begin(Prohibit modification and deletion)

import java.util.ArrayList;
import java.util.Arrays;

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

    List<Integer> res = new ArrayList<>();
    boolean breaked = false;
    int[] voyage;
    int index = 0;
    public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
        this.voyage = voyage;
        dfs(root);
        if (breaked){
            return Arrays.asList(-1);
        }
        return res;
    }


    private void dfs(TreeNode root){
        if (breaked){
            return;
        }
        if (root==null){
            return;
        }

        //中序遍历的当前节点判断
        if (root.val != voyage[index++]){
            breaked = true;
            return;
        }
        //左右对比
        if (root.left!=null && root.right !=null
                && root.right.val == voyage[index]
        ){
            //左右调换，先右再左
            res.add(root.val);
            dfs(root.right);
            dfs(root.left);
        }else{
            dfs(root.left);
            dfs(root.right);
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)