6257. 删除每行中的最大值

给你一个 m x n 大小的矩阵 grid ，由若干正整数组成。

执行下述操作，直到 grid 变为空矩阵：

  • 从每一行删除值最大的元素。如果存在多个这样的值，删除其中任何一个。
  • 将删除元素中的最大值与答案相加。

注意 每执行一次操作，矩阵中列的数据就会减 1 。

返回执行上述操作后的答案。

示例 1：

img

1
2
3
4
5
6
7
输入：grid = [[1,2,4],[3,3,1]]
输出：8
解释：上图展示在每一步中需要移除的值。
- 在第一步操作中，从第一行删除 4 ，从第二行删除 3（注意，有两个单元格中的值为 3 ，我们可以删除任一）。在答案上加 4 。
- 在第二步操作中，从第一行删除 2 ，从第二行删除 3 。在答案上加 3 。
- 在第三步操作中，从第一行删除 1 ，从第二行删除 1 。在答案上加 1 。
最终，答案 = 4 + 3 + 1 = 8 。

示例 2：

img

1
2
3
4
5
输入：grid = [[10]]
输出：10
解释：上图展示在每一步中需要移除的值。
- 在第一步操作中，从第一行删除 10 。在答案上加 10 。
最终，答案 = 10 。

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 50
  • 1 <= grid[i][j] <= 100

