我的题⽬：
-
songs duration找到⼀个pair让duration sum等于target time - 30，给的是那种List<List> [[30, 1], [60, 4], [50, 3]]，返回歌曲的ID，还有一个条件就是如果有好几对符合，返回的pair得是其中最长song duration最大的⼀个pair，要是压根没有的话就返回empty list。
所以其实就是有点corner case的2 sum啦～ -
给俩list, 存的foreground 跟 background程序需要消耗的memory，还给定了memory的limit，选出foreground跟background程序pair which can optimize the usage of limited memory (btw, 可能有很多种这个pair，得都输出来)。
这道题 其实就是2 sum closest，只不过限制就是得输出所有optimal pair。
再就是15分钟解释两题思路路 并且给时间复杂度
最近亚麻社招OA就是这8道题，我和室友遇到的都是这8道题里的。下⾯的题⽬描述和代码都是我做OA之前总结和⾃己写的，可能某些题的signature和原题有出入，欢迎指正～
class AmazonOA {
// https://leetcode.com/company/amazon/
// 1. MST
// 2. reorder log
// 3. 组装零件/⽂文件合并
// 4. Amazon Fresh送货(k closest points to origin)'
// 5. ⾛走迷宫(0,1,9 的2D Array， BFS)
// 6. ⽆无⼈人机送货/前后台进程 (Two Sum Closest)
// 7. 选合适的⾳音乐/卡⻋车装货物 (Two Sum)
// 8. Partition Label (LC 原题) ???
// 1. MST 城市建路路题。minimum spanning tree，
// https://www.1point3acres.com/bbs/forum.php?
// mod=viewthread&tid=498030
// 就是给的road是重复的
// 题⽬目意思是有⼀一定数量量的城市，城市之间已经有了了⼀一些道路路。还有⼀一些可以供选
// 择的道路路来建设。每个新建的道路路有 cost。问如果要连接所有的城市，新建路路的最⼩小的
/// cost 是多少。举个栗栗⼦子：
// Input 如下：
// numTotalAvailableCities = 6
// numTotalAvailableRoads = 3
// roadsAvailable = [[1, 4], [4, 5], [2, 3]]
// numNewRoadsConstruct = 4
// costNewRoadsConstruct = [[1, 2, 5], [1, 3, 10], [1, 6, 2],
// [5, 6, 5]]
// Output 应该是： 7
public int getMinimumCostConstruct(int n, int numTotalAvaiableRoads, List<List<Integer>> roadsAvailable,
int numNewRoadsContruct, List<List<Integer>> costNewRoadsConstruct) {
if (n < 2) {
return 0;
}
// Initialize available roads - O(Nn)
UnionFind uf = new UnionFind(n + 1);
int groupCount = n;
for (List<Integer> road : roadsAvailable) {
int i = road.get(0);
int j = road.get(1);
groupCount -= uf.union(i, j) ? 1 : 0;
}
// Initialize new roads - O(MlogM)
PriorityQueue<Node> heap = new PriorityQueue<>();
for (List<Integer> road : costNewRoadsConstruct) {
heap.offer(new Node(road.get(0), road.get(1), road.get(2)));
}
// construct roads - O(Mn)
int cost = 0;
while (!heap.isEmpty() && groupCount > 1) {
Node road = heap.poll();
if (uf.union(road.x, road.y)) {
groupCount--;
cost += road.val;
}
}
return groupCount > 1 ? -1 : cost;
}
class UnionFind {
int[] arr;
public UnionFind(int size) {
arr = new int[size];
for (int i = 0; i < size; i++) {
arr[i] = i;
}
}
private int root(int i) {
while (arr[i] != i) {
i = arr[i];
}
return i;
}
public boolean find(int i, int j) { // O(n)
return root(i) == root(j);
}
public boolean union(int i, int j) { // O(n)
if (find(i, j)) {
return false;
} else {
arr[root(i)] = j;
return true;
}
}
}
// 2. reorder log，
// LC 937。 https://leetcode.com/problems/reorder-log-files/
// Reorder the logs so that all of the letter-logs come before
// any digit-log.
// The letter-logs are ordered lexicographically ignoring
// identifier, with the identifier used in case of ties.
// The digit-logs should be put in their original order.
// Input: ["a1 9 2 3 1","g1 act car","zo4 4 7","ab1 off key
// dog","a8 act zoo"]
// Output: ["g1 act car","a8 act zoo","ab1 off key dog","a1 9
// 2 3 1","zo4 4 7"]
public String[] reorderLogFiles(String[] logs) {
Arrays.sort(logs, new FileComparator());
return logs;
}
class FileComparator implements Comparator<String> {
@Override
public int compare(String a, String b) {
String[] aa = a.split(" ", 2);
String[] bb = b.split(" ", 2);
String contentA = aa[1];
String contentB = bb[1];
boolean AisDigitFile = isDigitFile(contentA);
boolean BisDigitFile = isDigitFile(contentB);
if (AisDigitFile && BisDigitFile) {
return 0;
} else if (AisDigitFile) {
return 1;
} else if (BisDigitFile) {
return -1;
} else {
int compareContent = contentA.compareTo(contentB);
if (compareContent == 0) {
return aa[0].compareTo(bb[0]);
} else {
return compareContent;
}
}
}
private boolean isDigitFile(String content) {
return Character.isDigit(content.charAt(0));
}
}
// 3. 零件装配/合并part
// 给⼀一个array表示零件的size，每次可以把两个组装在⼀一起。每次组装的cost是
// 两个size之和。就是数字可能重复
// 新组装出来零件的size也是这两个⼩小零件size之和。问把所有零件组装成⼀一整个
// 的min cost。
public int minSum(int[] array) {
if (array == null || array.length < 2) {
return 0;
}
PriorityQueue<Integer> heap = new PriorityQueue<>();
for (int x : array) {
heap.offer(x);
}
int cost = 0;
while (!heap.isEmpty()) { // keep it as least 2
int cur = heap.poll() + heap.poll();
cost += cur;
if (heap.isEmpty()) {
break;
} else {
heap.offer(cur);
}
}
return cost;
}
// 4. 卡⻋车送货的题 (k closest points to origin)
// N个地点List<List<Integer>> 地点的坐标, M代表需要送的数量量
// output：⼀一个List<List<Integer>> 代表送货的地点坐标x,y, 其实就是让
// 你计算距离卡⻋车最近的M个地点.
// eg. N = 3, M = 2, List<List<Ingeter>> 是 [[2,3][3,4],
// [1,-3]] output: [[2,3],[1,-3]]
public List<List<Integer>> kClosest(List<List<Integer>> points, int K) {
List<List<Integer>> res = new ArrayList<>();
PriorityQueue<Node> heap = new PriorityQueue<>(K, Collections.<Node>reverseOrder());
for (List<Integer> point : points) {
int dis = (int) (Math.pow(point.get(0), 2) + Math.pow(point.get(1), 2));
if (heap.size() < K) {
heap.offer(new Node(point.get(0), point.get(1), dis));
} else if (dis < heap.peek().val) {
heap.poll();
heap.offer(new Node(point.get(0), point.get(1), dis));
}
}
while (!heap.isEmpty()) {
Node node = heap.poll();
List<Integer> cur = new ArrayList<>();
cur.add(node.x);
cur.add(node.y);
res.add(cur);
}
return res;
}
// 5. robot removes 障碍
// 9 is obstacle, 1 flat lot can move, 0 trenches can't move.
// Find the minimum val to reach obstacle in order to remove it
// e.g.
// [1,1,1]
// [1,0,0]
// [1,9,1]
// Output: 3
public int minSteps(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0 || matrix[0][0] == 0) {
return -1;
}
if (matrix[0][0] == 9) {
return 0;
}
PriorityQueue<Node> queue = new PriorityQueue<>();
queue.offer(new Node(0, 0, 0));
boolean[][] visited = new boolean[matrix.length][matrix[0].length];
visited[0][0] = true;
while (!queue.isEmpty()) {
for (Node nei : getNeighbors(queue.poll(), matrix, visited)) {
if (matrix[nei.x][nei.y] == 9) {
return nei.val;
}
queue.offer(nei);
visited[nei.x][nei.y] = true;
}
}
return -1;
}
private List<Node> getNeighbors(Node node, int[][] matrix, boolean[][] visited) {
List<Node> neis = new ArrayList<>();
int[][] dir = new int[][] { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
for (int[] d : dir) {
Node nei = new Node(node.x + d[0], node.y + d[1], node.val + 1);
if (nei.x < 0 || nei.x >= matrix.length || nei.y < 0 || nei.y >= matrix[0].length
|| visited[nei.x][nei.y] || matrix[nei.x][nei.y] == 0) {
continue;
}
neis.add(nei);
}
return neis;
}
class Node implements Comparable<Node> {
int x;
int y;
int val;
public Node(int i, int j, int s) {
x = i;
y = j;
val = s;
}
@Override
public int compareTo(Node another) {
if (val == another.val) {
return 0;
}
return val < another.val ? -1 : 1;
}
}
// 6. (Two Sum Closest)
// Two sum 的变种，回答位置，多个答案，选出包含最⼤数字的答案。
// - 给两个array和⼀个K，每个array⾥面各选⼀个数，要求sum<=K的最⼤大组
// - 给一个去程route的list和⼀一个回城route的list，还有⼀一个来回路程的上
// 限max。求来回路程最接近于max的route combination。
// foreground and background program / forward and return
// flight 那道题暴力解的
public List<Integer> solution(int target, List<Integer> foregroundSizes, List<Integer> backgroundSizes) { // O(n^2)
List<Integer> res = new ArrayList<>();
res.add(0);
res.add(0);
int max = 0;
for (int i = 0; i < foregroundSizes.size(); i++) {
for (int j = 0; j < backgroundSizes.size(); j++) {
int cur = foregroundSizes.get(i) + backgroundSizes.get(j);
if (cur <= target && cur > max) {
max = cur;
res.set(0, i);
res.set(1, j);
}
}
}
return max == 0 ? new ArrayList<Integer>() : res;
}
// 7. 卡车装箱 (TWO SUM)
// e.g. truck capacity - 90 / reserved capacity - 30 / paCkage
// capacities - [10, 25, 35, 60]
// 要求返回 [1, 2] (25和35的索引)
public List<Integer> solution(int trunkSpace, List<Integer> itemSpaces) { // O(n)
List<Integer> res = new ArrayList<>();
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < itemSpaces.size(); i++) {
Integer index = map.get(trunkSpace - itemSpaces.get(i));
if (index != null) {
res.add(index);
res.add(i);
break;
} else {
map.put(itemSpaces.get(i), i);
}
}
return res;
}
// 8. Partition label
public List<Integer> partitionLabels(String S) { // O(nlogn)
List<Integer> res = new ArrayList<>();
int[][] ranges = new int[26][];
for (int i = 0; i < S.length(); i++) {
int loc = S.charAt(i) - 'a';
if (ranges[loc] == null) {
ranges[loc] = new int[] { i, i };
} else {
ranges[loc][1] = i;
}
}
List<int[]> sorted = new ArrayList<>();
for (int[] range : ranges) {
if (range != null) {
sorted.add(range);
}
}
Collections.sort(sorted, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if (o1[0] == o2[0]) {
return 0;
}
return o1[0] < o2[0] ? -1 : 1;
}
});
int[] cur = sorted.get(0);
for (int[] range : sorted) {
if (range[0] <= cur[1]) {
cur[1] = Math.max(range[1], cur[1]);
} else {
res.add(cur[1] - cur[0] + 1);
cur = range;
}
}
res.add(cur[1] - cur[0] + 1);
return res;
}
public List<Integer> partitionLabels2(String S) { // O(n)
int[] last = new int[26];
for (int i = 0; i < S.length(); ++i) {
last[S.charAt(i) - 'a'] = i;
}
int start = 0;
int end = 0;
List<Integer> res = new ArrayList<>();
for (int i = 0; i < S.length(); i++) {
end = Math.max(end, last[S.charAt(i) - 'a']);
if (i == end) {
res.add(end - start + 1);
start = end + 1;
}
}
return res;
}
}