上岸算法LeetCode Weekly Contest 271解题报告
【 NO.1 环和杆】解题思路
签到题，遍历一次即可。
代码展示
class Solution {
public int countPoints(String rings) {
boolean[][] color = new boolean;
for (int i = 0; i < rings.length(); i += 2) {
color = true;
}
int result = 0;
for (int i = 0; i < 10; i++) {
if (color['R' - 'A'] && color['G' - 'A'] && color['B' - 'A']) {
result++;
}
}
return result;
}
}
【 NO.2 子数组范围和】
解题思路
枚举所有子数组即可。
代码展示
class Solution {
public long subArrayRanges(int[] nums) {
long result = 0;
for (int i = 0; i < nums.length; i++) {
int min = nums;
int max = nums;
for (int j = i + 1; j < nums.length; j++) {
min = Math.min(min, nums);
max = Math.max(max, nums);
result += max - min;
}
}
return result;
}
}
【 NO.3 给植物浇水 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) {
result++;
}
break;
}
if (a < plants) {
a = capacityA;
result++;
}
a -= plants;
if (b < plants) {
b = capacityB;
result++;
}
b -= plants;
}
return result;
}
}
【 NO.4 摘水果】
解题思路
我们不可能来回反复走，只会有以下四种策略：
从 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;
preSum = fruits;
for (int i = 1; i < preSum.length; i++) {
preSum = preSum + fruits;
}
// 1. 一直往左走
// 2. 一直往右走
// 3. 往左走到某个点折返，然后一直往右走
// 4. 往右走到某个点折返，然后一直往左走
int result = 0;
for (int i = 0; i < fruits.length; i++) {
if (k < Math.abs(startPos - fruits)) {
continue;
}
// 折返点是 i
result = Math.max(result, maxTotalFruitsStraight(fruits, preSum, i, k - Math.abs(startPos - fruits)));
}
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 - fruits) {
step /= 2;
continue;
}
idx -= step;
step *= 2;
}
int allLeft = preSum;
if (idx > 0) {
allLeft -= preSum;
}
// 2. 一直往右走
step = 1;
idx = startIdx;
while (step > 0) {
if (idx + step >= fruits.length || k < fruits - fruits) {
step /= 2;
continue;
}
idx += step;
step *= 2;
}
int allRight = preSum;
if (startIdx > 0) {
allRight -= preSum;
}
return Math.max(allLeft, allRight);
}
}
页:
[1]