You work for a pharmaceutical company that produces liquid medicines. Patients requiring these medications often require different amounts. To package the medication for delivery, you can choose between different sets of containers. Each container set specifies the sizes of containers it allows. For example, set 1 might contain containers with size 200 ml and 300 ml, while set 2 might use containers with size 400 ml, 300 ml and 100 ml.

When fulfilling a customer order for a given amount, a single container must be used and filled completely. If a container does not exist that matches the required amount, the next largest container is used. The extra medication included in that larger container (i.e., the size of the container minus required amount) is considered waste.

Your job is to evaluate different sets of containers and find the set that creates the minimum amount of waste over a set of orders. Return the 1-based index of the optimal container set. In case of a tie, return the lowest-indexed set.

Example

requirements = [10, 15]
containers = [
 [5, 30, 20, 10],
 [10, 5, 15, 20, 30],
]

Set 0: order 10 -> 10 (waste 0); order 15 -> 20 (waste 5). Total 5.
Set 1: order 10 -> 10 (waste 0); order 15 -> 15 (waste 0). Total 0.
Answer: 2 (1-based).

解法

每个 set 排序；对每个订单二分找 ≥ 需求的最小容器，找不到则跳过该 set；累加每个 set 的浪费，取最小。复杂度 O(S * (C log C + R log C))。

import bisect

def minWasteSet(requirements, containersList):
    best_idx, best_waste = -1, float('inf')
    for idx, containers in enumerate(containersList, start=1):
        sc = sorted(containers)
        waste = 0
        ok = True
        for r in requirements:
            pos = bisect.bisect_left(sc, r)
            if pos == len(sc):
                ok = False
                break
            waste += sc[pos] - r
        if ok and waste < best_waste:
            best_waste = waste
            best_idx = idx
    return best_idx

import java.util.*;

class Solution {
    static int minWasteSet(int[] req, int[][] sets) {
        int bestIdx = -1;
        long bestWaste = Long.MAX_VALUE;
        for (int s = 0; s < sets.length; s++) {
            int[] sc = sets[s].clone();
            Arrays.sort(sc);
            long waste = 0;
            boolean ok = true;
            for (int r : req) {
                int lo = 0, hi = sc.length;
                while (lo < hi) {
                    int mid = (lo + hi) >>> 1;
                    if (sc[mid] < r) lo = mid + 1; else hi = mid;
                }
                if (lo == sc.length) { ok = false; break; }
                waste += sc[lo] - r;
            }
            if (ok && waste < bestWaste) { bestWaste = waste; bestIdx = s + 1; }
        }
        return bestIdx;
    }
}

#include <bits/stdc++.h>
using namespace std;

int minWasteSet(vector<int>& requirements, vector<vector<int>>& containersList) {
 int bestIdx = -1;
 long long bestWaste = LLONG_MAX;
 for (int s = 0; s < (int) containersList.size(); s++) {
 vector<int> sc = containersList[s];
 sort(sc.begin(), sc.end());
 long long waste = 0;
 bool ok = true;
 for (int r : requirements) {
 auto it = lower_bound(sc.begin(), sc.end(), r);
 if (it == sc.end()) { ok = false; break; }
 waste += *it - r;
 }
 if (ok && waste < bestWaste) { bestWaste = waste; bestIdx = s + 1; }
 }
 return bestIdx;
}

An organization is made up of n people. The hierarchy is represented as a tree where parent[i] is the parent of node i; parent[0] = -1 is the root.

A directive issued from person p propagates this way:

• The issuer sends the directive to direct children in ascending order of indices.
• For each child, the directive fully propagates through that child's subtree before moving to the next child.
• Each child node propagates to its own children the same way.

For each query (p, k), return the k-th person to receive the directive starting from p (1-indexed counting the issuer as position 1). If fewer than k people exist in p's subtree, return -1.

Example: n=9, parent=[-1, 0, 0, 1, 1, 1, 2, 6, 7], queries=[(0, 4), (1, 3), (5, 1), (6, 2)] -> [5, 5, 6, 8].

解法

DFS 整棵树(孩子按升序)，记录欧拉序的 enter[u] 和 leave[u]。在 p 子树内第 k 个节点就是 tour[enter[p] + k - 1]，需保证下标 ≤ leave[p]。复杂度 O(n + q)。

def chainOfCommand(n, parent, queries):
    from collections import defaultdict
    children = defaultdict(list)
    root = 0
    for i, p in enumerate(parent):
        if p == -1:
            root = i
        else:
            children[p].append(i)
    for p in children:
        children[p].sort()

    enter, leave = [0] * n, [0] * n
    tour = []

    def dfs(u):
        enter[u] = len(tour)
        tour.append(u)
        for c in children[u]:
            dfs(c)
        leave[u] = len(tour) - 1

    dfs(root)

    out = []
    for p, k in queries:
        idx = enter[p] + k - 1
        if idx > leave[p]:
            out.append(-1)
        else:
            out.append(tour[idx])
    return out

