文章目录

   今天上午参加了华为实习生校招的机试,下学期老师是要求回南京的实验室去写论文的,所以也没打算真去实习,只是想去看看,做做题目玩一下。

   今年的和之前告知我们给我们练习的去年的提目格式差不多,也是3道,分别是60、100和160分,不过相对于去年的难度,今年的题目要简单多了。倒是评测系统把我恶心死了,第一道提目明明在本地做出来了,可是提交老是不通过,一开始我也为是用容器之类的东西不可以,后来改用最基本的矩阵操作也不行,估计是他们的评测系统有点问题。

   废话少说,下面开始正题。

   第一题:输入两个字符串M和N,从字符串M中删除字符串N中所有的字符。例如,输入”abcda”和”ac”,则删除之后的第一个字符串变成”bd”。

   样例输入:

   abcda

   ac

   样例输出:

   bd

   解析:最基本的字符串操作,没啥好解释的

   代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
String a="",b="";
while (cin.hasNext()){
a = cin.nextLine();
b = cin.nextLine();
       break;
}
System.out.println(deleteRepeat(a,b));
}

public static String deleteRepeat(String a,String b){
char[] select1=new char[100];
char[] select2=new char[100];
select1=a.toCharArray();
select2=b.toCharArray();
for (int i = 0; i < select1.length; i++) {
for (int j = 0; j < select2.length; j++) {
if (select1[i]==select2[j]) {
select1[i]='0';
}
}
}
String s="";
for (int i = 0; i < select1.length; i++) {
if (select1[i]!='0') {
s=s+select1[i];
}
}
return s;
}
}

    后来我比对了一下提交成功的同学的代码,发现系统判断错误的原因可能在于输入的部分,他们不是while (cin.hasNext()){… ; break;}这样的,而是直接

1
2
String M = cin.next();
String N = cin.next();

    读了2个字符串,评判系统这么挫我也是醉了,2333。

    第二题:在一个空的文件夹中,即可以装订增加文件数,也可以摘除减少文件数,在多次装订、摘除后,请输出最后剩余的文件数

   注:如果摘除的文件数大于当前的文件数,则将当前的文件全部摘除

   输入:

   装订文件数:binding 20(表明装订20个文件)

   摘除文件数:remove 20(表明摘除20个文件)

    结束装订摘除:end

   输出:

   当前文件夹的文件数:
   current 20(表明当前还有20个文件在文件夹中)

    样例输入:

    binding 30

    remove 20

    binding 10

    remove 10

    end

    样例输出:

    current 10

    解析:基本的字符串操作,没啥好说的

    代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner cin = new Scanner(System.in);
List<String> needOperation=new ArrayList<String>();
while (cin.hasNext()){
String temp=cin.nextLine();
needOperation.add(temp);
if (temp.equals("end")) {
break;
}
}
System.out.println("current "+fileOperation(needOperation));
}

public static int fileOperation(List<String> needOperation ) {
int total=0;
String[] temp=new String[1000];
for (Iterator iterator = needOperation.iterator(); iterator.hasNext();) {
String string = (String) iterator.next();
temp=string.split(" ");
if (temp[0].equals("binding")) {
total=total+Integer.parseInt(temp[1].toString());
}else if (temp[0].equals("remove")) {
total=total-Integer.parseInt(temp[1].toString());
}else if (temp[0].equals("end")) {
break;
}
}
return total;
}
}

   第三题:给你一个N*M的矩阵,每个位置的值是0或1,求一个面积最大的子矩阵,这个矩阵必须是一个正方形,且里面只能由1构成,输出最大的正方形边长

   输入:第一行输入两个整数n,m,之后n行,每行m个数字,为矩阵第i行第j列的值,只可能是0或者1

   n,m<=400

   输出:一个整数,为最大正方形的边长

   样例输入:
   3 3

   1 1 1

   1 1 1

   0 0 1

   样例输出:

   2

   解析:这题好多同学说没做完,或者直接就没做,其实很简单,主要就是如何将读入的字符串转换成对应的矩阵有点麻烦,下面对矩阵的处理直接一层层的从里往外剥就可以了。

   代码:

