方法一：大根堆
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public long pickGifts(int[] gifts, int k) {
int n = gifts.length;
long res = 0;
PriorityQueue<Integer> queue = new PriorityQueue<>(((o1, o2) -> o2 - o1));
for (int x : gifts)
queue.add(x);
while (k-- > 0) {
int x = queue.poll(), sqrt = (int) Math.sqrt(x);
queue.add(sqrt);
}
for (int x : queue)
res += x;
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
24
25
26
27
| class Solution {
public int[] vowelStrings(String[] words, int[][] queries) {
int m = queries.length, n = words.length;
boolean[] check = new boolean[n];
Set<Character> set = new HashSet<>();
set.add('a');
set.add('e');
set.add('i');
set.add('o');
set.add('u');
int index = 0;
for (String word : words) {
check[index] = (set.contains(word.charAt(0)) && set.contains(word.charAt(word.length() - 1))) ? true : false;
++index;
}
int[] preSum = new int[n + 1];
for (int i = 0; i < n; ++i)
preSum[i + 1] = preSum[i] + (check[i] ? 1 : 0);
int[] res = new int[m];
index = 0;
for (int[] query : queries) {
res[index] = preSum[query[1] + 1] - preSum[query[0]];
++index;
}
return res;
}
}
|
方法一：二分 + 记忆化搜索
枚举nums中的数字limit作为小偷的窃取能力，换句话说，小偷只能偷价值小于等于limit的房屋，如果在这个limit下，能偷大于等于k个房屋，limit可以尝试更小的数；否则limit需要尝试更大的数
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
| class Solution {
public int minCapability(int[] nums, int k) {
this.nums = nums;
n = nums.length;
int[] temp = nums.clone();
Arrays.sort(temp);
int l = 0, r = n - 1;
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid, temp, k))
r = mid - 1;
else
l = mid + 1;
}
return temp[l];
}
private boolean check(int mid, int[] temp, int k) {
dp = new int[n];
Arrays.fill(dp, -1);
int limit = temp[mid];
return dfs(0, limit) >= k ? true : false;
}
private int dfs(int index, int limit) {
if (index == n)
return 0;
if (dp[index] != -1)
return dp[index];
int pass = dfs(index + 1, limit), rob = 0;
if (nums[index] <= limit)
rob = dfs(index + 2, limit) + 1;
return dp[index] = Math.max(pass, rob);
}
int[] nums, dp;
int n;
}
|
方法二：记忆化搜索转DP
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
| class Solution {
public int minCapability(int[] nums, int k) {
this.nums = nums;
n = nums.length;
int[] temp = nums.clone();
Arrays.sort(temp);
int l = 0, r = n - 1;
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid, temp, k))
r = mid - 1;
else
l = mid + 1;
}
return temp[l];
}
private boolean check(int mid, int[] temp, int k) {
int limit = temp[mid];
dp = new int[n + 2];
for (int i = 2; i < n + 2; ++i) {
dp[i] = dp[i - 1];
if (nums[i - 2] <= limit)
dp[i] = Math.max(dp[i], dp[i - 2] + 1);
}
return dp[n + 1] >= k;
}
int[] nums, dp;
int n;
}
|
方法三：滚动数组
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
| class Solution {
public int minCapability(int[] nums, int k) {
this.nums = nums;
n = nums.length;
int[] temp = nums.clone();
Arrays.sort(temp);
int l = 0, r = n - 1;
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid, temp, k))
r = mid - 1;
else
l = mid + 1;
}
return temp[l];
}
private boolean check(int mid, int[] temp, int k) {
int limit = temp[mid];
dp = new int[3];
for (int i = 2; i < n + 2; ++i) {
dp[i % 3] = dp[(i - 1) % 3];
if (nums[i - 2] <= limit)
dp[i % 3] = Math.max(dp[i % 3], dp[(i - 2) % 3] + 1);
}
return dp[(n + 1) % 3] >= k;
}
int[] nums, dp;
int n;
}
|