突然觉得自己还是挺菜的，智商还是不够……第一题竟然最后都想打表了……其实很多时候，当思路挺乱的时候，先把代码备份到一边，然后再重新想，很可能答案就呼之欲出了。
A. 日期之间隔几天
题目链接
题目描述
请你编写一个程序来计算两个日期之间隔了多少天。
日期以字符串形式给出，格式为 YYYY-MM-DD，如示例所示。
思路
最开始想怎么算，其实这道题范围很小，只有 1971 到 2100 年，直接模拟就好了。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| class Solution {
public:
int cnt[3005],p[14];
int daysBetweenDates(string date1, string date2) {
int n1=0,m1=0,r1=0,n2=0,m2=0,r2=0;
for(int i=0;i < 4;i++)
{
n1=(n1*10)+date1[i]-'0';
n2=(n2*10)+date2[i]-'0';
}
for(int i=5;i < 7;i++)
{
m1=(m1*10)+date1[i]-'0';
m2=(m2*10)+date2[i]-'0';
}
for(int i=8;i < 10;i++)
{
r1=(r1*10)+date1[i]-'0';
r2=(r2*10)+date2[i]-'0';
}
p[1]=31;p[2]=28;p[3]=31;p[4]=30;p[5]=31;p[6]=30;
p[7]=31;p[8]=31;p[9]=30;p[10]=31;p[11]=30;p[12]=31;
if(n1 > n2)
{
swap(n1,n2);
swap(m1,m2);
swap(r1,r2);
}
else if(n1==n2)
{
if(m1 > m2)
{
swap(m1,m2);
swap(r1,r2);
}
else if(m1==m2)
{
if(r1 > r2) swap(r1,r2);
}
}
int ans=0;
while(n1!=n2||m1!=m2||r1!=r2)
{
if(n1%4==0&&n1!=2100) p[2]=29;
else p[2]=28;
r1++;ans++;
if(r1 > p[m1])
{
r1=1;m1++;
}
if(m1 > 12)
{
m1=1;n1++;
}
}
return ans;
}
};
|
B. 验证二叉树
题目链接
题目描述
二叉树上有 n 个节点，按从 0 到 n - 1 编号，其中节点 i 的两个子节点分别是 leftChild[i] 和 rightChild[i]。
只有 所有 节点能够形成且 只 形成 一颗 有效的二叉树时，返回 true；否则返回 false。
如果节点 i 没有左子节点，那么 leftChild[i] 就等于 -1。右子节点也符合该规则。
注意：节点没有值，本问题中仅仅使用节点编号。
思路
考查二叉树的定义：只有一个点入度为 0 ，其他点的入度都为 1 ，注意一些细节。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| class Solution {
public:
bool vis[100005];
int rd[100005],m=0;
bool validateBinaryTreeNodes(int n, vector < int > & leftChild, vector < int > & rightChild) {
for(int i=0;i < n;i++)
{
int x=leftChild[i],y=rightChild[i];
if(x!=-1)
{
vis[x]=true;
rd[x]++;
m++;
}
if(y!=-1)
{
vis[y]=true;
rd[y]++;
m++;
}
}
if(m!=n-1) return false;
int f=0,f2=0;
for(int i=1;i < n;i++)
{
if(rd[i]!=1)
{
if(!rd[i]&&!f) f=1;
else return false;
}
if(!vis[i])
{
if(!f&&!rd[i]) f2=1;
else return false;
}
}
return true;
}
};
|
C. 最接近的因数
题目链接
题目描述
给你一个整数 num，请你找出同时满足下面全部要求的两个整数：
- 两数乘积等于 num + 1 或 num + 2
- 以绝对差进行度量，两数大小最接近
你可以按任意顺序返回这两个整数。
思路
很显然以 O(n⋅n) 的时间复杂度直接枚举两个因数取最优就好了。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| class Solution {
public:
vector < int > closestDivisors(int num) {
int ta,tb,sa,sb;
int s=sqrt(num+1)+1;
for(int i=s;i;i--)
{
if((num+1)%i==0)
{
ta=i;
tb=(num+1)/i;
break;
}
}
s=sqrt(num+2)+1;
for(int i=s;i;i--)
{
if((num+2)%i==0)
{
sa=i;
sb=(num+2)/i;
break;
}
}
vector < int > ans;
int p1=abs(ta-tb),p2=abs(sa-sb);
if(p1 < p2)
{
ans.push_back(ta);
ans.push_back(tb);
}
else
{
ans.push_back(sa);
ans.push_back(sb);
}
return ans;
}
};
|
D. 形成三的最大倍数
题目链接
题目描述
给你一个整数数组 digits，你可以通过按任意顺序连接其中某些数字来形成 3 的倍数，请你返回所能得到的最大的 3 的倍数。
由于答案可能不在整数数据类型范围内，请以字符串形式返回答案。
如果无法得到答案，请返回一个空字符串。
思路
采用先全部选，然后删去的方法，先算出所有 digits 的和 tot
- 如果 (tot-1) % 3 == 0 ，那么肯定先扣除 1 , 4 , 7 ，如果没有，再考虑扣除两个 2 , 5 , 8 ，如果还不行就看是否有 0 ，如果没有就无解。
- 如果 (tot-2) % 3 == 0 ，那么就反着来就好了。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
| class Solution {
public:
int cnt[105],tot=0;
string largestMultipleOfThree(vector < int > & digits) {
for(int i=0;i < digits.size();i++)
{
cnt[digits[i]]++;
tot+=digits[i];
}
if(tot%3==1)
{
for(int i=1;i < =7;i+=3)
{
if(cnt[i])
{
cnt[i]--;
tot-=i;
break;
}
}
if(tot%3)
{
for(int i=2;i < =8;i+=3)
{
if(cnt[i] > =2)
{
cnt[i]-=2;
tot-=i*2;
break;
}
}
}
}
if(tot%3==2)
{
for(int i=2;i < =8;i+=3)
{
if(cnt[i])
{
cnt[i]--;
tot-=i;
break;
}
}
if(tot%3)
{
for(int i=1;i < =7;i+=3)
{
if(cnt[i] > =2)
{
cnt[i]-=2;
tot-=i*2;
break;
}
}
}
}
string ans="";
if(tot%3) return ans;
if(tot==0&&cnt[0])
{
ans+="0";
return ans;
}
for(int i=9;~i;i--)
{
for(int j=1;j < =cnt[i];j++) ans+=(char)(i+'0');
}
return ans;
}
};
|
