实习与工作

华为实习校招笔试

jxtxzzw · 4月11日 · 2019年 · · 702次已读

第 1 题,100 分,没什么好说的,照着模拟就行了。

我是读进来一个字符串,补全到 8 的倍数,然后每 8 位一取,加入到 List,然后排序,最后输出。

顺利通过所有数据。

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main{    
    public static void main(String args[]){
    	Scanner in = new Scanner(System.in);
    	int n = in.nextInt();
    	ArrayList<String> list = new ArrayList<>();
    	for (int i = 0; i < n; i++) {
    		StringBuffer sb = new StringBuffer();
    		sb.append(in.next());
    		while (sb.length() % 8 != 0)
    			sb.append("0");
    		for (int j = 0; j < sb.length(); j += 8) {
    			list.add(sb.substring(j, j + 8));
    		}
    	}
    	Collections.sort(list);
    	boolean isFirst = true;
    	for (String s : list) {
    		if (isFirst)
    			isFirst = false;
    		else
    			System.out.print(" ");
    		System.out.print(s);
    	}
    	in.close();	
    }
    
}

第 2 题,200 分,也没什么好说的,就是模拟。

括号是等价的,如果遇到括号,就找到匹配的括号组,对括号组内的部分可以递归地调动相同的处理函数,对于数组,就是重复后面的括号运算若干次,最后取反。

有 StringBuffer 以后事情变得简单,但是不知道为什么最后我是只通过了 80% 的数据,说数组下标越界。

要说超时或者答案错误还能理解,数组下标越界我是想不通,可能是哪里写炸了。

import java.util.Scanner;

public class Main {
	public static void main(String args[]) {
		Scanner in = new Scanner(System.in);
		StringBuffer sb = new StringBuffer();
		String inputString = in.next();
		sb.append(decodeRecursively(inputString));
		System.out.println(sb.reverse());
		in.close();
	}

	private static String decodeRecursively(String processingString) {
		StringBuffer sb = new StringBuffer();
		int index = 0;
		int length = processingString.length();
		while (index < length) {
			if (Character.isLetter(processingString.charAt(index))) {
				sb.append(processingString.charAt(index));
				index++;
			} else if (Character.isDigit(processingString.charAt(index))) {
				StringBuffer num = new StringBuffer();
				while (Character.isDigit(processingString.charAt(index))) {
					num.append(processingString.charAt(index));
					index++;
				}
				long x = Long.parseLong(num.toString());
				int end = findBracedSub(processingString, index);
				String sub = processingString.substring(index + 1, end - 1);
				index = end;
				while (x-- != 0)
					sb.append(decodeRecursively(sub));
			} else {
				int end = findBracedSub(processingString, index);
				String sub = processingString.substring(index + 1, end - 1);
				index = end;
				sb.append(decodeRecursively(sub));
			}
		}
		return sb.toString();
	}

	private static int findBracedSub(String s, int index) {
		int end = index++;
		int[] braceNumber = new int[4];
		boolean allClear = false;
		while (!allClear) {
			char c = s.charAt(end);
			switch (c) {
			case '(':
				braceNumber[0]++;
				break;
			case ')':
				braceNumber[0]--;
				break;
			case '[':
				braceNumber[1]++;
				break;
			case ']':
				braceNumber[1]--;
				break;
			case '{':
				braceNumber[2]++;
				break;
			case '}':
				braceNumber[2]--;
				break;
			case '<':
				braceNumber[3]++;
				break;
			case '>':
				braceNumber[3]--;
				break;
			}
			allClear = braceNumber[0] == 0 && braceNumber[1] == 0 && braceNumber[2] == 0 && braceNumber[3] == 0;
			end++;
		}
		return end;
	}

}

第 3 题,DP,感觉动态规划总是要考的。

题目思想很简单,到达某个点的可能条数,就是这个点的上、下、左、右四个方向的可能条数全加到自己身上。

动态转移方程的计算必须按照一定顺序,这个顺序显然是海拔高度。

因此,就是先对所有的高度排序,然后从起点开始,每次一层一层地扫,把自己的条数加到自己上下左右的四个方向上的合法的点。

所谓合法,就是高度满足要求,且不越界。

我的实现没有排序,直接用了优先级队列。

Point 类实现了 Comparable 接口,比较的标准是海拔高度,小的优先,这样的话每次都是处理了海拔最小的才会算更高的(不然的话,计算高度为 5 的点有多少可能,由于 5 右边可能是 3,如果此时 3 的条数是不正确的,那么 5 的条数也是不正确的,因此必须先算高度低的,由于路径只能一路更大,所以当比它小的都算完了,它的值肯定也就唯一确定了)。

加入队列我用了 BFS,从起点开始,合法的点加入队列,直到队列空。

非常容易就过了。


import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
	public static void main(String args[]) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();
		int[][] g = new int[n][m];
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				g[i][j] = in.nextInt();
		int s_x = in.nextInt();
		int s_y = in.nextInt();
		int t_x = in.nextInt();
		int t_y = in.nextInt();

		final int[][] DIRECTIONS = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
		final int MOD = 1000000000;

		int[][] dp = new int[n][m];
		dp[s_x][s_y] = 1;
		PriorityQueue<Point> q = new PriorityQueue<>();
		q.add(new Point(s_x, s_y, g[s_x][s_y]));
		while (!q.isEmpty()) {
			Point p = q.poll();
			for (int k = 0; k < 4; k++) {
				int x = p.x + DIRECTIONS[k][0];
				int y = p.y + DIRECTIONS[k][1];
				if (x >= 0 && x < n && y >= 0 && y < m) {
					if (g[x][y] > g[p.x][p.y]) {
						Point pp = new Point(x, y, g[x][y]);
						if (!q.contains(pp))
							q.add(pp);
						dp[x][y] += dp[p.x][p.y];
						dp[x][y] %= MOD;
					}
				}
			}
		}
		System.out.println(dp[t_x][t_y]);
		in.close();
	}
}

class Point implements Comparable<Point> {
	int x;
	int y;
	int g;

	public Point(int x, int y, int g) {
		super();
		this.x = x;
		this.y = y;
		this.g = g;
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + g;
		result = prime * result + x;
		result = prime * result + y;
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Point other = (Point) obj;
		if (g != other.g)
			return false;
		if (x != other.x)
			return false;
		if (y != other.y)
			return false;
		return true;
	}

	@Override
	public int compareTo(Point o) {
		return Integer.compare(g, o.g);
	}

	

}

//4 5
//0 1 0 0 0
//0 2 3 0 0
//0 5 4 5 0
//0 6 7 6 0
//0 1 3 2
//Expected: 4
0 条回应