5930. 两栋颜色不同且距离最远的房子
街上有 n 栋房子整齐地排成一列，每栋房子都粉刷上了漂亮的颜色。给你一个下标从 0 开始且长度为 n 的整数数组 colors ，其中 colors[i] 表示第 i 栋房子的颜色。
返回 两栋 颜色 不同 房子之间的 最大 距离。
第 i 栋房子和第 j 栋房子之间的距离是 abs(i - j) ，其中 abs(x) 是 x 的绝对值。
示例 1：
输入：colors = [1,1,1,6,1,1,1]
输出：3
解释：上图中，颜色 1 标识成蓝色，颜色 6 标识成红色。
两栋颜色不同且距离最远的房子是房子 0 和房子 3 。
房子 0 的颜色是颜色 1 ，房子 3 的颜色是颜色 6 。两栋房子之间的距离是 abs(0 - 3) = 3 。
注意，房子 3 和房子 6 也可以产生最佳答案。
示例 2：
输入：colors = [1,8,3,8,3]
输出：4
解释：上图中，颜色 1 标识成蓝色，颜色 8 标识成黄色，颜色 3 标识成绿色。
两栋颜色不同且距离最远的房子是房子 0 和房子 4 。
房子 0 的颜色是颜色 1 ，房子 4 的颜色是颜色 3 。两栋房子之间的距离是 abs(0 - 4) = 4 。
示例 3：
输入：colors = [0,1]
输出：1
解释：两栋颜色不同且距离最远的房子是房子 0 和房子 1 。
房子 0 的颜色是颜色 0 ，房子 1 的颜色是颜色 1 。两栋房子之间的距离是 abs(0 - 1) = 1 。
提示：
n == colors.length2 <= n <= 1000 <= colors[i] <= 100- 生成的测试数据满足 至少 存在 2 栋颜色不同的房子
思路：
题目已经保证了一定存在结果，数据范围只有100，直接爆搜，时间复杂度为O(n^2)
class Solution {public int maxDistance(int[] colors) {int res = 0;for (int i = 0; i < colors.length; i++) {for (int j = colors.length - 1; j > i; j--) {if (colors[i] != colors[j]) {res = Math.max(j - i, res);}}}return res;}}
5201. 给植物浇水
你打算用一个水罐给花园里的 n 株植物浇水。植物排成一行，从左到右进行标记，编号从 0 到 n - 1 。其中，第 i 株植物的位置是 x = i 。x = -1 处有一条河，你可以在那里重新灌满你的水罐。
每一株植物都需要浇特定量的水。你将会按下面描述的方式完成浇水：
- 按从左到右的顺序给植物浇水。
- 在给当前植物浇完水之后，如果你没有足够的水 完全 浇灌下一株植物，那么你就需要返回河边重新装满水罐。
- 你 不能 提前重新灌满水罐。
最初，你在河边（也就是，x = -1），在 x 轴上每移动 一个单位 都需要 一步 。
给你一个下标从 0 开始的整数数组 plants ，数组由 n 个整数组成。其中，plants[i] 为第 i 株植物需要的水量。另有一个整数 capacity 表示水罐的容量，返回浇灌所有植物需要的 步数 。
示例 1：
输入：plants = [2,2,3,3], capacity = 5
输出：14
解释：从河边开始，此时水罐是装满的：
- 走到植物 0 (1 步) ，浇水。水罐中还有 3 单位的水。
- 走到植物 1 (1 步) ，浇水。水罐中还有 1 单位的水。
- 由于不能完全浇灌植物 2 ，回到河边取水 (2 步)。
- 走到植物 2 (3 步) ，浇水。水罐中还有 2 单位的水。
- 由于不能完全浇灌植物 3 ，回到河边取水 (3 步)。
- 走到植物 3 (4 步) ，浇水。
需要的步数是 = 1 + 1 + 2 + 3 + 3 + 4 = 14 。
示例 2：
输入：plants = [1,1,1,4,2,3], capacity = 4
输出：30
解释：从河边开始，此时水罐是装满的：
- 走到植物 0，1，2 (3 步) ，浇水。回到河边取水 (3 步)。
- 走到植物 3 (4 步) ，浇水。回到河边取水 (4 步)。
- 走到植物 4 (5 步) ，浇水。回到河边取水 (5 步)。
- 走到植物 5 (6 步) ，浇水。
需要的步数是 = 3 + 3 + 4 + 4 + 5 + 5 + 6 = 30 。
示例 3：
输入：plants = [7,7,7,7,7,7,7], capacity = 8
输出：49
解释：每次浇水都需要重新灌满水罐。
需要的步数是 = 1 + 1 + 2 + 2 + 3 + 3 + 4 + 4 + 5 + 5 + 6 + 6 + 7 = 49 。
提示：
n == plants.length1 <= n <= 10001 <= plants[i] <= 10max(plants[i]) <= capacity <= 10
思路：
一道模拟题
直接从前往后扫描一遍即可！时间复杂度为O(n)
class Solution {public int wateringPlants(int[] plants, int capacity) {int res = 0, sum = capacity;for (int i = 0; i < plants.length; i++) {if (sum >= plants[i]) {res++;sum -= plants[i];} else {res += i + i + 1;sum = capacity - plants[i];}}return res;}}
5186. 区间内查询数字的频率
难度中等11收藏分享切换为英文接收动态反馈
请你设计一个数据结构，它能求出给定子数组内一个给定值的 频率 。
子数组中一个值的 频率 指的是这个子数组中这个值的出现次数。
请你实现 RangeFreqQuery 类：
RangeFreqQuery(int[] arr)用下标从 0 开始的整数数组arr构造一个类的实例。int query(int left, int right, int value)返回子数组arr[left...right]中value的 频率 。
一个 子数组 指的是数组中一段连续的元素。arr[left...right] 指的是 nums 中包含下标 left 和 right 在内 的中间一段连续元素。
示例 1：
输入：
[“RangeFreqQuery”, “query”, “query”]
[[[12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]], [1, 2, 4], [0, 11, 33]]
输出：
[null, 1, 2]
解释：
RangeFreqQuery rangeFreqQuery = new RangeFreqQuery([12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]);
rangeFreqQuery.query(1, 2, 4); // 返回 1 。4 在子数组 [33, 4] 中出现 1 次。
rangeFreqQuery.query(0, 11, 33); // 返回 2 。33 在整个子数组中出现 2 次。
提示：
1 <= arr.length <= 101 <= arr[i], value <= 100 <= left <= right < arr.length- 调用
query不超过10次。
思路：
用哈希表存储每个数字在数组中出现的所有下标 Map<Integer, List<Integer>>
二分查找给定区间目标数字出现的次数！
class RangeFreqQuery {Map<Integer, List<Integer>> map = new HashMap<>();public RangeFreqQuery(int[] arr) {for (int i = 0; i < arr.length; i++) {if (!map.containsKey(arr[i])) {List<Integer> list = new ArrayList<>();list.add(i);map.put(arr[i], list);} elsemap.get(arr[i]).add(i);}}public int query(int left, int right, int value) {List<Integer> list = map.get(value);if (list == null) return 0;//当然这里也可以手写二分，比赛时我就是手写的，，int l = Collections.binarySearch(list, left);if (l < 0) l = -(l + 1);if (l >= list.size() || list.get(l) > right)return 0;int r = Collections.binarySearch(list, right);if (r < 0) {r = -(r + 1);return r - l;} else {return r - l + 1;}}}/*** Your RangeFreqQuery object will be instantiated and called as such:* RangeFreqQuery obj = new RangeFreqQuery(arr);* int param_1 = obj.query(left,right,value);*/
💡5933. k 镜像数字的和
一个 k 镜像数字 指的是一个在十进制和 k 进制下从前往后读和从后往前读都一样的 没有前导 0 的 正 整数。
- 比方说，
9是一个 2 镜像数字。9在十进制下为9，二进制下为1001，两者从前往后读和从后往前读都一样。 - 相反地，
4不是一个 2 镜像数字。4在二进制下为100，从前往后和从后往前读不相同。
给你进制 k 和一个数字 n ，请你返回 k 镜像数字中 最小 的 n 个数 之和 。
示例 1：
输入：k = 2, n = 5
输出：25
解释：
最小的 5 个 2 镜像数字和它们的二进制表示如下：
十进制 二进制
1 1
3 11
5 101
7 111
9 1001
它们的和为 1 + 3 + 5 + 7 + 9 = 25 。
示例 2：
输入：k = 3, n = 7
输出：499
解释：
7 个最小的 3 镜像数字和它们的三进制表示如下：
十进制 三进制
1 1
2 2
4 11
8 22
121 11111
151 12121
212 21212
它们的和为 1 + 2 + 4 + 8 + 121 + 151 + 212 = 499 。
示例 3：
输入：k = 7, n = 17
输出：20379000
解释：17 个最小的 7 镜像数字分别为：
1, 2, 3, 4, 5, 6, 8, 121, 171, 242, 292, 16561, 65656, 2137312, 4602064, 6597956, 6958596
提示：
2 <= k <= 91 <= n <= 30
思路：
比赛的时候没想到解法，暴力打表
实际上是一道构造题，从小往大构造每个回文十进制数，将其转换成k进制数判断其是否仍是回文数，直至找到n个数为止，返回这n个数的和
注意：构造回文数时，每个数要考虑奇偶长度，例如，给定数 1234 用它构造回文数可以是 1234321 或者 12344321
还要保证构造的回文数是按照从小到大的顺序来的！
class Solution {public long kMirror(int k, int n) {long res = 0;for (int len = 1; ; len++) {//这两行太妙了，每组长度的数字都取了两次！！！long x = (long)Math.pow(10, (len - 1) / 2);long y = (long)Math.pow(10, (len + 1) / 2);for (long i = x; i < y; i++) {long b = i;//根据len奇偶性构造奇偶长度的回文串for (long j = len % 2 == 1 ? i / 10 : i; j > 0; j /= 10) {b = b * 10 + j % 10;}//这个函数可以直接将一个数转换为对应进制字符串String s = Long.toString(b, k);if (check(s.toCharArray())) {res += b;if (--n == 0)return res;}}}}boolean check(char[] chars) {for (int i = 0, j = chars.length - 1; i < j; i++, j--)if (chars[i] != chars[j])return false;return true;}}
若有收获，就点个赞吧
0 人点赞
