5.16 网易互娱笔试，第三题用常数时间判断全0全1。
第一题 题目的范围内是可以直接暴力的，但是也很迷，，太粗心了整了一个小时
package netease;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int st[][] = new int[n][10010];
for (int i = 0; i < n; i++) {
int m = in.nextInt();
int[][] vt = new int[m+1][2];
for (int j = 0; j < m; j++) {
vt[j][0] = in.nextInt();
vt[j][1] = in.nextInt();
}
vt[m][0] = 10001;
int ind = 1;
for (int k = 1; k < vt.length; k++) {
int l = vt[k][0] - vt[k-1][0];
for (int l2 = 0; l2 < l; l2++) {
st[i][ind] = st[i][ind-1]+vt[k-1][1];
ind++;
}
}
}
int test = in.nextInt();
for (int i = 0; i < test; i++) {
int time = in.nextInt();
int max = 0;
int maxlen= st[0][time];
// System.out.print(maxlen+" ");
for (int j = 1; j < n; j++) {
// System.out.print(st[j][time] +" ");
if(st[j][time]>maxlen) {
max = j;
maxlen = st[j][time];
}
}
// System.out.println();
System.out.println(max+1);
}
}
}第二题 也是暴力，，，先处理两边靠墙，再处理一边靠墙，就清晰很多了
package netease;
import java.util.Scanner;
public class t2 {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
int n = in.nextInt();
for (int z = 0; z < n; z++) {
int X = in.nextInt();
int Y = in.nextInt();
int x = in.nextInt();
int y = in.nextInt();
int d = in.nextInt();
int t = in.nextInt();
int [][]dir = {{-1,-1},{-1,1},{1,1},{1,-1}};
int cnt = 0;
x-=1;
y-=1;
for (int i = 0; i < t; i++) {
x+=dir[d][0];
y+=dir[d][1];
if((x==1&&y==1)||( x==1&&y==Y-2)||(x==X-2&&y==1)||(x==X-2&&y==Y-2)) {
if(d==1) {
d=3;
}else if(d==2) {
d = 0;
}else if(d==0) {
d = 2;
}else if(d==3) {
d = 1;
}
cnt+=2;
}else if(x==1) {
if(d== 0) {
d=3;
}else if(d==1) {
d=2;
}else {
System.out.println("wrong");
}
cnt ++;
}else if(x==X-2) {
if(d== 2) {
d=1;
}else if(d==3) {
d=0;
}else {
System.out.println("wrong");
}
cnt ++;
}
else if(y==1) {
if(d== 3) {
d=2;
}else if(d==0) {
d=1;
}else {
System.out.println("wrong");
}
cnt ++;
}
else if(y==Y-2) {
if(d== 2) {
d=3;
}else if(d==1) {
d=0;
}else {
System.out.println("wrong");
}
cnt ++;
}else {
//走就完事了。。
}
}
System.out.println(cnt);
}
}
}第三题，没时间了，暴力算法也没改出来，后面用常数时间判断给定起点和长度的正方形是否全0全1
，我用的是记录一个sum[i][j]，表示从[i,j]到左上所有的1的个数，然后正方形[x,y]到[x+l,y+l]的1的个数等于sum[x+l-1][y+l-1] - sum[x-1][y+l-1] - sum[x+l-1][y-1] + sum[x-1][y-1]，通过判断1的个数为0 或 l*l 得到是否为全1全0。
package netease;
import java.util.Scanner;
public class t3 {
static int map[][];
static int sum[][];
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
for (int ii = 0; ii < n; ii++) {
int X = in.nextInt();
int Y = in.nextInt();
in.nextLine();
map = new int[X][Y];
sum = new int[X][Y];
for (int i = 0; i < X; i++) {
String x = in.nextLine();
for (int j = 0; j < Y; j++) {
map[i][j] = x.charAt(j)=='1'?1:0;
}
}
sum[0][0] = map[0][0];
for (int i = 1; i < Y; i++) {
sum[0][i] = sum[0][i-1] + map[0][i];
}
for (int i = 1; i < X; i++) {
int sumx = 0;
for (int j = 0; j < Y; j++) {
sumx += map[i][j];
sum[i][j]=sumx + sum[i-1][j];
}
}
int max = Integer.min(X, Y)/3;
int now = max;
Boolean ok = false;
out:
for(int mow = max; now>=1; now--) {//3个1000 应该不会超时
for (int i = 0; i <= X - now*3; i++) {
for (int j = 0; j <= Y - now*3; j++) {
if(check(i, j, now)) {//常数时间
i+=1;
j+=1;
System.out.println(i+" "+j+" "+(i+now*3-1)+" "+(j+now*3-1));
ok = true;
break out;
}
}
}
}
if(!ok)
System.out.println("-1 -1 -1 -1");
}
}
private static boolean check(int x, int y, int now) {
// TODO Auto-generated method stub
if(check0(x, y, now)&&check0(x, y+2*now, now)&&
check0(x+2*now, y, now)&&check0(x+2*now, y+2*now, now)) {
if(check1(x, y+now, now)&&check1(x+now, y, now)&&check1(x+now, y+now, now)
&&check1(x+now, y+2*now, now)&&check1(x+2*now, y+now, now)) {
return true;
}
}
return false;
}
private static boolean check0(int x, int y, int now) {
return getArea(x, y, now) == 0;
}
private static int getArea(int x, int y, int now) {
int area = sum[x+now-1][y+now-1];
if(x-1>=0 && y-1>=0) {
area += sum[x-1][y-1];
}
if(x-1>=0) {
area -= sum[x-1][y+now-1];
}
if(y-1>=0) {
area -= sum[x+now-1][y-1];
}
return area;
}
private static boolean check1(int x, int y, int now) {
return getArea(x, y, now) == now * now;
}
}
/*
3
3 3
111
000
111
6 6
010010
111111
010010
010010
111111
010010
8 8
01000001
11100001
01001100
11001100
00111111
00111111
00001100
00001100
*/
#网易互娱笔试##笔试题目#
快手开奖39人在聊
投递蚂蚁集团等公司10个岗位 >