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

上岸算法 · 发表于 2021-12-12 22:20:14

登录后可回复主题

您需要登录才可以下载或查看，没有帐号？注册账号

x

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

帐号		自动登录	找回密码
密码			注册账号

[吹水聊天] 上岸算法LeetCode Weekly Contest 271解题报告

登录后可回复主题