解法：每次操作会让矩阵删除一列，最多删除n列，而后按照题意模拟即可 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int deleteGreatestValue(int[][] a) {
        int m = a.length, n = a[0].length, res = 0;
        for (int i = 0; i < m; i++) Arrays.sort(a[i]);
        for (int j = 0; j < n; j++) {
            int now = a[0][j];
            for (int i = 0; i < m; i++) {
                now = Math.max(now, a[i][j]);
            }
            res += now;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def deleteGreatestValue(self, a: List[List[int]]) -> int:
        m, n = len(a), len(a[0])
        res = 0
        for c in range(n):
            b = []
            for i in range(m):
                mx = max(a[i])
                idx = a[i].index(mx)
                a[i][idx] = 0
                b.append(mx)
            res += max(b)
        return res

6258. 数组中最长的方波

给你一个整数数组 nums 。如果 nums 的子序列满足下述条件，则认为该子序列是一个 方波 ：

  • 子序列的长度至少为 2 ，并且
  • 将子序列从小到大排序 之后 ，除第一个元素外，每个元素都是前一个元素的 平方 。

返回 nums 中 最长方波 的长度，如果不存在 方波 则返回 -1 。

子序列 也是一个数组，可以由另一个数组删除一些或不删除元素且不改变剩余元素的顺序得到。

示例 1 ：

1
2
3
4
5
6
7
输入：nums = [4,3,6,16,8,2]
输出：3
解释：选出子序列 [4,16,2] 。排序后，得到 [2,4,16] 。
- 4 = 2 * 2.
- 16 = 4 * 4.
因此，[4,16,2] 是一个方波.
可以证明长度为 4 的子序列都不是方波。

示例 2 ：

1
2
3
输入：nums = [2,3,5,6,7]
输出：-1
解释：nums 不存在方波，所以返回 -1 。

提示：

  • 2 <= nums.length <= 105
  • 2 <= nums[i] <= 105

解法：由于是子序列，而且可以后续排序，所以我们可以拿到任意位置的数字，因此可以直接排序，当当前数确定时，前一个数就一定是这个数的开平方，所以有如下关系：

由于最多有 $10 ^ 5$ 个数，因此可以使用 $f[i]$ 来表示以i结尾的满足题意的个数 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    int[] f = new int[100005];
    public int longestSquareStreak(int[] a) {
        int res = 0;
        Arrays.sort(a);
        for (int x : a) {
            int pre = (int) Math.sqrt(x);
            if (pre * pre == x) f[x] = f[pre] + 1;
            else f[x] = 1;
            res = Math.max(res, f[x]);
        }
        return res == 1 ? -1 : res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    int f[100005];
public:
    int longestSquareStreak(vector<int>& a) {
        int res = 0;
        sort(a.begin(), a.end());
        for (int x : a) {
            int pre = (int) sqrt(x);
            if (pre * pre == x) f[x] = f[pre] + 1;
            else f[x] = 1;
            res = max(res, f[x]);
        }
        
        return res == 1 ? -1 : res;
    }
};

6259. 设计内存分配器

给你一个整数 n ，表示下标从 0 开始的内存数组的大小。所有内存单元开始都是空闲的。

请你设计一个具备以下功能的内存分配器：

  1. 分配 一块大小为 size 的连续空闲内存单元并赋 id mID 。
  2. 释放 给定 id mID 对应的所有内存单元。

注意：

  • 多个块可以被分配到同一个 mID 。
  • 你必须释放 mID 对应的所有内存单元，即便这些内存单元被分配在不同的块中。

实现 Allocator 类：

  • Allocator(int n) 使用一个大小为 n 的内存数组初始化 Allocator 对象。
  • int allocate(int size, int mID) 找出大小为 size 个连续空闲内存单元且位于 最左侧 的块，分配并赋 id mID 。返回块的第一个下标。如果不存在这样的块，返回 -1 。
  • int free(int mID) 释放 id mID 对应的所有内存单元。返回释放的内存单元数目。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
输入
["Allocator", "allocate", "allocate", "allocate", "free", "allocate", "allocate", "allocate", "free", "allocate", "free"]
[[10], [1, 1], [1, 2], [1, 3], [2], [3, 4], [1, 1], [1, 1], [1], [10, 2], [7]]
输出
[null, 0, 1, 2, 1, 3, 1, 6, 3, -1, 0]

解释
Allocator loc = new Allocator(10); // 初始化一个大小为 10 的内存数组，所有内存单元都是空闲的。
loc.allocate(1, 1); // 最左侧的块的第一个下标是 0 。内存数组变为 [1, , , , , , , , , ]。返回 0 。
loc.allocate(1, 2); // 最左侧的块的第一个下标是 1 。内存数组变为 [1,2, , , , , , , , ]。返回 1 。
loc.allocate(1, 3); // 最左侧的块的第一个下标是 2 。内存数组变为 [1,2,3, , , , , , , ]。返回 2 。
loc.free(2); // 释放 mID 为 2 的所有内存单元。内存数组变为 [1, ,3, , , , , , , ] 。返回 1 ，因为只有 1 个 mID 为 2 的内存单元。
loc.allocate(3, 4); // 最左侧的块的第一个下标是 3 。内存数组变为 [1, ,3,4,4,4, , , , ]。返回 3 。
loc.allocate(1, 1); // 最左侧的块的第一个下标是 1 。内存数组变为 [1,1,3,4,4,4, , , , ]。返回 1 。
loc.allocate(1, 1); // 最左侧的块的第一个下标是 6 。内存数组变为 [1,1,3,4,4,4,1, , , ]。返回 6 。
loc.free(1); // 释放 mID 为 1 的所有内存单元。内存数组变为 [ , ,3,4,4,4, , , , ] 。返回 3 ，因为有 3 个 mID 为 1 的内存单元。
loc.allocate(10, 2); // 无法找出长度为 10 个连续空闲内存单元的空闲块，所有返回 -1 。
loc.free(7); // 释放 mID 为 7 的所有内存单元。内存数组保持原状，因为不存在 mID 为 7 的内存单元。返回 0 。

提示：

  • 1 <= n, size, mID <= 1000
  • 最多调用 allocate 和 free 方法 1000 次

解法：由于数据量比较小，可以直接模拟，对于分配，可以记录最大连续的0的个数，如果等于size，那么对这段进行分配，否则返回-1，对于释放，直接模拟即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Allocator {
    int[] a;
    int n;
    public Allocator(int n) {
        a = new int[n];
        this.n = n;
    }
    
    public int allocate(int size, int mID) {
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] > 0) cnt = 0;
            else {
                cnt++;
                if (cnt == size) {
                    for (int j = i; j >= i - size + 1; j--) a[j] = mID;
                    return i - size + 1;
                }
            }
        }
        return -1;
    }
    
    public int free(int mID) {
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] == mID) {
                a[i] = 0;
                cnt++;
            }
        }
        return cnt;
    }
}

/**
 * Your Allocator object will be instantiated and called as such:
 * Allocator obj = new Allocator(n);
 * int param_1 = obj.allocate(size,mID);
 * int param_2 = obj.free(mID);
 */