<span>蓝桥杯训练6</span>

分解单位数

形如：1/a 的分数称为单位分数。

可以把1分解为若干个互不相同的单位分数之和。
例如：
1 = 1/2 + 1/3 + 1/9 + 1/18
1 = 1/2 + 1/3 + 1/10 + 1/15
1 = 1/3 + 1/5 + 1/7 + 1/9 + 1/11 + 1/15 + 1/35 + 1/45 + 1/231
等等，类似这样的分解无穷无尽。

我们增加一个约束条件：最大的分母必须不超过30

请你求出分解为n项时的所有不同分解法。

数据格式要求：

输入一个整数n，表示要分解为n项（n<12）

#include<stdio.h>
#include<stdlib.h>
void dwfs(int a[], int n, int qishi, int ctrl) {
    int i;
    if(n == ctrl) {
        int sum = 1, sum2 = 0;
        for(i = 0; i < n; i++)
        sum *= a[i];
        for(i = 0; i < n; i++)
        sum2 += sum/a[i];
        if(sum == sum2) {
            for(i = 0; i < n; i++)
            printf("1/%d ", a[i]);
            printf("\n");
        }
        return;
    }
    for(i = qishi; i < 30; i++) {
           a[ctrl] = i;
           dwfs(a, n, i+1, ctrl+1);
       }
}
int main() {
    int i, n, *pa;
    scanf("%d", &n);
    pa = (int*)calloc(n, sizeof(int));
    dwfs(pa, n, 2, 0);
    return 0;
}

//递归全排列1~30之间的四各组合的分母，计算他们的倒数和是否为1，是，则输出
import java.util.Scanner;

public class Main {
	static int n;//要分解为n项（n<12）
	
	public static void main(String[] args) {
		@SuppressWarnings("resource")
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		int[] num=new int[n];
		cmp(0,num,2);//调用方法
	}
	//自定义方法
	private static void cmp(int fm, int[] num, int sum) {
	//fm=记录项数量,num=保存项(遍历得到分母),sum=每次递归遍历起始分母
		if(fm==n) {//满足项数量
			int z=1;//分子
			int m=num[0];//分母
			for(int i=1;i<n;i++) {
				//验证求和(分母全部相乘，求分子是否=分母)即，和为1
				z=z*num[i]+m;//分子和
				m=m*num[i];//分母和
			}
			if(z==m) {//和为1
				for(int i=0;i<n;i++) {
					System.out.print("1/"+num[i]+" ");
				}
				System.out.printf("\n");
			}
			return;
		}
		for(int i=sum;i<30;i++) {//递归全排列1~30
			num[fm]=i;//遍历得到分母存入数组
			cmp(fm+1,num,i+1);
		}
	}
}

G将军有一支训练有素的军队，这个军队除开G将军外，每名士兵都有一个直接上级（可能是其他士兵，也可能是G将军）。现在G将军将接受一个特别的任务，需要派遣一部分士兵（至少一个）组成一个敢死队，为了增加敢死队队员的独立性，要求如果一名士兵在敢死队中，他的直接上级不能在敢死队中。
请问，G将军有多少种派出敢死队的方法。注意，G将军也可以作为一个士兵进入敢死队。
输入格式
输入的第一行包含一个整数n，表示包括G将军在内的军队的人数。军队的士兵从1至n编号，G将军编号为1。
接下来n-1个数，分别表示编号为2, 3, …, n的士兵的直接上级编号，编号i的士兵的直接上级的编号小于i。
输出格式
输出一个整数，表示派出敢死队的方案数。由于数目可能很大，你只需要输出这个数除10007的余数即可。
样例输入1
3
1 1
样例输出1
4
样例说明
这四种方式分别是：

1. 选1；
2. 选2；
3. 选3；
4. 选2, 3。

样例输入2
7
1 1 2 2 3 3
样例输出2
40

#include<stdio.h>
#include<string.h>
int a[100001], b[100001],n, t;
int str(int i) {
    if(i > n){//假如已经将n名士兵遍历一遍，就加一
        t++;
        return t;
    }
    if(a[b[i]] == 0){//假如第i名士兵的直接上级已经出列
        str(i+1); //那么这名士兵就不能出列，直接跳到下一位
    }else{//假如第i名士兵的直接上级没有出列
        a[i] = 0; //让他出列并跳到下一位
        str(i+1);
        a[i] = i; //不让他出列并跳到下一位
        str(i+1);
    }
}
int main() {
    int i;
    while(scanf("%d", &n) != EOF){
        t = 0;
        a[0] = 1;
        for(i = 1; i <= n; i++){
            a[i] = i; //储存当前状态，如果已经出列就置为0
        }
        b[1] = 0;
        for(i = 2; i <= n; i++){
            scanf("%d", &b[i]); //记录第i号士兵的直接上级
        }
        printf("%d\n", (str(1)-1)%10007); //因为要排除没有人去的情况，所以要减一
        //G将军本人去和不去的2种情况下的方案和，去掉“G将军和它的下属全都不去”这种非法情况，再按题目要求模10007.
    }
    return 0;
}

