哔哩哔哩20校招后端笔试编程题 （8-20）

（翻转单词顺序）
题目：原地翻转句子中单词的顺序，但单词内字符的顺序不变。
实例1：
输入：
I am a student.
输出：
student. a am I

	

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static String reverse(String str){
        String s[] = str.split(" ");
        StringBuffer sb = new StringBuffer();
        for(int i=s.length;i>0;i--){
            if(i==1){
                sb.append(s[i-1]);
            }else {
                sb.append(s[i-1]).append(" ");
            }
        }
        return sb.toString();
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String str = bf.readLine();
        System.out.println(reverse(str));
    }
}

（输出最小整数）
输入一个正整数数组，将它们连接成一个数，使得排出的数是最小的。
实例：
输入：
32,231
输出：
23132

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;

public class Main {
        public static String PrintMinNumber(int [] numbers) {
            int len = numbers.length;
            if(len == 0)
                return "";
            if(len == 1)
                return String.valueOf(numbers[0]);
            StringBuffer res = new StringBuffer();
            String [] str = new String[len];
            for(int i=0; i<len; i++)
                str[i] = String.valueOf(numbers[i]);
            Arrays.sort(str, new Comparator<String>(){
            public int compare(String s1, String s2) {
                    String c1 = s1 + s2;
                    String c2 = s2 + s1;
                    return c1.compareTo(c2);
                }
            });
            for(int i=0; i<len; i++)
                res.append(str[i]);
            return res.toString();
        }

        public static void main(String[] args) throws IOException {
            BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            String s ="";
            while((s=bf.readLine())!=null) {
                String[] nm = s.split(",");
                int[] shuzu = new int[nm.length];
                for(int i=0;i<nm.length;i++){
                    shuzu[i] = Integer.parseInt(nm[i]);
                }
                System.out.println(PrintMinNumber(shuzu));
            }
        }
    }

背包问题：
动态规划中的背包问题。

	给定 n 种物品和一个容量为 C 的背包，物品 i 的重量是 wi，其价值为 vi 。



	问：应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？

import java.util.Scanner;

public class Main {
    public static int manyPack(int V, int N, int[] weight, int[] value) {
        //初始化动态规划数组
        int[][] dp = new int[N + 1][V + 1];
        //为了便于理解,将dp[i][0]和dp[0][j]均置为0，从1开始计算
        for (int i = 1; i < N + 1; i++) {
            for (int j = 1; j < V + 1; j++) {
                //如果第i件物品的重量大于背包容量j,则不装入背包
                //由于weight和value数组下标都是从0开始,故注意第i个物品的重量为weight[i-1],价值为value[i-1]
                if (weight[i - 1] > j)
                    dp[i][j] = dp[i - 1][j];
                else {
                    //考虑物品的件数限制
                    int maxV = Math.min(1, j / weight[i - 1]);
                    for (int k = 0; k < maxV + 1; k++) {
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - k * weight[i - 1]] + k * value[i - 1]);
                    }
                }
            }
        }
        return dp[N][V];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = Integer.parseInt(sc.nextLine());
        int M = Integer.parseInt(sc.nextLine());
        String[] strw = null;
        strw = sc.nextLine().split(" ");
        int[] w = new int[strw.length];
        for(int i=0;i<w.length;i++){
            w[i] = Integer.parseInt(strw[i]);
        }
        String[] strv = null;
        strv= sc.nextLine().split(" ");
        int[] v = new int[strv.length];
        for(int j=0;j<strv.length;j++){
            v[j] = Integer.parseInt(strv[j]);
        }
//      int[] v ={6,3,5,4,6};
//      int[] w ={2,2,6,5,4};
        System.out.println(manyPack(M,N,w,v));
    }
}