两栋颜色不同且距离最远的房子
签到题，循环判断即可
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;
}
}
给植物浇水
模拟浇水过程即可。
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;
}
}
区间内查询数字的频率
二分查找。统计出每个数字的所有出现位置，然后在位置列表上进行二分查找即可得到该列表中位于 [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;
}
}
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);
}
}
}