难度顺序:
。
你在一家生产小球的玩具厂工作,有 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());
}
};
存在一个由 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 == n
adjacentPairs.length == n - 1
adjacentPairs[i].length == 2
2 <= 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;
}
};
给你一个下标从 0 开始的正整数数组 candiesCount
,其中 candiesCount[i]
表示你拥有的第 i
类糖果的数目。同时给你一个二维数组 queries
,其中 queries[i] = [favoriteTypei, favoriteDayi, dailyCapi]
。
你按照如下规则进行一场游戏:
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^5
1 <= candiesCount[i] <= 10^5
1 <= queries.length <= 10^5
queries[i].length == 3
0 <= favoriteTypei < candiesCount.length
0 <= favoriteDayi <= 10^9
1 <= 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;
}
};
给你一个字符串 s
,如果可以将它分割成三个 非空 回文子字符串,那么返回 true
,否则返回 false
。
当一个字符串正着读和反着读是一模一样的,就称其为 回文字符串 。
示例 1:
输入:s = "abcbdd"
输出:true
解释:"abcbdd" = "a" + "bcb" + "dd",三个子字符串都是回文的。
示例 2:
输入:s = "bcbddxy"
输出:false
解释:s 没办法被分割成 3 个回文子字符串。
提示:
3 <= s.length <= 2000
s
只包含小写英文字母。思路
既然是问能否分成三段回文串,我们就枚举前一段子串和后一段子串即可,枚举的复杂度是
的。
只要我们能
判断一个子串是否是回文串本题就解决了,这个操作可以用马拉车算法或者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;
}
};