import java.util.*;

class Solution {
    int[] enter, leave;
    List<Integer> tour;
    List<List<Integer>> children;

    void dfs(int u) {
        enter[u] = tour.size();
        tour.add(u);
        for (int c : children.get(u)) dfs(c);
        leave[u] = tour.size() - 1;
    }

    int[] chainOfCommand(int n, int[] parent, int[][] queries) {
        children = new ArrayList<>();
        for (int i = 0; i < n; i++) children.add(new ArrayList<>());
        int root = 0;
        for (int i = 0; i < n; i++) {
            if (parent[i] == -1) root = i;
            else children.get(parent[i]).add(i);
        }
        for (List<Integer> l : children) Collections.sort(l);
        enter = new int[n];
        leave = new int[n];
        tour = new ArrayList<>();
        dfs(root);
        int[] out = new int[queries.length];
        for (int q = 0; q < queries.length; q++) {
            int p = queries[q][0], k = queries[q][1];
            int idx = enter[p] + k - 1;
            out[q] = (idx > leave[p]) ? -1 : tour.get(idx);
        }
        return out;
    }
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
    vector<int> enter_, leave_, tour;
    vector<vector<int>> children;

    void dfs(int u) {
        enter_[u] = tour.size();
        tour.push_back(u);
        for (int c : children[u]) dfs(c);
        leave_[u] = tour.size() - 1;
    }

public:
    vector<int> chainOfCommand(int n, vector<int>& parent, vector<pair<int,int>>& queries) {
        children.assign(n, {});
        int root = 0;
        for (int i = 0; i < n; i++) {
            if (parent[i] == -1) root = i;
            else children[parent[i]].push_back(i);
        }
        for (auto& l : children) sort(l.begin(), l.end());
        enter_.assign(n, 0);
        leave_.assign(n, 0);
        tour.clear();
        dfs(root);
        vector<int> out;
        for (auto& [p, k] : queries) {
            int idx = enter_[p] + k - 1;
            out.push_back(idx > leave_[p] ? -1 : tour[idx]);
        }
        return out;
    }
};

In this game, there are a number asteroids arranged in line. These asteroids can all move either left or right on the line and all asteroids move at the same speed. Each asteroid also has a size associated with it. If two asteroids that are next to each other move towards each other, they will collide. In this case, the larger asteroid will destroy the smaller one. If both asteroids have the same size, then both asteroids are destroyed. The purpose of this game is to determine which asteroids remain after all possible collisions occur. Thus, given an array size of length n, where size[i] is the size of the i^th asteroid and a second array direction of size n where direction[i] is the direction of the i^thasteroid where 0 indicates moving left and 1 indicates moving right. Given these inputs, find which asteroids remain after all collisions have taken place. Return an array containing the sizes of the remaining asteroids (in order). If no asteroids remain, then return an empty array.

Constraints

A mysterious secrete for now

Example 1

Input:

size = [4, 5, 6, 7, 4]
direction = [1, 1, 1, 0, 1, 0]

Output:

[6, 7]

Explanation: A direction value if 1 indicates moving to the right and a direction value of 0 indicates moving to the left. Collisions:

• size[1], size[2]: 5 4 so size[4] vanishes and there are no more asteroids to the right of size[4] Only size[2] and size[3] remain. Return them in the order they appear in size [6, 7].

Example 2

Input:

size = [3, 4, 2, 1, 6, 4, 5]
direction = [1, 0, 1, 0, 1, 1, 0]

Output:

[4, 2, 6]

Explanation: The initial size array = [3, 4, 2, 1, 6, 4, 5] with direction = [1, 0, 1, 0, 1, 1, 0] The collisions are between asteroids with sizes:

• (3, 4) 4 remains
• (2, 1) 2 remains
• (4, 5) 5 remains (no more collision to go)
• (6, 5) 6 remains The remaining asteroids are [4, 2, 6].

Example 3

Input:

size = [5, 5]
direction = [1, 0]

Output:

[]

Explanation: The initial size array = [5, -5] with direction = [1, 0] The first and second asteroids collide. Since they are of the same size, both of them disappear .

解法

单调栈模拟。把 direction == 1 视为正向(右行)，direction == 0 视为反向(左行)。维护栈：遇到右行直接入栈；遇到左行则不断与栈顶右行碰撞(若栈顶 < 当前，弹出栈顶继续；等于则两者都消失；大于则当前消失)，否则入栈。复杂度 O(n)。

from typing import List

def asteroid_game(size: List[int], direction: List[int]) -> List[int]:
    stk = []
    for s, d in zip(size, direction):
        alive = True
        while alive and d == 0 and stk and stk[-1][1] == 1:
            top_s, _ = stk[-1]
            if top_s < s:
                stk.pop()
            elif top_s == s:
                stk.pop()
                alive = False
            else:
                alive = False
        if alive:
            stk.append((s, d))
    return [s for s, _ in stk]

