这周的周赛想的很多，总是想着最优的方法到最后浪费了一堆时间，其实用空间换时间是在竞赛里非常好用的解法。
错误解法
在本题中，我一开始想利用map来记录出现字母与出现的位置，但这题中需要注意的细节是在面对大写字母和小写字母的时候处理是不一样的，本题中需要所有小写字母都在大写字母前面，所以小写字母的位置要更新大写字母只保存第一个出现的位置。
func numberOfSpecialChars(word string) int {
s,b := make([]int,26),make([]int,26) //用数组来代替数组，方便遍历
for i,_ := range b{
b[i] = -1
}
res := 0
for i,x := range word{
if unicode.IsLower(x){
s[x-'a'] = i
}else{
if b[x-'A'] == -1{
b[x-'A'] = i
}
}
}
for _,x := range word{
if unicode.IsLower(x){
if b[unicode.ToUpper(x)-'A'] != -1 && b[unicode.ToUpper(x)-'A'] > s[x-'a']{
res++
b[unicode.ToUpper(x)-'A'] = -2 //将已经计算过的字母位置重置，以免重复计算。
}
}
}
return res
}
想法
这道题我在竞赛的时候，我想到了数形dp但忘了模板怎么写了。
dp就是暴力把这个想通就好了。再从这步找到递推公式。
解题思路
这道题需要最少改变次数，于是反过来求最多保存个数。(为了解决这个问题，需要一个数组保存每一列出现数字的次数)
这道题需要左右相邻的数字不同，于是想到递归转化成动态规划。(利用动态规划暴力的点，将其对每个数字都遍历一遍，遇到相同的数字就跳过)
最后再相减取反即可。
func minimumOperations(grid [][]int) int {
n,m := len(grid),len(grid[0])
tmp := make([][]int,m) //先记录下每列出现数字的次数
for i := 0; i < m; i++{
tmp[i] = make([]int,10)
}
for i := 0; i <m; i++{
for j := 0; j < n; j++{
tmp[i][grid[j][i]] ++
}
}
memo := make([][11]int,m) //记忆化搜索
for i := range memo{
for j := range memo[i]{
memo[i][j] = -1
}
}
var dfs func(i,j int)int
dfs = func(i,j int)(res int){
if i < 0{
return
}
p := &memo[i][j]
if *p != -1{
return *p
}
for k,c := range tmp[i]{
if k != j{
res = max(res,dfs(i-1,k)+c) //递推
}
}
*p = res
return
}
return n*m - dfs(m-1,10)
}
解题思路
这道题的关键在想到用滑动窗口与把问题分成不生气和生气两个部分。
于是滑动窗口的条件:
- 判断是否需要更新窗口的条件在于，店长是否在窗口开始处生气，显然在不生气的时候并不需要滑动，在窗口开始处生气的话就需要更新
func maxSatisfied(customers []int, grumpy []int, minutes int) int {
s := [2]int{} //答案为生气的最大值和不生气的总和
maxS1 := 0
for i := 0; i < len(customers); i++{
s[grumpy[i]] += customers[i]
if i - minutes + 1 < 0{
continue
}
maxS1 = max(maxS1,s[1])
if grumpy[i-minutes+1] == 1{ //注意这个判断必须在更新maxS1之后，否则会影响答案
s[1] -= customers[i-minutes+1]
}
}
return s[0]+maxS1
}
