type
status
date
slug
summary
tags
category
icon
password
Last edited time
Jun 20, 2024 05:32 PM
LeetCode第130场双周赛题解
📝 主旨内容
判断矩阵是否满足条件(模拟)
给你一个大小为
m x n 的二维矩阵 grid 。你需要判断每一个格子 grid[i][j] 是否满足：- 如果它下面的格子存在，那么它需要等于它下面的格子，也就是
grid[i][j] == grid[i + 1][j]。
- 如果它右边的格子存在，那么它需要不等于它右边的格子，也就是
grid[i][j] != grid[i][j + 1]。
如果 所有 格子都满足以上条件，那么返回
true ，否则返回 false 。示例 1：
输入：grid = [[1,0,2],[1,0,2]]
输出：true
解释：
网格图中所有格子都符合条件。
示例 2：
输入：grid = [[1,1,1],[0,0,0]]
输出：false
解释：
同一行中的格子值都相等。
示例 3：
输入：grid = [[1],[2],[3]]
输出：false
解释：
同一列中的格子值不相等。
提示：
1 <= n, m <= 10
0 <= grid[i][j] <= 9
签到题，数据最大10*10，直接模拟即可
正方形中最多点数(二分，贪心)
给你一个二维数组
points 和一个字符串 s ，其中 points[i] 表示第 i 个点的坐标，s[i] 表示第 i 个点的 标签 。如果一个正方形的中心在
(0, 0) ，所有边都平行于坐标轴，且正方形内 不 存在标签相同的两个点，那么我们称这个正方形是 合法 的。请你返回 合法 正方形中可以包含的 最多 点数。
注意：
- 如果一个点位于正方形的边上或者在边以内，则认为该点位于正方形内。
- 正方形的边长可以为零。
示例 1：
输入：points = [[2,2],[-1,-2],[-4,4],[-3,1],[3,-3]], s = "abdca"
输出：2
解释：
边长为 4 的正方形包含两个点
points[0] 和 points[1] 。示例 2：
输入：points = [[1,1],[-2,-2],[-2,2]], s = "abb"
输出：1
解释：
边长为 2 的正方形包含 1 个点
points[0] 。示例 3：
输入：points = [[1,1],[-1,-1],[2,-2]], s = "ccd"
输出：0
解释：
任何正方形都无法只包含
points[0] 和 points[1] 中的一个点，所以合法正方形中都不包含任何点。提示：
1 <= s.length, points.length <= 10^5
points[i].length == 2
109 <= points[i][0], points[i][1] <= 10^9
s.length == points.length
points中的点坐标互不相同。
s只包含小写英文字母。
看到边长的范围在0~10^9就想到了二分。问题的单调性体现在边长越长，可能包含的点就越多，产生冲突的概率也越大，复杂度O(nlogk)
也可以借助离散化的思想用贪心去思考这道题。虽然边长不能枚举(10^9)，但是点数是可以枚举的，以
max(abs(x), abs(y))(点能否被考虑取决于x和y绝对值的最大值)为索引建立数组存入label，随后从大到小遍历数组，一旦发生冲突，答案就是发生冲突前上一层的累计点数分割字符频率相等的最少子字符串(DP)
给你一个字符串
s ，你需要将它分割成一个或者更多的 平衡 子字符串。比方说，s == "ababcc" 那么 ("abab", "c", "c") ，("ab", "abc", "c") 和 ("ababcc") 都是合法分割，但是 ("a", "bab", "cc") ，("aba", "bc", "c") 和 ("ab", "abcc") 不是，不平衡的子字符串用粗体表示。请你返回
s 最少 能分割成多少个平衡子字符串。注意：一个 平衡 字符串指的是字符串中所有字符出现的次数都相同。
示例 1：
输入：s = "fabccddg"
输出：3
解释：
我们可以将
s 分割成 3 个子字符串：("fab, "ccdd", "g") 或者 ("fabc", "cd", "dg") 。示例 2：
输入：s = "abababaccddb"
输出：2
解释：
我们可以将
s 分割成 2 个子字符串：("abab", "abaccddb") 。提示：
1 <= s.length <= 1000
s只包含小写英文字母。
字符串+贪心，每次都是将单个字符抠出来，最后输出的字符串长度。放在第三题不可能那么简单，但是500多人过了，是不是应该不难，是不是还没考DP，那就是你了，只要我不会那就是DP了
考虑状态定义和状态转移，一般问题问什么就定义成什么样，dp[i]表示s[0~i]分割出的最少字符串数。状态转移呢？是不是要开始秒了，很简单就在0~i内找一个端点j，使得s[0~j]和s[j+1~i]都是平衡串，那么dp[i]就可以从dp[j]转移了(这里需要考虑dp[])，
dp[i] = min(dp[i], dp[j] + 1) 大数组元素的乘积(数学，试填法，二分)
一个整数
x 的 强数组 指的是满足和为 x 的二的幂的最短有序数组。比方说，11 的强数组为 [1, 2, 8] 。我们将每一个正整数
i （即1，2，3等等）的 强数组 连接得到数组 big_nums ，big_nums 开始部分为 [1, 2, 1, 2, 4, 1, 4, 2, 4, 1, 2, 4, 8, ...] 。给你一个二维整数数组
queries ，其中 queries[i] = [fromi, toi, modi] ，你需要计算 (big_nums[fromi] * big_nums[fromi + 1] * ... * big_nums[toi]) % modi 。请你返回一个整数数组
answer ，其中 answer[i] 是第 i 个查询的答案。示例 1：
输入：queries = [[1,3,7]]
输出：[4]
解释：
只有一个查询。
big_nums[1..3] = [2,1,2] 。它们的乘积为 4 ，4 对 7 取余数得到 4 。示例 2：
输入：queries = [[2,5,3],[7,7,4]]
输出：[2,2]
解释：
有两个查询。
第一个查询：
big_nums[2..5] = [1,2,4,1] 。它们的乘积为 8 ，8 对 3 取余数得到 2 。第二个查询：
big_nums[7] = 2 ，2 对 4 取余数得到 2 。提示：
1 <= queries.length <= 500
queries[i].length == 3
0 <= queries[i][0] <= queries[i][1] <= 1015
1 <= queries[i][2] <= 105
连续的以2为底的指数求乘积，等价于先对指数求前缀和得到幂次之和，最后再用快速幂求2的幂取mod的结果
前n项的强数组之和等价于[0,n-1]内转换成2进制后1的个数
凑出符合最大满足要求的前缀和，很容易想到二分，但会引入一个log复杂度，所以引入了试填法，思想和试除法类似
🤗 总结归纳
很久没写了，第一题都敲了挺久的，都忘报名了在那等哈哈哈
第二题又是熟悉的二分，还以为要排序，结果不用，调试代码又wa一次，没意思
第三题平衡字符串，怎么写都很贴心的帮我把单个字符抠出来求字符串长，我是真的会谢，500人过了这题，嘴真严急死了，不会就是DP好吧，然后果然是，还是简单的DP
然后愉悦下机(看了下第四题，没必要了只能说)
上小分只能说，没掉就好
📎 参考文章
- 作者:ziuch
- 链接:https://ziuch.com/article/LeetCode-biweekly-contest-130-solution
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。