月度归档： 2022年3月

给定一个二进制数组 nums ，如果最多可以翻转一个 0 ，则返回数组中连续 1 的最大个数。

示例 1：

输入：nums = [1,0,1,1,0]
输出：4
解释：翻转第一个 0 可以得到最长的连续 1。
     当翻转以后，最大连续 1 的个数为 4。

示例 2:

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

提示:

• 1 <= nums.length <= 105
• nums[i] 不是 0 就是 1.

进阶：如果输入的数字是作为 无限流 逐个输入如何处理？换句话说，内存不能存储下所有从流中输入的数字。您可以有效地解决吗？

【动态桂花】详细分析总结过程

自己写个例子试一下看看
[1,0,1,1,0,0,1,1,1,1,0]
定义两个值，一个定义当遍历中的这段有连续多长了。
另一个表示如果翻转这个位置的0变成1能得到连续多长的1字符，如果不是0则之前的连续长度加1

如下

   1,0,1,1,0,0,1,1,1,1,0
a) 1 0 1 2 0 0 1 2 3 4 0
b) 1 2 3 4 3 1 2 3 4 5 5

分析下

1. 第一位为1，则a表示的，当前可以得到的连续长度为1，b同样，如果第一位为0的话，a等于0，b依旧等于1
2. 第二位为0，a的连续性中断了，此时a等于0，b的话可以在之前的a等于1的后面转换一个得到长度为2
3. 第三位为1，此时a继续等于1，b可以在之前的长度上继续延长得到3
4. 第四位为1，同上一步a等于2，b等于4
5. 第五位为0，a的连续性中断了，此时a等于0。如果翻转这里的0可以得到和前面的a等于相连，得到长度为3的连续1数字
6. 第六位依旧为0，a依旧等于0，b只能和前面的第五位的时候的a等于0相连得到长度为1的连续数字1
7. 第七位变为了1，a这里等于1了，b可以连着前面的，此时b等于2
8. 第八、九、十位，都是1，按照前面的规律依次叠加，最终a等于4，b等于5
9. 最后第十一位0，这里的a再次变为0，而把这里的0翻转为1的话只能和前面的第十位的a等于4相连得到一个连续5位的数组1
10. 在这个过程中保存b得到的最大值

确实，动态规划这个问题的代码本身并不是非常难写，困难的是如何总结归纳出正确的转移方程，如何定义出正确的dp数组赋予正确的定义

//当前位置为0 
dp[i][0] = 0 
dp[i][1] = dp[i-1][0]+1 
//当前位置为1 
dp[i][0] = dp[i-1][0]+1 
dp[i][1] = dp[i-1][1]+1

代码

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int[][] dp = new int[nums.length][2];
        dp[0][0] = nums[0];
        dp[0][1] = 1;
        int idx = 0;
        int max = 1;
        while (++idx < nums.length){
            dp[idx][0] = nums[idx] == 0?0:dp[idx-1][0]+1;
            dp[idx][1] = nums[idx] == 0?dp[idx-1][0]+1:dp[idx-1][1]+1;
            max = Math.max(max,dp[idx][1]);
//            System.out.println(Arrays.toString(dp[idx]));
        }
        return max;
    }
}

继续优化的版本就省略了，其实看下上面的分析步骤就可以自己非常容易的总结出如何进一步优化了

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

    1
   / \
  2   2
   \   \
   3    3

示例 1：

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

示例 2：

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

限制：

0 <= 节点个数 <= 1000

注意：本题与主站 101 题相同：https://leetcode-cn.com/problems/symmetric-tree/

递归比较

分析

1. 左节点等于右节点
2. 左节点的左子节点 == 右节点的右子节点
3. 左节点的右子节点 == 右节点的左子节点
4. 没有了

代码

class Solution {
    public boolean isSymmetric(TreeNode root) {
        //如果root==null 直接返回true,
        //否则比较root的左右节点是否相等
        
        return root==null || compare(root.left, root.right);
    }

    public boolean compare(TreeNode nodeL, TreeNode nodeR){
        //如果要比较的两个节点都是null 符合要求，且不用再往下比较了，直接返回true
        if (null == nodeL && null == nodeR){
            return true;
        }
        //进入到了这里的时候，不可能两个都是null了，如果有一个是null，则不是镜像的，返回false
        //如果两个节点都不是null，且两个的值不一样，也表名不是镜像的，返回false,不用再往下比较了
        if (nodeL == null || nodeR == null || nodeL.val != nodeR.val ){
            return false;
        }
        //继续对比两个节点的左右子节点是否对应相等
        //       左节点的左子节点 == 右节点的右子节点
        //且     左节点的右子节点 == 右节点的左子节点
        return compare(nodeL.left, nodeR.right) && compare( nodeL.right, nodeR.left);
    }
}

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

例如输入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9
镜像输出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

限制：

0 <= 节点个数 <= 1000

注意：本题与主站 226 题相同：https://leetcode-cn.com/problems/invert-binary-tree/

深度优先搜索，直接交换

思考

直接交换，从上往下换，或者从下往上换都可以。
注意是交换节点不是交换值，如果当成交换值来处理的话就会陷入非常严重的误区了，交换节点的时候，会连带这这个节点的下面所有子节点一起交换带过去，所以还是比较简单的

代码

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if (null == root){
            return null;
        }
        TreeNode tmp = root.left;
        root.left = mirrorTree(root.right);
        root.right = mirrorTree(tmp);
        return root;
    }
}

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

例如:
给定的树 A:

     3
    / \
   4   5
  / \
 1   2
给定的树 B：

   4 
  /
 1
返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

示例 1：

输入：A = [1,2,3], B = [3,1]
输出：false

示例 2：

