奇安信 提前批 Java开发 笔经

2020.08.01 下午 笔试 2h

1）采购员

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        int n = in.nextInt();
        int[] p = new int[n];
        int[] w = new int[n];
        for(int i = 0; i < 2 * n; i++) {
            if(i % 2 == 0) {
                p[i / 2] = in.nextInt();
            } else {
                w[i / 2] = in.nextInt();
            }
        }

        int[] dp = new int[t + 1];
        Arrays.fill(dp, 0);
        for(int i = 1; i <= t; i++) {
            for(int j = 0; j < n; j++) {
                if(i >= p[j]) {
                    dp[i] = Math.max(dp[i], dp[i - p[j]] + w[j]);
                }
            }
        }

        System.out.print(dp[t]);
    }
}

2）找亲戚

public class Solution {
    /**
     * 返回亲7数个数
     * @param digit int整型一维数组 组成亲7数的数字数组
     * @return int整型
     */
    private int res = 0;

    public int reletive_7 (int[] digit) {
        backtrack(digit, 0, 0);

        return res;
    }

    private void backtrack(int[] digit, int idx, int num) {
        if(idx == digit.length) {
            if(num % 7 == 0) {
                res++;
            }
            return;
        }

        for(int i = idx; i < digit.length; i++) {
            swap(digit, idx, i);
            int tmp = num;
            num = num * 10 + digit[idx];
            backtrack(digit, idx + 1, num);
            num = tmp;
            swap(digit, idx, i);
        }
    }

    private void swap(int[] a, int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        int[] digit = {1, 1, 2};
        System.out.println(s.reletive_7(digit));
    }
}