哔哩哔哩后台笔试题分享（Java版本）
人生的第一次AC，纪念一下。
第一题：翻转字符串 （空间复杂度O(1))
先将I am a students.翻转.tneduts a ma I，然后空格分隔，并将每个字串各自翻转
翻转使用双指针去交换左右两边。
I am a student.翻转成student. a am I public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
char[] chs = s.toCharArray();
swap(chs, 0,s.length() - 1);
String reverse = String.valueOf(chs);
StringBuilder sb = new StringBuilder();
String[] sArray = reverse.split(" ");
for (int i = 0; i < sArray.length; i++) {
char[] chars = sArray[i].toCharArray();
swap(chars, 0, chars.length - 1);
sb.append(chars);
sb.append(" ".toCharArray());
}
System.out.println(sb.toString().trim());
}
public static void swap(char[] chs, int left, int right) {
while (left < right) {
char tmp = chs[left];
chs[left] = chs[right];
chs[right] = tmp;
left++;
right--;
}
}
第二题：和题字符串拼接最小字典序相似，输入多个字符串然后可以依次组合，输出组合最小的字符串（因为之前听过左神的课，知道了此用法）
思路：贪心的思路！重写比较器，比较两种相加情况，两个字符串加起来（可以有两种不同的相加情况：a + b和b + a），哪一个作为前缀结果小那么就将哪一个排在前面，例如：如果(a + b) >(b + a) 那么b放在前面。
这样将每次排在最前面的拿出来拼接，那么结果就最小。
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String data = sc.next();
String[] dataArray = data.split(",");
if (dataArray == null) System.out.println(data);
PriorityQueue<String> pQ = new PriorityQueue<String>(new Comparator<String>() { @Override public int compare(String o1, String o2) {
if (Long.valueOf(o1 + o2) > Long.valueOf(o2 + o1)) {
return 1;
} else if (Long.valueOf(o1 + o2) == Long.valueOf(o2 + o1)) {
return 0;
} else {
return -1;
}
}
});
for (String s : dataArray) {
s = s.trim();
pQ.add(s);
}
StringBuilder sb = new StringBuilder();
while (!pQ.isEmpty()) {
sb.append(pQ.poll());
}
System.out.println(sb.toString());
} 第三题：背包问题
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
int[] weight = new int[N];
int[] value = new int[N];
for (int i = 0; i < N; i++) {
weight[i] = sc.nextInt();
}
for (int i = 0; i < N; i++) {
value[i] = sc.nextInt();
}
int [][]dp=new int[N+1][M+1];
for(int i=1; i<=N; i++) {
int w=weight[i-1];
int v=value[i-1];
for(int j=1;j<=M;j++) {
if(j>=w) {
dp[i][j]=Math.max(dp[i-1][j], dp[i-1][j-w]+v);
}else {
dp[i][j]=dp[i-1][j];
}
}
}
System.out.println(dp[N][M]);
}