每日算法刷题Day3-起始时间转换、二次方根、while连续输入、斐波那契思路
每日算法刷题Day3-起始时间转换、二次方根、while连续输入、斐波那契思路
每日算法刷题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：
O JOGO DUROU 2 HORA(S) E 2 MINUTO(S)输入样例2：
7 7 7 7输出样例2：
O JOGO DUROU 24 HORA(S) E 0 MINUTO(S)输入样例3：
7 10 8 9输出样例3：
O JOGO DUROU 0 HORA(S) E 59 MINUTO(S)代码
思路1：全部转换为分钟计算起始和结束时间，这样方便计算，当计算spent时间小于0时，加上一整天的时间数1440即可。最后输出时采用spent_time / 60计算小时数，spent_time % 60计算分钟数。
#include <cstdio>
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;
}思路2：将借位的方式处理一下，总体思路还是c-a计算小时，d-b计算分钟。
#include <iostream>
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);
}反思
#include <bits/stdc++.h>
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;
}做法太过于冗余，观察可知c>a和c<a输出的逻辑差别不大，可以进一步统一，直接对变量进行自增减，输出采用同一语句，以达到化简的目的。
9.求解二次方根
总结
在求解二次方根的公式中，
(-b-sqrt(b*b-4*a*c))/2*a有问题，注意括号问题，改为：
(-b-sqrt(b*b-4*a*c))/(2*a)10. 连续整数相加
如果读入的N为0或负数，则继续读取数字直至读入N值为正整数为止。
可以将式子由
while(n<=0){
cin>>n;
}化简到
while(cin>>n,n<=0);11. 区间 2
第一行包含整数 N，表示共有 N 个整数需要进行判断。
接下来 N 行，每行包含一个整数 Xi。
int n;
cin >> n;
while(n--)比
for(int i = 0;i<n;i++)更加简便。
12. 简单斐波那契
以下数列 0 1 1 2 3 5 8 13 21 ... 被称为斐波纳契数列。
这个数列从第 3 项开始，每一项都等于前两项之和。
输入一个整数 N，请你输出这个序列的前 N 项。
输入格式
一个整数 N。
输出格式
在一行中输出斐波那契数列的前 N 项，数字之间用空格隔开。
数据范围
0<N<46
输入样例：
5输出样例：
0 1 1 2 3代码
#include<bits/stdc++.h>
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;
}开数组过于浪费空间，并且多个循环效率不高。
一般斐波那契的不开数组思路如下：
#include<stdio.h>
long long n,a,b=1,c;
int main(){
scanf("%d",&n);
while(n--){
printf("%d ",a);
c=a+b;
a=b;
b=c;
}
}其中a=b,b=c,c=a+b是一个整体左移的思想。
专题往期合集：每日算法题解
本专题练习题目、学习、面试、内推均在：牛客刷题网