第一题
A pizza shop offers n pizzas along with m toppings. A customer plans to spend around x coins. The customer should order exactly one pizza, and may order zero, one or two toppings. Each topping may be order only once.
Given the lists of prices of available pizzas and toppings, what is the price closest to x of possible orders? Here, a price said closer to x when the difference from x is the smaller. Note the customer is allowed to make an order that costs more than x.
Example 1:
Input: pizza = [800, 850, 900], topping = [100, 150], x = 1000
Output: 1000
Explanation:
The customer can spend exactly 1000 coins (two possible orders).
Example 2:
Input: pizza = [850, 900], topping = [200, 250], x = 1000
Output: 1050
Explanation:
The customer may make an order more expensive than 1000 coins.
Example 3:
Input: pizza = [1100, 900], topping = [200], x = 1000
Output: 900
Explanation:
The customer should prefer 900 (lower) over 1100 (higher).
Example 4:
Input: pizza = [800, 800, 800, 800], topping = [100], x = 1000
Output: 900
Explanation:
The customer may not order 2 same toppings to make it 1000.
Constraints:
Customer’s budget: 1 <= x <= 10000
Number of pizzas: 1 <= n <= 10
Number of toppings: 0 <= m <= 10
Price of each pizza: 1 <= pizza[i] <= 10000
Price of each topping: 1 <= topping[i] <= 10000
The total price of all toppings does not exceed 10000.
第二题
Given an array of integers nums and an int target, return indices of the two numbers such that they add up to a target - 30.
Conditions:
- You will pick exactly 2 numbers.
- You cannot pick the same element twice.
- If you have muliple pairs, select the pair with the largest number.
Example 1:
Input: nums = [1, 10, 25, 35, 60], target = 90
Output: [2, 3]
Explanation:
nums[2] + nums[3] = 25 + 35 = 60 = 90 - 30
Example 2:
Input: nums = [20, 50, 40, 25, 30, 10], target = 90
Output: [1, 5]
Explanation:
nums[0] + nums[2] = 20 + 40 = 60 = 90 - 30
nums[1] + nums[5] = 50 + 10 = 60 = 90 - 30
You should return the pair with the largest number.
我的解法
public class Main {
public static int[] findPair(int[] nums, int target) {
target -= 30;
Map<Integer, Integer> map = new HashMap<>();
int[] result = {-1, -1};
for (int i = 0; i < nums.length; i++) {
Integer idx = map.get(target - nums[i]);
if (idx != null) {
// first valid pair
if (result[0] == -1) {
result[0] = idx;
result[1] = i;
}
// we already have a valid pair
// need to choose the pair with the largest value
else if (Math.max(nums[idx], nums[i]) > Math.max(nums[result[0]], nums[result[1]])) {
result[0] = idx;
result[1] = i;
}
}
map.put(nums[i], i);
}
return result;
}
public static void main(String[] args) {
test(new int[]{1, 10, 25, 35, 60}, 90);
test(new int[]{20, 50, 40, 25, 30, 10}, 90);
test(new int[]{5, 55, 40, 20, 30, 30}, 90);
}
private static void test(int[] nums, int target) {
System.out.println(Arrays.toString(findPair(nums, target)));
}
}
Time complexity: O(n).
Space complexity: O(n).
第三题
Given an undirected graph with n nodes labeled 1…n. Some of the nodes are already connected. The i-th edge connects nodes edges[i][0] and edges[i][1] together. Your task is to augment this set of edges with additional edges to connect all the nodes. Find the minimum cost to add new edges between the nodes such that all the nodes are accessible from each other.
Input:
- n, an int representing the total number of nodes.
- edges, a list of integer pair representing the nodes already connected by an edge.
- newEdges, a list where each element is a triplet representing the pair of nodes between which an edge can be added and the cost of addition, respectively (e.g. [1, 2, 5] means to add an edge between node 1 and 2, the cost would be 5).
Example 1:
Input: n = 6, edges = [[1, 4], [4, 5], [2, 3]], newEdges = [[1, 2, 5], [1, 3, 10], [1, 6, 2], [5, 6, 5]]
Output: 7
Explanation:
There’re 3 connected components [1, 4, 5], [2, 3] and [6].
We can connect these components into a single component by connecting node 1 to node 2 and node 1 to node 6 at a minimum cost of 5 + 2 = 7.
我的解法用了Kruskal’s MST algorithm
public class Main {
public static void main(String[] args) {
int n = 6;
int[][] edges = {{1, 4}, {4, 5}, {2, 3}};
int[][] newEdges = {{1, 2, 5}, {1, 3, 10}, {1, 6, 2}, {5, 6, 5}};
System.out.println(minCost(n, edges, newEdges));
}
public static int minCost(int n, int[][] edges, int[][] newEdges) {
UF uf = new UF(n + 1); // + 1 because nodes are 1-based
for (int[] edge : edges) {
uf.union(edge[0], edge[1]);
}
Queue<int[]> pq = new PriorityQueue<>(newEdges.length, (e1, e2) -> Integer.compare(e1[2], e2[2]));
pq.addAll(Arrays.asList(newEdges));
int totalCost = 0;
// 2 because nodes are 1-based and we have 1 unused component at index 0
while (!pq.isEmpty() && uf.count != 2) {
int[] edge = pq.poll();
if (!uf.connected(edge[0], edge[1])) {
uf.union(edge[0], edge[1]);
totalCost += edge[2];
}
}
return totalCost;
}
}
class UF {
private int[] parent; // parent[i] = parent of i
private byte[] rank; // rank[i] = rank of subtree rooted at i (never more than 31)
public int count; // number of connected components
public UF(int n) {
if (n < 0) throw new IllegalArgumentException();
parent = new int[n];
rank = new byte[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
count = n;
}
public int find(int p) {
while (p != parent[p]) {
parent[p] = parent[parent[p]];
p = parent[p];
}
return p;
}
public void union(int p, int q) {
int pr = find(p);
int qr = find(q);
if (pr == qr) return;
if (rank[pr] < rank[qr]) {
parent[pr] = qr;
} else {
parent[qr] = pr;
if (rank[pr] == rank[qr]) rank[pr]++;
}
count--;
}
public boolean connected(int p, int q) {
return find(p) == find(q);
}
}
参考