import java.util.*;

class Solution {
    int[] asteroidGame(int[] size, int[] direction) {
        Deque<int[]> stk = new ArrayDeque<>();
        for (int i = 0; i < size.length; i++) {
            int s = size[i], d = direction[i];
            boolean alive = true;
            while (alive && d == 0 && !stk.isEmpty() && stk.peek()[1] == 1) {
                int[] top = stk.peek();
                if (top[0] < s) stk.pop();
                else if (top[0] == s) { stk.pop(); alive = false; }
                else alive = false;
            }
            if (alive) stk.push(new int[]{s, d});
        }
        int[] res = new int[stk.size()];
        int idx = res.length - 1;
        for (int[] a : stk) res[idx--] = a[0];
        return res;
    }
}

class Solution {
public:
    vector<int> asteroidGame(vector<int>& size, vector<int>& direction) {
        vector<pair<int, int>> stk;
        for (size_t i = 0; i < size.size(); ++i) {
            int s = size[i], d = direction[i];
            bool alive = true;
            while (alive && d == 0 && !stk.empty() && stk.back().second == 1) {
                if (stk.back().first < s) stk.pop_back();
                else if (stk.back().first == s) { stk.pop_back(); alive = false; }
                else alive = false;
            }
            if (alive) stk.push_back({s, d});
        }
        vector<int> res;
        for (auto& p : stk) res.push_back(p.first);
        return res;
    }
};

In this game, a player begins on a two-dimensional grid of size n × m. One cell of the grid is marked as the end and the player wants to reach this cell by moving up, down, left or right. However, some cells are occupied by obstacles. The goal of the player is to reach the end cell using a path that maximizes the minimum distance from any obstacle along that path. The distance between any two points on the grid with coordinates (x1, y1) and (x2, y2) is calculated as |x1 - x2| + |y1 - y2|, where |a| is the absolute value of integer a. Notes: One can visit a cell with an obstacle if necessary, i.e. no other path exists.

• A cell can be visited only once on a given path. Function Description Complete the function findBestPath in the editor below. findBestPath has the following parameters:
• int n: the number of rows in the grid
• int m: the number of columns in the grid
• int startRow: the row index of the starting position
• int startColumn: the column index of the starting position
• int endRow: the row index of the ending position
• int endColumn: the column index of the ending position
• int[] obstacleRow: the row index of the ith obstacle
• int[] obstacleColumn: the column index of the ith obstacle Returns int: the largest possible minimum distance from an obstacle in any path from the starting point to the ending point

Constraints

• 2 ≤ n, m ≤ 200
• 0 ≤ startRow, endRow < n
• 0 ≤ startColumn, endColumn < m
• 0 ≤ number of obstacles = n * m - 2
• 0 ≤ obstacleRow[i] < n
• 0 ≤ obstacleColumn[i] < m
• No obstacle at any start cell
• There is exactly one end cell
• There is at least one obstacle

Example 1

Input:

n = 4
m = 4
startRow = 0
startColumn = 0
endRow = 3
endColumn = 3
obstacleRow = [0, 1]
obstacleColumn = [3, 2]

Output:

2

Explanation: Consider the following grid of size 4*4 where empty cells are free, 'S' indicates the start, 'E' indicates the end and 'X' indicates an obstcle: The optimal path is shown in the 'cell' column. Note, the cell coordinates are given as (r, c) where r is the index of the row and c is the index of the column. Thus, the coordinates of any of the nearest obstacles is in 'Obstacle'. Coordinates of any of the nearest obstacles thus, the obstacles in the above example are located at (0, 3) and (1,2). Coordinates of any of the nearest obstacles is in 'Obstacle'.

• The blocked cell (1, 2) is also 3 units distant. Return 2, the closest distance to any obstacle along the path.

There is a matrix of size nxn and we are given a threshold value k. We need to make a function which returns the highest sub square matrix we can find which has a total sum less than k and the sub square matrix should be able to occupy the complete matrix at every possible position. For example, imagine we have a matrix of size 3x3 1 1 1 1 1 1 1 1 1 Where k is 4. We would like to return the length of the valid sub square matrix which sums up to less than k. So in this case, the way we would compute the result is first by taking sub matrices of size 1x1. [1] [1] [1] [1] [1] [1] [1] [1] [1] Since the sum of each of the submatrices does not exceed k, the current result stands at 1. Now let's try for 2x2. [1 1] 1 1 [1 1] 1 1 1 1 1 1 [1 1] 1 1 [1 1] [1 1] 1 1 [1 1] 1 1 1 & 1 1 1 & [1 1] 1 & 1 [1 1] Now as you can see that the sum of each of the sub matrices is 4 which stays inside the threshold, the result is now 2. Now let's finally try for 3x3. [1 1 1] [1 1 1] [1 1 1] The sum exceeds the threshold since it is 9. Hence, we would result 2 as the answer since the maximum sub square matrix we could make which stayed inside the threshold was of size 2.