我参加的机试是昨天晚上19：00到21：00，三道编程题目
由于考试期间在牛客网需要录屏所以没办法得到准确题目（华为允许使用本地IDE），我只能按照记忆描述
题目1
大概意思是：有n个人，每一个人都有一种礼物（礼物种类有两种，1是A类，2是B类），求三个人礼物数量（同种类）相加和最大，如果存在多组则输出序号小的那一组。如果不存在输出字符串"null"
输入：第一行n，后面n行就是每个人所拥有的礼物数目和礼物种类
输出：第一行3个人的序号（处于第几行就是该人的序号），第二行礼物种类，第三行礼物数目最多是多少
输入样例：
6
2 2
2 1
3 2
5 2
3 1
7 2
输出样例：
3 4 6
2
15
解释：此样例选了第3、4、6行，都是种类2，礼物数目是3+5+7=15
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int n = sc.nextInt();
int []num = new int[n];
int []type = new int[n];
int cnt =0;
for(int i=0;i<n;i++){
num[i]=sc.nextInt();
type[i]=sc.nextInt();
if(type[i]==1) cnt++;
}
//四个数组可以用两个treemap代替
int []n1 =new int[cnt];
int[]t1 = new int[cnt];
int[] n2 = new int[n-cnt];
int[] t2 = new int[n-cnt];
int top1=0,top2=0,t11=0,t22=0;
for(int i=0;i<n;i++){
if(type[i]==1){
n1[top1++] = num[i];
t1[t11++] = i+1;//注意这里是从第1行开始的
}else if(type[i]==2){
n2[top2++] = num[i];
t2[t22++] = i+1;
}
}
if(cnt<3&&n-cnt<3) {//没满足情况
System.out.println("null");continue;
}
if(cnt < 3){
helper(n2,t2);
System.out.println(t2[t2.length-3]+" "+t2[t2.length-2]+" "+t2[t2.length-1]);
System.out.println(2);
System.out.println(n2[n2.length-1]+n2[n2.length-2]+n2[n2.length-3]);
}
else if(n-cnt<3){
helper(n1,t1);
System.out.println(t1[t1.length-3]+" "+t1[t1.length-2]+" "+t1[t1.length-1]);
System.out.println(1);
System.out.println(n1[n1.length-1]+n1[n1.length-2]+n1[n1.length-3]);
}else{//两个种类礼物的人都>=3
helper(n2,t2);
helper(n1,t1);
if(n2[n2.length-1]+n2[n2.length-2]+n2[n2.length-3] > n1[n1.length-1]+n1[n1.length-2]+n1[n1.length-3]){//比较总量谁大
System.out.println(t2[t2.length-3]+" "+t2[t2.length-2]+" "+t2[t2.length-1]);
System.out.println(2);
System.out.println(n2[n2.length-1]+n2[n2.length-2]+n2[n2.length-3]);
}else if(n2[n2.length-1]+n2[n2.length-2]+n2[n2.length-3] < n1[n1.length-1]+n1[n1.length-2]+n1[n1.length-3]){
System.out.println(t1[t1.length-3]+" "+t1[t1.length-2]+" "+t1[t1.length-1]);
System.out.println(1);
System.out.println(n1[n1.length-1]+n1[n1.length-2]+n1[n1.length-3]);
}else{
if(t2[t2.length-3] > t1[t1.length-3]){//总量相等比较序号
System.out.println(t1[t1.length-3]+" "+t1[t1.length-2]+" "+t1[t1.length-1]);
System.out.println(1);
System.out.println(n1[n1.length-1]+n1[n1.length-2]+n1[n1.length-3]);
}else{
System.out.println(t2[t2.length-3]+" "+t2[t2.length-2]+" "+t2[t2.length-1]);
System.out.println(2);
System.out.println(n2[n2.length-1]+n2[n2.length-2]+n2[n2.length-3]);
}
}
}
}
public static void helper(int[] n,int[]t){//此过程完全可以用treemap自动完成
for(int i=0;i<n.length;i++){
for (int j = 0; j <n.length-i-1 ; j++) {
if(n[j]>n[j+1]){
int t1 = n[j];
n[j] = n[j+1];
n[j+1]=t1;
int x = t[j];
t[j] = t[j+1];
t[j+1] = x;
}
}
}
}
}
}
这道题其实可以用treemap进行排序，不用进行我这样，treemap我用的不是很多机考时忘了。。。。。。
通过率：100%
题目2
这道题目我见过类似的，输入矩阵的行和列，接下来输入字符矩阵，H代表陆地，S代表水池，被H或者边界包围的S算成有一个水池，让你计算有多少个水池
例如：
输入样例
3，5
SSHHH
SSHSH
HHHHS
输出样例：
3
我的思路：深搜，当找到一个S时让它向四个方向走，遇到S变成H，这样当遍历到水池中的一个第一个S时，同一水池的其它S都变成H了，所以只需要统计S的数目就可以了。
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
String[] strs= sc.nextLine().split(",");
int m = Integer.valueOf(strs[0]);
int n = Integer.valueOf(strs[1]);
String[] map = new String[m];
char[][] map1 = new char[m][n];
for(int i=0;i<m;i++){
map[i] = sc.nextLine();
}
for(int i=0;i<m;i++){
for (int j = 0; j <n ; j++) {
map1[i][j] = map[i].charAt(j);
}
}
int res = 0;
for(int i=0;i<m;i++){
for (int j = 0; j < n; j++) {
if(map1[i][j] == 'S'){
dfs(map1,i,j,m,n);
res++;
}
}
}
System.out.println(res);
}
}
public static void dfs(char[][] map,int i,int j,int m,int n){
if(i<0||i>=m||j<0||j>=n ||map[i][j]=='H') return;
if(map[i][j]=='S') map[i][j] = 'H';
dfs(map,i+1,j,m,n);
dfs(map,i,j+1,m,n);
dfs(map,i-1,j,m,n);
dfs(map,i,j-1,m,n);
}
}
通过率：80%，说是有数组越界，我没检查出来，思路就是这样
题目3
这道题经典的01背包问题，我一看不会想着就混通过率吧，题目还是简单说一下，题目描述有一个卡车空间k，有n个物品，物品有它的大小和价值，问你如何将物品放到卡车中保证他的价值最大。
输入就是：n k 两个价值和大小的数组
输出：最大价值
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int k = sc.nextInt();
int n =sc.nextInt();
int []size = new int[n];
int[] value =new int[n];
//double []perV = new double[n];
for (int i = 0; i <n ; i++) {
size[i] = sc.nextInt();
}
for (int i = 0; i <n ; i++) {
value[i] = sc.nextInt();
//perV[i] = value[i]*1.0/size[i];
}
helper(size,value);
int res = 0;
for (int i = n-1; i >=0 ; i--) {
if(k - size[i] >= 0){
res += value[i];
k-=size[i];
}
}
for (int i = 0; i < n; i++) {
if(k - size[i] >= 0){
res += value[i];
k-=size[i];
}
}
System.out.println(res);
}
}
public static void helper(int[] size,int [] value){
for (int i = 0; i <size.length ; i++) {
for (int j = 0; j <size.length-1-i ; j++) {
if(value[j] > value[j+1]){
int v1 = value[j];
value[j] = value[j+1];
value[j+1] = v1;
int s1 = size[j];
size[j] = size[j+1];
size[j+1] = s1;
}
}
}
}
}
通过率：45.45%
我是通过贪心进行做的，我知道可以得到较优解，正确做法。。。。。。。
01背包//好像这个做法也只能过80%
下面代码来源：https://www.cnblogs.com/TestAndDevelp/p/12378831.html
import java.util.*;
public class test {
public static int getMaxValue(int[] weight, int[] value, int w, int n) {
int[][] table = new int[n + 1][w + 1];
for (int i = 1; i <= n; i++) { //物品
for (int j = 1; j <= w; j++) { //背包大小
if (weight[i] > j) {
//当前物品i的重量比背包容量j大，装不下，肯定就是不装
table[i][j] = table[i - 1][j];
// System.out.print(table[i][j]+ " ");
} else { //装得下，Max{装物品i， 不装物品i}
table[i][j] = Math.max(table[i - 1][j], table[i - 1][j - weight[i]] + value[i]);
//System.out.print(table[i][j]+ " ");
}
}
// System.out.println();
}
return table[n][w];
}
public static void main(String[] args) {
int n = 5, w = 10; //物品个数，背包容量
int[] value = {0, 6, 3, 5, 4, 6}; //各个物品的价值
int[] weight = {0, 2, 2, 6, 5, 4}; //各个物品的重量
System.out.println(getMaxValue(weight,value,w,n));
}
}