只做出前两题。
https://leetcode-cn.com/contest/weekly-contest-268/

1.两栋颜色不同且距离最远的房子

题目描述

街上有 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.length
2 <= n <= 100
0 <= colors[i] <= 100
生成的测试数据满足至少存在 2 栋颜色不同的房子

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-furthest-houses-with-different-colors
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

直接用暴力法，两层遍历找到最大的不同颜色的房子。

class Solution {
public:
    int maxDistance(vector<int>& colors) {
        int n = colors.size();
        int maxLen = 0;
        for (int i = 0; i < n - 1; i++){
            for (int j = i + 1; j < n; j++){
                maxLen = colors[i] != colors[j] ? max(maxLen, j - i) : maxLen;
            }
        }
        return maxLen;
    }
};

2.给植物浇水

题目描述

你打算用一个水罐给花园里的 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.length
1 <= n <= 1000
1 <= plants[i] <= 106
max(plants[i]) <= capacity <= 109

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/watering-plants
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

模拟浇水的过程

class Solution {
public:
    int wateringPlants(vector<int>& plants, int capacity) {
        int ans = 0, cur = capacity;
        int n = plants.size();
        for (int i = 0; i < n; i++){
            if (cur < plants[i]){
                ans += 2 * i + 1;
                cur = capacity - plants[i];
            }
            else{
                ans++;
                cur -= plants[i];
            }
            cout << cur << " " << ans << endl;
        }
        return ans;
    }
};

3.区间内查询数字的频率

题目描述

请你设计一个数据结构，它能求出给定子数组内一个给定值的频率。
子数组中一个值的频率指的是这个子数组中这个值的出现次数。
请你实现 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 <= 105
1 <= arr[i], value <= 104
0 <= left <= right < arr.length
调用 query 不超过 105 次。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/range-frequency-queries
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

看了下题解还是挺简单的，用一个map来记录每个数字出现的位置，然后用二分法来找到子数组中左右的位置。两个相减就是出现的次数了。

class RangeFreqQuery {
public:
    unordered_map<int, vector<int>> m;
    RangeFreqQuery(vector<int>& arr) {
        for (int i = 0; i < arr.size(); i++)
            m[arr[i]].emplace_back(i);
    }
    
    int query(int left, int right, int value) {
        const vector<int>& pos = m[value];
        auto l = lower_bound(pos.begin(), pos.end(), left);
        auto r = upper_bound(pos.begin(), pos.end(), right);
        return r - l;
    }
};

4.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 <= 9
1 <= n <= 30

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sum-of-k-mirror-numbers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出

解题思路

做的时候也就只能想到暴力法，到示例2就超时了。

我的「精神家园」

A周赛268

1.两栋颜色不同且距离最远的房子

题目描述

解题思路

2.给植物浇水

题目描述

解题思路

3.区间内查询数字的频率

题目描述

解题思路

4.k镜像数字的和

题目描述

解题思路