环和杆
签到题，遍历一次即可。
class Solution {
public int countPoints(String rings) {
boolean[][] color = new boolean[10][26];
for (int i = 0; i < rings.length(); i += 2) {
color[rings.charAt(i + 1) - '0'][rings.charAt(i) - 'A'] = true;
}
int result = 0;
for (int i = 0; i < 10; i++) {
if (color[i]['R' - 'A'] && color[i]['G' - 'A'] && color[i]['B' - 'A']) {
result++;
}
}
return result;
}
}
子数组范围和
枚举所有子数组即可。
class Solution {
public long subArrayRanges(int[] nums) {
long result = 0;
for (int i = 0; i < nums.length; i++) {
int min = nums[i];
int max = nums[i];
for (int j = i + 1; j < nums.length; j++) {
min = Math.min(min, nums[j]);
max = Math.max(max, nums[j]);
result += max - min;
}
}
return result;
}
}
给植物浇水 II
模拟即可。
class Solution {
public int minimumRefill(int[] plants, int capacityA, int capacityB) {
int result = 0;
for (int i = 0, j = plants.length - 1, a = capacityA, b = capacityB; i <= j; i++, j--) {
if (i == j) {
int c = Math.max(a, b);
if (c < plants[i]) {
result++;
}
break;
}
if (a < plants[i]) {
a = capacityA;
result++;
}
a -= plants[i];
if (b < plants[j]) {
b = capacityB;
result++;
}
b -= plants[j];
}
return result;
}
}
摘水果
我们不可能来回反复走，只会有以下四种策略：
- 从 startPos 一直往左走 k 步
- 从 startPos 一直往右走 k 步
- 从 startPos 往左走到某个水果位置，然后折返一直往右走，直到累计 k 步
- 从 startPos 往右走到某个水果位置，然后折返一直往左走，直到累计 k 步
1、2 均可一次性求出来，3、4 需要枚举折返点。
整体上计算前缀和，然后利用二分或倍增加快 3、4 的求值。
class Solution {
public int maxTotalFruits(int[][] fruits, int startPos, int k) {
int[] preSum = new int[fruits.length];
preSum[0] = fruits[0][1];
for (int i = 1; i < preSum.length; i++) {
preSum[i] = preSum[i - 1] + fruits[i][1];
}
// 1. 一直往左走
// 2. 一直往右走
// 3. 往左走到某个点折返，然后一直往右走
// 4. 往右走到某个点折返，然后一直往左走
int result = 0;
for (int i = 0; i < fruits.length; i++) {
if (k < Math.abs(startPos - fruits[i][0])) {
continue;
}
// 折返点是 i
result = Math.max(result, maxTotalFruitsStraight(fruits, preSum, i, k - Math.abs(startPos - fruits[i][0])));
}
return result;
}
int maxTotalFruitsStraight(int[][] fruits, int[] preSum, int startIdx, int k) {
// 1. 一直往左走
int step = 1, idx = startIdx;
while (step > 0) {
if (idx - step < 0 || k < fruits[startIdx][0] - fruits[idx - step][0]) {
step /= 2;
continue;
}
idx -= step;
step *= 2;
}
int allLeft = preSum[startIdx];
if (idx > 0) {
allLeft -= preSum[idx - 1];
}
// 2. 一直往右走
step = 1;
idx = startIdx;
while (step > 0) {
if (idx + step >= fruits.length || k < fruits[idx + step][0] - fruits[startIdx][0]) {
step /= 2;
continue;
}
idx += step;
step *= 2;
}
int allRight = preSum[idx];
if (startIdx > 0) {
allRight -= preSum[startIdx - 1];
}
return Math.max(allLeft, allRight);
}
}