上岸算法LeetCode Weekly Contest 268解题报告
【 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 != colors) {
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) {
water = capacity;
res += i * 2;
}
res++;
water -= plants;
}
return res;
}
}
【 NO.3 区间内查询数字的频率】
解题思路
二分查找。统计出每个数字的所有出现位置，然后在位置列表上进行二分查找即可得到该列表中位于 范围的元素有多少个。
代码展示
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)) {
pos.put(arr, new ArrayList<>());
}
pos.get(arr).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;
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 = (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 = chars = (char) ('0' + p);
dfs(chars, i + 1, j - 1, k);
}
}
}
页:
[1]