【 NO.1 环和杆】

解题思路

签到题，遍历一次即可。

代码展示

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;

  }

}

【 NO.2 子数组范围和】

解题思路

枚举所有子数组即可。

代码展示

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;

  }

}

【 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[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;

  }

}

【 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[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);

  }

}