注册一亩三分地论坛,查看更多干货!
您需要 登录 才可以下载或查看附件。没有帐号?注册账号 
x
都是高频面经题
幸亏之前过了一遍地里的帖子,虽然米不够看不全 还是有帮助,基本都cover 住了
share一下 希望有助于后面面的同胞, 如果有帮助请加米
第一轮俩题
第一题 选3个距离某个餐馆最近的k个dasher
用min heap 秒过
第二题 就是 最短距离的点 类似力扣 药七七旧
A number of cities are arranged on a graph that has been divided up like an ordinary Cartesian plane.
Each city is located at an integral (x, y) coordinate intersection.
City names and locations are given in the form of three arrays: c, x, and y, which are aligned by the index to provide the city name (c[i]), and its coordinates, (x[i], y[i]).
Determine the name of the nearest city that
- shares either an x or a y coordinate with the queried city.
- If no other cities share an x or y coordinate, return 'NONE'.
- If two cities have the same distance to the queried city, q[i], consider the one with first lexicographically order name (i.e. 'ab' < 'aba' < 'abb') as the closest choice.
The distance is the Manhattan distance, the absolute difference in x plus the absolute difference in y.
我能作到O(NlogK+M*N)
地里有人提过这个题 我实现作了功课 所以很快就做完了
public List<String> closestStraightCity(String[] citys, int[] xs, int[] ys, String[] queryCitys) {
Map<String, int[]> cs = new HashMap<>(); // city name: (x,y)
Map<Integer, TreeMap<Integer, String>> X = new HashMap<>();
// x line: y1: city2 name( < city1name) y3: city3 name
Map<Integer, TreeMap<Integer, String>> Y = new HashMap<>();
// y line: x1: city1 name, x2: city2 name
int N = citys.length;
for (int i = 0; i < N; i++) {
int x = xs[i], y = ys[i];
String name = citys[i];
X.computeIfAbsent(x, k -> new TreeMap<>());
if (!X.get(x).containsKey(y) || name.compareTo(X.get(x).get(y)) < 0) {
X.get(x).put(y, name); // lexicographically order name
}
Y.computeIfAbsent(y, k -> new TreeMap<>());
if (!Y.get(y).containsKey(x) || name.compareTo(Y.get(y).get(x)) < 0) {
Y.get(y).put(x, name); // lexicographically order name
}
cs.put(name, new int[] {x, y});
}
Lis d(4, T) e(5, T) g(7, T)
New Menu sent by the Merchant:
a(1, T)
/ \
b(2, T) c(3, T)
/ | \ \
d(4, T) e(5, T) f(6, T) g(7, F)
Expected Answer: 2
Explanation: Node f is a newly-added node.
Node g changed from Active to inactive
public int f(Node n1, Node n2) {
int r = 0;
if (n1 == null && n2 == null) return r;
if (n1 == null || n2 == null || !equals(n2, n1)) r++;
Map<String, Node> child1 = mapChildren(n1);
Map<String, Node> child2 = mapChildren(n2);
for (String k : child1.keySet()) {
r += f(child1.get(k), child2.getOrDefault(k, null));
}
for (String k : child2.keySet()) {
if (!child1.containsKey(k)) {
r += f(null, child2.get(k));
}
}
return r;
}
private static Map<String, Node> mapChildren(Node n) {
Map<String, Node> map = new HashMap<>();
if (n == null) return map;
for (Node c : n.children) map.put(c.key, c);
return map;
}
public boolean equals(Node n1, Node n2) {
return n2.key.equals(n1.key) && n2.value == n1.value && n2.active == n1.active;
}
花了很多时间讨论corner cases 和 什么叫diff
没时间作完第二道,第二道是 Patching Array 力扣原题
总的来说 题库不大,但是需要尽快些,还需要解决compile error hackranker 真不习惯
如果事先没见过 当时思考的时间肯定不够, 确认理解问题就会花很多时间。
所以还是事先好好看看地里的帖子。
估计黄了
希望对后边的能有帮助 过关斩将
求米
|