阿里秋招笔试两道编程题（2021-08-18）

恭喜发现宝藏！微信搜索公众号【TechGuide】实时互联网大厂笔经面经闪电速递！ 作者@TechGuide【全网同名】 点赞再看，养成习惯，您动动手指对原创作者意义非凡🤝

番哥提示

1. 阿里的题也是会和高中的数学知识相结合，有些比较巧妙。
2. 一小时两题，很考验一次通过率。

第一道：求缺失正方形顶点（100%） 题目描述

找到非对角点的那一个点，设为（x0, y0), 另外两个对角点为（x1, y1), (x2, y2)，求 (x, y);

思路解析

向量法： 先找3个点的交点，记为a, 剩余两个点为b，c，问题为求d。 向量法: 由 ad = ab + ac 可接解出 d = ab + ac + a

参考代码： Java版本

public static int[] pair(int x1, int y1, int x2, int y2, int x3, int y3) {
        int[] arr = new int[2];
        if ((x1 - x2) * (x1 - x3) + (y1 - y2) * (y1 - y3) == 0) {
            arr[0] = x2 + x3 - x1;
            arr[1] = y2 + y3 - y1;
            return arr;
        }
        if ((x2 - x1) * (x2 - x3) + (y2 - y1) * (y2 - y3) == 0) {
            arr[0] = x1 + x3 - x2;
            arr[1] = y1 + y3 - y2;
            return arr;
        }
        if ((x3 - x1) * (x3 - x2) + (y3 - y1) * (y3 - y2) == 0) {
            arr[0] = x1 + x2 - x3;
            arr[1] = y1 + y2 - y3;
            return arr;
        }
        return arr;
    }

Python版本

arr = [[-1,1],[0,0],[0,1]]
idx = [[0,1,2],[1,0,2],[2,0,1]]
for a, b, c in idx:
    ab = [ arr[b][0] - arr[a][0], arr[b][1] - arr[a][1]] 
    ac = [ arr[c][0] - arr[a][0], arr[c][1] - arr[a][1]] 
    res = sum([x * y for x, y in zip(ab, ac)])
    if res == 0:
        res = [x + y for x, y in zip(ab, ac)]
        res = [res[0] + arr[a][0], res[1] + arr[a][1]]
        print('%d %d' % (res[0], res[1]))
        break

第二道： 图（题目待补充，可以尝试理解思路，两种算法实现供参考） 思路解析

回溯法： 数据处理， 将人工通道和天然通道合并为代码中的 channels, 不可达的点专门用数组表示，问题就变得简单了 使用used数组表示，是否之前到达过该点，如果到达过，则返回；

示例：

6 2 2 0
9 1 6 3 6
2 5 1
3 6 2
1 5 3
6 5 9

参考代码 Java版本

public class Solution2 {
    private static int rst = Integer.MAX_VALUE;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for (int i = 0; i