【 NO.1 两栋色彩不同且间隔最远的房子】
解题思路
签到题，循环判断即可。
代码展现
class Solution {
public int maxDistance(int[] colors) {
for (int len = colors.length; len >= 1; len--) { for (int i = 0; i + len <= colors.length; i++) { if (colors[i] != colors[i + len - 1]) { return len - 1; } } } return 0;}
}
【 NO.2 给动物浇水】
解题思路
模仿浇水过程即可。
代码展现
class Solution {
public int wateringPlants(int[] plants, int capacity) {
int res = 0; int water = capacity; for (int i = 0; i < plants.length; i++) { if (water < plants[i]) { water = capacity; res += i * 2; } res++; water -= plants[i]; } return res;}
}
【 NO.3 区间内查问数字的频率】
解题思路
二分查找。统计出每个数字的所有呈现地位，而后在地位列表上进行二分查找即可失去该列表中位于 [left, right] 范畴的元素有多少个。
代码展现
class RangeFreqQuery {
Map<Integer, List<Integer>> pos;
public RangeFreqQuery(int[] arr) {
pos = new HashMap<>(); for (int i = 0; i < arr.length; i++) { if (!pos.containsKey(arr[i])) { pos.put(arr[i], new ArrayList<>()); } pos.get(arr[i]).add(i); }}
public int query(int left, int right, int value) {
if (!pos.containsKey(value)) { return 0; } List<Integer> p = pos.get(value); int start = bSearch2(p, left); int end = bSearch(p, right); return end - start + 1;}
// 二分查找最初一个 <= value 的元素下标
int bSearch(List<Integer> arr, int value) {
if (arr.size() == 0 || value < arr.get(0)) { return -1; } int left = 0, right = arr.size() - 1; while (left + 1 < right) { int mid = (left + right) / 2; if (arr.get(mid) <= value) { left = mid; } else { right = mid; } } return arr.get(right) <= value ? right : left;}
// 二分查找第一个 >= value 的元素下标
int bSearch2(List<Integer> arr, int value) {
if (arr.size() == 0 || arr.get(arr.size() - 1) < value) { return arr.size(); } int left = 0, right = arr.size() - 1; while (left + 1 < right) { int mid = (left + right) / 2; if (arr.get(mid) < value) { left = mid; } else { right = mid; } } return arr.get(left) < value ? right : left;}
}
【 NO.4 k 镜像数字的和】
解题思路
回溯法枚举即可。
代码展现
class Solution {
int n;
long sum;
public long kMirror(int k, int n) {
this.sum = 0; this.n = n; for (int len = 1; this.n > 0; len++) { // 长度为 len 的 k 进制的镜像数字 char[] chars = new char[len]; dfs(chars, 0, chars.length - 1, k); } return sum;}
private void dfs(char[] chars, int i, int j, int k) {
if (this.n == 0) { return; } if (i == j) { for (int p = 0; p < k; p++) { if (p == 0 && i == 0) { continue; } chars[i] = (char) ('0' + p); dfs(chars, i + 1, j - 1, k); } return; } if (i > j) { long ten = Long.parseLong(String.valueOf(chars), k); String str = String.valueOf(ten); for (int l = 0, r = str.length() - 1; l < r; l++, r--) { if (str.charAt(l) != str.charAt(r)) { return; } } this.n--; sum += ten; return; } for (int p = 0; p < k && this.n > 0; p++) { if (i == 0 && p == 0) { continue; } chars[i] = chars[j] = (char) ('0' + p); dfs(chars, i + 1, j - 1, k); }}
}