上岸算法LeetCode Weekly Contest 271解题报告

环和杆

签到题,遍历一次即可。

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;
    }
}

摘水果

我们不可能来回反复走,只会有以下四种策略:

  1. 从 startPos 一直往左走 k 步
  2. 从 startPos 一直往右走 k 步
  3. 从 startPos 往左走到某个水果位置,然后折返一直往右走,直到累计 k 步
  4. 从 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);
    }
}