找出最大的可达成数字
1
2
3
4
5
6
7
8
| class Solution {
public int theMaximumAchievableX(int num, int t) {
for (int i = 0; i < t; ++i) {
num += 2;
}
return num;
}
}
|
达到末尾下标所需的最大跳跃次数
方法一：记忆化搜索 flags存储可达路径
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 int maximumJumps(int[] nums, int target) {
this.nums = nums;
this.target = target;
dp = new int[nums.length];
Arrays.fill(dp, -1);
flags = new boolean[nums.length];
int res = dfs(0, 0);
return flags[0] ? res : -1;
}
boolean flag = false;
boolean[] flags;
int[] nums, dp;
int target;
private int dfs(int index, int from) {
if (index == nums.length - 1) {
flags[from] = true;
return 0;
}
if (dp[index] != -1)
return dp[index];
int res = 0;
for (int i = index + 1; i < nums.length; ++i) {
int max = 0;
if (Math.abs(nums[i] - nums[index]) <= target) {
max += dfs(i,i) + 1;
if (flags[i])
flags[index] = true;
if (flags[i]) {
res = Math.max(res, max);
}
}
}
return dp[index] = res;
}
}
|
方法二：
题目中有：全部不满足情况下返回-1时，要重视dfs里res的初始化， -inf, inf等，根据具体要求具体分析
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
| class Solution {
public int maximumJumps(int[] nums, int target) {
this.nums = nums;
this.target = target;
dp = new int[nums.length];
Arrays.fill(dp, -1);
int res = dfs(0);
return res < 0 ? -1 : res;
}
int[] nums;
int target;
int[] dp;
private int dfs(int index) {
if (index == nums.length - 1)
return 0;
if (dp[index] != -1)
return dp[index];
int res = -Integer.MAX_VALUE / 2;
for (int i = index + 1; i < nums.length; ++i) {
if (Math.abs(nums[i] - nums[index]) <= target)
res = Math.max(res, dfs(i) + 1);
}
return dp[index] = res;
}
}
|
构造最长非递减子数组
方法一：记忆化搜索
要遍历完从0到n-1开始的下标，因为最长不一定从下标0开始，比如nums1 = [8,7,4] nums2 = [13,4,4]，最大长度从下标1开始 [4,4]
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
| class Solution {
public int maxNonDecreasingLength(int[] nums1, int[] nums2) {
this.nums1 = nums1;
this.nums2 = nums2;
int res = 1;
for (int i = 0; i < nums1.length; ++i)
res = Math.max(res, dfs(i, 0));
return res;
}
int[] nums1, nums2;
Map<String, Integer> dp = new HashMap<>();
private int dfs(int index, int pre) {
if (index == nums1.length)
return 0;
String key = index + "-" + pre;
if (dp.containsKey(key))
return dp.get(key);
int res = 0;
if (pre <= nums1[index])
res = Math.max(res, dfs(index + 1, nums1[index]) + 1);
if (pre <= nums2[index])
res = Math.max(res, dfs(index + 1, nums2[index]) + 1);
dp.put(key, res);
return res;
}
}
|
使数组中的所有元素都等于零
方法一：差分数组
与995. K 连续位的最小翻转次数相似，草稿纸上模拟，多Debug
注意diff[i + k - 1] += nums[i] + curDiff; 复原的位置是i + k - 1
举例
1
2
3
4
5
6
| 输入：nums = , k = 3
输出：true
解释：可以执行下述操作：
- 选出子数组 ，执行操作后，数组变为 nums = 。
- 选出子数组 ，执行操作后，数组变为 nums = 。
- 选出子数组 ，执行操作后，数组变为 nums = 。
|
| diff i = 0 |
-2 |
0 |
2 |
0 |
0 |
0 |
-2 |
| diff i = 1 |
-2 |
0 |
2 |
0 |
0 |
0 |
-2 |
| diff i = 2 |
-2 |
0 |
1 |
0 |
1 |
0 |
-1 |
| diff i = 3 |
-2 |
0 |
1 |
0 |
1 |
0 |
-1 |
| diff i = 4 |
-2 |
0 |
1 |
0 |
1 |
0 |
0 |
| diff i = 5 |
-2 |
0 |
1 |
0 |
1 |
0 |
0 |
|
|
|
|
|
|
|
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public boolean checkArray(int[] nums, int k) {
int n = nums.length;
int[] diff = new int[n];
int curDiff = 0;
for (int i = 0; i < n; ++i) {
if (nums[i] + curDiff > 0) {
if (i + k > n)
return false;
diff[i] += -nums[i] - curDiff;
diff[i + k - 1] += nums[i] + curDiff;
}
else if (nums[i] + curDiff < 0)
return false;
if (diff[i] != 0)
curDiff += diff[i];
}
return true;
}
}
|
image-20230709144240215