题目1: 115. 不同的子序列

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 10^9 + 7 取模。

eg1:
abbbit”, t = “rabbit”
输出：3

image-20231103114913957

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public static final int N = (int)1e9+7;
    public int numDistinct(String s, String t) {
        //dp[i][j]表示在 s[i:] 的子序列中 t[j:] 出现的个数。
        //上述表示中，s[i:]表示 s 从下标 i 到末尾的子字符串，t[j:] 表示 t 从下标 j 到末尾的子字符串。
        //当s[i]==t[j]时,dp[i][j]=dp[i+1][j+1]+dp[i+1][j];
        //当s[i]!=t[j]时,dp[i][j]=dp[i+1][j]
        int m = s.length(),n=t.length();
        if(m<n) return 0;

        int dp[][] = new int[m+1][n+1];
        for(int i=0;i<=m;i++) dp[i][n]=1; // 任意字符串都至少能匹配一个为空的子序列
        for(int i=m-1;i>=0;i--){
            char s1=s.charAt(i);
            for(int j=n-1;j>=0;j--){
                char s2=t.charAt(j);
                if(s1==s2) dp[i][j]=(dp[i+1][j+1]+dp[i+1][j])%N;//匹配上,可以选或不选
                else dp[i][j]=dp[i+1][j];//选不了,继续往后找
            }
        }
        return dp[0][0];
    }
}

题目2: 117. 填充每个节点的下一个右侧节点指针

给定一个二叉树：

1
2
3
4
5
6
struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。

初始状态下，所有 next 指针都被设置为 NULL 。

示例 1：

1
2
3
输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化输出按层序遍历顺序（由 next 指针连接），'#' 表示每层的末尾。

使用层序遍历求解

借助queue,标记每层第一个节点为lastNode并将其出队,加入其孩子节点到队尾,然后继续出队新节点,新的节点就是lastNode的next, 遍历完一层后,判断队列是否为空, 若非空,更新下一次遍历层的节点数量,重复上述操作,直到队列为空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
    public Node connect(Node root) {
        //层序遍历解决
        if(root == null) return null;

        Queue<Node> q = new ArrayDeque<Node>();
        q.offer(root);
        while(!q.isEmpty()){
            //逐层遍历
            int n = q.size();
            Node lastNode = null;
            for(int i=1;i<=n;i++){
                Node node = q.poll();
                //将孩子节点依次入队
                if(node.left!=null)
                    q.offer(node.left);
                if(node.right!=null)
                    q.offer(node.right);
                if(i!=1){
                    lastNode.next = node;
                }
                //进入下一层时将lastNode迁移到层内最左侧
                lastNode = node;
            }
        }
        return root;
    }
}