🎽7.金额差错
某财务部门结账时发现总金额不对头。很可能是从明细上漏掉了某 1 笔或几笔。如果已知明细账目清单，能通过编程找到漏掉的是哪 1 笔或几笔吗？
如果有多种可能，则输出所有可能的情况。
题目链接：金额查错https://www.lanqiao.cn/problems/291/learning/
经典的组合问题，我们先要计算出差了多少金额target，然后从所有的子序列中找出和为target的所有组合。难点在于去重，因为这题是不允许出现一模一样的组合（虽然题目没说，但从它给的例子是可以看出来的）。像这样题目有Set去重和排序去重两种方法，效率更好的方法是排序去重，因为排序可以减枝。这道题力扣也有类似原题，我会附上地址
力扣类似题： 组合总和||https://leetcode-cn.com/problems/combination-sum-ii/comments/
代码转换：
import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.Scanner; public class Main { static List<Integer> path=new ArrayList(); public static void main(String[] args) { Scanner sc=new Scanner(System.in); //错误的金额 int count=sc.nextInt(); int n=sc.nextInt(); int[] arr=new int[n]; //计算正确的金额 int ans=0; for(int i=0;i<n;++i) { arr[i]=sc.nextInt(); ans+=arr[i]; } int target=ans-count; Arrays.sort(arr); dfs(arr,target,0); } static void dfs(int[] arr,int target,int start) { //剪枝 if(target<0) return; if(target==0) { for(int a:path) { System.out.print(a+" "); } System.out.println(); return; } for(int i=start;i<arr.length;i++) { //去重核心代码 if(i>start&&arr[i]==arr[i-1]) continue; path.add(arr[i]); dfs(arr,target-arr[i],i+1); path.remove(path.size()-1); } } }
🍰 8.四平方和
四平方和定理，又称为拉格朗日定理：
每个正整数都可以表示为至多 44 个正整数的平方和。
如果把 00 包括进去，就正好可以表示为 44 个数的平方和。
比如：
5=0^2+0^2+1^2+2^2
7=1^2+1^2+1^2+2^2
对于一个给定的正整数，可能存在多种平方和的表示法。
要求你对 4 个数排序：
0≤a≤b≤c≤d
并对所有的可能表示法按 a,b,c,d为联合主键升序排列，最后输出第一个表示法。
题目链接：四平方和http://lx.lanqiao.cn/problem.page?gpid=T2766
这道题目是往年一道非常非常经典的题目，在ABC组它都出现了。它有二分和哈希两种做法，哈希的做法更易于理解，所以我在这讲解哈希的做法。
首先这里出现了4个数字a，b，c，d。我们能去通过循环去模拟四位数的情况吗？当然不行，这样的时间复杂度为O(n^3)，当然因为这是大题，实习想不到方法这样写也是可以过一些案例得一些分数。考虑到这种情况，我们应该就这个字母分为两组，ab为一组，cd为一组，这样分别枚举的话时间复杂度可以降到O(n^2)。先将某一组的所有的组合情况枚举放到Map集合中，然后枚举另外一对组合的情况，每次判断Map中是否有值让两者相加等于我们的N。
这时有一个问题——我们是把ab组合的值放入到map还是cd？
答案是CD。因为题目要求的输出方式是升序且保证a≤b≤c≤d，我们要尽可能让a和b小。所以我们把cd组合的值放到Map中，去从小到大枚举ab，只要找到Map存在符合的值，此时就是我们的答案。
因为Map中的key是c^2+d^2的值，Value需要同时能记录c和d，所以我们需要一个Node节点能同时记录c和d的值。这样枚举到符合的情况时，我们可以同时取出c和d。
代码转换：
import java.util.HashMap; import java.util.Map; import java.util.Scanner; public class Main { static Map<Integer,Node> map=new HashMap<>(); public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); //注意abcd枚举时的判断条件 for(int c=0;c*c<=n;++c) { for(int d=c;d*d+c*c<=n;d++) { int t=c*c+d*d; if(!map.containsKey(t)) { map.put(t, new Node(c,d)); } } } for(int a=0;a*a<=n;++a) { for(int b=a;a*a+b*b<=n;++b) { int ans=n-a*a-b*b; if(map.containsKey(ans)) { System.out.println(a+" "+b+" "+map.get(ans).c+" "+map.get(ans).d); return; } } } } } //同时存入c和d class Node{ int c,d; public Node(int c,int d) { this.c=c; this.d=d; } }
🚀9.刷题总结
这次出的大题难度还是不算高，甚至很多都是模板题，大家如果能在掌握填空题的基础上，掌握好这些基础的大题，进国赛的可能性是非常非常大的。希望大家能够持之以恒，对于题目有任何的疑问，都可以在评论区提出一起交流。
