LeetCode第215场周赛20201115(Java)_0 <= introvertscount, extrovertscount <= min(m * n

第 215 场周赛

20201115

1656. 设计有序流

题目描述1

有 n 个 (id, value) 对，其中 id 是 1 到 n 之间的一个整数，value 是一个字符串。不存在 id 相同的两个 (id, value) 对。

设计一个流，以 任意 顺序获取 n 个 (id, value) 对，并在多次调用时 按 id 递增的顺序 返回一些值。

实现 OrderedStream 类：

OrderedStream(int n) 构造一个能接收 n 个值的流，并将当前指针 ptr 设为 1 。
String[] insert(int id, String value) 向流中存储新的 (id, value) 对。存储后：
    如果流存储有 id = ptr 的 (id, value) 对，则找出从 id = ptr 开始的 最长 id 连续递增序列 ，并 按顺序 返回与这些 id 关联的值的列表。然后，将 ptr 更新为最后那个  id + 1 。

    否则，返回一个空列表。
1
2
3
4
5

示例：

输入
["OrderedStream", "insert", "insert", "insert", "insert", "insert"]
[[5], [3, "ccccc"], [1, "aaaaa"], [2, "bbbbb"], [5, "eeeee"], [4, "ddddd"]]
输出
[null, [], ["aaaaa"], ["bbbbb", "ccccc"], [], ["ddddd", "eeeee"]]

解释
OrderedStream os= new OrderedStream(5);
os.insert(3, "ccccc"); // 插入 (3, "ccccc")，返回 []
os.insert(1, "aaaaa"); // 插入 (1, "aaaaa")，返回 ["aaaaa"]
os.insert(2, "bbbbb"); // 插入 (2, "bbbbb")，返回 ["bbbbb", "ccccc"]
os.insert(5, "eeeee"); // 插入 (5, "eeeee")，返回 []
os.insert(4, "ddddd"); // 插入 (4, "ddddd")，返回 ["ddddd", "eeeee"]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

提示：

• 1 <= n <= 1000
• 1 <= id <= n
• value.length == 5
• value 仅由小写字母组成
• 每次调用 insert 都会使用一个唯一的 id
• 恰好调用 n 次 insert

链接：https://leetcode-cn.com/problems/design-an-ordered-stream

解答1

class OrderedStream {
    String[] sa;
    int ptr = 1;
    List<String> res = new ArrayList<>();
    public OrderedStream(int n) {
        sa = new String[n + 10];
    }
    public List<String> insert(int id, String value) {
        List<String> res = new ArrayList<>();
        sa[id] = value;
        if(ptr != id) {
            return res;
        }
        else{
            int idx = id;
            while(sa[idx] != null){
                res.add(sa[idx]);
                idx++;
            }
            ptr = idx;
        }
        return res;
    }
}
/**
 * Your OrderedStream object will be instantiated and called as such:
 * OrderedStream obj = new OrderedStream(n);
 * List<String> param_1 = obj.insert(id,value);
 */
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

1657. 确定两个字符串是否接近

题目描述2

如果可以使用以下操作从一个字符串得到另一个字符串，则认为两个字符串 接近 ：

• 操作 1：交换任意两个 现有 字符。例如，abcde -> aecdb
• 操作 2：将一个 现有 字符的每次出现转换为另一个 现有 字符，并对另一个字符执行相同的操作。例如，aacabb -> bbcbaa（所有 a 转化为 b ，而所有的 b 转换为 a ）

你可以根据需要对任意一个字符串多次使用这两种操作。

给你两个字符串，word1 和 word2 。如果 word1 和 word2 接近 ，就返回 true ；否则，返回 false 。

示例 1：

输入：word1 = "abc", word2 = "bca"
输出：true
解释：2 次操作从 word1 获得 word2 。
执行操作 1："abc" -> "acb"
执行操作 1："acb" -> "bca"

示例 2：

输入：word1 = "a", word2 = "aa"
输出：false
解释：不管执行多少次操作，都无法从 word1 得到 word2 ，反之亦然。

示例 3：

输入：word1 = "cabbba", word2 = "abbccc"
输出：true
解释：3 次操作从 word1 获得 word2 。
执行操作 1："cabbba" -> "caabbb"
执行操作 2："caabbb" -> "baaccc"
执行操作 2："baaccc" -> "abbccc"

示例 4：

输入：word1 = "cabbba", word2 = "aabbss"
输出：false
解释：不管执行多少次操作，都无法从 word1 得到 word2 ，反之亦然。
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

提示：

• 1 <= word1.length, word2.length <= 105
• word1 和 word2 仅包含小写英文字母

链接：https://leetcode-cn.com/problems/determine-if-two-strings-are-close

解答2

class Solution {
    public boolean closeStrings(String word1, String word2) {
        int n1 = word1.length(), n2 = word2.length();
        // 两个字符串满足两个条件
        // 1. word1 和 word2 包含的字符种类相同
        // 2. word1 和 word2 不同种类字母的数量的种类要相同
        int[] a1 = new int[26];
        int[] a2 = new int[26];
        if(n1 != n2) return false;
        for(int i = 0; i < n1; i++){
            int t1 = word1.charAt(i) - 'a';
            int t2 = word2.charAt(i) - 'a';
            a1[t1] ++;
            a2[t2] ++;
        }
        for(int i = 0; i< 26; i++){
            if(a1[i] == 0 && a2[i] != 0) return false;
            if(a1[i] != 0 && a2[i] == 0) return false;
        }
        // 看字母的数量了
        Arrays.sort(a1);
        Arrays.sort(a2);
        return Arrays.equals(a1, a2);
    }
}
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

1658. 将 x 减到 0 的最小操作数

题目描述3

给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。

如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。

示例 1：

输入：nums = [1,1,4,2,3], x = 5
输出：2
解释：最佳解决方案是移除后两个元素，将 x 减到 0 。

示例 2：

输入：nums = [5,6,7,8,9], x = 4
输出：-1

示例 3：

输入：nums = [3,2,20,1,1,3], x = 10
输出：5
解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 104
• 1 <= x <= 109

链接：https://leetcode-cn.com/problems/minimum-operations-to-reduce-x-to-zero

解答3

class Solution {
    public int minOperations(int[] nums, int x) {
        int n = nums.length;
        int[] s1 = new int[n + 10];
        int[] s2 = new int[n + 10];
        int res = 0x3f3f3f3f;
        // 处理前缀和,倒叙前缀和
        // s1[i] 表示前 i 个元素之和, 从 1 开始
        for(int i = 1; i <= n; i++){
            s1[i] = s1[i - 1] + nums[i - 1];
            if(s1[i] == x) res = Math.min(res, i);
        }
        // s2[i] 表示第 i 个元素到末尾元素的和, 从 1 开始
        for(int i = n; i > 0; i--){
            s2[i] = s2[i + 1] + nums[i - 1];
            if(s2[i] == x) res = Math.min(res, n - i + 1);
        }
        // 如果整个数组加起来不够,就返回 -1
        if(s1[n] < x) return -1;
        // 双指针
        for(int i = 0, j = 1; i < n; i++){
            // 如果两者之和大于 x, j 右移
            // System.out.println("xian: " + "i: " + i + " j: " + j);
            while(j <= n && s1[i] + s2[j] > x) j++;
            // 如果 s1[i] + s2[j] == x 记录答案
            // System.out.println("hou: " + "i: " + i + " j: " + j);
            if(j <= n && s1[i] + s2[j] == x) res = Math.min(res, i + n - j + 1);
        }
        if(res > n) return -1;
        return res;
    }
}
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

1659. 最大化网格幸福感

题目描述4

给你四个整数 m、n、introvertsCount 和 extrovertsCount 。有一个 m x n 网格，和两种类型的人：内向的人和外向的人。总共有 introvertsCount 个内向的人和 extrovertsCount 个外向的人。

请你决定网格中应当居住多少人，并为每个人分配一个网格单元。 注意，不必 让所有人都生活在网格中。

每个人的 幸福感 计算如下：

• 内向的人 开始 时有 120 个幸福感，但每存在一个邻居（内向的或外向的）他都会 失去 30 个幸福感。
• 外向的人 开始 时有 40 个幸福感，每存在一个邻居（内向的或外向的）他都会 得到 20 个幸福感。

邻居是指居住在一个人所在单元的上、下、左、右四个直接相邻的单元中的其他人。

网格幸福感 是每个人幸福感的 总和 。 返回最大可能的网格幸福感 。

示例 1：

输入：m = 2, n = 3, introvertsCount = 1, extrovertsCount = 2
输出：240
解释：假设网格坐标 (row, column) 从 1 开始编号。
将内向的人放置在单元 (1,1) ，将外向的人放置在单元 (1,3) 和 (2,3) 。
- 位于 (1,1) 的内向的人的幸福感：120（初始幸福感）- (0 * 30)（0 位邻居）= 120
- 位于 (1,3) 的外向的人的幸福感：40（初始幸福感）+ (1 * 20)（1 位邻居）= 60
- 位于 (2,3) 的外向的人的幸福感：40（初始幸福感）+ (1 * 20)（1 位邻居）= 60
网格幸福感为：120 + 60 + 60 = 240
上图展示该示例对应网格中每个人的幸福感。内向的人在浅绿色单元中，而外向的人在浅紫色单元中。

示例 2：

输入：m = 3, n = 1, introvertsCount = 2, extrovertsCount = 1
输出：260
解释：将内向的人放置在单元 (1,1) 和 (3,1) ，将外向的人放置在单元 (2,1) 。
- 位于 (1,1) 的内向的人的幸福感：120（初始幸福感）- (1 * 30)（1 位邻居）= 90
- 位于 (2,1) 的外向的人的幸福感：40（初始幸福感）+ (2 * 20)（2 位邻居）= 80
- 位于 (3,1) 的内向的人的幸福感：120（初始幸福感）- (1 * 30)（1 位邻居）= 90
网格幸福感为 90 + 80 + 90 = 260

示例 3：

输入：m = 2, n = 2, introvertsCount = 4, extrovertsCount = 0
输出：240
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

提示：

• 1 <= m, n <= 5
• 0 <= introvertsCount, extrovertsCount <= min(m * n, 6)

链接：https://leetcode-cn.com/problems/maximize-grid-happiness

解答4

TODO