资金匹配_乐信笔试题

菲尼克斯弗兰克

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] amount = in.nextLine().split(",");
        int target = in.nextInt();
        back(amount, target, 0);
        System.out.println(cnt);
    }
    // 回溯框架直接秒杀
    static List<Integer> select = new ArrayList<>();
    static int cnt = 0;
    public static void back(String[] amount, int target, int idx) {
        if (target < 0) return;
        if (target == 0) {
            cnt++;
            return;
        }
        for (int i = idx; i < amount.length; i++) {
            target -= Integer.parseInt(amount[i]);
            back(amount, target, i+1);
            target += Integer.parseInt(amount[i]);
        }
    }
}

发表于 2022-06-27 11:29:12 回复(0)

牛客896365265号

dfs直接求解就可以了，每一个元素都可以选择要或者不要

import java.util.*;
public class Main {
    // 匹配方案个数
    public static intcount = 0;
    public static intsum = 0;
    public static void kSum(List<Integer> numbers, int target, int i) {
        if(sum == target){
            count++;
            return;
        }
        if(i == numbers.size())  return;
        if(sum > target)  return;
        sum += numbers.get(i);
        kSum(numbers, target, i + 1);
        sum -= numbers.get(i);
        kSum(numbers, target, i + 1);
    }
   
    public static void main(String[] args) {
        Scanner sc = newScanner(System.in);
        String source = sc.nextLine();
        String[] str = source.split(",");
        List<Integer> in = newArrayList<Integer>();
        for(inti = 0; i < str.length; i++)
            in.add(Integer.parseInt(str[i]));
        inttarget = Integer.parseInt(sc.nextLine());
        kSum(in, target, 0);
        System.out.println(count);
    }
}

发表于 2020-05-26 21:28:26 回复(0)

牛客143061234号

子集和问题

发表于 2019-12-15 20:47:15 回复(0)

小鲸鱼历险记

这题是典型的组合类型的题，用dfs求解即可，注意一下题目要求要刚好才算一个，代码如下(话说有大佬在用getline成功了吗，我不知道为什么在牛客上用getline一直报错呐，求解答~~~)：

#include <bits/stdc++.h>
#include <iostream>
 
using namespace std;
 
int kSum(vector<int>& n, int loc, int target) {
    if(target == 0) return 1;
    if(target < 0) return 0;
    if(loc == n.size()) {
        return target == 0 ? 1 : 0;
    }
     
    int ans = 0;
    for(int i = loc; i < n.size(); ++i) {
        ans += kSum(n, i + 1, target - n[i]);
    }
    return ans;
}
 
int main() {
    int target;
     
    vector<int> n;
    string s;
    cin >> s;
    int temp;
    int i = 0;
    while(i < s.size()) {
        if(s[i] == ',') {
            ++i;
            continue;
        };
        int left = i;
        while(i < s.size() && s[i] != ',')
            ++i;
        temp = stoi(s.substr(left, i - left));
        ++i;
        n.push_back(temp);
    }
     
    cin >> target;
     
    cout << kSum(n, 0, target);
}

发表于 2019-12-13 16:54:23 回复(0)

资金匹配

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题