import java.util.*;
public class Main{
public static void main(String args[]){
Scanner cin = new Scanner(System.in);
List needOperation=new ArrayList();

   这题没有给我通过全部的测试用例,我找了半天也没发现bug在哪里,希望知道的朋友能批评指正。

   回头再看一下,自己简直渣到爆啊,把题目想的太简单了,2333。

  解析:把矩阵每行的各个数进行向下累加,遇到零则置为零,也就是把矩阵的元素处理为该元素每列的高度,如示例的矩阵处理为

  1 1 1

  2 2 2

  0 0 3

  然后再把矩阵的每行看成一个直方图,分别求出各个直方图的最大矩形面积,至于正方形什么的,加一个面积为完全平方数的判定即可(糊脸2333),计算矩形面积的时候加判断来处理吧,是正方形再压栈,话说用单调栈来求解直方图最大矩形面积的算法简直碉堡了,膜拜想出这些牛逼算法的大神。

  代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
import java.util.*;
public class CubeAnalysis {

public static void main(String args[]){
Scanner cin = new Scanner(System.in);
List<String> needOperation=new ArrayList<String>();
int row=0,col=0;
while (cin.hasNext()){
String temp=cin.nextLine();
needOperation.add(temp);
String[] tempArray=new String[2];
tempArray=needOperation.get(0).split(" ");
row=Integer.parseInt(tempArray[0].toString());
col=Integer.parseInt(tempArray[1].toString());
if (needOperation.size()==row+1) {
break;
}
}
//去到第一行
needOperation.remove(0);
int[][] cube=new int[row][col];
cube=cubeReadOperation(needOperation,row,col);
int max=cubeOperation(cube);
if (max!=0) {
System.out.println(max);
}
//System.out.println(Arrays.deepToString(cube));
}
private static int[][] cubeReadOperation(List<String> needOperation,int row,int col){
int[][] cube=new int[row][col];
for (int i=0;i<needOperation.size();i++) {
String singleLine=needOperation.get(i);
String[] oneRowString=singleLine.split(" ");
int[] oneRow=new int[col];
for (int j = 0; j < oneRowString.length; j++) {
oneRow[j]=Integer.parseInt(oneRowString[j]);
}
for (int j = 0; j < oneRow.length; j++) {
cube[i][j]=oneRow[j];
}
}
return cube;
}

public static int cubeOperation(int[][] cube ) {
int row=cube.length;
int col=cube[0].length;
int[] sum=new int[col];
int[][] newCube=new int[row][col];
int maximunCubeArea=0;
for (int i = 0; i < row; i++) {//一行行的处理,sum[j]存储的是到第i行时,在第j列从第i行开始往上1的个数
for(int j=0;j<col;j++){
if(cube[i][j]==1)
sum[j]++;
else
sum[j]=0;
newCube[i][j]=sum[j];
}
}
//System.out.println(Arrays.deepToString(newCube));
//对处理好的数组的每一行进行计算直方图最大矩形面积的计算
for(int i=0;i<row;i++){
sum=newCube[i];
int maxArea=largestRectangleArea(sum);
if (maxArea>maximunCubeArea) {
maximunCubeArea=maxArea;
}
}
return (int) Math.sqrt(maximunCubeArea);
}


// O(n) using one stack
private static int largestRectangleArea(int[] height) {
int area = 0;
java.util.Stack<Integer> stack = new java.util.Stack<Integer>();
for (int i = 0; i < height.length; i++) {
if (stack.empty() || height[stack.peek()] < height[i]) {
stack.push(i);
} else {
int start = stack.pop();
int width = stack.empty() ? i : i - stack.peek() - 1;
if (height[start]==width) {//判断
area = Math.max(area, height[start] * width);
}

i--;
}
}
while (!stack.empty()) {
int start = stack.pop();
int width = stack.empty() ? height.length : height.length - stack.peek() - 1;
if (height[start]==width) {//判断
area = Math.max(area, height[start] * width);
}
}
return area;
}
}

   通过这次机试,发现自己还是很菜啊,果然还得要到hihocoder、LeetCode、hdu(牛哥告诉我的)这些类似的网站刷刷题目啥的,防止自己以后抓瞎。


如果觉得文章很有趣或对你带来了帮助,欢迎请我喝杯咖啡哦~

文章目录