15. 三数之和

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

#include <stdio.h>
typedef int bool;//自定义bool
#define false 0
#define true 1
void cmp(int a[],int n){
    int i,j,tmp;
    bool flag;
    for(i=1;i<n;i++){
        flag=false;
        for(j=0;j<n-1;j++){
            if(a[j]>a[j+1]){
                tmp=a[j];
                a[j]=a[j+1];
                a[j+1]=tmp;
                flag=true;
            }
        }
        if(!flag){
            break;
        }
    }
}
int main()
{
    int n,i,j,k;
    scanf("%d",&n);
    int nums[n];
    for(i=0;i<n;i++){
        scanf("%d",&nums[i]);
    }
    cmp(nums,n);
    for(i=0;i<n;i++){
        printf("%d ",nums[i]);
    }
    printf("\n");
    for(i=0;i<n;i++){
        if(nums[i]==nums[i-1]){// 该处为关键点（去重）：判断当前的数是否与前一个相等.
            continue;// 若相等则说明从该数开始的所有可能性已经输出，则跳过该数
        }else{
            for(j=i+1;j<n;j++){
                for(k=j+1;k<n;k++){
                    if(nums[i]+nums[j]+nums[k]==0)
                        printf("%d,%d,%d ",nums[i],nums[j],nums[k]);
                }
            }
        }
    }
    return 0;
}

AC的C

int comp(const void *a,const void *b)
{
    return *(int *)a - *(int *)b;
}

int** threeSum(int* nums, int shu02, int* shu03, int** shu04){
    *shu03 = 0;
    if (shu02 == 0) {
        return 0;
    }
    int **ret = (int **)malloc(sizeof(int *) * (shu02 + 1) * 6);
    *shu03 = 0;
    short left = 0;
    short right = shu02 - 1;;
    int target = 0;
    
    *shu04 = malloc(sizeof(int) * (shu02 + 1) * 6);
    qsort(nums, shu02, sizeof(int), comp);
    ret[*shu03] = malloc(sizeof(int) * 3);

    while (left + 1 < right) {
        int i = left + 1;
        int j = right;
        target = 0 - nums[left];
        while (i < j) {
            if (nums[i] + nums[j] < target) {
                i++;
            } else if (nums[i] + nums[j] > target) {
                j--;
            } else {
                ret[*shu03][0] = nums[left];
                ret[*shu03][1] = nums[i];
                ret[*shu03][2] = nums[j];
                (*shu04)[*shu03] = 3;
                (*shu03)++;
                ret[*shu03] = malloc(sizeof(int) * 3);

                while(nums[i] == nums[++i] && i < j) {}
                while(nums[j] == nums[--j] && i < j) {}
            }
        }
        while(nums[left] == nums[++left] && left + 1 < right) {}
    }
    return ret;
}

java

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>();
        int len = nums.length;
        if(len < 3 || nums == null) return lists;
        //先对数组进行排序
        Arrays.sort(nums);
        for(int i = 0;i<nums.length;i++){
            //如果当前数字大于0，则不可能存在等于0的情况了
            if( nums[i] > 0) break;
            //去除重复 注：：可借鉴这个写法
            if(i>0 && nums[i] == nums[i-1]) continue;
            //左指针
            int l = i+1;
            //右指针
            int r = len - 1;
            while(l < r){
                int sum = nums[i] + nums[l] + nums[r];
                if(sum == 0){
                    lists.add(Arrays.asList(nums[i],nums[l],nums[r]));
                    //前后去重
                    while(l<r && nums[l] == nums[l+1]) l++;
                    while(l<r && nums[r] == nums[r-1]) r--;
                    l++;
                    r--;
                }
                //如果数小于0 ，证明前面的数太小
                else if(sum < 0) l++;
                //如果数大于1，证明后面的数太大
                else if(sum > 0) r--;
            }
        }
        return lists;
    }
}

python

