A quality agent is responsible for inspecting samples of the finished products in the production line. Each sample contains defective and non-defective products represented by 1 and 0 respectively. The product samples are placed sequentially in a two-dimensional square matrix. The goal is to determine the size of the largest square of defective products in the two-dimensional square matrix. Each line i of the n subsequent lines (where 0 ≤ i Function Description Complete the function largestSquareOfOnes in the editor. largestSquareOfOnes has the following parameter:

• int[][] samples: a two-dimensional array of integers representing the product samples Returns int: the size of the largest square of defective products

Example 1

Input:

samples = [[1,1,1,1,1],[1,1,1,0,0],[1,1,1,0,0],[1,1,1,0,0],[1,1,1,1,1]]

Output:

3

Explanation: The first square of defective products is a sub-matrix 3 x 3 starting at (0,0) and ending at (3,3). The second square of defective products is also a sub-matrix 3 x 3 at (1,0), and ending at (4,3). The third square of defective products is also a sub-matrix 3 x 3 at (2,0), and ending at (5,3). The size of the largest square of defective products is 3.

Example 2

Input:

samples = [[1,1,1],[1,1,0],[1,0,1]]

Output:

2

Explanation: The first square of defective products is a sub-matrix 2 x 2 starting at (0,0) and ending at (1,1). The other square of defective products are a sub-matrix 1 x 1 at (2,0), (0,2), and (2,2). The size of the largest square of defective products is 2.

Example 3

Input:

samples = [[0,1,1],[1,1,0],[1,0,1]]

Output:

1

Explanation: All square of defective products are a sub-matrix 1 x 1 at (0,1), (0,2), (1,0), (1,1), (2,0), and (2,2). The size of the largest square of defective products is 1.

解法

LC 221 经典 DP。dp[i][j] 表示以 (i, j) 为右下角的全 1 正方形最大边长，转移 dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 当 samples[i][j]==1。时间复杂度 O(mn)，空间复杂度 O(mn) 可优化为 O(n)。

from typing import List

def largestSquareOfOnes(samples: List[List[int]]) -> int:
    m, n = len(samples), len(samples[0])
    dp = [[0] * n for _ in range(m)]
    ans = 0
    for i in range(m):
        for j in range(n):
            if samples[i][j] == 1:
                if i == 0 or j == 0:
                    dp[i][j] = 1
                else:
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
                ans = max(ans, dp[i][j])
    return ans

class Solution {
    int largestSquareOfOnes(int[][] samples) {
        int m = samples.length, n = samples[0].length, ans = 0;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) {
            if (samples[i][j] == 1) {
                dp[i][j] = (i == 0 || j == 0) ? 1 : Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
                ans = Math.max(ans, dp[i][j]);
            }
        }
        return ans;
    }
}

class Solution {
public:
    int largestSquareOfOnes(vector<vector<int>>& samples) {
        int m = samples.size(), n = samples[0].size(), ans = 0;
        vector<vector<int>> dp(m, vector<int>(n, 0));
        for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) {
            if (samples[i][j] == 1) {
                dp[i][j] = (i == 0 || j == 0) ? 1 : min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;
                ans = max(ans, dp[i][j]);
            }
        }
        return ans;
    }
};

Each day a quarry-worker is given a pile of stones and told to reduce the larger stones into smaller ones. The worker must smash the stones together to reduce them, and is told to always pick up the largest two stones and smash them together. If the stones are of equal weight, they both disintegrate entirely. If one is larger, the smaller one is disintegrated and the larger one is reduced by the weight of the smaller one. Eventually, there is either one stone left that cannot be broken, or all of the stones have been smashed. Determine the weight of the last stone, or return 0 if there is none. Function Description Complete the function lastStoneWeight in the editor below. The function must return an integer that denotes the weight of the last stone, or 0 if all stones shattered into dust. lastStoneWeight has the following parameter(s):

• int weights[n]: an array of integers indicating the weights of each stone

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ weights[i] ≤ 10⁹

Example 1

Input:

weights = [1,2,3,6,7,7]

Output:

0

Explanation: The worker always starts with the two largest stones. In this case, the two largest stones have equal weights of 7 so they both disintegrate when smashed. Next the worker smashes weights 3 and 6. The smaller one is destroyed and the larger weighs 6 - 3 = 3 units. Then, weights 3 and 2 are smashed together, which leaves a stone of weight 1. This is smashed with the last remaining stone of weight 1. There are no stones left, so the remaining stone weight is 0.

解法

LC 1046 大顶堆。每次取两个最大；相等都消失，否则差放回堆。时间复杂度 O(n log n)。

import heapq
from typing import List

def lastStoneWeight(weights: List[int]) -> int:
    h = [-w for w in weights]
    heapq.heapify(h)
    while len(h) > 1:
        a = -heapq.heappop(h); b = -heapq.heappop(h)
        if a != b: heapq.heappush(h, -(a - b))
    return -h[0] if h else 0

class Solution {
    int lastStoneWeight(int[] weights) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for (int w : weights) pq.add(w);
        while (pq.size() > 1) {
            int a = pq.poll(), b = pq.poll();
            if (a != b) pq.add(a - b);
        }
        return pq.isEmpty() ? 0 : pq.peek();
    }
}

class Solution {
public:
    int lastStoneWeight(vector<int>& weights) {
        priority_queue<int> pq(weights.begin(), weights.end());
        while (pq.size() > 1) {
            int a = pq.top(); pq.pop();
            int b = pq.top(); pq.pop();
            if (a != b) pq.push(a - b);
        }
        return pq.empty() ? 0 : pq.top();
    }
};

There is a collection of photos to place into an empty photo album, one at a time by order of importance. Each time a photo is inserted, all subsequent photos are shifted toward the right by one position. Given the id's of the photos and the positions where each should be placed, find out the sequence of the photos in the album after all photos have been inserted. Function Description Complete the function photoAlbum in the editor. photoAlbum has the following parameter(s):

• int index[n]: the positions where the photos are to be inserted
• int identity[n]: the photograph id numbers Returns int[n]: the sequence of identity values after all are inserted Input Format For Custom Testing The first line contains an integer, n, the number of elements in the array index. Each line i of the n subsequent lines (where 0 ≤ i The next line contains an integer, n, the number of elements in the array identity. Each line i of the n subsequent lines (where 0 ≤ i < n) contains an integer, identity[i].

Constraints

• 1 ≤ n ≤ 2 x 10⁵
• 0 ≤ index[i], identity[i] < n (0 ≤ i < n)

解法

直接用动态数组的 insert(pos, val)：每次在指定位置插入。O(n²) 最坏。也可用平衡树/树状数组优化到 O(n log n)，这里给出朴素版。

from typing import List

def photoAlbum(index: List[int], identity: List[int]) -> List[int]:
    res = []
    for i, idx in enumerate(index):
        res.insert(idx, identity[i])
    return res

class Solution {
    int[] photoAlbum(int[] index, int[] identity) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < index.length; i++) res.add(index[i], identity[i]);
        int[] out = new int[res.size()];
        for (int i = 0; i < res.size(); i++) out[i] = res.get(i);
        return out;
    }
}

class Solution {
public:
    vector<int> photoAlbum(vector<int>& index, vector<int>& identity) {
        vector<int> res;
        for (int i = 0; i < (int)index.size(); i++) res.insert(res.begin() + index[i], identity[i]);
        return res;
    }
};