蓝桥杯刷题——day5
- 题目一
- 题干
- 解题思路一
- 代码
- 解题思路二
- 代码
- 题目二
- 题干
- 解题思路
- 代码
题目一
题干
给定n个整数 a1,a2,⋯ ,an，求它们两两相乘再相加的和，即：
示例一：
输入：
4
1 3 6 9
输出：
117
题目链接：求和
解题思路一
初次看这个题目第一感觉是用两个双循环首先外循环的i从a1开始一直到an-1(n-1是下标)，内层循环从i+1开始一直到an，然后设置一个sum用于接收他们的和，如此一来就完成了求和，下面是完整代码：
代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int num = scanner.nextInt();
int[] arr = new int[num];
int i = 0;
while (num > 0) {
arr[i] = scanner.nextInt();
num--;
i++;
}
int sum = 0;
for (int n = 0; n < arr.length - 1; n++) {
for (int m = n + 1; m < arr.length; m++) {
sum = sum + arr[n] * arr[m];
}
}
System.out.println(sum);
}
}
这个方法很容易想到，但是我们发现了此方法的时间复杂度是O(n)，因此时间复杂度很大，如果用这个代码去提交我们就会发现并不能完全通过，因此需要找更简便的方法。
解题思路二
原题是：
提取公因式，我们可以化简为：
现在，我们要使用一种叫“前缀和”的方法，定义一个数组b，令bi=a1+a2+⋯+aj，很容易发现：
因此上述化简后的计算就可以化简为：
根据这个公式我们就能够完成求和，首先，我们创建另一个数组用于存储b，用一个for循环完成求和，下面是完整代码：
代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int num = scanner.nextInt();
long[] arr1 = new long[num];
long[] arr2 = new long[num];
int i = 0;
while (num > 0) {
arr1[i] = scanner.nextInt();
num--;
i++;
}
for (i = 0; i < arr2.length; i++) {
if (i == 0) {
arr2[i] = arr1[i];
} else {
arr2[i] = arr2[i - 1] + arr1[i];
}
}
long sum = 0L;
for (i = 0; i < arr1.length; i++) {
sum = sum +arr1[i] * (arr2[arr2.length-1] - arr2[i]);
}
System.out.println(sum);
}
}
题目二
题干
给定一个 8 位数的日期，请你计算该日期之后下一个回文日期和下一个ABABBABA型的回文日期各是哪一天。
示例一：
输入：
20200202
输出：
20211202
21211212
题目链接：回文日期
解题思路
这道题其实不难，只是考虑的东西很多，考察的就是看问题的严谨程度，首先我们要保证这个数的日期要是一个合法的日期，什么意思？月只能是1到12，而日的合法性更多，日根据月来定，比如一月是31天，四月是30天，并且还要判断闰年，因为闰年2月才是29天。因此我们可以创建一个函数判断日期是否合法。那么整体的思路就可以是，从输入的数字后一位开始逐一遍历，首先判断这个日期是否合法，如果日期合法再通过双指针判断是否是回文日期，如果是回文日期了，在判断该日期是否是ABABBABA型的回文日期。下面是完整代码：
代码
import java.util.Scanner;
public class Main {
public static boolean check_data(int data) {
int[] months = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int year = data / 10000; //年
int month = data % 10000 / 100; //月
int day = data % 100; //日
if (day == 0 || month <= 0 || month > 12) {
return false;
}
if (month != 2 && day > months[month]) {
return false;
}
if (month == 2) {//月份是2
if ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0)) if (day > 29) return false;//是闰月， day必须<=29
else if (day > 28) return false;//是平月，day必须<=28
}
return true;
}
public static boolean check_huiwen(String s) {
char[] arr = s.toCharArray();
int len = s.length();
for (int i = 0, j = len - 1; i < j; i++, j--)//i从前往后，j从后往前扫一遍
if (arr[i] != arr[j]) {
return false;//不对称，就不回文
}
return true;
}
public static boolean check_ABAB(String s) {
char[] arr = s.toCharArray();
if (check_huiwen(s)) {
return arr[0] == arr[2] && arr[1] == arr[3] && arr[0] != arr[1];
}
return false;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int num = scanner.nextInt();
boolean flag = false;
for (int i = num + 1; i <= 99999999; i++) {//枚举回文数
if (check_data(i)) {
String s = String.valueOf(i);
if (check_huiwen(s) && !flag) {
System.out.println(i);
flag = true;
}
if (check_ABAB(s)) {
System.out.println(i);
break;
}
}
}
}
}
check_data函数用于判断日期是否是合法日期，其中有一个值得注意的地方是，我是用数组来存储每个月份应该有的天数，这个也方便了我们用于if判断。check_huiwen函数是用于判断日期是否是回文日期，我用了前后两个指针进行比较i往前，j往后。check_ABAB函数是用于判断日期是否是ABABBABA的日期，我们知道如果是ABABBABA那么一定是回文，因此我们只需要判断第一个数跟第三个数是否一样，并且第二个数跟第四个数是否一样，并且第一个数跟第二个数不能一样（因为第一个数跟第二个数一样了，就变成了AAAAAAAA），有细心的同学会问哪个flag的目的是什么？我们知道题目要求打印第一个回文日期，那么我们设置一个flag，如果找到了我们就把flag致为true，而ABABBABA找到了之后直接跳出循环就可以了，问题解决。如果有什么问题或者想说的欢迎私信和评论，谢谢各位的点赞收藏。
