leetcode周赛226
难度顺序：
。
5654. 盒子中小球的最大数量
你在一家生产小球的玩具厂工作，有 n 个小球，编号从 lowLimit 开始，到 highLimit 结束（包括 lowLimit 和 highLimit ，即 n == highLimit - lowLimit + 1）。另有无限数量的盒子，编号从 1 到 infinity 。
你的工作是将每个小球放入盒子中，其中盒子的编号应当等于小球编号上每位数字的和。例如，编号 321 的小球应当放入编号 3 + 2 + 1 = 6 的盒子，而编号 10 的小球应当放入编号 1 + 0 = 1 的盒子。
给你两个整数 lowLimit 和 highLimit ，返回放有最多小球的盒子中的小球数量*。*如果有多个盒子都满足放有最多小球，只需返回其中任一盒子的小球数量。
示例 1：
输入：lowLimit = 1, highLimit = 10
输出：2
解释：
盒子编号：1 2 3 4 5 6 7 8 9 10 11 ...
小球数量：2 1 1 1 1 1 1 1 1 0 0 ...
编号 1 的盒子放有最多小球，小球数量为 2 。
示例 2：
输入：lowLimit = 5, highLimit = 15
输出：2
解释：
盒子编号：1 2 3 4 5 6 7 8 9 10 11 ...
小球数量：1 1 1 1 2 2 1 1 1 0 0 ...
编号 5 和 6 的盒子放有最多小球，每个盒子中的小球数量都是 2 。
示例 3：
输入：lowLimit = 19, highLimit = 28
输出：2
解释：
盒子编号：1 2 3 4 5 6 7 8 9 10 11 12 ...
小球数量：0 1 1 1 1 1 1 1 1 2 0 0 ...
编号 10 的盒子放有最多小球，小球数量为 2 。
提示：
1 <= lowLimit <= highLimit <= 10^5
思路：
求出范围内每个数字的 各位数之和，再找到出现最多的次数即可。
时间复杂度：
.
class Solution {
public:
int countBalls(int lowLimit, int highLimit) {
vector<int> vs(100);
for(int i = lowLimit; i <= highLimit; ++i) {
int sum = 0;
for(int j = i; j > 0; j /= 10) {
sum += j % 10;
}
++ vs[sum];
}
return *max_element(vs.begin(), vs.end());
}
};
5665. 从相邻元素对还原数组
存在一个由 n 个不同元素组成的整数数组 nums ，但你已经记不清具体内容。好在你还记得 nums 中的每一对相邻元素。
给你一个二维整数数组 adjacentPairs ，大小为 n - 1 ，其中每个 adjacentPairs[i] = [ui, vi] 表示元素 ui 和 vi 在 nums 中相邻。
题目数据保证所有由元素 nums[i] 和 nums[i+1] 组成的相邻元素对都存在于 adjacentPairs 中，存在形式可能是 [nums[i], nums[i+1]] ，也可能是 [nums[i+1], nums[i]] 。这些相邻元素对可以 按任意顺序 出现。
返回 原始数组 nums 。如果存在多种解答，返回 其中任意一个 即可。
示例 1：
输入：adjacentPairs = [[2,1],[3,4],[3,2]]
输出：[1,2,3,4]
解释：数组的所有相邻元素对都在 adjacentPairs 中。
特别要注意的是，adjacentPairs[i] 只表示两个元素相邻，并不保证其 左-右 顺序。
示例 2：
输入：adjacentPairs = [[4,-2],[1,4],[-3,1]]
输出：[-2,4,1,-3]
解释：数组中可能存在负数。
另一种解答是 [-3,1,4,-2] ，也会被视作正确答案。
示例 3：
输入：adjacentPairs = [[100000,-100000]]
输出：[100000,-100000]
提示：
nums.length == nadjacentPairs.length == n - 1adjacentPairs[i].length == 22 <= n <= 10^5-10^5 <= nums[i], ui, vi <= 10^5- 题目数据保证存在一些以
adjacentPairs作为元素对的数组nums
思路：
首先把每个数字与其相邻的数组存起来，题目说所有数字都不相同，那么每个点的度数最大为
。
找到数组的第一个元素或者最后一个元素，然后一位位还原即可。
时间复杂度：
.
const int MXN = 2e5 + 5;
const int b = 100000;
class Solution {
public:
int du[MXN];
vector<int> mp[MXN];
vector<int> restoreArray(vector<vector<int>>& adjacentPairs) {
for(auto x: adjacentPairs) {
mp[x[0] + b].emplace_back(x[1] + b);
mp[x[1] + b].emplace_back(x[0] + b);
++ du[x[0] + b], ++ du[x[1] + b];
}
int st = 0, n = adjacentPairs.size() + 1;
for(int i = 0; i < MXN; ++i) if(du[i] == 1) st = i;
vector<int> ans(1, st - b);
int now = mp[st][0];
for(int i = 1; i < n; ++i) {
ans.emplace_back(now - b);
if(i == n - 1) break;
now = (mp[now][0] != st? mp[now][0]: mp[now][1]);
st = ans.back() + b;
}
return ans;
}
};
5667. 你能在你最喜欢的那天吃到你最喜欢的糖果吗？
给你一个下标从 0 开始的正整数数组 candiesCount ，其中 candiesCount[i] 表示你拥有的第 i 类糖果的数目。同时给你一个二维数组 queries ，其中 queries[i] = [favoriteTypei, favoriteDayi, dailyCapi] 。
你按照如下规则进行一场游戏：
- 你从第0天开始吃糖果。
- 你在吃完所有第
i - 1类糖果之前，不能吃任何一颗第i类糖果。 - 在吃完所有糖果之前，你必须每天至少吃一颗糖果。
请你构建一个布尔型数组 answer ，满足 answer.length == queries.length 。answer[i] 为 true 的条件是：在每天吃 不超过 dailyCapi 颗糖果的前提下，你可以在第 favoriteDayi 天吃到第 favoriteTypei 类糖果；否则 answer[i] 为 false 。注意，只要满足上面 3 条规则中的第二条规则，你就可以在同一天吃不同类型的糖果。
请你返回得到的数组 answer 。
示例 1：
输入：candiesCount = [7,4,5,3,8], queries = [[0,2,2],[4,2,4],[2,13,1000000000]]
输出：[true,false,true]
提示：
1- 在第 0 天吃 2 颗糖果(类型 0），第 1 天吃 2 颗糖果（类型 0），第 2 天你可以吃到类型 0 的糖果。
2- 每天你最多吃 4 颗糖果。即使第 0 天吃 4 颗糖果（类型 0），第 1 天吃 4 颗糖果（类型 0 和类型 1），你也没办法在第 2 天吃到类型 4 的糖果。换言之，你没法在每天吃 4 颗糖果的限制下在第 2 天吃到第 4 类糖果。
3- 如果你每天吃 1 颗糖果，你可以在第 13 天吃到类型 2 的糖果。
示例 2：
输入：candiesCount = [5,2,6,4,1], queries = [[3,1,2],[4,10,3],[3,10,100],[4,100,30],[1,3,1]]
输出：[false,true,true,false,false]
提示：
1 <= candiesCount.length <= 10^51 <= candiesCount[i] <= 10^51 <= queries.length <= 10^5queries[i].length == 30 <= favoriteTypei < candiesCount.length0 <= favoriteDayi <= 10^91 <= dailyCapi <= 10^9
思路
刚开始看题目有一点点难读懂。
每个询问是独立的，糖果必须按编号顺序来吃。
首先求出在第favoriteDayi天最少吃到第几个糖果
和最多吃到第几个糖果
。
然后只要保证在上述范围内能吃到第favoriteTypei类糖果即可。
求出前favoriteTypei-1类糖果个数为
，前favoriteTypei类糖果个数为
。
只要满足
答案就是true。
时间复杂度：
.
class Solution {
public:
vector<bool> canEat(vector<int>& candiesCount, vector<vector<int>>& queries) {
int n = queries.size(), m = candiesCount.size();
vector<bool> ans(n, false);
vector<int64_t> sum(m, 0);
sum[0] = candiesCount[0];
for(int i = 1; i < m; ++i) {
sum[i] = sum[i - 1] + candiesCount[i];
}
for(int i = 0; i < n; ++i) {
queries[i][1] += 1;
int64_t Min = queries[i][1], Max = (int64_t)queries[i][1] * queries[i][2];
int64_t x = sum[queries[i][0]] - candiesCount[queries[i][0]] + 1, y = sum[queries[i][0]];
if(Min <= y && x <= Max) ans[i] = true;
}
return ans;
}
};
5666. 回文串分割 IV
给你一个字符串 s ，如果可以将它分割成三个 非空 回文子字符串，那么返回 true ，否则返回 false 。
当一个字符串正着读和反着读是一模一样的，就称其为 回文字符串 。
示例 1：
输入：s = "abcbdd"
输出：true
解释："abcbdd" = "a" + "bcb" + "dd"，三个子字符串都是回文的。
示例 2：
输入：s = "bcbddxy"
输出：false
解释：s 没办法被分割成 3 个回文子字符串。
提示：
3 <= s.length <= 2000s只包含小写英文字母。
思路
既然是问能否分成三段回文串，我们就枚举前一段子串和后一段子串即可，枚举的复杂度是
的。
只要我们能
判断一个子串是否是回文串本题就解决了，这个操作可以用马拉车算法或者hash算法轻松解决。
我选择首先正序hash处理一遍字符串，然后再逆序处理一遍字符串，判断是否是回文串，就是判断正序和逆序的hash值是否相同。
时间复杂度：
.
const int MXN = 2000 + 5;
const int base = 23333;
const int mod = 1e9 + 7;
class Solution {
public:
int rep[MXN], per[MXN], bs[MXN];
int hash1(int a, int b) {
return ((rep[b] - (int64_t)rep[a - 1] * bs[b - a + 1]) % mod + mod) % mod;
}
int hash2(int a, int b) {
return ((per[a] - (int64_t)per[b + 1] * bs[b - a + 1]) % mod + mod) % mod;
}
bool check(int a, int b) {
return hash1(a, b) == hash2(a, b);
}
bool checkPartitioning(string s) {
bs[0] = 1;
for(int i = 1; i < MXN; ++i) bs[i] = (int64_t)bs[i - 1] * base % mod;
int n = s.length();
for(int i = 1; i <= n; ++i) {
rep[i] = ((int64_t)rep[i - 1] * base + s[i - 1]) % mod;
}
for(int i = n; i >= 1; --i) {
per[i] = ((int64_t)per[i + 1] * base + s[i - 1]) % mod;
}
bool ans = false;
for(int i = 1; i <= n - 2 && ans == false; ++i) {
for(int j = i + 2; j <= n && ans == false; ++j) {
if(check(1, i) && check(i + 1, j - 1) && check(j, n)) ans = true;
}
}
return ans;
}
};
腾讯云开发者
