蓝桥杯刷题——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) {//月份是2if ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0)) if (day > 29) return false;//是闰月， day必须<=29else 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找到了之后直接跳出循环就可以了，问题解决。如果有什么问题或者想说的欢迎私信和评论，谢谢各位的点赞收藏。