华为OD机试真题 2023 B + 2023 C&D 卷（JAVA&JS&Python&C++）

善若君: 可以先找墙再判断路径，如果小华或小明到聚餐地点间有墙，那无论那条路，一定被墙隔断，也就是和墙交叉在墙上某一点。 步骤1：判断哪些坐标是墙。 墙：将区域完全分割成两部分； 1. 首尾两端分别与外围相接 2. 自己形成一个环 判断哪些是墙之后，将墙所在的坐标全部加入到集合中。 步骤2：判断小华或小为到某个聚餐点的路径是否和墙交叉。 墙和路径的坐标都经过排序，路径可以直接走直角，将路径上的坐标与每个墙上的坐标比较，比较时可使用二分法，直到得到交叉点或不相交，有交叉点代表此路不通，break。如果所有的墙都拦不住，此路可行。

夏小森: 13行start==1为啥要break

weixin_44958345: function minSum(arr1, arr2, k) { let pairs = []; // 生成所有的组合，并计算它们之和 for (let num1 of arr1) { for (let num2 of arr2) { pairs.push(num1 + num2); } } // 对合进行排序 pairs.sort((a, b) => a - b); // 取前k个并计算它们之和 return pairs.slice(0, k).reduce((acc, curr) => acc + curr, 0);//acc累加器，curr是当前的值，0是从第0个开始 } // 输入 let array1 = [1, 1, 2]; let array2 = [1, 2, 3]; let k = 2; // 输出 console.log(minSum(array1.slice(1), array2.slice(1), k)); // 4[code=html] [/code]

李景景: 这里用hashset和treeset是不是一样？感觉并没有用到treeste有序的特性

善若君: 代码三： [code=java] static class UF { private int[] parent; private int size; public int getSize() { return size; } public UF(int size) { this.size = size; parent = new int[size]; for (int i = 0; i < size; i++) { parent[i] = i; } } public void union(int p, int q) { if (!isConnected(p, q)) { parent[q] = p; size--; } } public boolean isConnected(int p, int q) { return find(p) == find(q); } public int find(int x) { if (parent[x] != x) { parent[x] = find(parent[x]); } return parent[x]; } } [/code]