Leetcode 第268场周赛题解

Problem A - 两栋颜色不同且距离最远的房子 (opens new window)

方法一：暴力

枚举所有房子对。

• 时间复杂度$\mathcal{O}(N^2)$。
• 空间复杂度$\mathcal{O}(N^2)$。

参考代码（Python 3）

class Solution:
    def maxDistance(self, colors: List[int]) -> int:
        return max(abs(i - j) for i, ic in enumerate(colors) for j, jc in enumerate(colors) if ic != jc)

方法二：贪心

首先，如果首尾两栋房子颜色不同，答案显然是$N-1$。

在首尾两栋房子颜色相同（设为$C$）的情况下，我们找到最左边的不是$C$的房子$L$，以及最右边的不是$C$的房子$R$，答案即为$\max(R, N-L-1)$。

• 时间复杂度$\mathcal{O}(N)$。
• 空间复杂度$\mathcal{O}(1)$。

参考代码（Python 3）

class Solution:
    def maxDistance(self, colors: List[int]) -> int:
        n = len(colors)
        if colors[0] != colors[n - 1]:
            return n - 1
        
        l = 1
        while colors[l] == colors[0]:
            l += 1
        r = n - 2
        while colors[r] == colors[n - 1]:
            r -= 1
        return max(r, n - 1 - l)

Problem B - 给植物浇水 (opens new window)

方法一：模拟

按题意模拟即可。

• 时间复杂度$\mathcal{O}(N)$。
• 空间复杂度$\mathcal{O}(1)$。

参考代码（C++）

class Solution {
public:
    int wateringPlants(vector<int>& plants, int capacity) {
        int ans = 0, now = capacity, pos = -1, n = plants.size();
        for (int i = 0; i < n; ++i) {
            ans += i - pos;
            pos = i;
            now -= plants[i];
            if (i + 1 < n && now < plants[i + 1]) {
                pos = -1;
                ans += i - pos;
                now = capacity;
            }
        }
        return ans;
    }
};

Problem C - 区间内查询数字的频率 (opens new window)

方法一：二分查找

在初始化时，预处理得到每一数字出现位置的数组，显然这一数组是有序的。

在查询时，利用位置数组二分查找即可。注意可以事先筛除掉不存在的value，这样可以节约空间。

• 初始化时间复杂度$\mathcal{O}(N)$，单次查询时间复杂度$\mathcal{O}(\log N)$。
• 空间复杂度$\mathcal{O}(N)$。

参考代码（C++）

class RangeFreqQuery {
    unordered_map<int, vector<int>> mp;
public:
    RangeFreqQuery(vector<int>& arr) {
        for (int i = 0; i < arr.size(); ++i) 
            mp[arr[i]].emplace_back(i);
    }
    
    int query(int left, int right, int value) {
        if (!mp.count(value))
            return 0;
        
        auto &v = mp[value];
        auto r = upper_bound(v.begin(), v.end(), right);
        auto l = upper_bound(v.begin(), v.end(), left - 1);
        return r - l;
    }
};

Problem D - k 镜像数字的和 (opens new window)

方法一：打表

我们可以针对每种进制数$k$求出足够多的$k$镜像数字，然后直接查表得答案。

注意在打表时，也不能太过暴力。枚举回文数时，只需要枚举半边即可，这样可以大大节约时间。另外，枚举时合理安排顺序，保证按照升序枚举所有数字，可以避免可能的漏解或错解。

• 时间复杂度$\mathcal{O}(N)$（如果直接打前缀和的表，就是$\mathcal{O}(1)$）
• 空间复杂度$\mathcal{O}(1)$（对于本题来说，表是恒定的）

参考代码（Python 3）

