前言
该系列文章用于我对一周中leetcode每日一题or其他不会的题的复盘总结。
一方面用于自己加深印象，另一方面也希望能对读者的算法能力有所帮助，
同时也希望能帮助同样坚持刷题的同学加深印象~
该复盘对我来说比较容易的题我会复盘的比较粗糙，反之较为细致
解答语言：Golang
周一：318. 最大单词长度乘积（middle）
题目描述：
给你一个字符串数组 words ，找出并返回 length(words[i]) * length(words[j]) 的最大值，并且这两个单词不含有公共字母。如果不存在这样的两个单词，返回 0 。
示例 1：
输入： words = ["abcw","baz","foo","bar","xtfn","abcdef"]
输出： 16
解释 ： 这两个单词为 "abcw", "xtfn"。
复盘：
这个题是比较简单的，比较暴力的解法就是两层遍历，一层去记忆，一层去搜索，但是值得注意第二层遍历我们可以应当去遍历（0，i）而非（i,j)因为（0，i)的状态我们已经记录下来了，所以遍历（0，i)时我们就可以直接进行判断是否符合要求。。而在记录状态时可以用数组ormap，但是空间复杂度是比较高的，熟悉位运算的同学应该很容易想到直接使用二进制位去存储word即可。
代码：
func maxProduct(words []string) (ans int) {
n := len(words)
mask := make([]int, n)
for i, s := range words {
for _, c := range s {
mask[i] |= 1 << (c - 'a')
}
for j, t := range words[:i] {
if mask[i]&mask[j] == 0 {
ans = max(ans, len(s)*len(t))
}
}
}
return
}
周二：2586. 统计范围内的元音字符串数（easy）
题目描述：
给你一个下标从 0 开始的字符串数组 words 和两个整数：left 和 right 。
如果字符串以元音字母开头并以元音字母结尾，那么该字符串就是一个 元音字符串 ，其中元音字母是 'a'、'e'、'i'、'o'、'u' 。
返回 **words[i] 是元音字符串的数目，其中 **i 在闭区间 [left, right] 内。
示例 1：
输入： words = ["are","amy","u"], left = 0, right = 2
输出： 2
解释：
- "are" 是一个元音字符串，因为它以 'a' 开头并以 'e' 结尾。
- "amy" 不是元音字符串，因为它没有以元音字母结尾。
- "u" 是一个元音字符串，因为它以 'u' 开头并以 'u' 结尾。
在上述范围中的元音字符串数目为 2 。
复盘：
简单题，直接模拟即可
代码：
func vowelStrings(words []string, left int, right int) int {
ans:=0
lis:=make([]int,26)
lis['a'-'a']=1
lis['e'-'a']=1
lis['i'-'a']=1
lis['o'-'a']=1
lis['u'-'a']=1
for i:=left;i<=right;i++{
word:=words[i]
if lis[word[0]-'a']==1&&lis[word[len(word)-1]-'a']==1{
ans+=1
}
}
return ans
}
周三:2609. 最长平衡子字符串(easy)
题目描述：
给你一个仅由 0 和 1 组成的二进制字符串 s 。
如果子字符串中 所有的 0 都在 1 之前 且其中 0 的数量等于 1 的数量，则认为 s 的这个子字符串是平衡子字符串。请注意，空子字符串也视作平衡子字符串。
返回 s 中最长的平衡子字符串长度。
子字符串是字符串中的一个连续字符序列。
示例 1：
输入： s = "01000111"
输出： 6
解释： 最长的平衡子字符串是 "000111" ，长度为 6 。
复盘：
也是一道easy难度的简单模拟题，遍历遇到0和1进行不同处理维护答案即可
代码：
func findTheLongestBalancedSubstring(s string) int {
if len(s)<2{
return 0
}
ans:=0
tmpAns:=0
tmp0:=0
tmp1:=0
i:=0
for i<len(s){
if s[i]=='0'{
tmp0+=1
i+=1
}
if i<len(s)&&s[i]=='1'{
for i<len(s)&&s[i]=='1'{
tmp1+=1
i+=1
}
tmpAns=min(tmp0,tmp1)*2
if tmpAns>ans{
ans=tmpAns
}
tmp0=0
tmp1=0
tmpAns=0
}
}
return ans
}
周四：2258. 逃离火灾（hard）
题目描述：
给你一个下标从 0 开始大小为 m x n 的二维整数数组 grid ，它表示一个网格图。每个格子为下面 3 个值之一：
0表示草地。1表示着火的格子。2表示一座墙，你跟火都不能通过这个格子。
一开始你在最左上角的格子 (0, 0) ，你想要到达最右下角的安全屋格子 (m - 1, n - 1) 。每一分钟，你可以移动到 相邻 的草地格子。每次你移动 之后 ，着火的格子会扩散到所有不是墙的 相邻 格子。
请你返回你在初始位置可以停留的 最多 分钟数，且停留完这段时间后你还能安全到达安全屋。如果无法实现，请你返回 -1 。如果不管你在初始位置停留多久，你 总是 能到达安全屋，请你返回 109 。
注意，如果你到达安全屋后，火马上到了安全屋，这视为你能够安全到达安全屋。
如果两个格子有共同边，那么它们为 相邻 格子。
示例 1：
输入： grid = [[0,2,0,0,0,0,0],[0,0,0,2,2,1,0],[0,2,0,0,1,2,0],[0,0,2,2,2,0,2],[0,0,0,0,0,0,0]]
输出： 3
解释： 上图展示了你在初始位置停留 3 分钟后的情形。
你仍然可以安全到达安全屋。
停留超过 3 分钟会让你无法安全到达安全屋。
复盘：
做这个题的时候我是没什么思路的，看了灵神题解之后还是比较清晰的，hard题就是这样，有一个很难想到的一个关键核心思想，如果没想到那么就很难做出来。
逃离火灾这个题主要有一个思想就是贪心，如果人到安全屋的最短时间小于所有火到安全屋的最短时间，那显然人是可以逃出安全屋的，而差值就是可以停留的最长时间。不过还需考虑的就是需要考虑到安全屋上方和下方的最短时间，如果人去安全屋上方或者去下方的速度比火快，那答案还可以+1，因为火是到不了安全屋的。
而计算时间就可以使用bfs，容易得到最短时间。
代码：
type pair struct{ x, y int }
var dirs = []pair{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
func maximumMinutes(grid [][]int) int {
m, n := len(grid), len(grid[0])
// 返回三个数，分别表示到达安全屋/安全屋左边/安全屋上边的最短时间
bfs := func(q []pair) (int, int, int) {
time := make([][]int, m)
for i := range time {
time[i] = make([]int, n)
for j := range time[i] {
time[i][j] = -1 // -1 表示未访问
}
}
for _, p := range q {
time[p.x][p.y] = 0
}
for t := 1; len(q) > 0; t++ { // 每次循环向外扩展一圈
tmp := q
q = nil
for _, p := range tmp {
for _, d := range dirs { // 枚举上下左右四个方向
if x, y := p.x+d.x, p.y+d.y; 0 <= x && x < m && 0 <= y && y < n && grid[x][y] == 0 && time[x][y] < 0 {
time[x][y] = t
q = append(q, pair{x, y})
}
}
}
}
return time[m-1][n-1], time[m-1][n-2], time[m-2][n-1]
}
manToHouseTime, m1, m2 := bfs([]pair{{}})
if manToHouseTime < 0 { // 人无法到安全屋
return -1
}
firePos := []pair{}
for i, row := range grid {
for j, x := range row {
if x == 1 {
firePos = append(firePos, pair{i, j})
}
}
}
fireToHouseTime, f1, f2 := bfs(firePos) // 多个着火点同时跑 BFS
if fireToHouseTime < 0 { // 火无法到安全屋
return 1_000_000_000
}
d := fireToHouseTime - manToHouseTime
if d < 0 { // 火比人先到安全屋
return -1
}
if m1 != -1 && m1+d < f1 || // 安全屋左边相邻格子，人比火先到
m2 != -1 && m2+d < f2 { // 安全屋上边相邻格子，人比火先到
return d // 图中第一种情况
}
return d - 1 // 图中第二种情况
}
周五：2300. 咒语和药水的成功对数（middle）
题目描述：
给你两个正整数数组 spells 和 potions ，长度分别为 n 和 m ，其中 spells[i] 表示第 i 个咒语的能量强度，potions[j] 表示第 j 瓶药水的能量强度。
同时给你一个整数 success 。一个咒语和药水的能量强度 相乘 如果 大于等于 success ，那么它们视为一对 成功 的组合。
请你返回一个长度为 n 的整数数组 **pairs，其中 **pairs[i] 是能跟第 i 个咒语成功组合的 药水 数目。
示例 1：
输入： spells = [5,1,3], potions = [1,2,3,4,5], success = 7
输出： [4,0,3]
解释：
- 第 0 个咒语：5 * [1,2,3,4,5] = [5,10,15,20,25] 。总共 4 个成功组合。
- 第 1 个咒语：1 * [1,2,3,4,5] = [1,2,3,4,5] 。总共 0 个成功组合。
- 第 2 个咒语：3 * [1,2,3,4,5] = [3,6,9,12,15] 。总共 3 个成功组合。
所以返回 [4,0,3] 。
复盘：
这个题是比较容易，直接去遍历spells，去看有多少potion能够去组合，而我们实现对potions排序，那么在查找时就可以二分查找，将复杂度降为O(nlogn)
代码：
func successfulPairs(spells []int, potions []int, success int64) (ans []int) {
var search func(spell int)int
search=func(spell int)int{
right:=len(potions)-1
left:=0
for left<=right{
mid:=left+(right-left)>>1
if spell*potions[mid]>=int(success){
right=mid-1
}else{
left=mid+1
}
}
return right
}
sort.Ints(potions)
m := len(potions)
for _, v := range spells {
i :=search(v)
ans = append(ans, m-i-1)
}
return ans
}
周六：765. 情侣牵手（hard）
题目描述：
n 对情侣坐在连续排列的 2n 个座位上，想要牵到对方的手。
人和座位由一个整数数组 row 表示，其中 row[i] 是坐在第 i 个座位上的人的 ID。情侣们按顺序编号，第一对是 (0, 1)，第二对是 (2, 3)，以此类推，最后一对是 (2n-2, 2n-1)。
返回 最少交换座位的次数，以便每对情侣可以并肩坐在一起。 每次交换可选择任意两人，让他们站起来交换座位。
示例 1:
输入: row = [0,2,1,3]
输出: 1
解释: 只需要交换row[1]和row[2]的位置即可。
复盘：
hard还是太难了，，真是没啥思路。。。。。。。。看题解去理解也很勉强。。
首先，我们总是以「情侣对」为单位进行设想：
当有两对情侣相互坐错了位置，ta们两对之间形成了一个环。需要进行一次交换，使得每队情侣独立（相互牵手）
如果三对情侣相互坐错了位置，ta们三对之间形成了一个环，需要进行两次交换，使得每队情侣独立（相互牵手）
如果四对情侣相互坐错了位置，ta们四对之间形成了一个环，需要进行三次交换，使得每队情侣独立（相互牵手）
也就是说，如果我们有 k 对情侣形成了错误环，需要交换 k - 1 次才能让情侣牵手。
于是问题转化成 n / 2 对情侣中，有多少个这样的环。
可以直接使用「并查集」来做。
由于 0和1配对、2和3配对 ... 因此互为情侣的两个编号除以 2 对应同一个数字，可直接作为它们的「情侣组」编号：
作者：宫水三叶
链接：https://leetcode.cn/problems/couples-holding-hands/
来源：力扣（LeetCode）
。
代码：
func minSwapsCouples(row []int) int {
n := len(row) >> 1
p := make([]int, n)
for i := range p {
p[i] = i
}
var find func(int) int
find = func(x int) int {
if p[x] != x {
p[x] = find(p[x])
}
return p[x]
}
for i := 0; i < n<<1; i += 2 {
a, b := row[i]>>1, row[i+1]>>1
p[find(a)] = find(b)
}
ans := n
for i := range p {
if find(i) == i {
ans--
}
}
return ans
}
#周日：715. Range 模块（hard）
懒得写了~~~~没做。。。
总结：
除了hard题都是比较简单，但是hard真是太难了，，，，
最后，，T1太顶了。。。。。
