【Java版oj】day14计算日期到天数转换、幸运的袋子

左手的ㄟ右手 2024-03-25 22:08 32阅读 0赞

**目录**

一、计算日期到天数转换

（1）原题再现

（2）问题分析

（3）完整代码

二、幸运的袋子

（1）原题再现

（2）问题分析

（3）完整代码

--------------------

> ## 一、计算日期到天数转换 ##
> 
> ### （1）原题再现 ###
> 
> [计算日期到天数转换\_牛客题霸\_牛客网][Link 1]
> 
> **描述**
> 
> 根据输入的日期，计算是这一年的第几天。
> 
> 保证年份为4位数且日期合法。
> 
> 进阶：时间复杂度：O(n)\\O(n) ，空间复杂度：O(1)\\O(1)
> 
> **输入描述：**
> 
> 输入一行，每行空格分割，分别是年，月，日
> 
> **输出描述：**
> 
> 输出是这一年的第几天
> 
> **示例1**
> 
> 输入：
> 
> 2012 12 3
> 
> 输出：
> 
> 366
> 
> **示例2**
> 
> 输入：
> 
> 1982 3 4
> 
> 输出：
> 
> 63
> 
> ### （2）问题分析 ###
> 
> 这道题很简单。首先需要定义一个判断是否为闰年的函数，闰年是能整除400或者能够整除4却不能整除100的数。其次闰年的二月是29天。
> 
> 这题有个关键的是划分输入的一串字符，将它划分成年月日，然后将String类型转换成Int类型。首先我们不能用String类的subString方法，因为月份的下标是不确定的，如果是两位数，下标就是（5,7）（左闭右开），如果是一位数就变成了（5,6），所以我们使用**快慢指针法**，当快指针指向空格时，我们记录从慢指针到快指针的一个字符串。将String类型转换成Int类型，我们可以使用**Integer.praseInt(str)**方法或者**Integer.valueOf(str)**方法
> 
> ### （3）完整代码 ###
> 
>     import java.util.*;
>     
>     public class Main {
>         public static void main(String[] args) {
>             Scanner sc = new Scanner(System.in);
>             String date = sc.nextLine();
>             int slow = 0;
>             int fast = 1;
>             String []str = date.split(" ", 3);
>             String year = str[0];
>             String month = str[1];
>             String day = str[2];
>             int ans = count(year, month, day);
>             System.out.println(ans);
>         }
>         public static boolean isLeapYear(String year) {
>             int year1 = Integer.parseInt(year);
>             return year1 % 400 == 0 || (year1 % 4 == 0 && year1 % 100 != 0);
>         }
>         public static int chooseMonth(String year, int month) {
>             int m = 0;
>             switch (month) {
>                 case 1:
>                 case 3:
>                 case 5:
>                 case 7:
>                 case 8:
>                 case 10:
>                 case 12:
>                     m = 31;
>                     break;
>                 case 2:
>                     if (isLeapYear(year)) {
>                         m = 29;
>                     } else {
>                         m = 28;
>                     }
>                     break;
>                 default:
>                     m = 30;
>             }
>             return m;
>         }
>         public static int count(String year, String month, String day) {
>             int year1 = Integer.parseInt(year);
>             int month1 = Integer.parseInt(month);
>             int day1 = Integer.parseInt(day);
>             int sum = 0;
>             if (month1 == 1) {
>                 return day1;
>             } else {
>                 for (int i = 1; i < month1; i++) {
>                     sum += chooseMonth(year, i);
>                 }
>                 sum += day1;
>                 return sum;
>             }
>         }
>     }
> 
> ![b08db313714c4700ae18837e59fdd4c9.png][]

