每日算法刷题Day3-起始时间转换、二次方根、while连续输入、斐波那契思路

⭐每日算法题解系列文章旨在精选重点与易错的算法题，总结常见的算法思路与可能出现的错误，与笔者另一系列文章有所区别，并不是以知识点的形式提升算法能力，而是以实战习题的形式理解算法，使用算法。在众多刷题平台中我比较推荐“牛客”平台，它与其他平台相比有以下优点：

• 在线编程环境，可以省去配置环境的繁琐，直接上手刷题。
• 众多企业面试真题，更精准地解决面试算法问题。
• 有非常广泛的论坛与题解讨论基础，可谓是融合了力扣和脉脉的长处。
• 题库难易划分精准，即使小白也可以快速上手学习，同时也包含非常友好的入门题目，学练一体。

学习网站链接：牛客刷题网

开启刷题成长之旅吧！

8.游戏时间2

读取四个整数 A,B,C,D，用来表示游戏的开始时间和结束时间。

其中 A 和 B 为开始时刻的小时和分钟数，C 和 D 为结束时刻的小时和分钟数。

请你计算游戏的持续时间。

比赛最短持续 1分钟，最长持续 24 小时。

输入格式

共一行，包含四个整数 A,B,C,D。

输出格式

输出格式为 O JOGO DUROU X HORA(S) E Y MINUTO(S)，表示游戏共持续了 X 小时 Y 分钟。

数据范围

0≤A,C≤23
0≤B,D≤59

输入/出样例

输入样例1：

7 8 9 10
1

输出样例1：

O JOGO DUROU 2 HORA(S) E 2 MINUTO(S)
1

输入样例2：

7 7 7 7
1

输出样例2：

O JOGO DUROU 24 HORA(S) E 0 MINUTO(S)
1

输入样例3：

7 10 8 9
1

输出样例3：

O JOGO DUROU 0 HORA(S) E 59 MINUTO(S)
1

代码

思路1：全部转换为分钟计算起始和结束时间，这样方便计算，当计算spent时间小于0时，加上一整天的时间数1440即可。最后输出时采用spent_time / 60计算小时数，spent_time % 60计算分钟数。

#include 

int main()
{
    int a, b, c, d;
    scanf("%d%d%d%d", &a, &b, &c, &d);

    int start = a * 60 + b;
    int end = c * 60 + d;

    int spent_time = end - start;
    if (spent_time <= 0) spent_time += 1440;

    printf("O JOGO DUROU %d HORA(S) E %d MINUTO(S)", spent_time / 60, spent_time % 60);

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

思路2：将借位的方式处理一下，总体思路还是c-a计算小时，d-b计算分钟。

#include 

using namespace std;

int main()
{
    int a, b, c, d;
    cin >> a >> b >> c >> d;

    if(d < b) c -= 1,d += 60; // 分钟数不够减,借小时，补60分钟

    if(c < a) c += 24; 

    if(c == a  && d == b) c += 24; // 特判，这种情况表示过了一天

    printf("O JOGO DUROU %d HORA(S) E %d MINUTO(S)",c-a,d-b);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

反思

#include 
using namespace std;
int main()
{
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    if(a==c)
    {
        if(d>b)printf("O JOGO DUROU %d HORA(S) E %d MINUTO(S)",c-a,d-b);
        else if(d<b)printf("O JOGO DUROU %d HORA(S) E %d MINUTO(S)",c-a-1+24,d+60-b);
        else cout<<"O JOGO DUROU 24 HORA(S) E 0 MINUTO(S)";
    }
    else if(c>a)
    {
        if(d>=b)printf("O JOGO DUROU %d HORA(S) E %d MINUTO(S)",c-a,d-b);
        else if(d<b)printf("O JOGO DUROU %d HORA(S) E %d MINUTO(S)",c-a-1,d+60-b);
    }
    else if(c<a)
    {
        if(d>=b)printf("O JOGO DUROU %d HORA(S) E %d MINUTO(S)",c-a+24,d-b);
        else if(d<b)printf("O JOGO DUROU %d HORA(S) E %d MINUTO(S)",c-a-1+24,d+60-b);
    }
    return 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

做法太过于冗余，观察可知c>a和c

9.求解二次方根

总结

在求解二次方根的公式中，

(-b-sqrt(b*b-4*a*c))/2*a
1

有问题，注意括号问题，改为：

(-b-sqrt(b*b-4*a*c))/(2*a)
1

10. 连续整数相加

如果读入的N为0或负数，则继续读取数字直至读入N值为正整数为止。

可以将式子由

    while(n<=0){
        cin>>n;
    }
1
2
3

化简到

while(cin>>n,n<=0);
1

11. 区间 2

第一行包含整数 N，表示共有 N 个整数需要进行判断。

接下来 N 行，每行包含一个整数 Xi。

 	int n;
    cin >> n;
    while(n--)
1
2
3

比

for(int i = 0;i<n;i++)
1

更加简便。

12. 简单斐波那契

以下数列 0 1 1 2 3 5 8 13 21 ... 被称为斐波纳契数列。

这个数列从第 3 项开始，每一项都等于前两项之和。

输入一个整数 N，请你输出这个序列的前 N 项。

输入格式

一个整数 N。

输出格式

在一行中输出斐波那契数列的前 N 项，数字之间用空格隔开。

数据范围

0

输入样例：

5
1

输出样例：

0 1 1 2 3
1

代码

#include
using namespace std;
int main()
{
    int n,a[46]={0,1};
    cin>>n;
    for(int i=2;i<n;i++){
    a[i]=a[i-1]+a[i-2];
    }
    for(int i = 0;i<n;i++)
    {
        cout<<a[i]<<" ";
    }
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

开数组过于浪费空间，并且多个循环效率不高。

一般斐波那契的不开数组思路如下：

#include
long long n,a,b=1,c;
int main(){
    scanf("%d",&n);
    while(n--){
        printf("%d ",a);
        c=a+b;
        a=b;
        b=c;
    }
}
1
2
3
4
5
6
7
8
9
10
11

其中a=b,b=c,c=a+b是一个整体左移的思想。

---

专题往期合集：每日算法题解

本专题练习题目、学习、面试、内推均在：牛客刷题网