方法一：模拟
比赛时没看明白，写复杂了一点。
1
2
3
4
5
| class Solution {
public int accountBalanceAfterPurchase(int purchaseAmount) {
return 100 - (purchaseAmount + 5) / 10 * 10;
}
}
|
复杂度分析
- 时间复杂度：\(O(1)\)。
- 空间复杂度：\(O(1)\)。
方法一：模拟
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public ListNode insertGreatestCommonDivisors(ListNode head) {
ListNode cur = head;
while (cur.next != null) {
cur.next = new ListNode(gcd(cur.val, cur.next.val), cur.next);
cur = cur.next.next;
}
return head;
}
private int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
}
|
复杂度分析
- 时间复杂度：\(O(n\log m)\)，其中 \(m\) 表示节点的最大值。
- 空间复杂度：\(O(1)\)。
方法一：枚举
假设最后数组中的元素是 \(x\)，那么需要的最少秒数就是所有值为 \(x\) 的元素之间的最大间距的一半向上取整。由于数组是循环数组，我们可以在遍历时添加两次，或者在处理哈希表中的列表时特殊处理最后一个元素与第一个元素的间距。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int minimumSeconds(List<Integer> nums) {
int n = nums.size();
Map<Integer, List<Integer>> map = new HashMap<>();
for (int i = 0; i < 2 * n; i++) {
map.computeIfAbsent(nums.get(i % n), k -> new ArrayList<>()).add(i);
}
int ans = Integer.MAX_VALUE;
for (var list : map.values()) {
int m = list.size(), max = 0;
for (int i = 0; i < m - 1; i++) {
max = Math.max(max, list.get(i + 1) - list.get(i) - 1);
}
ans = Math.min(ans, (max + 1) / 2);
}
return ans;
}
}
|
复杂度分析
- 时间复杂度：\(O(n)\)。
- 空间复杂度：\(O(n)\)。
方法一：动态规划
比赛时其实很多点都想到了，当时遇到的问题就是不知道如何对 \(nums1[i]+nums2[i]\times t\) 排序，没想到要用动态规划，而且动态规划的建模方式有点技巧性，利用了排序来确定选择的第 \(j\) 个数就是在时间 \(j\) 操作的数。
状态定义：\(dp[i][j]\) 表示从前 \(i\) 个数中选择 \(j\) 个数进行操作，可以使元素和减少的最大值（相对于不进行任何操作）。因为我们将 \(aux\) 按照 \(nums_{2}\) 从小到大排序，所以如果 \(i\) 是选择的第 \(j\) 个数，那么就表示在时间 \(j\) 操作 \(i\)，因此减少的时间为 \(nums_{1}[aux[i]]+nums_{2}[aux[i]]\times j\)。
状态转移方程：\(dp[i+1][j]=\max(dp[i][j],dp[i][j-1]+nums_{1}[aux[i]]+nums_{2}[aux[i]]\times j)\)。
可以将空间复杂度优化为 \(O(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
| class Solution {
public int minimumTime(List<Integer> nums1, List<Integer> nums2, int x) {
int n = nums1.size(), sum1 =0, sum2 = 0;
Integer[] aux = new Integer[n];
for (int i = 0; i < n; i++) {
aux[i] = i;
sum1 += nums1.get(i);
sum2 += nums2.get(i);
}
Arrays.sort(aux, (a, b) -> nums2.get(a) - nums2.get(b));
int[][] dp = new int[n + 1][n + 1];
for (int i = 0; i < n; i++) {
for (int j = n; j > 0; j--) {
dp[i + 1][j] = Math.max(dp[i][j], dp[i][j - 1] + nums1.get(aux[i]) + nums2.get(aux[i]) * j);
}
}
for (int i = 0; i <= n; i++) {
if (sum1 + sum2 * i - dp[n][i] <= x) {
return i;
}
}
return -1;
}
}
|
复杂度分析
- 时间复杂度：\(O(n^{2})\)。
- 空间复杂度：\(O(n^{2})\)。