总行驶距离
二刷：模拟
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int distanceTraveled(int mainTank, int additionalTank) {
if (mainTank < 5)
return mainTank * 10;
int x = mainTank, res = (mainTank - mainTank % 5) * 10, s = mainTank % 5;
while (x >= 5) {
int y = x / 5;
x = x % 5;
y = Math.min(y, additionalTank);
additionalTank -= y;
x += y;
s += y;
}
res += s * 10;
return res;
}
}
|
时间复杂度：\(O(1)\)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int distanceTraveled(int mainTank, int additionalTank) {
int res = 0, ori = mainTank;
while (mainTank > 0) {
--mainTank;
res += 10;
if (ori == mainTank + 5) {
if (additionalTank > 0) {
--additionalTank;
++mainTank;
ori = mainTank;
}
}
}
return res;
}
}
|
找出分区值
二刷：排序
1
2
3
4
5
6
7
8
9
| class Solution {
public int findValueOfPartition(int[] nums) {
Arrays.sort(nums);
int min = Integer.MAX_VALUE;
for (int i = 0; i < nums.length - 1; ++i)
min = Math.min(min,nums[i + 1] - nums[i]);
return min;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public int findValueOfPartition(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
int[] arr = new int[n - 1];
for (int i = 0; i < n - 1; ++i)
arr[i] = nums[i + 1] - nums[i];
int min = Integer.MAX_VALUE;
for (int x : arr) {
min = Math.min(min, x);
}
return min;
}
}
|
特别的排列
方法一：三种回溯(超时)
回溯一
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 specialPerm(int[] nums) {
visited = new boolean[nums.length];
Arrays.sort(nums);
dfs(nums, 0);
return res;
}
int res = 0, MOD = (int) (1e9 + 7);
Deque<Integer> path = new LinkedList<>();
boolean[] visited;
private void dfs(int[] nums, int index) {
if (path.size() == nums.length) {
res = (res + 1) % MOD;
return;
}
for (int i = 0; i < nums.length; ++i) {
if (visited[i])
continue;
if (i != 0 && nums[i - 1] == nums[i] && !visited[i - 1])
continue;
if (path.isEmpty() || check(nums[i], path.peekLast())) {
visited[i] = true;
path.offerLast(nums[i]);
dfs(nums, i + 1);
path.pollLast();
visited[i] = false;
}
}
}
private boolean check(int a, int b) {
return (a % b == 0) || (b % a == 0);
}
}
|
回溯二
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
| public int specialPerm(int[] nums) {
visited = new boolean[nums.length];
dp = new HashMap<>();
Arrays.sort(nums);
return dfs(nums);
}
int MOD = (int) (1e9 + 7);
Deque<Integer> path = new LinkedList<>();
boolean[] visited;
Map<String, Integer> dp;
private int dfs(int[] nums) {
if (path.size() == nums.length)
return 1;
int res = 0;
for (int i = 0; i < nums.length; ++i) {
if (visited[i])
continue;
if (i != 0 && nums[i - 1] == nums[i] && !visited[i - 1])
continue;
if (path.isEmpty() || check(nums[i], path.peekLast())) {
visited[i] = true;
path.offerLast(nums[i]);
res = (res + dfs(nums)) % MOD;
path.pollLast();
visited[i] = false;
}
}
return res;
}
private boolean check(int a, int b) {
return (a % b == 0) || (b % a == 0);
}
|
回溯三
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
| public int specialPerm(int[] nums) {
this.nums = nums;
visited = new boolean[nums.length];
dp = new HashMap<>();
Arrays.sort(nums);
return dfs(0, -1);
}
private int dfs(int index, int lastChoosed) {
if (index == nums.length)
return 1;
int res = 0;
for (int i = 0; i < nums.length; ++i) {
if (visited[i])
continue;
if (lastChoosed != -1 && nums[lastChoosed] == nums[i] && !visited[i])
continue;
if (lastChoosed == -1 || check(nums[lastChoosed], nums[i])) {
visited[i] = true;
res = (res + dfs(index + 1, i)) % MOD;
visited[i] = false;
}
}
return res;
}
int MOD = (int) (1e9 + 7);
boolean[] visited;
int[] nums;
Map<String, Integer> dp;
private boolean check(int a, int b) {
return (a % b == 0) || (b % a == 0);
}
|
方法二：记忆化搜索 + 状态压缩
举例 nums = [2, 3, 6, 6]
- 2，6，3，6
- 3，6，2，6
- 6，2，6，3
- 6，3，6，2
- 2，6，6，3
- 3，6，6，2
其中2，6，6，3与6，2，6，3可以使用记忆化搜索
[2，6]，6，3与[6，2]，6，3, 下标为2的6前[2, 6]与[6,2]是同一个组合(不考虑顺序)
只要下标为i(2)是相同的数(6)，并且前i个数是同一个组合，那么在i之后是重复计算
计算过[2，6]，6后，再遇到[6，2]，6，只要返回map里的值就行
状态压缩
u | (1 << i)存储的是数组下标，初始u = 0。 | 是或运算, 1 << i 将1左移i位
例如，将2(下标0)存入u中，
初始u = 0000,
0000 | (1 << 0) = 0001
将6(下标1)存入u中
u = 0001
0001 | (1 << 1) = 0011
将[2, 6]存入u中 u = 0011 == 将[6, 2]存入u中u = 0011
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
38
39
40
41
| class Solution {
public int specialPerm(int[] nums) {
this.nums = nums;
visited = new boolean[nums.length];
dp = new HashMap<>();
Arrays.sort(nums);
return dfs(0, -1, 0);
}
private int dfs(int index, int lastChoosed, int u) {
if (index == nums.length)
return 1;
String key = lastChoosed + "#" + u;
if (dp.containsKey(key))
return dp.get(key);
int res = 0;
for (int i = 0; i < nums.length; ++i) {
if (visited[i])
continue;
if (lastChoosed != -1 && nums[lastChoosed] == nums[i] && !visited[i])
continue;
if (lastChoosed == -1 || check(nums[lastChoosed], nums[i])) {
visited[i] = true;
res = (res + dfs(index + 1, i, (u | (1 << i)))) % MOD;
visited[i] = false;
}
}
dp.put(key, res);
return res;
}
int MOD = (int) (1e9 + 7);
boolean[] visited;
int[] nums;
Map<String, Integer> dp;
private boolean check(int a, int b) {
return (a % b == 0) || (b % a == 0);
}
}
|
给墙壁刷油漆
方法一：记忆化搜索
dfs(int index, int leftTime) index是遍历到的cost的下标，leftTime是可以白嫖的次数(1单位时间白嫖1次)
付费：dfs(index + 1, leftTime + time[index]) + cost[index];
白嫖：dfs(index + 1, leftTime - 1);
初始化：dp = new int[n][2 * n]; leftTime可能是负数而且最小-n
剪枝：如果白嫖次数大于等于剩余需要刷漆的次数，那么全部白嫖的花费最小
1
2
| if (leftTime >= n - index)
return 0;
|
代码
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 paintWalls(int[] cost, int[] time) {
n = cost.length;
this.cost = cost;
this.time = time;
dp = new int[n][2 * n];
for (int[] arr : dp)
Arrays.fill(arr, -1);
return dfs(0, 0);
}
private int dfs(int index, int leftTime) {
if (index == n)
return leftTime >= 0 ? 0 : Integer.MAX_VALUE / 2;
if (leftTime >= n - index)
return 0;
if (dp[index][leftTime + n] != -1)
return dp[index][leftTime + n];
int pay = dfs(index + 1, leftTime + time[index]) + cost[index];
int free = dfs(index + 1, leftTime - 1);
return dp[index][leftTime + n] = Math.min(pay, free);
}
int[] cost, time;
int[][] dp;
int n;
}
|