Weekly Contest 107 AC思路

比赛题目链接：https://leetcode-cn.com/contest/weekly-contest-107/

第一题：925. 长按键入
原题链接：https://leetcode-cn.com/contest/weekly-contest-107/problems/long-pressed-name/

思路：看题目的话，会分析出一个出来一个思路就是，对字符串进行压缩，举例分析
abbccca
序号 字符 出现次数
1 a 1
2 b 2
3 c 3
4 a 1

那么，我们可以对name和typed字符串进行压缩，存储到切片里（或数组），然后进行比较

// 定义一个结构体
type longScan struct {
    num int    // 次数
    char byte // 字符
}

// 定义存储变量
nScan, tScan := []longScan{}, []longScan{}

// 压缩存储name
// 压缩存储typed
// 比较nScan, tScan
for i := 0;i < len(nScan);i++ {
        if nScan[i].char != tScan[i].char || nScan.num > tScan.num {
                  return false
        }
}
return false

第一题的整体思路就这样了
我AC代码链接：https://github.com/laijinhang/acm-go/blob/master/leetcode_go/%E6%AF%94%E8%B5%9B/925.%20%E9%95%BF%E6%8C%89%E9%94%AE%E5%85%A5.go

第二题：926. 将字符串翻转到单调递增
原题链接：https://leetcode-cn.com/contest/weekly-contest-107/problems/flip-string-to-monotone-increasing/

思路：分析题目，可以知道最终结果第一次出现1的地方开始后都要为1
思路一：
那么转化成出现1的地方要么 1-> 0，要么 1 -> 1。
第一种操作的话，加上翻转次数，继续往下找到出现1的地方，重复这个步骤
第二种操作的话，计算后面出现0的个数，判断是否为最小，是的话，就值替换

思路二：
1）先将字符串进行压缩

type MonoIncr struct {
    num int    // 次数
    char byte // 字符
}

2）然后对压缩之后的内容计算，要么 1->0，要1->1后面全部变1，计算翻转次数

我AC代码链接：https://github.com/laijinhang/acm-go/blob/master/leetcode_go/%E6%AF%94%E8%B5%9B/926.%20%E5%B0%86%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%BF%BB%E8%BD%AC%E5%88%B0%E5%8D%95%E8%B0%83%E9%80%92%E5%A2%9E.go

会发现很像01背包问题

题目三：927. 三等分
原题链接：https://leetcode-cn.com/contest/weekly-contest-107/problems/three-equal-parts/

思路：分析题目，要得到三等分，那么三个区间1的个数要能整除3，而且每一个区间1的个数要相等
1）如果A的长度小于3，则直接返回[-1,-1]
2）如果A中1的个数%3不等于0，则直接返回[-1,-1]

一个二进制数出现第一个1之前出现的0都不算在二进制数里面

3）计算A中1的个数
4）设a1、a2、a3、a4、a5、a6，意思分别表示a1的第一个区间第一次出现1的下标值，a2是从a1开始出现第num/3个1的下标值，a3表示a2+1开始第一次出现1的下标值，a4表示从a3开始出现第num/3个1的下标值，a5表示a4+1开始第一次出现1的下标值，a6表示从a5开始第num/3个1的下标值。
5）分别计算出a1、a2、a3、a4、a5、a6的值
6）要满足len(A) - a6 - 1 + a2 < a3 && len(A) - a6 - 1 + a4 < a5，不满足则返回[-1,-1]
7）比较A[a1:a2+1]，A[a3:a4+1]，A[a5:a6+1]，如果相同则返回[len(A) - a6 - 1 + a2, len(A) - a6 + a4]，不同则返回[-1,-1]

我AC代码链接：https://github.com/laijinhang/acm-go/blob/master/leetcode_go/%E6%AF%94%E8%B5%9B/927.%20%E4%B8%89%E7%AD%89%E5%88%86.go

简书博客链接：https://www.jianshu.com/p/bbb0744f70a4