模拟。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public List<Integer> lastVisitedIntegers(List<String> words) {
int idx = -1;
List<Integer> ans = new ArrayList<>();
List<Integer> aux = new ArrayList<>();
for (String word : words) {
if (word.equals("prev")) {
if (idx < 0) ans.add(-1);
else ans.add(aux.get(idx--));
} else {
aux.add(Integer.valueOf(word));
idx = aux.size() - 1;
}
}
return ans;
}
}
|
贪心。
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public List<String> getWordsInLongestSubsequence(int n, String[] words, int[] groups) {
List<String> ans = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (i == n - 1 || groups[i] != groups[i + 1]) {
ans.add(words[i]);
}
}
return ans;
}
}
|
和最长递增子序列有点像，处理的时候记录一下路径就好。
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
| class Solution {
public List<String> getWordsInLongestSubsequence(int n, String[] words, int[] groups) {
int pos = 0;
int[] from = new int[n];
int[] maxLen = new int[n];
Arrays.fill(maxLen, 1);
for (int i = 1; i < n; i++) {
for (int j = i - 1; j >= 0; j--) {
if (maxLen[i] < maxLen[j] + 1 && groups[i] != groups[j] && words[i].length() == words[j].length()) {
int cnt = 0;
for (int k = 0; k < words[i].length(); k++) {
if (words[i].charAt(k) != words[j].charAt(k) && ++cnt > 1) {
break;
}
}
if (cnt == 1) {
maxLen[i] = maxLen[j] + 1;
from[i] = j;
if (maxLen[i] > maxLen[pos]) {
pos = i;
}
}
}
}
}
int m = maxLen[pos];
LinkedList<String> ans = new LinkedList<>();
for (int i = 0; i < m; i++) {
ans.addFirst(words[pos]);
pos = from[pos];
}
return ans;
}
}
|
明显是多重背包问题，求背包中物品重量在 \([l,r]\) 之间的方案数，朴素的转移方程为：
$$
dp[i][j]=\sum_{k=0}^{cnt[i]}{(dp[i-1][j-k\cdot w[i]])}
$$
这样做的时间复杂度为 \(O(rn)\)，其中 \(n\) 为 \(nums\) 的长度。在题目的数据范围下，复杂度达到 \(4\cdot 1e8\) 数量级，会导致超时。优化方式如下，当 \(j\geq(cnt[i]+1)\cdot w[i]\) 且 \(w[i]\neq 0\) 时，有：
$$
dp[i][j-w[i]]=dp[i-1][j-w[i]]+dp[i-1][j-2\cdot w[i]]+\cdots+dp[i-1][j-(cnt[i]+1)\cdot w[i]]
$$
$$
dp[i][j]=dp[i-1][j]+dp[i-1][j-w[i]]+\cdots+dp[i-1][j-cnt[i]\cdot w[i]]
$$
然后错位相减，得到：
$$
dp[i][j]=dp[i][j-w[i]]+(dp[i-1][j]-dp[i-1][j-(cnt[i]+1)\cdot w[i]])
$$
当 \(j\geq(cnt[i]+1)\cdot w[i]\) 且 \(w[i]=0\) 时，直接使用朴素转移方程，得到：
$$
dp[i][j]=\sum_{k=0}^{cnt[i]}{(dp[i-1][j])}
$$
同理可得，当 \(w[i]\leq j<(cnt[i]+1)\cdot w[i]\) 时，错位相减得到：
$$
dp[i][j]=dp[i][j-w[i]]+dp[i-1][j]
$$
当 \(j<w[i]\) 时，直接使用朴素转移方程，得到：
$$
dp[i][j]=dp[i-1][j]
$$
这样做的时间复杂度为 \(O(r\sqrt{S})\)，其中 \(S\) 表示 \(nums\) 的元素和，\(\sqrt{S}\) 表示 \(nums\) 中不同元素的最大数量。不同元素的最大数量满足 \(\frac{(0+(x-1))\cdot x}{2}\leq S\)，解得 \(x\leq \frac{1+\sqrt{1+8\cdot S}}{2}\)。还有一些常数级别的优化，比如减少遍历的上界等。
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
| class Solution {
private static final int MOD = (int) 1e9 + 7;
public int countSubMultisets(List<Integer> nums, int l, int r) {
int n = nums.size();
Map<Integer, Integer> map = new HashMap<>();
for (int x : nums) {
map.merge(x, 1, Integer::sum);
}
int zero = map.getOrDefault(0, 0);
map.remove(0);
int m = map.size();
int[] f = new int[r + 1];
int[] g = new int[r + 1];
f[0] = zero + 1;
for (var e : map.entrySet()) {
int w = e.getKey(), c = e.getValue();
System.arraycopy(f, 0, g, 0, r + 1);
for (int j = w; j <= r; j++) {
f[j] = (f[j - w] + f[j]) % MOD;
if (j - (c + 1) * w >= 0) {
f[j] = (f[j] - g[j - (c + 1) * w] + MOD) % MOD;
}
}
}
int ans = 0;
for (int i = l; i <= r; i++) {
ans = (ans + f[i]) % MOD;
}
return ans;
}
}
|
分开处理，先做前缀和，再倒序减去某个前缀和，就可以不使用辅助数组 \(g\)：
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
| class Solution {
private static final int MOD = (int) 1e9 + 7;
public int countSubMultisets(List<Integer> nums, int l, int r) {
int n = nums.size();
Map<Integer, Integer> map = new HashMap<>();
for (int x : nums) {
map.merge(x, 1, Integer::sum);
}
int zero = map.getOrDefault(0, 0);
map.remove(0);
int m = map.size();
int[] f = new int[r + 1];
f[0] = zero + 1;
for (var e : map.entrySet()) {
int w = e.getKey(), c = e.getValue();
for (int j = w; j <= r; j++) {
f[j] = (f[j - w] + f[j]) % MOD;
}
for (int j = r; j >= (c + 1) * w; j--) {
f[j] = (f[j] - f[j - (c + 1) * w] + MOD) % MOD;
}
}
int ans = 0;
for (int i = l; i <= r; i++) {
ans = (ans + f[i]) % MOD;
}
return ans;
}
}
|