LeetCodeEveryday
Coding Everyday
2575. 找出字符串的可整除数组
给你一个下标从 0 开始的字符串 word
,长度为 n
,由从 0
到 9
的数字组成。另给你一个正整数 m
。
word
的 可整除数组 div
是一个长度为 n
的整数数组,并满足:
- 如果
word[0,...,i]
所表示的 数值 能被m
整除,div[i] = 1
- 否则,
div[i] = 0
返回 word
的可整除数组。
示例 1:
输入:word = "998244353", m = 3
输出:[1,1,0,0,0,1,1,0,0]
解释:仅有 4 个前缀可以被 3 整除:"9"、"99"、"998244" 和 "9982443" 。
示例 2:
输入:word = "1010", m = 10
输出:[0,1,0,1]
解释:仅有 2 个前缀可以被 10 整除:"10" 和 "1010" 。
提示:
1 <= n <= 105
word.length == n
word
由数字0
到9
组成1 <= m <= 109
Code
240307
class Solution {
public:
vector<int> divisibilityArray(string word, int m) {
int len=word.length();
vector<int> res(len);
long long num=0;
for(int i=0;i<len;i++){
num*=10;
num+=word[i]-'0';
if(num%m==0) res[i]=1;
else res[i]=0;
num%=m;
}
return res;
}
};
class Solution:
def divisibilityArray(self, word: str, m: int) -> List[int]:
length=len(word)
res=[0]*length
num=0
for i in range(0,length):
num*=10
num+=int(word[i])
if(num%m==0):
res[i]=1
else:
res[i]=0
num%=m
return res
2834. 找出美丽数组的最小和
给你两个正整数:n
和 target
。
如果数组 nums
满足下述条件,则称其为
美丽数组 。
nums.length == n
.nums
由两两互不相同的正整数组成。- 在范围
[0, n-1]
内,不存在 两个 不同 下标i
和j
,使得nums[i] + nums[j] == target
。
返回符合条件的美丽数组所可能具备的 最小
和,并对结果进行取模 109 + 7
。
示例 1:
输入:n = 2, target = 3
输出:4
解释:nums = [1,3] 是美丽数组。
- nums 的长度为 n = 2 。
- nums 由两两互不相同的正整数组成。
- 不存在两个不同下标 i 和 j ,使得 nums[i] + nums[j] == 3 。
可以证明 4 是符合条件的美丽数组所可能具备的最小和。
示例 2:
输入:n = 3, target = 3
输出:8
解释:
nums = [1,3,4] 是美丽数组。
- nums 的长度为 n = 3 。
- nums 由两两互不相同的正整数组成。
- 不存在两个不同下标 i 和 j ,使得 nums[i] + nums[j] == 3 。
可以证明 8 是符合条件的美丽数组所可能具备的最小和。
示例 3:
输入:n = 1, target = 1
输出:1
解释:nums = [1] 是美丽数组。
提示:
1 <= n <= 109
1 <= target <= 109
Code1
240308
超时,n=1000000000
target=1000000000
。
class Solution {
public:
const int MOD=1000000007;
int minimumPossibleSum(int n, int target) {
int sum=0;
int last=min(target/2,n);
for(int i=1;i<=last;i++){
sum=(sum+i)%MOD;
// cout<<i<<",";
}
last=target+n-min(target/2,n);
for(int i=target;i<last;i++){
sum=(sum+i)%MOD;
// cout<<target<<",";
}
// cout<<endl;
return sum;
}
};
Code2
240308
数学题,优化成O(1)
了。
class Solution {
public:
const int MOD=1000000007;
int minimumPossibleSum(int n, int target) {
long long sum=0;
long long last=min(target/2,n);
sum=(1+last)*last/2;
last=target+n-min(target/2,n);
sum+=(target+last-1)*(last-target)/2;
return sum%MOD;
}
};
class Solution {
public:
int minimumPossibleSum(int n, int target) {
long long Min=min(target/2,n);
return ((Min+1)*Min/2+((long long)target+target+n-Min-1)*(n-Min)/2)%1000000007;
}
};
class Solution:
def minimumPossibleSum(self, n: int, target: int) -> int:
temp=min(n,target//2)
sum=(1+temp)*temp//2
temp=target+n-temp
sum+=(target+temp-1)*(temp-target)//2
return sum%1000000007
# if(n<=target//2):
# res=(1+n)*n//2
# return res%1000000007
# else:
# res=(1+target//2)*target//4
# res+=(target+target+(n-target//2)-1)*(n-target//2)//2
# return res%1000000007
2386. 找出数组的第 K 大和
给你一个整数数组 nums
和一个 正 整数
k
。你可以选择数组的任一 子序列
并且对其全部元素求和。
数组的 第 k 大和 定义为:可以获得的第 k
个 最大 子序列和(子序列和允许出现重复)
返回数组的 第 k 大和 。
子序列是一个可以由其他数组删除某些或不删除元素排生而来的数组,且派生过程不改变剩余元素的顺序。
注意:空子序列的和视作 0
。
示例 1:
输入:nums = [2,4,-2], k = 5
输出:2
解释:所有可能获得的子序列和列出如下,按递减顺序排列:
- 6、4、4、2、2、0、0、-2
数组的第 5 大和是 2 。
示例 2:
输入:nums = [1,-2,3,4,-10,12], k = 16
输出:10
解释:数组的第 16 大和是 10 。
提示:
n == nums.length
1 <= n <= 105
-109 <= nums[i] <= 109
1 <= k <= min(2000, 2n)
Code
240309
超时,时间复杂度\(O(nk)\)。
class Solution {
public:
void debug(priority_queue<long long,vector<long long>,greater<long long>> q){
while(!q.empty()){
cout<<q.top()<<",";
q.pop();
}
cout<<endl;
}
long long kSum(vector<int>& nums, int k) {
sort(nums.begin(),nums.end(),greater<int>());
priority_queue<long long,vector<long long>,greater<long long>> q;
priority_queue<long long,vector<long long>,greater<long long>> temp;
for(int num:nums){
// if(num<0 && q.size()>=k) break;
temp=q;
while(!temp.empty()){
q.emplace(temp.top()+num);
temp.pop();
}
q.emplace(num);
// debug(q);
while(q.size()>k){
q.pop();
}
// cout<<q.size()<<endl;
// debug(q);
// cout<<endl;
}
q.emplace(0);
while(q.size()>k) q.pop();
// debug(q);
return q.top();
}
};
Code2
230309
做不来了。。。
2129. 将标题首字母大写
给你一个字符串 title
,它由单个空格连接一个或多个单词组成,每个单词都只包含英文字母。请你按以下规则将每个单词的首字母
大写 :
- 如果单词的长度为
1
或者2
,所有字母变成小写。 - 否则,将单词首字母大写,剩余字母变成小写。
请你返回 大写后 的 title
。
示例 1:
输入:title = "capiTalIze tHe titLe"
输出:"Capitalize The Title"
解释:
由于所有单词的长度都至少为 3 ,将每个单词首字母大写,剩余字母变为小写。
示例 2:
输入:title = "First leTTeR of EACH Word"
输出:"First Letter of Each Word"
解释:
单词 "of" 长度为 2 ,所以它保持完全小写。
其他单词长度都至少为 3 ,所以其他单词首字母大写,剩余字母小写。
示例 3:
输入:title = "i lOve leetcode"
输出:"i Love Leetcode"
解释:
单词 "i" 长度为 1 ,所以它保留小写。
其他单词长度都至少为 3 ,所以其他单词首字母大写,剩余字母小写。
Code
240311
class Solution {
public:
string capitalizeTitle(string title) {
stringstream ss(title);
string word,res;
while(ss>>word){
if(word.length()<=2){
for(char& c:word){
c=tolower(c);
}
res+=word+" ";
}else{
for(char& c:word) c=tolower(c);
word[0]=toupper(word[0]);
res+=word+" ";
}
}
res.pop_back();
return res;
}
};
2684. 矩阵中移动的最大次数
给你一个下标从 0 开始、大小为 m x n
的矩阵 grid
,矩阵由若干 正 整数组成。
你可以从矩阵第一列中的 任一
单元格出发,按以下方式遍历 grid
:
- 从单元格
(row, col)
可以移动到(row - 1, col + 1)
、(row, col + 1)
和(row + 1, col + 1)
三个单元格中任一满足值 严格 大于当前单元格的单元格。
返回你在矩阵中能够 移动 的 最大 次数。
示例 1:
![img](https://assets.leetcode.com/uploads/2023/04/11/yetgriddrawio-10.png)
输入:grid = [[2,4,3,5],[5,4,9,3],[3,4,2,11],[10,9,13,15]]
输出:3
解释:可以从单元格 (0, 0) 开始并且按下面的路径移动:
- (0, 0) -> (0, 1).
- (0, 1) -> (1, 2).
- (1, 2) -> (2, 3).
可以证明这是能够移动的最大次数。
示例 2:
输入:grid = [[3,2,4],[2,1,9],[1,1,7]]
输出:0
解释:从第一列的任一单元格开始都无法移动。
提示:
m == grid.length
n == grid[i].length
2 <= m, n <= 1000
4 <= m * n <= 105
1 <= grid[i][j] <= 106
Code
240316
class Solution {
public:
int Max,m,n;
// void bfs(vector<vector<int>>& matrix,int xx){
// queue<pair<int,int>> q;
// // vector<vector<int>> vis(m,vector<int>(n,0));
// q.push({xx,0});
// // vis[xx][0]=1;
// while(!q.empty()){
// int x=q.front().first;
// int y=q.front().second;
// // cout<<x<<","<<y<<endl;
// Max=max(Max,y);
// q.pop();
// for(int i=-1;i<=1;i++){
// if(x+i>=0 && x+i<m && y+1<n && matrix[x+i][y+1]>matrix[x][y]){
// // vis[x+i][y+1]=1;
// q.push({x+i,y+1});
// }
// }
// }
// }
int maxMoves(vector<vector<int>>& grid) {
m=grid.size();
n=grid[0].size();
Max=0;
// for(int i=0;i<m;i++){
// bfs(grid,i);
// }
queue<pair<int,int>> q;
vector<vector<int>> vis(m,vector<int>(n,0));
for(int i=0;i<m;i++){
q.push(make_pair(i,0));
}
// vis[xx][0]=1;
while(!q.empty()){
int x=q.front().first;
int y=q.front().second;
// cout<<x<<","<<y<<endl;
Max=max(Max,y);
q.pop();
for(int i=-1;i<=1;i++){
if(x+i>=0 && x+i<m && y+1<n && grid[x+i][y+1]>grid[x][y] && !vis[x+i][y+1]){
vis[x+i][y+1]=1;
q.push({x+i,y+1});
}
}
}
return Max;
}
};
303. 区域和检索 - 数组不可变
给定一个整数数组 nums
,处理以下类型的多个查询:
- 计算索引
left
和right
(包含left
和right
)之间的nums
元素的 和 ,其中left <= right
实现 NumArray
类:
NumArray(int[] nums)
使用数组nums
初始化对象int sumRange(int i, int j)
返回数组nums
中索引left
和right
之间的元素的 总和 ,包含left
和right
两点(也就是nums[left] + nums[left + 1] + ... + nums[right]
)
示例 1:
输入:
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
输出:
[null, 1, -1, -3]
解释:
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1))
numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))
提示:
1 <= nums.length <= 104
-105 <= nums[i] <= 105
0 <= i <= j < nums.length
- 最多调用
104
次sumRange
方法
Code
240318
class NumArray {
public:
vector<int> v;
NumArray(vector<int>& nums) {
int n=nums.size();
v.resize(n,0);
v[0]=nums[0];
for(int i=1;i<n;i++){
v[i]=v[i-1]+nums[i];
}
}
int sumRange(int left, int right) {
if(left==0) return v[right];
else return v[right]-v[left-1];
}
};
/**
* Your NumArray object will be instantiated and called as such:
* NumArray* obj = new NumArray(nums);
* int param_1 = obj->sumRange(left,right);
*/