力扣 第 177 场周赛 题解
2个月前攒够了衣服就没打了，重新捡起来，被吊打。。
在这里插入图片描述
日期之间隔几天
- 题面：
第一题
- 思路：主要是考虑一下闰年和平年，以及每个月有多少天，简单的模拟题。
- 代码：
bool runnian(int a){
if(a%400 == 0 || (a%4==0 && a%100 != 0)) return 1;
else return 0;
}
int dijitian(int a,int b,int c){
int sum=c;
for(int i=1;i<b;i++){
if(i==1||i==3||i==5||i==7||i==8||i==10||i==12)
sum+=31;
if(i==4||i==6||i==9||i==11)
sum+=30;
if(i==2){
if(runnian(a)) sum+=29;
else sum+=28;
}
}
return sum;
}
class Solution {
public:
int daysBetweenDates(string date1, string date2) {
int y1 = 0, m1 = 0, d1 = 0;
int y2 = 0, m2 = 0, d2 = 0;
y1 = (date1[0]-'0')*1000+(date1[1]-'0')*100+(date1[2]-'0')*10+(date1[3]-'0');
m1 = (date1[5]-'0')*10+(date1[6]-'0');
d1 = (date1[8]-'0')*10+(date1[9]-'0');
y2 = (date2[0]-'0')*1000+(date2[1]-'0')*100+(date2[2]-'0')*10+(date2[3]-'0');
m2 = (date2[5]-'0')*10+(date2[6]-'0');
d2 = (date2[8]-'0')*10+(date2[9]-'0');
int ans=0;
if(y1==y2)
ans = abs(dijitian(y1,m1,d1)-dijitian(y2,m2,d2));
else{
if(y1>y2){
swap(y1,y2);
swap(m1,m2);
swap(d1,d2);
}
for(int i=y1+1;i<y2;i++){
if(runnian(i))
ans+=366;
else ans+=365;
}
ans+=dijitian(y2,m2,d2);
if(runnian(y1)) ans+=(366-dijitian(y1,m1,d1));
else ans+=(365-dijitian(y1,m1,d1));
}
return ans;
}
};
验证二叉树
- 题面：
第二题
- 数据范围：
1 <= n <= 10^4，leftChild.length == rightChild.length == n，-1 <= leftChild[i], rightChild[i] <= n - 1。 - 思路：这个题呢，需要稍微想一下，其实直接判断一下二叉树的每个节点入度和出度的取值是否合理，并且判断根节点（入度为0的节点）是否唯一就可以了。
- 复杂度：O(n)
- 代码：
class Solution {
public:
int in[10010], out[10010];
bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
memset(in, 0, sizeof(in));
memset(out, 0, sizeof(out));
for(int i=0; i<n; i++){
out[i]++;
if(leftChild[i]!=-1) in[leftChild[i]]++;
if(rightChild[i]!=-1) in[rightChild[i]]++;
}
int root = 0;
bool flag = true;
for(int i=0; i<n; i++){
if(in[i]==0) root++;
if(in[i]>1) flag=false;
if(out[i]>2) flag=false;
}
if(root==1&&flag) return true;
else return false;
}
};
最接近的因数
- 题面：
第3题
- 思路：暴力题，直接把所有的因子对枚举出来，放到一个
vector中，然后按照因子对的绝对值差从小到大排序之后取第1个因子对就可以了。所谓因子对就是对于(a,b)，如果a=num/b，那么(a,b)就是因子对。 - 复杂度：O(2*sqrt(num))
- 代码：
class Solution {
public:
struct node{
int x,y;
node(){}
node(int x_,int y_):x(x_),y(y_){}
bool operator<(const node&rhs) const{
return abs(x-y) < abs(rhs.x-rhs.y);
}
};
vector<int> closestDivisors(int num) {
int n = num+1;
vector<node>v;
for(int i=1; i*i<=n; i++){
if(n%i==0){
v.push_back(node(i,n/i));
}
}
n=num+2;
for(int i=1; i*i<=n; i++){
if(n%i==0){
v.push_back(node(i,n/i));
}
}
sort(v.begin(), v.end());
vector <int> ans;
ans.push_back(v[0].x);
ans.push_back(v[0].y);
return ans;
}
};
形成3的最大倍数
- 题面：
第4题
- 思路：老题了，先按照字符大小从大到小排序，然后看一下所有数字求和(记作
sum)模上3等于多少，分情况讨论即可。- 如果sum=0，那么所有数字都可以，直接返回排序后的字符串。
- 如果sum=1，要么直接删除一个最小（从后往前遍历）的模上3等于1的（记住这里就可以直接return了，我脑子晕了会，wa了5发，差点前200都保不住），要么删除2个模上3等于2的数。否则无解。
- 如果sum=2，要么直接删除一个最小（从后往前遍历）的模上3等于2的（记住这里就可以直接return了），要么删除2个模上3等于1的数。否则无解。
- 复杂度：O(n)
- 代码（写得很丑。。）：
class Solution {
public:
string largestMultipleOfThree(vector<int>& digits) {
sort(digits.begin(), digits.end(), greater<int>{});
int sum = 0;
int len = digits.size();
for(int i=0; i<len; i++){
sum += digits[i]%3;
}
sum %= 3;
string ans="";
if(sum==0){
for(int i=0; i<len; i++){
ans += digits[i]+'0';
}
}
else if(sum==1){
int pos = -1;
for(int i=len-1; i>=0; i--){
if(digits[i]%3==1){
pos=i;
break;
}
}
if(pos != -1){
for(int i=0; i<len; i++){
if(i==pos) continue;
ans += digits[i]+'0';
}
return ans;
}
int pos1 = -1, pos2 = -1;
for(int i=len-1; i>=0; i--){
if(digits[i]%3==2 && pos1==-1){
pos1 = i;
}
else if(digits[i]%3==2 && pos2==-1){
pos2 = i;
}
else if(pos1>0&&pos2>0){
break;
}
}
if(pos1!=-1&&pos2!=-1){
for(int i=0; i<len; i++){
if(i==pos1||i==pos2) continue;
ans += digits[i]+'0';
}
}
}
else{
int pos = -1;
for(int i=len-1; i>=0; i--){
if(digits[i]%3==2){
pos=i;
break;
}
}
if(pos != -1){
for(int i=0; i<len; i++){
if(i==pos) continue;
ans += digits[i]+'0';
}
return ans;
}
int pos1 = -1, pos2 = -1;
for(int i=len-1; i>=0; i--){
if(digits[i]%3==1 && pos1==-1){
pos1 = i;
}
else if(digits[i]%3==1 && pos2==-1){
pos2 = i;
}
else if(pos1>0&&pos2>0){
break;
}
}
if(pos1!=-1&&pos2!=-1){
for(int i=0; i<len; i++){
if(i==pos1||i==pos2) continue;
ans += digits[i]+'0';
}
}
}
if(ans=="") return ans;
string ans2 = "";
int p = -1;
for(int i=0; i<ans.size(); i++){
if(ans[i]!='0'){
p=i;
break;
}
}
if(p==-1) ans2="0";
else{
for(int i=p; i<ans.size(); i++){
ans2+=ans[i];
}
}
return ans2;
}
};
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2020-02-24，如有侵权请联系 cloudcommunity@tencent.com 删除
本文分享自 GiantPandaCV 微信公众号，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ，欢迎热爱写作的你一起参与！
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
