关于leetcode:上岸算法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);
    }
}