方法一：暴力
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public int countPairs(List<Integer> nums, int target) {
int res = 0, n = nums.size();
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (nums.get(i) + nums.get(j) < target)
++res;
}
}
return res;
}
}
|
方法一：模拟
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 boolean canMakeSubsequence(String str1, String str2) {
int m = str1.length(), n = str2.length();
if (m < n)
return false;
Map<Character, Character> next = new HashMap<>();
for (char i = 'a'; i < 'z'; ++i)
next.put(i, (char) (i + 1));
next.put('z', 'a');
int l = 0, r = 0;
while (l < m && r < n) {
char ch1 = str1.charAt(l), ch2 = str2.charAt(r);
if (ch1 == ch2 || next.get(ch1) == ch2) {
++l;
++r;
}
else {
++l;
}
}
return r == n;
}
}
|
方法一：n - 最长非递减子序列
https://leetcode.cn/submissions/detail/460143737/
算出最长非递减子序列，修改剩余的元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int minimumOperations(List<Integer> nums) {
int n = nums.size(), res = 1;
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (nums.get(j) <= nums.get(i)) {
dp[i] = Math.max(dp[i], dp[j] + 1);
res = Math.max(res, dp[i]);
}
}
}
return n - res;
}
}
|
方法二：状态机DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public int minimumOperations(List<Integer> nums) {
int n = nums.size();
int[][] dp = new int[n + 1][4];
for (int i = 0; i < n; ++i) {
for (int j = 1; j <= 3; ++j) {
dp[i + 1][j] = Integer.MAX_VALUE;
for (int k = 1; k <= j; ++k) {
dp[i + 1][j] = Math.min(dp[i + 1][j], dp[i][k]);
}
dp[i + 1][j] += (nums.get(i) == j ? 0 : 1);
}
}
int min = dp[n][1];
for (int i = 2; i <= 3; ++i)
min = Math.min(min, dp[n][i]);
return min;
}
}
|