力扣随机题

分割等和子集

题目

LCR 101. 分割等和子集 - 力扣（LeetCode）

思路

这里使用一个动态规划数组 dp，其中 dp[i] 表示能否通过数组中的某些元素组合得到和为 i 的子集。

dp[result] 如果为 true，意味着存在一个子集的和为 result（即 sum / 2），因此可以将数组分为两个和相等的子集，返回 true；否则返回 false。

代码

public boolean canPartition(int[] nums) {int sum = 0;for(int num:nums){sum=sum+num;}Arrays.sort(nums);if(sum%2!=0){return false;}int result = sum/2;boolean[] dp = new boolean[result + 1];dp[0] = true;for (int i = 1; i <= result; i++) {for (int j = result; j >= nums[i - 1]; j--) {dp[j] |= dp[j - nums[i - 1]];}}return dp[result];}

不同的子序列

题目

LCR 097. 不同的子序列 - 力扣（LeetCode）

思路

dp[i][j]代表s串的前i个字符里有多少个t子串的前j个字符的子串

状态转移方程就是 

1. 如果s.charAt(i-1)==t.charAt(j-1)，dp[i][j]=dp[i-1][j]+dp[i-1][j-1]
2. 否则 dp[i][j]=dp[i-1][j]

代码

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];}

模糊搜索验证

题目

LCR 137. 模糊搜索验证 - 力扣（LeetCode）

思路

dp[i][j] 表示 input 的前 i 个字符是否可以匹配 article 的前 j 个字符。

dp[0][0] 表示空字符串和空字符串是匹配的，因此 dp[0][0] = true。
对于 dp[i][0]（即 article 为空的情况），只有当 input 是由 * 组成的才可能匹配。我们需要处理 '*' 能否匹配零次的情况。

如果 input[i-1] == article[j-1] 或者 input[i-1] == '.'，表示当前字符匹配，那么 dp[i][j] = dp[i-1][j-1]。
如果 input[i-1] == '*'，则分两种情况：

1. '*'匹配零次：可以忽略 '*' 和其前一个字符，转移为 dp[i][j-2]。
2. '*'匹配一次或多次：如果 input[i-2] == article[j-1] 或 input[i-2] == '.'，则表示可以继续匹配当前字符，转移为 dp[i][j-1]。

代码

public boolean articleMatch(String article, String input) {int m = input.length();int n = article.length();boolean[][] dp = new boolean[m + 1][n + 1];dp[0][0] = true;for (int i = 1; i <= m; i++) {if (input.charAt(i - 1) == '*' && dp[i - 2][0]) {dp[i][0] = true;}}for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {char in = input.charAt(i - 1);char art = article.charAt(j - 1);if (in == art || in == '.') {dp[i][j] = dp[i - 1][j - 1];}else if (in == '*') {dp[i][j] = dp[i - 2][j]; if (input.charAt(i - 2) == art || input.charAt(i - 2) == '.') {dp[i][j] = dp[i][j] || dp[i][j - 1]; }}}}return dp[m][n];}