环和杆
签到题，遍历一次即可。
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; }}摘水果
咱们不可能来回重复走，只会有以下四种策略：
- 从 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); }}