ans = [[], [], [1, 3, 5, 7, 9, 33, 99, 313, 585, 717, 7447, 9009, 15351, 32223, 39993, 53235, 53835, 73737, 585585, 1758571, 1934391, 1979791, 3129213, 5071705, 5259525, 5841485, 13500531, 719848917, 910373019, 939474939, 1290880921, 7451111547, 10050905001, 18462126481, 32479297423, 75015151057, 110948849011, 136525525631], [1, 2, 4, 8, 121, 151, 212, 242, 484, 656, 757, 29092, 48884, 74647, 75457, 76267, 92929, 93739, 848848, 1521251, 2985892, 4022204, 4219124, 4251524, 4287824, 5737375, 7875787, 7949497, 27711772, 83155138, 112969211, 123464321, 211131112, 239060932, 387505783, 520080025, 885626588, 2518338152, 58049094085, 81234543218], [1, 2, 3, 5, 55, 373, 393, 666, 787, 939, 7997, 53235, 55255, 55655, 57675, 506605, 1801081, 2215122, 3826283, 3866683, 5051505, 5226225, 5259525, 5297925, 5614165, 5679765, 53822835, 623010326, 954656459, 51717171715, 53406060435, 59201610295, 73979697937, 506802208605, 508152251805], [1, 2, 3, 4, 6, 88, 252, 282, 626, 676, 1221, 15751, 18881, 10088001, 10400401, 27711772, 30322303, 47633674, 65977956, 808656808, 831333138, 831868138, 836131638, 836181638, 2512882152, 2596886952, 2893553982, 6761551676, 12114741121, 12185058121], [1, 2, 3, 4, 5, 7, 55, 111, 141, 191, 343, 434, 777, 868, 1441, 7667, 7777, 22022, 39893, 74647, 168861, 808808, 909909, 1867681, 3097903, 4232324, 4265624, 4298924, 4516154, 4565654, 4598954, 4849484, 5100015, 5182815, 5400045, 5433345, 5482845, 5733375, 5766675, 5799975, 6901096, 6934396, 6983896, 8164618, 9081809, 15266251, 24466442, 103656301, 104888401, 108151801, 290222092, 310393013, 342050243, 3733113373, 4368778634, 7111881117, 7786556877, 8801331088, 11271517211, 12482428421, 18013531081, 61662426616, 71771717717, 75535653557], [1, 2, 3, 4, 5, 6, 8, 121, 171, 242, 292, 16561, 65656, 2137312, 4602064, 6597956, 6958596, 9470749, 61255216, 230474032, 466828664, 485494584, 638828836, 657494756, 858474858, 25699499652, 40130703104, 45862226854, 61454945416, 64454545446, 65796069756, 75016161057, 75431213457, 90750705709, 91023932019, 95365056359, 426970079624, 775350053577], [1, 2, 3, 4, 5, 6, 7, 9, 121, 292, 333, 373, 414, 585, 3663, 8778, 13131, 13331, 26462, 26662, 30103, 30303, 207702, 628826, 660066, 1496941, 1935391, 1970791, 4198914, 55366355, 130535031, 532898235, 719848917, 799535997, 1820330281, 2464554642, 4424994244, 4480880844, 4637337364, 20855555802, 94029892049, 94466666449, 294378873492, 390894498093], [1, 2, 3, 4, 5, 6, 7, 8, 191, 282, 373, 464, 555, 646, 656, 6886, 25752, 27472, 42324, 50605, 626626, 1540451, 1713171, 1721271, 1828281, 1877781, 1885881, 2401042, 2434342, 2442442, 2450542, 3106013, 3114113, 3122213, 3163613, 3171713, 3303033, 3360633, 65666656, 167191761, 181434181, 232000232, 382000283, 5435665345, 8901111098, 9565335659, 827362263728]]

class Solution:
    def kMirror(self, k: int, n: int) -> int:
        return sum(ans[k][:n])
    
# ans = [[] for _ in range(10)]


# def check(num, k):
#     val = []
#     while num > 0:
#         val.append(num % k)
#         num //= k
#     return val == val[::-1]


# for k in range(2, 10):
#     for d in range(6):
#         lo = 10 ** d
#         hi = 10 ** (d + 1)
#         for i in range(lo, hi):
#             s = str(i)
#             num = int(s[:-1] + s[-1] + s[:-1][::-1])
#             if check(num, k):
#                 ans[k].append(num)

#         for i in range(lo, hi):
#             s = str(i)
#             num = int(s + s[::-1])
#             if check(num, k):
#                 ans[k].append(num)

#     assert(len(ans[k]) >= 30)

# print(ans)