华为笔试4.20记录_按照路径替换二叉树

春招惨痛，目前仍颗粒无收。
做了阿里、字节、华为的笔试，除了字节是LeetCode风格，阿里华为都偏向ACM模式，而这正是我不熟悉的。
前车之鉴，后事之师，教训如被人接受，此经验可贵十倍。因此记录下笔试题目。

1、新员工的答题情况（100分）

新员工入职公司，参加考试，其中判断题10道（每题2分），单选题10道（每题4分），多选题5道（每题8分）。只能顺序作答，答完题不知道对错，答对得分，答错不得分。答错累计三道，则终止考试。输入考试结果分数，输出答题可能情况个数。

补充：关于回溯和DFS

在具体的做题时，似乎回溯总是和DFS一起出现，但两者到底是什么关系呢？
借鉴知乎用户Aetherus的答案 回溯和DFS的区别，
“回溯的关键不在于递归，而在于状态。在回溯算法向前的每一步，你都会去设置某个状态，而当向前走走不通的时候回退，此时需要把之前设置的状态撤销掉。DFS 只是找某个或某些满足条件的东西而已，找到就返回，找不到拉倒，没状态啥事儿。”
语言淳朴，浅显易懂。

所以本题采用回溯的思想，以DFS为工具。

public class Main {
	// 按顺序的题目分数值
	public static int[] score = {2,2,2,2,2,2,2,2,2,2,4,4,4,4,4,4,4,4,4,4,8,8,8,8,8};
	private static int N; // 输入的最终成绩
	private static int sum; // 存储答题情况值用于输出
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		backTrace(0, 0, 0);
		System.out.print(sum);
	}

	/* @parameter
	 * index对应题目序号
	 * score对应当前分数
	 * err表示累计错误题数
	 */
	public static void backTrace(int index, int score, int err) {
		if (err >= 3) return;
		// 满足输入分数
		if (score == N) {
			sum++; // 答题情况+1
			return;
        } 
        // 不满足且不可能再满足输入分数
        if (score > N) return;
        
        for (int i = index; i < score.length; i++) {
        	// 首先假设这题答对了
			score += score[i];
			backTrace(i + 1, score, err); // DFS，接着往下做
			// 上面的函数返回了，说明要么已经符合条件，sum自增1
			// 要么不满足输入分数或error达到三个，返回了
			score -= score[i]; // 把前面加上分数的减去
			err++; // 错误题数自增
		}
	}
}
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

2、按照路径替换二叉树（200分）

数据输入有三行：
第一行以[1,2,0,3,5]构造原二叉树（0表示无结点，所以1是根结点，2是左子节点，无右子节点，3、5分别是2的左右子节点）。
第二行以\1\2\5指定要替换的根结点（假设同一父节点的两子节点的值不能相同）。
第三行给出要替换进去的二叉树[4,7,8]。
题目要求输出替换完后的二叉树，但与构造时不同，输出的二叉树构造数组不包含0，即应输出[1,2,3,4,7,8]。