腾讯（Tencent）4.5号后台开发笔试-java题解

第一题，钱币数量问题，注意是1-m全部都能组成。
循环找到最大的小于等于sum+1的值为a[i]，则sum+a[i]之内的都可以；
import java.util.Arrays;
import java.util.Scanner;

/**

• Created by ouyangxizhu on 2019/4/5.
• /
  public class Tencent1 {
  public static void main(String args[]) {

    Scanner sc = new Scanner(System.in);
    int m = sc.nextInt();
    int n = sc.nextInt();
    int[] a = new int[n];
    for (int i = 0; i< n; i ++){
        a[i] = sc.nextInt();
    }
    Arrays.sort(a);
    int sum = 0;
    int res = 0;
    if (a[0] != 1){
        System.out.println( -1);
    }else{
        while(true){
            if(sum >= m){
                System.out.println(res);
                return;
            }
            for (int i = n - 1; i >= 0; i--){
                if (a[i] <= sum + 1){
                    sum += a[i];
                    res ++;
                    break;
                }
            }
        }

    }
}

}

第二题，全部替换01 和 10 ，现在看数一下0和1 的差值就好了

import java.util.Scanner;

/**

• Created by ouyangxizhu on 2019/4/5.

• /
  public class Tencent2 {
  public static void main(String args[]) {

    Scanner sc = new Scanner(System.in);
    String n = sc.nextLine();
    String str = sc.nextLine();
  
    while (str.contains("01")){
        str = str.replace("01", "");
    }
    while (str.contains("10")){
       str = str.replace("10", "");
    }
    System.out.println(str.length());

  }
  }
  第三题递归，因为数据量小，不需要剪枝了

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

/**

• Created by ouyangxizhu on 2019/4/5.

• /
  public class Tencent3 {
  static ArrayList<Integer> list = new ArrayList<>();
  public static void main(String args[]) {

    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    long[] p = new long[n];
    int[] m = new int[n];
    for (int i = 0; i < n; i ++){
        p[i] = sc.nextLong();
    }
    for (int i = 0; i < n; i ++){
        m[i] = sc.nextInt();
    }
    if(n == 1){
        System.out.println(m[0]);
        return;
    }
  
    Long sum = 0L;
    int res = 0;
    cal(sum, res, p, m, 0);
    Collections.sort(list);
    System.out.println(list.get(0));

  }

  private static void cal(Long sum, int res, long[] p, int[] m, int index) {

    if (index >= p.length){
        list.add(res);
        return;
    }
    if (sum >=  p[index])
        cal(sum, res, p, m, index + 1);
  
    cal(sum + p[index], res + m[index], p, m, index + 1);

  }
  }