LeetCode第166场周赛题解
LeetCode第166场周赛题解
BBuf
发布于 2019-12-11 17:50:56
发布于 2019-12-11 17:50:56
前言
这是LeetCode的第166场周赛的题解，不出意外的又爆炸了，前三题只做了20分钟，第4题因为题意读错了耽误了40分钟，到1小时15分钟左右才写完。排名直接100开完，不过这次倒是一次错误都没有，4份代码都AC了。可惜啦这把。
整数的各位积和之差
- 题意：给你一个整数 n，请你帮忙计算并返回该整数「各位数字之积」与「各位数字之和」的差。
- 数据范围：1 <= n <= 10^5
- 思路：直接模拟。
- 复杂度：O(1)
- 代码：
class Solution {
public:
int subtractProductAndSum(int n) {
vector <int> v;
while(n){
v.push_back(n%10);
n/=10;
}
int a=1,b=0;
for(int i=0; i<v.size(); i++){
a*=v[i];
b+=v[i];
}
return a-b;
}
};
用户分组
- 题意：有 位用户参加活动，他们的 ID 从 到 ，每位用户都 恰好 属于某一用户组。给你一个长度为 n 的数组 ，其中包含每位用户所处的用户组的大小，请你返回用户分组情况（存在的用户组以及每个组中用户的 ID）。你可以任何顺序返回解决方案，ID 的顺序也不受限制。此外，题目给出的数据保证至少存在一种解决方案。
- 数据范围：
- 思路：统计一下每个组的人数，开一个维的vector，表示用户所处用户组大小为的用户编号，然后对于，我们把这里面每个分成一组就做完了。
- 复杂度：O(n)
- 代码：
class Solution {
public:
vector <int> v[510];
vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
for(int i=0; i<510; i++) v[i].clear();
int n = groupSizes.size();
for(int i=0; i<n; i++){
v[groupSizes[i]].push_back(i);
}
vector <vector<int> >ans;
for(int i=1; i<=n; i++){
int cnt = 0;
vector <int> tmp;
for(int j=0; j<v[i].size(); j++){
tmp.push_back(v[i][j]);
cnt++;
if(cnt==i){
ans.push_back(tmp);
tmp.clear();
cnt=0;
}
}
}
return ans;
}
};
使结果不超过阈值的最小除数
- 题意：给你一个整数数组 nums 和一个正整数 threshold ，你需要选择一个正整数作为除数，然后将数组里每个数都除以它，并对除法结果求和。请你找出能够使上述结果小于等于阈值 threshold 的除数中 最小 的那个。每个数除以除数后都向上取整，比方说 7/3 = 3 ， 10/2 = 5 。题目保证一定有解。
- 数据范围：
- 思路：二分，因为函数显然是具有单调性的。
- 复杂度：O(nlogS),S为二分的上界
- 代码：
class Solution {
public:
bool check(int x, vector <int>v, int thres){
int ans=0;
for(int i=0; i<v.size(); i++){
int t = v[i]/x;
if(v[i]%x!=0) t+=1;
ans+=t;
if(ans>thres) return false;
}
return true;
}
int smallestDivisor(vector<int>& nums, int threshold) {
int l=1, r=1e9;
int ans=0;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid, nums, threshold)){
ans=mid;
r=mid-1;
}
else{
l=mid+1;
}
}
return ans;
}
};
转化为全零矩阵的最少反转次数
- 题意：给你一个 m x n 的二进制矩阵 mat。每一步，你可以选择一个单元格并将它反转（反转表示 0 变 1 ，1 变 0 ）。如果存在和它相邻的单元格，那么这些相邻的单元格也会被反转。（注：相邻的两个单元格共享同一条边。）请你返回将矩阵 mat 转化为全零矩阵的最少反转次数，如果无法转化为全零矩阵，请返回 -1 。二进制矩阵的每一个格子要么是 0 要么是 1 。全零矩阵是所有格子都为 0 的矩阵。
- 数据范围：1<=n，m<=3。
- 思路：由于n, m特别小直接BFS爆搜就可以了。最开始以为是高斯消园来着，样例错了很久才反应过来。。。
- 代码：
class Solution {
public:
struct node{
int n, m, step;
vector <int> v;
node(){}
node(int n_, int m_, int step_, vector<int>v_):n(n_),m(m_),step(step),v(v_){}
};
int dir[4][2]={{0, 1},{0, -1}, {1, 0}, {-1, 0}};
int minFlips(vector<vector<int>>& mat) {
int n = mat.size();
int m = mat[0].size();
map <vector<int>, bool>vis;
queue <node> q;
node now;
now.n=n, now.m=m, now.step=0;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
now.v.push_back(mat[i][j]);
}
}
q.push(now);
vis[now.v]=1;
int ans = -1;
int a[3][3]={0};
while(q.size()){
now = q.front();
q.pop();
bool flag = true;
for(int i=0; i<n*m; i++){
if(now.v[i]>0){
flag = false;
}
}
if(flag){
ans = now.step;
break;
}
//printf("%d\n", now.step);
node nex;
nex.n = n, nex.m = m;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
a[i][j] = now.v[i*m+j];
}
}
int b[3][3]={0};
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
memset(b, 0, sizeof(b));
for(int x=0; x<n; x++){
for(int y=0; y<m; y++){
b[x][y]=a[x][y];
}
}
b[i][j]=a[i][j]^1;
for(int k=0; k<4; k++){
int tx = i+dir[k][0], ty = j+dir[k][1];
if(tx>=0&&tx<n&&ty>=0&&ty<m){
b[tx][ty]=a[tx][ty]^1;
}
}
nex.v.clear();
for(int x=0; x<n; x++){
for(int y=0; y<m; y++){
nex.v.push_back(b[x][y]);
}
}
if(!vis[nex.v]){
nex.step=now.step+1;
vis[nex.v]=1;
q.push(nex);
}
}
}
}
return ans;
}
};
后记
连续爆炸，我顶不住了。。。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-12-08，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读