''' 特判，对于数组长度 nn，如果数组为 nullnull 或者数组长度小于 33，返回 [][]。 对数组进行排序。 遍历排序后数组： 若 nums[i]>0nums[i]>0：因为已经排序好，所以后面不可能有三个数加和等于 00，直接返回结果。 对于重复元素：跳过，避免出现重复解 令左指针 L=i+1L=i+1，右指针 R=n-1R=n−1，当 L<RL<R 时，执行循环： 当 nums[i]+nums[L]+nums[R]==0nums[i]+nums[L]+nums[R]==0，执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将 L,RL,R 移到下一位置，寻找新的解 若和大于 00，说明 nums[R]nums[R] 太大，RR 左移 若和小于 00，说明 nums[L]nums[L] 太小，LL 右移 '''
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n=len(nums)
        res=[]
        if(not nums or n<3):
            return []
        nums.sort()
        res=[]
        for i in range(n):
            if(nums[i]>0):
                return res
            if(i>0 and nums[i]==nums[i-1]):
                continue
            L=i+1
            R=n-1
            while(L<R):
                if(nums[i]+nums[L]+nums[R]==0):
                    res.append([nums[i],nums[L],nums[R]])
                    while(L<R and nums[L]==nums[L+1]):
                        L=L+1
                    while(L<R and nums[R]==nums[R-1]):
                        R=R-1
                    L=L+1
                    R=R-1
                elif(nums[i]+nums[L]+nums[R]>0):
                    R=R-1
                else:
                    L=L+1
        return res

16. 最接近的三数之和

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

C

int cmp(const void *a,const void *b) {
    return *(int*)a - *(int*)b;
}
    
int threeSumClosest(int* nums, int nums2, int nums3){
    qsort(nums, nums2, sizeof(int), cmp);
    int min = INT_MAX;
    for (int i = 0;i < nums2;i++) {
        int j = i + 1;
        int k = nums2 - 1;
        int curmin = INT_MAX;
        int cha = nums3 - nums[i];
        while(j < k) {
            int sum = nums[j] + nums[k];
            if (abs(curmin) > abs(sum - cha)) {
                curmin = sum - cha;
            }
            if (sum > cha) {
                k--;
            } else if (sum < cha) {
                j++;
            } else {
                return nums3;
            }
        }
        if (abs(curmin) < abs(min)) {
            min = curmin;
        }
    }
    return nums3 + min;
}

java

class Solution {
    public int threeSumClosest(int[] arr,int t) {
        Arrays.sort(arr);//对数组进行排序
        int closeNum = arr[0] + arr[1] + arr[2];//将前三个数相加赋给closeNum，表示初始化
        for(int i = 0;i<arr.length - 2;i++) {
            int j = i+1;
            int k = arr.length - 1;
            while(j<k) {
                int tmp = arr[i]+arr[j]+arr[k];
                if(Math.abs(tmp - t) < Math.abs(closeNum - t)) {
                    closeNum = tmp;
                }
                if(tmp < t) {
                    j++;
                }else if(tmp > t) {
                    k--;
                }else {
                    return tmp;
                }
            }
        }
        return closeNum;
    }
}
//在第一层循环中for(int i = 0;i<arr.length;i++)，我们定义双指针就j和k;
//j指向当前i的下一个元素，k指向末尾元素，计算三数之和并且赋给tmp，int tmp = arr[i]+arr[j]+arr[k];
//判断Math.abs(tmp - t) 和 Math.abs(closeNum - t)的大小，前者小，将前者赋给初始变量closeNum；
//之后判断tmp和目标值t的大小，大于 k--；小于j++，等于 直接返回tmp

python

''' 特判，对于数组长度nn，如果数组为Null或者数组长度小于3，返回[][]。 对数组进行排序，并定义resres，保存最接近和。 遍历排序后数组： 对于重复元素，跳过，避免重复计算（也可以不跳过） 令左指针L=i+1L=i+1,右指针R=n-1R=n−1,当L<RL<R时，执行循环： *令cur\_sum=nums[i]+nums[L]+nums[R]cur_sum=nums[i]+nums[L]+nums[R],如果cur\_sum=targetcur_sum=target,返回targettarget *若abs(cur\_sum-target)<abs(res-target)abs(cur_sum−target)<abs(res−target),说明cur\_sumcur_sum更接近目标，更新resres *若cur\_sum-targetcur_sum−target大于0，说明nums[R]nums[R]太大，RR左移 *若cur\_sum-targetcur_sum−target小于0，说明nums[L]nums[L]太小，LL右移 '''
class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        n=len(nums)
        if(not nums or n<3):
            return None
        nums.sort()
        res=float("inf")
        for i in range(n):
            if(i>0 and nums[i]==nums[i-1]):
                continue
            L=i+1
            R=n-1
            while(L<R):
                sum=nums[i]+nums[L]+nums[R]
                if(sum==target):
                    return target
                if(abs(sum-target)<abs(res-target)):
                    res=sum
                if(sum-target<0):
                    L+=1
                else:
                    R-=1
        return res