> ## 二、幸运的袋子 ##
> 
> ### （1）原题再现 ###
> 
> [幸运的袋子\_\_牛客网][Link 2]
> 
> 一个袋子里面有n个球，每个球上面都有一个号码(拥有相同号码的球是无区别的)。如果一个袋子是幸运的当且仅当所有球的号码的和大于所有球的号码的积。  
> 例如：如果袋子里面的球的号码是\{1, 1, 2, 3\}，这个袋子就是幸运的，因为1 + 1 + 2 + 3 > 1 \* 1 \* 2 \* 3  
> 你可以适当从袋子里移除一些球(可以移除0个,但是别移除完)，要使移除后的袋子是幸运的。现在让你编程计算一下你可以获得的多少种不同的幸运的袋子。
> 
> **输入描述:**
> 
> 第一行输入一个正整数n(n ≤ 1000)
> 
> 第二行为n个数正整数xi(xi ≤ 1000)
> 
> **输出描述:**
> 
> 输出可以产生的幸运的袋子数
> 
> **示例1**
> 
> 输入
> 
> 3
> 
> 1 1 1
> 
> 输出
> 
> 2
> 
> ### （2）问题分析 ###
> 
> 这道题是有点难度的。需要用到**数论+DFS深度优先搜索+搜索剪枝+回溯**等方法。
> 
>  **数论**：**对于任意两个正整数x,y，如果要满足x+y>x\*y，则必须有一个数为1。**
> 
> 证明：
> 
> ![c0078c5c3ba34c419e59770cabdb07cc.png][]推广到任意i个正整数**，序列中必须有1**才可能满足+>\*的可能，否则必然不是这样的幸运袋子
> 
> 所以我们可以现将序列**按照升序排序**，然后分两种情况：一种是序列中没有1的情况，直接打印0，另一种是序列中有1的情况，使用DFS算法计算。
> 
>  **搜索剪枝**：如果不进行剪枝，那么使用DFS遍历搜索会超出时间限制。剪枝的依据：如果选择一个数num能使add+num>mul\*num，即满足题目要求，就继续往下搜索；如果add+num<=mul\*num，即不满足题目要求，因为序列是按照升序排序的，所以也不需要往后继续添加num了，必然不符合题目要求，这时我们就可以进行**剪枝**，跳出这一次的循环。根据题目要求，编号一样的球没有任何区别，所以我们还要进行**去重操作**，比对这一位置和下一位置是否相同，相同就直接跳过这个位置的处理即可。
> 
>  **回溯**：一组情况处理完毕了，我们需要将其结果删去，在进行下一组操作。比如，序列\[1,1,2,3,4\]当我们选择1,1,2,3,4时，不满足幸运袋子的要求，我们回退上一层选择的1,1,2,3，这组序列满足题目要求，此时假定位置3的情况已经全部列完了，我们就需要删除位置3的数即add(1+1+2+3-3)，mul(1\*1\*2\*3/3)，然后添加位置4看看是否符合题意,add（1+1+2+4），mul(1\*1\*2\*4)。
> 
> ![a5fadf4d0f0f4552bc92bf5df5489b44.png][]
> 
> ### （3）完整代码 ###
> 
>     import java.util.*;
>     
>     public class Main {
>         public static void main(String[] args) {
>             Scanner sc = new Scanner(System.in);
>             int n = sc.nextInt();
>             int []num = new int[n];
>             for (int i = 0; i < n; i++) {
>                 num[i] = sc.nextInt();
>             }
>             Arrays.sort(num);
>             if(num[0]==1){
>                 int ans = DFS(num, n, 1, 1, 1);
>                 System.out.println(ans);
>             }else{
>                 System.out.println(0);
>             }
>         }
>         public static int DFS(int []num, int n, int index, int add, int mul) {
>             int count = 0;
>             for (int i = index; i < n; i++) {
>                 add += num[i];
>                 mul *= num[i];
>                 if (add > mul) {
>                     count += 1 + DFS(num, n, i + 1, add, mul);
>                 }else {
>                     break;
>                 }
>                 add -= num[i];
>                 mul /= num[i];
>                 while (i < n - 1 && num[i] == num[i + 1]) {
>                     i++;
>                 }
>             }
>             return count;
>         }
>     }
> 
> ![a92a2f52ee8c4c1aa2099bbe5ce72261.png][]

--------------------

![0a502defb9724058b9ad4c0a24b22aaa.png][]

[Link 1]: https://www.nowcoder.com/practice/769d45d455fe40b385ba32f97e7bcded?tpId=37&&tqId=21296&rp=1&ru=/ta/huawei&qru=/ta/huawei/question-ranking
[b08db313714c4700ae18837e59fdd4c9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/07bed6ebe950434090f1117756c8cf99.png
[Link 2]: https://www.nowcoder.com/questionTerminal/a5190a7c3ec045ce9273beebdfe029ee?
[c0078c5c3ba34c419e59770cabdb07cc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/c9f8f6d294df48888f749ae99883c68b.png
[a5fadf4d0f0f4552bc92bf5df5489b44.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/69ec3ebeb5bb47e086ed0e9a11d87c7b.png
[a92a2f52ee8c4c1aa2099bbe5ce72261.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/b2db7e21af214ea5b5d638442ad66d7e.png
[0a502defb9724058b9ad4c0a24b22aaa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/e7ea73b64c5c400f89a317e81f27ba8d.png