一.计算日期到天数转换

题目链接：

计算日期到天数转换

题目描述：

根据输入的日期，计算是这一年的第几天。
保证年份为4位数且日期合法。
进阶：时间复杂度：O(n) ，空间复杂度：O(1)

输入描述：

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

输出描述：

输出是这一年的第几天

示例1：

输入：
2012 12 31
输出：
366

示例2：

输入：
1982 3 4
输出：
63

个人总结：

代码有注释，该题较简单，应该可以直接看懂。

代码实现：

import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int yy = sc.nextInt();int mm = sc.nextInt();int dd = sc.nextInt();int[] sum = {0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365};//先不当成闰年int res = sum[mm - 1] + dd;//只有是闰年且大于二月份才多加一个1if (mm > 2 && isLeapYear(yy)) {res += 1;}System.out.println(res);}public static boolean isLeapYear(int yy) {if (yy % 4 == 0 && yy % 100 != 0 || yy % 400 == 0) {return true;}return false;}
}

二.幸运的袋子

题目链接：

幸运的袋子

题目描述：

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

个人总结：

回溯 + 剪枝

代码实现：

import java.util.*;public class Main {static int cnt = 0;public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int[] nums = new int[n];for (int i = 0; i < n; i++) {nums[i] = sc.nextInt();}Arrays.sort(nums);dfs(nums, 0, 1, 0);System.out.println(cnt);}public static void dfs(int[] nums, int idx, int mul, int sum) {if (idx == nums.length) {return;}for (int i = idx; i < nums.length; i++) {//去重if (i > idx && nums[i] == nums[i - 1]) {continue;}mul *= nums[i];sum += nums[i];//如果sum > mulif (sum > mul) {cnt++;dfs(nums, i + 1, mul, sum);//如果不符合要求但是nums[i] == 1则继续向下搜索//因为1可以使sum增大而mul不变 所有还有可能达到sum > mul} else if (nums[i] == 1) {dfs(nums, i + 1, mul, sum);//上述条件均不满足 则后面没有满足条件的组合了} else {break;}mul /= nums[i];sum -= nums[i];}}
}