输入：A = [3,4,5,1,2], B = [4,1]
输出：true

限制：

0 <= 节点个数 <= 10000

一顿分析

1. 遍历A树的每个节点，找到和B树的头结点值相同的
2. 找到了相同的节点之后，则开始遍历A、B比较值是否相同，如果相同则直接返回true
3. 如果不相等，还得继续遍历A树寻找是否还有节点和B的头结点值相等
4. 更多细节参见代码注释

代码

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        //排除掉null节点的情况，以及递归截止调节
        if (A == null || B == null){
            return false;
        }
        //找到了树头结点相等的
        if (A.val == B.val){
            //从这个节点开始往下比较，如果能匹配则直接返回true
            //如果不能匹配，还得继续遍历找其他的节点看有没和B的头结点相等的
            if( comapre(A,B) ) {
                return true;
            }
        }
        //递归往左下和往右下
        //任意一边有返回能匹配上就可以用 || 条件
        return isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }

    //树比较
    public boolean comapre(TreeNode A, TreeNode B){
        //如果B以及到结尾了，则无论A上此时是啥，都表示能完全匹配上
        if (B == null){
            return true;
        }
        //如果A到结尾了而，B没到结尾，则不能继续匹配了，返回false
        if (A==null){
            return false;
        }
        //A、B都没到结尾，如果不相等的话则直接返回false
        if (A.val != B.val){
            return false;
        }
        //到了这里表示A、B树节点比较目前都是相等的，则继续比较 A左&B左  和 A右&B右
        //两边都要同时满足相等 用 && 条件
        return comapre(A.left,B.left) && comapre(A.right,B.right);
    }
}

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

示例 1:

输入：s = "abaccdeff"
输出：'b'

示例 2:

输入：s = "" 
输出：' '

限制：

0 <= s 的长度 <= 50000

1. 声明一个HashMap<Character,Integer> firstShowMap记录各个字符第一次出现的位置
2. 声明一个HashSet<Character> moreThenOneSet保存出现超过一次的字符
3. 遍历一遍字符串完成上面两个哈希集合的赋值
4. 遍历firstShowMap，对比moreThenOneSet处理只有出现一次的字符
5. 声明firstSingle保存单个的字符和firstSingleIndex对应的出现位置
6. 遍历firstShowMap的过程中如果找到一个新的只出现过一次的字符，两者比较firstSingleIndex，留下位置跟靠前的那一个

代码

class Solution {
    public char firstUniqChar(String s) {
        HashMap<Character,Integer> firstShowMap = new HashMap<>();
        HashSet<Character> moreThenOneSet = new HashSet<>();
        int i = -1;
        while (++i < s.length()){
            if (!firstShowMap.containsKey(s.charAt(i))){
                firstShowMap.put(s.charAt(i),i);
            }else{
                moreThenOneSet.add(s.charAt(i));
            }
        }

        final char[] firstSingle = {' '};
        final int[] firstSingleIndex = {s.length()};
        firstShowMap.forEach((theChar,theIndex)->{
            if (!moreThenOneSet.contains(theChar)){
                if (theIndex < firstSingleIndex[0]){
                    firstSingleIndex[0] = theIndex;
                    firstSingle[0] = theChar;
                }
            }
        });
        return firstSingle[0];
    }
}

思路就是这样，实现形式有很多种
比如

1. firstSingleIndex也可以不存下来，直接回firstShowMap中取到
2. 又或者官方题解中说的那样的moreThenOneSet可以省略，有重复的直接修改firstShowMap对应的value为一个不合理的值，后面判断的时候也就根据这个不合理的值来判断。

21年11月30日，重新做了一次这个题目

class Solution {
    public char firstUniqChar(String s) {
        if (s.length()==0){
            return ' ';
        }
        //重复的
        boolean[] map1 = new boolean[26];
        //第一次出现的位置
        int[] map2 = new int[26];
        Arrays.fill(map2,-1);
        int idx = -1;
        while (++idx < s.length()){
            int charIdx = s.charAt(idx)-'a';
            if (!map1[charIdx]){
                if (map2[charIdx] != -1){
                    map1[charIdx] = true;
                    map2[charIdx] = -1;
                }else{
                    map2[charIdx] = idx;
                }
            }
        }
        char ans = ' ';
        int min = s.length();
        for (int i = 0; i < map2.length; i++) {
            if (map2[i] != -1 &&  map2[i] < min){
                min = map2[i];
                ans = s.charAt(min);
            }
        }
        return ans;
    }
}

再次思考，也可以不用两个map，在一个map上定义更多的状态来实现，除了现有的-1表示默认没处理的情况，也可以再定一个-2为已经有多个相同字符出现的情况

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

例如:
给定二叉树: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回其层次遍历结果：

[
  [3],
  [20,9],
  [15,7]
]

提示：

1. 节点总数 <= 1000

接上文JAVA BFS 3 连发（2），的从上到下打印二叉树 II
一层正序、一层倒序的话，也好办、一层正向往Integer[] line里填，下一层逆向往Integer[] line里填就可以了

代码

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        boolean flag = true;
        Queue<TreeNode> queue = new LinkedList<>();
        if (null!=root)queue.offer(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            flag = !flag;
            Integer[] line = new Integer[size];
            while (size-- > 0){
                if (null != queue.peek().left)queue.offer(queue.peek().left);
                if (null != queue.peek().right)queue.offer(queue.peek().right);
                if (flag) {
                    line[size] = queue.poll().val;
                }else{
                    line[line.length-size-1] = queue.poll().val;
                }
            }
            res.add( Arrays.asList(line));
        }
        return res;
    }

}

BFS相关合集

BFS三连发1

BFS三连发2

BFS三连发3