参考：https://blog.csdn.net/qq_33241802/article/details/107884289
1. 素数的个数：给出一个包含n个正整数的数组a，把a[i]拆分为若干个和为a[i]的素数，求拆分后最多能有多少个素数。
第一行数据为n，表示数组长度，第二行为n个元素。 输入 3 1 1 1 输出 0 1 不可拆分 输入 1 3 5 7 6 1为0个，3为1个，5为（2,3），7为（2,2,3）
根据规律可得：nums[i]/2就是该元素可以分出的素数个数
import java.util.Scanner;
class Solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int len = sc.nextInt();
int[] nums = new int[len];
long result = 0;
for (int i = 0; i < nums.length; i++) {
nums[i] = sc.nextInt();
//规律：nums[i]/2就是nums[i]可以分出的素数个数
result += nums[i] / 2;
}
System.out.println(result);
}
}2. 字典序最小的排列：给出一个长度为m的序列T，求一个长度为n且字典序最小的排列S，要求不改变原序列中元素的相对位置。
第一行输入两个正整数n和m 第二行输入m个数，表示序列 5 3 2 1 5 输出 2 1 3 4 5
合并数组 + 双指针。先通过HashSet取出缺失的元素，组成nums2数组。需要result数组的注意第一个元素，nums1和nums2的第一个元素，谁小，先存谁。
import java.util.HashSet;
import java.util.Scanner;
public class Solution{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int len = sc.nextInt();
int len1 = sc.nextInt();
int[] nums1 = new int[len1];
HashSet<Integer> set = new HashSet<>();
for(int i=0;i<nums1.length;i++){
nums1[i] = sc.nextInt();
set.add(nums1[i]);
}
//nums2，长度为len-len1，存放互补的元素
int[] nums2 = new int[len-len1];
int index = 0;
for(int i=1;i<=len;i++){
if(!set.contains(i)){
nums2[index++] = i;
}
}
/*双指针判断
i指针用于控制nums1移动
j指针用于控制nums2移动
*/
int i = 0;
int j = 0;
int[] result = new int[len];
int Resultindex = 0;
//谁的第一个小谁就先存
if(nums1[0] < nums2[0]){
result[Resultindex++] = nums1[0];
i=1;
}else{
result[Resultindex++] = nums2[0];
j=1;
}
while(i < nums1.length && j < nums2.length){
//谁小存谁
if(nums1[i] < nums2[j]){
result[Resultindex++] = nums1[i++];
}else{
result[Resultindex++] = nums2[j++];
}
}
//补充存入最后一个数
while(i == nums1.length && j < nums2.length){
//如果nums1完但nums2未完，存入nums2
result[Resultindex++] = nums2[j++];
}
while(i < nums1.length && j == nums2.length){
//如果nums2完但nums1未完，存入nums1
result[Resultindex++] = nums1[i++];
}
for(int k=0;k<result.length-1;k++){
System.out.print(result[k] + " ");
}
System.out.print(result[result.length-1]);
}
}3. 丢弃最少物品：给出n个物品，每个物品都有自己的价值，每个物品只有一件，这些物品需要分给两个人，要求分配完之后，两个人的物品价值相同。分配完成之后，会丢弃剩下的物品，求最少要丢弃多少物品。
输入 输入第一行为总的测试数据个数，第二行为物品个数n，第三行为n个物品的价值。 1 5 30 60 5 15 30 输出 20 丢弃5和15，把60分配给第一个人，2个30分配给第二个人。
根据大佬的思路：dfs回溯 + 分与不分，实在是没想到dfs还有这种用法，之前只会用dfs计算组合，这次算是学到了。
import java.util.Scanner;
public class Solution{
public static int result = Integer.MAX_VALUE;
public static int sum = 0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int group = sc.nextInt();
//以后多组读入可以采用这种方式,学到了
while(group-- > 0){
int len = sc.nextInt();
int[] nums = new int[len];
for(int i=0;i<nums.length;i++){
nums[i] = sc.nextInt();
sum += nums[i];
}
//index从0开始，第一个人拥有的为result1，第二个人用于的为result2。都初始为0
dfs(nums,0,0,0);
System.out.println(result);
}
}
private static void dfs(int[] nums, int index, int result1, int result2) {
//递归出口
if(index == nums.length){
//当result1 == result2时
if(result1 == result2){
result = Math.min(result,sum - 2*result1);
}
return;
}
//分为3中情况，
/*
1. 谁都不给
2. 给第一个：result1 + nums[index]
3. 给第二个：result2 + nums[index]
*/
dfs(nums,index+1,result1,result2);
dfs(nums,index+1,result1+nums[index],result2);
dfs(nums,index+1,result1,result2+nums[index]);
}
}
京公网安备 11010502036488号