Java日常练习题,每天进步一点点(16)

让我来为你详细讲解“Java日常练习题,每天进步一点点(16)”的完整攻略吧。

首先，这个练习题是一道比较典型的算法练习题，旨在让练习者熟悉并掌握常见的算法思想以及数据结构基本操作。下面我们将对这个练习题进行分析。

题目描述

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

示例说明

例如，输入s="rabbbit"，t="rabbit"，则输出3。因为s中有3个子序列是t。

解题思路

这个问题和之前的题目大有不同，因为这次我们并不是简单的给定两个字符串，而是需要找出其中一个字符串 s 的子串或子序列。那么，显然我们需要使用一些常见的算法思想来帮助我们完成这个任务。

这道题可以使用动态规划的思想来解决。我们可以定义一个二维数组 dp[i][j] 表示在 s 的前 i 个字符中，t 的前 j 个字符出现的个数。

当 s[i] = t[j] 时，有两种情况：

• 不使用s[i]：此时 s 的前 i-1 个字符中，t 的前 j 个字符出现的个数为 dp[i-1][j]。
• 使用s[i]：此时 s 的前 i-1 个字符中，t 的前 j-1 个字符出现的个数为 dp[i-1][j-1]。而 s[i] 可以和 t[j] 匹配，所以最终 dp[i][j] 的值为 dp[i-1][j] + dp[i-1][j-1]。

当 s[i] != t[j] 时，此时 s 的前 i 个字符中，t 的前 j 个字符出现的个数只能是 s 的前 i-1 个字符中，t 的前 j 个字符出现的个数，即 dp[i][j] = dp[i-1][j]。

最终答案为 dp[m][n]，其中 m 和 n 分别为字符串 s 和 t 的长度。

代码实现

public int numDistinct(String s, String t) {
    int m = s.length();
    int n = t.length();

    int[][] dp = new int[m+1][n+1];
    for (int i = 0; i <= m; i++) {
        dp[i][0] = 1;
    }

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s.charAt(i-1) == t.charAt(j-1)) {
                dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }

    return dp[m][n];
}

总结

这道题目需要我们熟练掌握动态规划的思想，并加强对Java字符串的基础操作的理解。虽然这个题目看起来有些复杂，但是只要掌握了关键的算法思想，那么解决起来就没那么困难了。