阿里3.14笔试，三题JAVA代码
第一题
16进制转2进制算1的个数，直接打卡
import java.util.HashMap;
import java.util.Scanner;
public class Q1 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
HashMap<Character,Integer> map = new HashMap<>();
map.put('0',0);
map.put('1',1);
map.put('2',1);
map.put('3',2);
map.put('4',1);
map.put('5',2);
map.put('6',2);
map.put('7',3);
map.put('8',1);
map.put('9',2);
map.put('a',2);
map.put('b',3);
map.put('c',2);
map.put('d',3);
map.put('e',3);
map.put('f',4);
int ans= 0;
for (int i = 2; i < str.length(); i++) {
ans+=map.get(str.charAt(i));
}
System.out.println(ans);
}
}
第二题
一个nxm矩阵，有的是人，有的是灯，灯可以上下左右都看，如果能看到人就计1，问所有灯能看到的人数
思路：从左到右，从右到左，从上到下，从下到上，4nm复杂度。
import java.util.Scanner;
public class Q2 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int map[][] = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
//取反
map[i][j] = 1 - sc.nextInt();
}
}
System.out.println(maxScore(map, n, m));
}
public static long maxScore(int[][] map, int n, int m) {
//1是灯，0是人 上面取反了 （这步其实没必要，一开始思路没定）
long ans = 0;
for (int i = 0; i < n; i++) {
//从左到右按行
boolean havePerson = false;
for (int j = 0; j < m; j++) {
if (map[i][j] == 1) {
// System.out.println("正序，第" + i + "行，第" + j + "列");
if (havePerson) {
ans++;
// System.out.println("成功:ans:"+ans);
}
} else {
havePerson = true;
}
}
havePerson = false;
for (int j = m - 1; j >= 0; j--) {
if (map[i][j] == 1) {
// System.out.println("逆序，第" + i + "行，第" + j + "列");
if (havePerson) {
ans++;
// System.out.println("成功:ans:"+ans);
}
} else {
havePerson = true;
}
}
}
// System.out.println("+++++++++++++++");
for (int i = 0; i < m; i++) {
boolean havePerson = false;
//从上到下
for (int j = 0; j < n; j++) {
if (map[j][i] == 1) {
// System.out.println("正序，第" + j + "行，第" + i + "列");
if (havePerson) {
ans++;
// System.out.println("成功:ans:"+ans);
}
} else {
havePerson = true;
}
}
//从下到上
havePerson = false;
for (int j = n - 1; j >= 0; j--) {
if (map[j][i] == 1) {
// System.out.println("序，第" + j + "行，第" + i + "列");
if (havePerson) {
ans++;
// System.out.println("成功:ans:"+ans);
}
} else {
havePerson = true;
}
}
}
return ans;
}
}
第三题
消消乐，一个8x8地图，点一个格子，该格子连通的同样颜色的都会消掉...题目太长了 自己搜一下吧
思路：主要是模拟，先用BFS标记消除，然后再填充
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Queue;
import java.util.Scanner;
public class Main {
public static int[] appendPoint = new int[8];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
sc.nextLine();
char map[][] = new char[8][8];
for (int i = 0; i < 8; i++) {
String str = sc.nextLine();
for (int j = 0; j < str.length(); j++) {
map[i][j] = str.charAt(j);
}
}
String[] appendStrs = new String[8];
for (int i = 0; i < 8; i++) {
appendStrs[i] = sc.nextLine();
}
char dir[] = new char[n];
int x[] = new int[n];
int y[] = new int[n];
for (int i = 0; i < n; i++) {
String ops = sc.nextLine();
String strs[] = ops.split(" ");
x[i] = Integer.parseInt(strs[0])-1;
y[i] = Integer.parseInt(strs[1])-1;
dir[i] = strs[2].charAt(0);
}
int ans[] = getDamage(map,n,appendStrs,x,y,dir);
for (int i = 0; i < n; i++) {
System.out.println(ans[i]);
}
}
public static int[] getDamage(char[][] map, int n, String[] appendStrs, int[] x, int[] y, char[] dir) {
int[] ans = new int[n];
for (int i = 0; i < n; i++) {
ans[i] = bfs(map,x[i],y[i]);
//.out.println("bfs消除后的map");
// printMap(map);
move(map,dir[i],appendStrs);
// System.out.println("填充后的map");
// printMap(map);
}
return ans;
}
public static void move(char[][] map, char dir, String[] appendStrs) {
// wasd 上 左 下 右
if (dir == 'w') {
for (int col = 0; col < 8; col++) {
//向上移动
int k = 0;
for (int row = 0; row < 8; row++) {
if (map[row][col] != '*') {
map[k++][col] = map[row][col];
}
}
//填充
//int idx = appendPoint[col];
while (k < 8) {
map[k++][col] = appendStrs[col].charAt(appendPoint[col]++);
}
}
} else if (dir == 'a') {
for (int row = 0; row < 8; row++) {
//向左移动
int k = 0;
for (int col = 0; col < 8; col++) {
if (map[row][col] != '*') {
map[row][k++] = map[row][col];
}
}
//向左填充
while (k < 8) {
map[row][k++] = appendStrs[row].charAt(appendPoint[row]++);
}
}
} else if (dir == 's') {
for (int col = 0; col < 8; col++) {
//向下移动
int k = 7;
for (int row = 7; row >= 0; row--) {
if (map[row][col] != '*') {
map[k--][col] = map[row][col];
}
}
//填充
//int idx = appendPoint[col];
while (k >= 0) {
map[k--][col] = appendStrs[col].charAt(appendPoint[col]++);
}
}
} else if (dir == 'd') {
for (int row = 0; row < 8; row++) {
//向右移动
int k = 7;
for (int col = 7; col >= 0; col--) {
if (map[row][col] != '*') {
map[row][k--] = map[row][col];
}
}
//向左填充
while (k >= 0) {
map[row][k--] = appendStrs[row].charAt(appendPoint[row]++);
}
}
}
}
public static int bfs(char[][] map, int x, int y) {
int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int ans = 0;
Deque<int[]> Q = new ArrayDeque<>();
Q.add(new int[]{x, y});
char color = map[x][y];
map[x][y] = '*';
while (!Q.isEmpty()) {
int[] p = Q.poll();
// System.out.println("当前点:"+p[0]+","+p[1]+"\ty暗色:"+color);
ans++;
// for (int i = 0; i < 4; i++) {
// System.out.println("dirs"+dirs[i][0]+","+dirs[i][1]);
// }
for (int[] dir : dirs) {
int newx = p[0] + dir[0];
int newy = p[1] + dir[1];
// System.out.println("\t考虑点:"+p[0]+","+p[1]);
if (newx < 0 || newx >= 8 || newy < 0 || newy >= 8) continue;
// System.out.println("\t考虑点:"+p[0]+","+p[1]+"\ty暗色:"+map[newx][newy]);
if (map[newx][newy] == color) {
// System.out.println("\t加入当前点");
map[newx][newy] = '*';
Q.add(new int[]{newx, newy});
}
}
}
return ans;
}
public static void printMap(char[][] map){
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
System.out.print(map[i][j]);
}
System.out.println();
}
}
}
