⭐️前面的话⭐️

本篇文章介绍来自牛客试题广场的两道题题解，分别为【计算日期到天数转换】和【幸运的袋子】，展示语言java。

📒博客主页：未见花闻的博客主页
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
📌本文由未见花闻原创！
📆首发时间：🌴2022年8月31日🌴
✉️坚持和努力一定能换来诗与远方！
💭参考书籍：📚《算法》，📚《算法导论》
💬参考在线编程网站：🌐牛客网🌐力扣
博主的码云gitee，平常博主写的程序代码都在里面。
博主的github，平常博主写的程序代码都在里面。
🍭作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！

⭐️计算日期到天数转换⭐️

🔐题目详情

根据输入的日期，计算是这一年的第几天。

保证年份为4位数且日期合法。

进阶：时间复杂度：O(n) ，空间复杂度：O(1)

输入描述：

输入一行，每行空格分割，分别是年，月，日

输出描述：

输出是这一年的第几天

示例1

输入：

2012 12 31

输出：

366

示例2

输入：

1982 3 4

输出：

63

题目链接：计算日期到天数转换

💡解题思路

基本思路： 模拟

解题思路：
我们知道年分为闰年与平年，闰年相比于平年，闰年的二月比平年多一天，我们需要计算的是某年某月某日在当年是第几天，其实只需要将在此日当月的天数与当年历月所有天数相加即可。

由于闰年的存在，二月的天数可能是28天也可能是29天，所以我们需要判断当年是否是闰年，如果是闰年二月计算29天，不是闰年计算28天即可。

其他月份的天数我们也很清楚，不想在程序中做太多的判断我们可以对十二个月的天数打个表，事先使用数组存起来。

比如，2022年的7月26日，设它在2022年第x天，则x为前6个月的天数加上7月的26天，2022年是平年，所以二月计算28天，因此使用算式表示x=31+28+31+30+31+30+26=207。

🔑源代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int year = sc.nextInt();
        int month = sc.nextInt();
        int day = sc.nextInt();
        
        //打个普通年的月表
        int[] months = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
        int ans = 0;
        if (isLeap(year)) {
            months[1] = 29;
        } else {
            months[1] = 28;
        }
        for (int i = 1; i < month && i <= 12; i++) {
            ans += months[i-1];
        }
        ans += day;
        
        System.out.println(ans);
    }
    
    //判断闰年
    private static boolean isLeap(int y) {
        return (y % 4 == 0 && y % 100 != 0) || y % 400 == 0;
    }
}

🌱总结

本题为简单模拟计数题，只要会判断闰年和知道每年每月有多少天就很容易求解此题。

⭐️幸运的袋子⭐️

🔐题目详情

一个袋子里面有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

题目链接：幸运的袋子

💡解题思路

基本思路： 深度优先搜索

解题思路：

这道题本质上就是要我们求袋子里面数字集合的子集，并且选出满足题目“幸运”条件的子集，那没办法，最简单的想法就是把所有的子集都求出来，那么我们就需要使用搜索。

那要如何进行搜索呢？这里不好说，我就画图吧，看完图你就知道要如何搜索了，其实就是深度优先搜索搜索,，看图之前，先说说搜索思路，毕竟我们要的是幸运袋，需要筛选。

但你先要知道，每向下搜索一次，就会多搭配一个数，横向搜索一次，表示替换上一次搜索的那个数。

第一步，对数组进行排序。
第二步，搜索过程中，同步计算和sum与积mul，如果不满足幸运袋条件，由于数组是非递减排序的，所以后面的数搭配更加不可能满足幸运袋，那就停止继续向下搜索，其实横向也是如此，当然有一个特例，我们另说。
第三步，对于第二步说的情况有一个特例，就是当搜索到的数arr[i]=1时，由于数组非递减并且1与任何正整数搭配都是满足幸运袋的，就单独一个1时是不满足的，但是只需要加上任意一个正整数，都可以满足，因此要在第二步的基础上剔除这种情况。
第四步，注意题目中说每个相同数字的球是没有区别的，因此横向搜索时，如果下一个数与当前的数相同，需要跳过，不然会重复计算。
第五步，向下搜索完，回溯到上一层横向搜索时，需取去除前一个横向元素带来的权重，向下方向的权重，由于是使用递归进行向下方向的搜索，搜索完回溯后，权重自然就没有了，毕竟栈帧销毁了，里面的临时变量也随之销毁了。

假设袋子里面有球1 3 2 6 8 4 1 9，搜索图如下：

我们就是按照上述的搜索思路，来枚举所有的情况，并判断是否满足幸运袋，如果满足则计数，不满足则停止搜索。

🔑源代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        Arrays.sort(arr);
        int ans = dfs(arr, 0, 0, 1);
        System.out.println(ans);
    }
    private static int dfs(int[] arr, int pos, int sum, int mul) {
        int n = arr.length;
        int cnt = 0;
        for (int i = pos; i < n; i++) {
            sum += arr[i];
            mul *= arr[i];
            
            if (sum > mul) {
                //情况1：满足幸运袋，则继续往后搜索
                cnt += dfs(arr, i + 1, sum, mul) + 1;
            } else if (arr[i] == 1) {
                //情况2：当值为1时，虽然此时不满足幸运袋，但再搭配一个数就能满足幸运袋
                cnt += dfs(arr, i + 1, sum, mul);
            } else {
                //其他情况不满足幸运袋，由于数组是升序的，那与后面的数搭配也不可能满足
                break;
            }
            //取出arr[i]带来的权重
            sum -= arr[i];
            mul /= arr[i];
            //相同号码无区别，因此下一次还是相同的数就跳过
            while (i < n - 1 && arr[i+1] == arr[i]) {
                i++;
            }
        }
        return cnt;
    }
}

🌱总结

本题为搜索运用题，需要使用搜索的方式枚举所有的情况，来计算满足题意的组合数目，其实本质上就是求一个集合的子集。