1101-1200-Easy

1103.分糖果 II(3)

• 题目

排排坐，分糖果。
我们买了一些糖果 candies，打算把它们分给排好队的 n = num_people 个小朋友。
给第一个小朋友 1 颗糖果，第二个小朋友 2 颗，依此类推，直到给最后一个小朋友 n 颗糖果。
然后，我们再回到队伍的起点，给第一个小朋友 n + 1 颗糖果，第二个小朋友 n + 2 颗，
依此类推，直到给最后一个小朋友 2 * n 颗糖果。
重复上述过程（每次都比上一次多给出一颗糖果，当到达队伍终点后再次从队伍起点开始），直到我们分完所有的糖果。
注意，就算我们手中的剩下糖果数不够（不比前一次发出的糖果多），这些糖果也会全部发给当前的小朋友。
返回一个长度为 num_people、元素之和为 candies 的数组，
以表示糖果的最终分发情况（即 ans[i] 表示第 i 个小朋友分到的糖果数）。
示例 1：输入：candies = 7, num_people = 4 输出：[1,2,3,1]
解释：
第一次，ans[0] += 1，数组变为 [1,0,0,0]。
第二次，ans[1] += 2，数组变为 [1,2,0,0]。
第三次，ans[2] += 3，数组变为 [1,2,3,0]。
第四次，ans[3] += 1（因为此时只剩下 1 颗糖果），最终数组变为 [1,2,3,1]。

示例 2：输入：candies = 10, num_people = 3 输出：[5,2,3]
解释：
第一次，ans[0] += 1，数组变为 [1,0,0]。
第二次，ans[1] += 2，数组变为 [1,2,0]。
第三次，ans[2] += 3，数组变为 [1,2,3]。
第四次，ans[0] += 4，最终数组变为 [5,2,3]。
提示：
    1 <= candies <= 10^9
    1 <= num_people <= 1000

• 解题思路

func distributeCandies(candies int, num_people int) []int {
    res := make([]int, num_people)
    i := 0
    count := 0
    for candies > 0 {
        count++
        if candies >= count {
            res[i%num_people] += count
        } else {
            res[i%num_people] += candies
        }
        i++
        candies = candies - count
    }
    return res
}

#
func distributeCandies(candies int, num_people int) []int {
    res := make([]int, num_people)
    count := 1
    for candies > 0 {
        for i := 0; i < num_people; i++ {
            if candies >= count {
                res[i] = res[i] + count
                candies = candies - count
            } else {
                res[i] = res[i] + candies
                candies = 0
            }
            count++
        }
    }
    return res
}

#
func distributeCandies(candies int, num_people int) []int {
    res := make([]int, num_people)
    times := 1
    for times*(times+1)/2 <= candies {
        times++
    }
    // 计算出当前糖果最多可以发给多少个人,剩下最后一个人多少颗糖
    times--
    last := candies - times*(times+1)/2
    for i := 0; i < num_people; i++ {
        n := times / num_people
        if times%num_people > i {
            n = n + 1
        }
        // 等差数列{an}的通项公式为：an=a1+(n-1)d。
        // 前n项和公式为：Sn=n*a1+n(n-1)d/2或Sn=n(a1+an)/2
        // Sn=n(a1+a1+(n-1)d)/2=n(2a1+(n-1)d)/2
        // (i+1)为首项，num_people为公差，n为数列长度，的等差数列的和
        res[i] = n * (2*(i+1) + (n-1)*num_people) / 2
        if times%num_people == i {
            res[i] = res[i] + last
        }
    }
    return res
}

1108.IP地址无效化(2)

• 题目

给你一个有效的 IPv4 地址 address，返回这个 IP 地址的无效化版本。
所谓无效化 IP 地址，其实就是用 "[.]" 代替了每个 "."。
示例 1：输入：address = "1.1.1.1" 输出："1[.]1[.]1[.]1"
示例 2：输入：address = "255.100.50.0" 输出："255[.]100[.]50[.]0"
提示：
    给出的 address 是一个有效的 IPv4 地址

• 解题思路

func defangIPaddr(address string) string {
    return strings.ReplaceAll(address, ".", "[.]")
}

#
func defangIPaddr(address string) string {
    res := ""
    for i := range address {
        if address[i] == '.' {
            res = res + "[.]"
        } else {
            res = res + string(address[i])
        }
    }
    return res
}

1122.数组的相对排序(3)

• 题目

给你两个数组，arr1 和 arr2，
    arr2 中的元素各不相同
    arr2 中的每个元素都出现在 arr1 中
对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。
未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
示例：
输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
输出：[2,2,2,1,4,3,3,9,6,7,19]
提示：
    arr1.length, arr2.length <= 1000
    0 <= arr1[i], arr2[i] <= 1000
    arr2 中的元素 arr2[i] 各不相同
    arr2 中的每个元素 arr2[i] 都出现在 arr1 中

• 解题思路

func relativeSortArray(arr1 []int, arr2 []int) []int {
    if len(arr2) == 0 {
        sort.Ints(arr1)
        return arr1
    }
    res := make([]int, 0)
    m := make(map[int]int)
    for i := range arr1 {
        m[arr1[i]]++
    }
    for i := 0; i < len(arr2); i++ {
        for j := 0; j < m[arr2[i]]; j++ {
            res = append(res, arr2[i])
        }
        m[arr2[i]] = 0
    }
    tempArr := make([]int, 0)
    for key, value := range m {
        for value > 0 {
            tempArr = append(tempArr, key)
            value--
        }
    }
    sort.Ints(tempArr)
    res = append(res, tempArr...)
    return res
}

#
func relativeSortArray(arr1 []int, arr2 []int) []int {
    count := 0
    for i := 0; i < len(arr2); i++ {
        for j := count; j < len(arr1); j++ {
            if arr2[i] == arr1[j] {
                arr1[count], arr1[j] = arr1[j], arr1[count]
                count++
            }
        }
    }
    sort.Ints(arr1[count:])
    return arr1
}

#
func relativeSortArray(arr1 []int, arr2 []int) []int {
    temp := make([]int, 1001)
    for i := range arr1 {
        temp[arr1[i]]++
    }
    count := 0
    for i := range arr2 {
        for temp[arr2[i]] > 0 {
            arr1[count] = arr2[i]
            temp[arr2[i]]--
            count++
        }
    }
    for i := 0; i < len(temp); i++ {
        for temp[i] > 0 {
            arr1[count] = i
            temp[i]--
            count++
        }
    }
    return arr1
}

1128.等价多米诺骨牌对的数量(2)

• 题目

给你一个由一些多米诺骨牌组成的列表 dominoes。
如果其中某一张多米诺骨牌可以通过旋转 0 度或 180 度得到另一张多米诺骨牌，我们就认为这两张牌是等价的。
形式上，dominoes[i] = [a, b] 和 dominoes[j] = [c, d] 
等价的前提是 a==c 且 b==d，或是 a==d 且 b==c。
在 0 <= i < j < dominoes.length 的前提下，
找出满足 dominoes[i] 和 dominoes[j] 等价的骨牌对 (i, j) 的数量。

示例：输入：dominoes = [[1,2],[2,1],[3,4],[5,6]] 输出：1
提示：
    1 <= dominoes.length <= 40000
    1 <= dominoes[i][j] <= 9

• 解题思路

func numEquivDominoPairs(dominoes [][]int) int {
    m := make(map[string]int)
    for i := 0; i < len(dominoes); i++ {
        a := dominoes[i][0]
        b := dominoes[i][1]
        if a > b {
            a, b = b, a
        }
        m[fmt.Sprintf("%d,%d", a, b)]++
    }
    res := 0
    for _, v := range m {
        res = res + v*(v-1)/2
    }
    return res
}

#
func numEquivDominoPairs(dominoes [][]int) int {
    res := 0
    arr := make([]int, 101)
    for i := 0; i < len(dominoes); i++ {
        a := dominoes[i][0]
        b := dominoes[i][1]
        if a > b {
            a, b = b, a
        }
        res = res + arr[a*10+b]
        arr[a*10+b]++
    }
    return res
}

1137.第N个泰波那契数(3)

• 题目

泰波那契序列 Tn 定义如下： 
T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
给你整数 n，请返回第 n 个泰波那契数 Tn 的值。

示例 1：输入：n = 4 输出：4
解释：
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4
示例 2：
输入：n = 25
输出：1389537
提示：
    0 <= n <= 37
    答案保证是一个 32 位整数，即 answer <= 2^31 - 1。

• 解题思路

func tribonacci(n int) int {
    arr := make([]int, n+3)
    arr[0] = 0
    arr[1] = 1
    arr[2] = 1
    for i := 3; i <= n; i++ {
        arr[i] = arr[i-1] + arr[i-2] + arr[i-3]
    }
    return arr[n]
}

#
func tribonacci(n int) int {
    if n == 0 {
        return 0
    }
    if n == 1 || n == 2 {
        return 1
    }
    a := 0
    b := 1
    c := 1
    for i := 3; i <= n; i++ {
        c, b, a = a+b+c, c, b
    }
    return c
}

#
var m map[int]int

func tribonacci(n int) int {
    if m == nil {
        m = make(map[int]int)
    }
    if n == 0 {
        return 0
    }
    if n == 1 || n == 2 {
        return 1
    }
    if value, ok := m[n]; ok {
        return value
    } else {
        value := tribonacci(n-1) + tribonacci(n-2) + tribonacci(n-3)
        m[n] = value
    }
    return m[n]
}

1154.一年中的第几天(2)

• 题目

给你一个按 YYYY-MM-DD 格式表示日期的字符串 date，请你计算并返回该日期是当年的第几天。
通常情况下，我们认为 1 月 1 日是每年的第 1 天，1 月 2 日是每年的第 2 天，依此类推。
每个月的天数与现行公元纪年法（格里高利历）一致。
示例 1：输入：date = "2019-01-09" 输出：9
示例 2：输入：date = "2019-02-10" 输出：41
示例 3：输入：date = "2003-03-01" 输出：60
示例 4：输入：date = "2004-03-01" 输出：61
提示：
    date.length == 10
    date[4] == date[7] == '-'，其他的 date[i] 都是数字。
    date 表示的范围从 1900 年 1 月 1 日至 2019 年 12 月 31 日。

• 解题思路

func dayOfYear(date string) int {
    arr := strings.Split(date, "-")
    year, _ := strconv.Atoi(arr[0])
    month, _ := strconv.Atoi(arr[1])
    day, _ := strconv.Atoi(arr[2])
    res := 0
    for i := 0; i < month; i++ {
        switch i {
        case 1, 3, 5, 7, 8, 10, 12:
            res = res + 31
        case 4, 6, 9, 11:
            res = res + 30
        case 2:
            res = res + 28
            if year%400 == 0 || (year%4 == 0 && year%100 != 0) {
                res = res + 1
            }
        }
    }
    res = res + day
    return res
}

#
func dayOfYear(date string) int {
    format := "2006-01-02"
    t, _ := time.Parse(format, date)
    return t.YearDay()
}

1160.拼写单词(3)

• 题目

给你一份『词汇表』（字符串数组） words 和一张『字母表』（字符串） chars。
假如你可以用 chars 中的『字母』（字符）拼写出 words 中的某个『单词』（字符串），
那么我们就认为你掌握了这个单词。
注意：每次拼写（指拼写词汇表中的一个单词）时，chars 中的每个字母都只能用一次。
返回词汇表 words 中你掌握的所有单词的 长度之和。
示例 1：输入：words = ["cat","bt","hat","tree"], chars = "atach" 输出：6
解释：  可以形成字符串 "cat" 和 "hat"，所以答案是 3 + 3 = 6。
示例 2：输入：words = ["hello","world","leetcode"], chars = "welldonehoneyr" 输出：10
解释： 可以形成字符串 "hello" 和 "world"，所以答案是 5 + 5 = 10。
提示：
    1 <= words.length <= 1000
    1 <= words[i].length, chars.length <= 100
    所有字符串中都仅包含小写英文字母

• 解题思路

func countCharacters(words []string, chars string) int {
    m := make(map[byte]int)
    for i := range chars {
        m[chars[i]]++
    }
    res := 0
    for i := 0; i < len(words); i++ {
        temp := make(map[byte]int)
        flag := true
        for j := range words[i] {
            temp[words[i][j]]++
        }
        if len(temp) > len(m) {
            continue
        }
        for k, v := range temp {
            if v > m[k] {
                flag = false
                break
            }
        }
        if flag == true {
            res = res + len(words[i])
        }
    }
    return res
}

#
func countCharacters(words []string, chars string) int {
    res := 0
    for i := 0; i < len(words); i++ {
        flag := true
        for _, v := range words[i] {
            if strings.Count(words[i], string(v)) > strings.Count(chars, string(v)) {
                flag = false
                continue
            }
        }
        if flag == true {
            res = res + len(words[i])
        }
    }
    return res
}

#
func countCharacters(words []string, chars string) int {
    m := make([]int, 26)
    for i := range chars {
        m[chars[i]-'a']++
    }
    res := 0
    for i := 0; i < len(words); i++ {
        temp := make([]int, 26)
        flag := true
        for j := range words[i] {
            temp[words[i][j]-'a']++
        }
        if len(temp) > len(m) {
            continue
        }
        for k, v := range temp {
            if v > m[k] {
                flag = false
                break
            }
        }
        if flag == true {
            res = res + len(words[i])
        }
    }
    return res
}

1170.比较字符串最小字母出现频次(2)

• 题目

我们来定义一个函数 f(s)，其中传入参数 s 是一个非空字符串；
该函数的功能是统计 s  中（按字典序比较）最小字母的出现频次。
例如，若 s = "dcce"，那么 f(s) = 2，因为最小的字母是 "c"，它出现了 2 次。
现在，给你两个字符串数组待查表 queries 和词汇表 words，请你返回一个整数数组 answer 作为答案，
其中每个 answer[i] 是满足 f(queries[i]) < f(W) 的词的数目，W 是词汇表 words 中的词。
示例 1：输入：queries = ["cbd"], words = ["zaaaz"] 输出：[1]
解释：查询 f("cbd") = 1，而 f("zaaaz") = 3 所以 f("cbd") < f("zaaaz")。
示例 2：输入：queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"] 输出：[1,2]
解释：第一个查询 f("bbb") < f("aaaa")，第二个查询 f("aaa") 和 f("aaaa") 都 > f("cc")。
提示：
    1 <= queries.length <= 2000
    1 <= words.length <= 2000
    1 <= queries[i].length, words[i].length <= 10
    queries[i][j], words[i][j] 都是小写英文字母

• 解题思路

func numSmallerByFrequency(queries []string, words []string) []int {
    queriesArr := make([]int, len(queries))
    wordsArr := make([]int, len(words))
    res := make([]int, 0)
    for i := 0; i < len(words); i++ {
        wordsArr[i] = f(words[i])
    }
    for i := 0; i < len(queries); i++ {
        queriesArr[i] = f(queries[i])
        count := 0
        for j := 0; j < len(wordsArr); j++ {
            if queriesArr[i] < wordsArr[j] {
                count++
            }
        }
        res = append(res, count)
    }
    return res
}

func f(str string) int {
    min := str[0]
    count := 1
    for i := 1; i < len(str); i++ {
        if str[i] < min {
            min = str[i]
            count = 1
        } else if str[i] == min{
            count++
        }
    }
    return count
}

#
func numSmallerByFrequency(queries []string, words []string) []int {
    wordsArr := make([]int, len(words))
    res := make([]int, 0)
    for i := 0; i < len(words); i++ {
        wordsArr[i] = f(words[i])
    }
    sort.Ints(wordsArr)
    for i := 0; i < len(queries); i++ {
        value := f(queries[i])
        count := binarySearch(value, wordsArr)
        res = append(res, count)
    }
    return res
}

func binarySearch(value int, target []int) int {
    left := 0
    right := len(target) - 1
    for left < right {
        mid := left + (right-left)/2
        if target[mid] > value {
            right = mid
        } else {
            left = mid + 1
        }
    }
    if target[left] <= value {
        return 0
    }
    return len(target) - left
}

func f(str string) int {
    min := str[0]
    count := 1
    for i := 1; i < len(str); i++ {
        if str[i] < min {
            min = str[i]
            count = 1
        } else if str[i] == min {
            count++
        }
    }
    return count
}

1175.质数排列(1)

• 题目

请你帮忙给从 1 到 n 的数设计排列方案，使得所有的「质数」都应该被放在「质数索引」（索引从 1 开始）上；
你需要返回可能的方案总数。
让我们一起来回顾一下「质数」：质数一定是大于 1 的，并且不能用两个小于它的正整数的乘积来表示。
由于答案可能会很大，所以请你返回答案 模 mod 10^9 + 7 之后的结果即可。
示例 1：输入：n = 5 输出：12
解释：举个例子，[1,2,5,4,3] 是一个有效的排列，但 [5,2,3,4,1] 不是，
因为在第二种情况里质数 5 被错误地放在索引为 1 的位置上。
示例 2：输入：n = 100 输出：682289015
提示：
    1 <= n <= 100

• 解题思路

func numPrimeArrangements(n int) int {
    primeNum := 0
    for i := 2; i <= n; i++ {
        if isPrime(i) {
            primeNum++
        }
    }
    a := 1
    for i := 2; i <= primeNum; i++ {
        a = a * i % 1000000007
    }
    for i := 2; i <= n-primeNum; i++ {
        a = a * i % 1000000007
    }
    return a
}

func isPrime(n int) bool {
    if n == 2 || n == 3 {
        return true
    }
    for i := 2; i*i <= n; i++ {
        if n%i == 0 {
            return false
        }
    }
    return true
}

1184.公交站间的距离(2)

• 题目

环形公交路线上有 n 个站，按次序从 0 到 n - 1 进行编号。
我们已知每一对相邻公交站之间的距离，
distance[i] 表示编号为 i 的车站和编号为 (i + 1) % n 的车站之间的距离。
环线上的公交车都可以按顺时针和逆时针的方向行驶。
返回乘客从出发点 start 到目的地 destination 之间的最短距离。
示例 1：输入：distance = [1,2,3,4], start = 0, destination = 1 输出：1
解释：公交站 0 和 1 之间的距离是 1 或 9，最小值是 1。
示例 2：输入：distance = [1,2,3,4], start = 0, destination = 2 输出：3
解释：公交站 0 和 2 之间的距离是 3 或 7，最小值是 3。
示例 3：输入：distance = [1,2,3,4], start = 0, destination = 3 输出：4
解释：公交站 0 和 3 之间的距离是 6 或 4，最小值是 4。
提示：
    1 <= n <= 10^4
    distance.length == n
    0 <= start, destination < n
    0 <= distance[i] <= 10^4

• 解题思路

func distanceBetweenBusStops(distance []int, start int, destination int) int {
    x := 0
    y := 0
    for i := start; i != destination; i = (i + 1) % len(distance) {
        x = x + distance[i]
    }
    for i := destination; i != start; i = (i + 1) % len(distance) {
        y = y + distance[i]
    }
    if x > y {
        return y
    }
    return x
}

#
func distanceBetweenBusStops(distance []int, start int, destination int) int {
    x := 0
    sum := 0
    for i := 0; i < len(distance); i++ {
        sum = sum + distance[i]
        if start < destination {
            if i >= start && i < destination {
                x = x + distance[i]
            }
        } else {
            if i >= destination && i < start {
                x = x + distance[i]
            }
        }
    }
    if sum-x > x {
        return x
    }
    return sum - x
}

1185.一周中的第几天(3)

• 题目

给你一个日期，请你设计一个算法来判断它是对应一周中的哪一天。
输入为三个整数：day、month 和 year，分别表示日、月、年。
您返回的结果必须是这几个值中的一个 
{"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"}。
示例 1：输入：day = 31, month = 8, year = 2019 输出："Saturday"
示例 2：输入：day = 18, month = 7, year = 1999 输出："Sunday"
示例 3：输入：day = 15, month = 8, year = 1993 输出："Sunday"
提示：
    给出的日期一定是在 1971 到 2100 年之间的有效日期。

• 解题思路

func dayOfTheWeek(day int, month int, year int) string {
    t, _ := time.Parse("2006-01-02", fmt.Sprintf("%04d-%02d-%02d", year, month, day))
    return t.Weekday().String()
}

#
// 蔡勒公式
// 基姆拉尔森计算公式
// https://baike.baidu.com/item/%E8%94%A1%E5%8B%92%E5%85%AC%E5%BC%8F
// https://www.cnblogs.com/SeekHit/p/7498408.html
// Week = (y+y/4-y/100+y/400+2*m+3*(m+1)/5+d) mod 7；
func dayOfTheWeek(day int, month int, year int) string {
    arr := []string{"Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"}
    if month == 1 || month == 2 {
        month = month + 12
        year--
    }
    week := (year + year/4 - year/100 + year/400 + 2*month + 3*(month+1)/5 + day) % 7
    return arr[week]
}

#
var arr = []string{"Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"}
var monthDate = []int{31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}

func dayOfTheWeek(day int, month int, year int) string {
    day1 := totalDay(1993, 8, 15)
    day2 := totalDay(year, month, day)
    diff := 6 - day1%7
    return arr[(day2+diff)%7]
}

func totalDay(year, month, day int) int {
    total := 0
    for i := 1971; i < year; i++ {
        total = total + 365
        if isLeap(i) {
            total = total + 1
        }
    }
    for i := 0; i < month-1; i++ {
        total = total + monthDate[i]
        if i == 1 && isLeap(year) {
            total = total + 1
        }
    }
    total = total + day
    return total
}

func isLeap(year int) bool {
    return year%400 == 0 || (year%4 == 0 && year%100 != 0)
}

1189.“气球”的最大数量(3)

• 题目

给你一个字符串 text，你需要使用 text 中的字母来拼凑尽可能多的单词 "balloon"（气球）。
字符串 text 中的每个字母最多只能被使用一次。请你返回最多可以拼凑出多少个单词 "balloon"。
示例 1：输入：text = "nlaebolko" 输出：1
示例 2：输入：text = "loonbalxballpoon" 输出：2
示例 3：输入：text = "leetcode" 输出：0
提示：
    1 <= text.length <= 10^4
    text 全部由小写英文字母组成

• 解题思路

func maxNumberOfBalloons(text string) int {
    m := make([]int, 26)
    str := "ablon"
    for i := 0; i < len(str); i++ {
        m[str[i]-'a']++
    }
    for i := 0; i < len(text); i++ {
        if m[text[i]-'a'] > 0 {
            m[text[i]-'a']++
        }
    }
    min := math.MaxInt32
    for k, v := range m {
        if v == 0 {
            continue
        }
        if k+'a' == 'l' || k+'a' == 'o' {
            v = (v - 1) / 2
        } else {
            v = v - 1
        }
        if v < min {
            min = v
        }
    }
    return min
}

#
func maxNumberOfBalloons(text string) int {
    m := make([]int, 26)
    for i := 0; i < len(text); i++ {
        m[text[i]-'a']++
    }
    res := 0
    str := "balloon"
    for {
        for i := 0; i < len(str); i++ {
            m[str[i]-'a']--
            if m[str[i]-'a'] < 0 {
                return res
            }
        }
        res++
    }
}

#
func maxNumberOfBalloons(text string) int {
    arr := make([]int, 0)
    str := "ablon"
    for i := 0; i < len(str); i++ {
        if str[i] == 'l' || str[i] == 'o' {
            arr = append(arr, strings.Count(text, string(str[i]))/2)
        } else {
            arr = append(arr, strings.Count(text, string(str[i])))
        }
    }
    min := arr[0]
    for i := 1; i < len(arr); i++ {
        if arr[i] < min {
            min = arr[i]
        }
    }
    return min
}

1200.最小绝对差(2)

• 题目

给你个整数数组 arr，其中每个元素都 不相同。
请你找到所有具有最小绝对差的元素对，并且按升序的顺序返回。
示例 1：输入：arr = [4,2,1,3] 输出：[[1,2],[2,3],[3,4]]
示例 2：输入：arr = [1,3,6,10,15] 输出：[[1,3]]
示例 3：输入：arr = [3,8,-10,23,19,-4,-14,27] 输出：[[-14,-10],[19,23],[23,27]]
提示：
    2 <= arr.length <= 10^5
    -10^6 <= arr[i] <= 10^6

• 解题思路

func minimumAbsDifference(arr []int) [][]int {
    sort.Ints(arr)
    result := make([][]int, 0)
    min := arr[1] - arr[0]
    result = append(result, []int{arr[0], arr[1]})
    for i := 2; i < len(arr); i++ {
        value := arr[i] - arr[i-1]
        if value < min {
            min = value
            result = make([][]int, 0)
            result = append(result, []int{arr[i-1], arr[i]})
        } else if value == min {
            result = append(result, []int{arr[i-1], arr[i]})
        }
    }
    return result
}

#
func minimumAbsDifference(arr []int) [][]int {
    sort.Ints(arr)
    result := make([][]int, 0)
    min := arr[1] - arr[0]
    for i := 2; i < len(arr); i++ {
        if min > arr[i]-arr[i-1] {
            min = arr[i] - arr[i-1]
        }
    }
    for i := 1; i < len(arr); i++ {
        if min == arr[i]-arr[i-1] {
            result = append(result, []int{arr[i-1], arr[i]})
        }
    }
    return result
}

1101-1200-Medium

1104.二叉树寻路(3)

• 题目

在一棵无限的二叉树上，每个节点都有两个子节点，树中的节点 逐行 依次按“之” 字形进行标记。
如下图所示，在奇数行（即，第一行、第三行、第五行……）中，按从左到右的顺序进行标记；
而偶数行（即，第二行、第四行、第六行……）中，按从右到左的顺序进行标记。
给你树上某一个节点的标号 label，请你返回从根节点到该标号为 label 节点的路径，
该路径是由途经的节点标号所组成的。
示例 1：输入：label = 14 输出：[1,3,4,14]
示例 2：输入：label = 26 输出：[1,2,6,10,26]
提示：1 <= label <= 10^6

• 解题思路

func pathInZigZagTree(label int) []int {
    res := make([]int, 0)
    for label > 0 {
        res = append(res, label)
        label = label / 2
    }
    for i := 0; i < len(res)/2; i++ {
        res[i], res[len(res)-1-i] = res[len(res)-1-i], res[i]
    }
    i := 1
    if len(res)%2 == 0 {
        i = 2
    }
    for ; i < len(res); i = i + 2 {
        res[i] = (1<<i)*3 - 1 - res[i]
    }
    return res
}

# 2
func pathInZigZagTree(label int) []int {
    length := int(math.Log2(float64(label)))
    res := make([]int, length+1)
    res[length] = label
    length--
    i := 1
    for length >= 0 {
        target := int(math.Pow(2, float64(length+1))) + int(math.Pow(2, float64(length))) - 1
        if i%2 == 1 {
            res[length] = target - label/2
        } else {
            res[length] = label / 2
        }
        i++
        length--
        label = label / 2
    }
    return res
}

# 3
func pathInZigZagTree(label int) []int {
    res := make([]int, 0)
    for label > 1 {
        res = append([]int{label}, res...)
        label = label / 2
        length := bits.Len32(uint32(label)) - 1
        label = label ^ ((1 << length) - 1) // 7^3=4 => 111^11=100
    }
    res = append([]int{1}, res...)
    return res
}

1105.填充书架(1)

• 题目

附近的家居城促销，你买回了一直心仪的可调节书架，打算把自己的书都整理到新的书架上。
你把要摆放的书 books都整理好，叠成一摞：
从上往下，第 i本书的厚度为 books[i][0]，高度为 books[i][1]。
按顺序将这些书摆放到总宽度为shelf_width 的书架上。
先选几本书放在书架上（它们的厚度之和小于等于书架的宽度 shelf_width），然后再建一层书架。
重复这个过程，直到把所有的书都放在书架上。
需要注意的是，在上述过程的每个步骤中，摆放书的顺序与你整理好的顺序相同。 
例如，如果这里有 5 本书，那么可能的一种摆放情况是：
第一和第二本书放在第一层书架上，第三本书放在第二层书架上，第四和第五本书放在最后一层书架上。
每一层所摆放的书的最大高度就是这一层书架的层高，书架整体的高度为各层高之和。
以这种方式布置书架，返回书架整体可能的最小高度。
示例：输入：books = [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]], shelf_width = 4 输出：6
解释：3 层书架的高度和为 1 + 3 + 2 = 6 。
第 2 本书不必放在第一层书架上。
提示：1 <= books.length <= 1000
1 <= books[i][0] <= shelf_width <= 1000
1 <= books[i][1] <= 1000

• 解题思路

func minHeightShelves(books [][]int, shelf_width int) int {
    n := len(books)
    dp := make([]int, n+1) // 以第i本书作为结尾的总高度
    for i := 1; i <= n; i++ {
        w, h := books[i-1][0], books[i-1][1]
        dp[i] = dp[i-1] + h // 当前这本书单独一层的高度
        for j := i - 1; j > 0; j-- {
            if w+books[j-1][0] <= shelf_width {
                w = w + books[j-1][0]
                h = max(h, books[j-1][1])
                dp[i] = min(dp[i], dp[j-1]+h)
            } else {
                break
            }
        }
    }
    return dp[n]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

1109.航班预订统计(2)

• 题目

这里有 n 个航班，它们分别从 1 到 n 进行编号。
我们这儿有一份航班预订表，
表中第 i 条预订记录 bookings[i] = [i, j, k] 意味着我们在从 i 到 j 的每个航班上预订了 k 个座位。
请你返回一个长度为 n 的数组 answer，按航班编号顺序返回每个航班上预订的座位数。
示例：输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5 输出：[10,55,45,25,25]
提示：1 <= bookings.length <= 20000
    1 <= bookings[i][0] <= bookings[i][1] <= n <= 20000
    1 <= bookings[i][2] <= 10000

• 解题思路

func corpFlightBookings(bookings [][]int, n int) []int {
    arr := make([]int, n+1)
    for i := 0; i < len(bookings); i++ {
        start := bookings[i][0] - 1
        end := bookings[i][1] - 1
        count := bookings[i][2]
        arr[start] = arr[start] + count
        arr[end+1] = arr[end+1] - count
    }
    res := make([]int, 0)
    total := 0
    for i := 0; i < n; i++ {
        total = total + arr[i]
        res = append(res, total)
    }
    return res
}

# 2
func corpFlightBookings(bookings [][]int, n int) []int {
    arr := make([]int, n)
    for i := 0; i < len(bookings); i++ {
        start := bookings[i][0]
        end := bookings[i][1]
        count := bookings[i][2]
        arr[start-1] = arr[start-1] + count
        if end < n {
            arr[end] = arr[end] - count
        }
    }
    for i := 1; i < n; i++ {
        arr[i] = arr[i] + arr[i-1]
    }
    return arr
}

1110.删点成林(1)

• 题目

给出二叉树的根节点root，树上每个节点都有一个不同的值。
如果节点值在to_delete中出现，我们就把该节点从树上删去，最后得到一个森林（一些不相交的树构成的集合）。
返回森林中的每棵树。你可以按任意顺序组织答案。
示例：输入：root = [1,2,3,4,5,6,7], to_delete = [3,5] 输出：[[1,2,null,4],[6],[7]]
提示：树中的节点数最大为1000。
每个节点都有一个介于1 到1000之间的值，且各不相同。
to_delete.length <= 1000
to_delete 包含一些从1 到1000、各不相同的值。

• 解题思路

var res []*TreeNode
var m map[int]bool

func delNodes(root *TreeNode, to_delete []int) []*TreeNode {
    res = make([]*TreeNode, 0)
    m = make(map[int]bool)
    for i := 0; i < len(to_delete); i++ {
        m[to_delete[i]] = true
    }
    root = dfs(root)
    if root != nil {
        res = append(res, root)
    }
    return res
}

func dfs(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    root.Left = dfs(root.Left)
    root.Right = dfs(root.Right)
    if m[root.Val] == true {
        if root.Left != nil {
            res = append(res, root.Left)
        }
        if root.Right != nil {
            res = append(res, root.Right)
        }
        return nil
    }
    return root
}

1111.有效括号的嵌套深度(3)

• 题目

有效括号字符串 定义：对于每个左括号，都能找到与之对应的右括号，反之亦然。
详情参见题末「有效括号字符串」部分。
嵌套深度 depth 定义：即有效括号字符串嵌套的层数，depth(A) 表示有效括号字符串 A 的嵌套深度。
详情参见题末「嵌套深度」部分。
有效括号字符串类型与对应的嵌套深度计算方法如下图所示：
给你一个「有效括号字符串」 seq，请你将其分成两个不相交的有效括号字符串，A 和 B，
并使这两个字符串的深度最小。
    不相交：每个 seq[i] 只能分给 A 和 B 二者中的一个，不能既属于 A 也属于 B 。
    A 或 B 中的元素在原字符串中可以不连续。
    A.length + B.length = seq.length
    深度最小：max(depth(A), depth(B)) 的可能取值最小。 
划分方案用一个长度为 seq.length 的答案数组 answer 表示，编码规则如下：
    answer[i] = 0，seq[i] 分给 A 。
    answer[i] = 1，seq[i] 分给 B 。
如果存在多个满足要求的答案，只需返回其中任意 一个 即可。
示例 1：输入：seq = "(()())" 输出：[0,1,1,1,1,0]
示例 2：输入：seq = "()(())()" 输出：[0,0,0,1,1,0,1,1]
解释：本示例答案不唯一。
按此输出 A = "()()", B = "()()", max(depth(A), depth(B)) = 1，它们的深度最小。
像 [1,1,1,0,0,1,1,1]，也是正确结果，其中 A = "()()()", B = "()", max(depth(A), depth(B)) = 1 。 
提示：1 < seq.size <= 10000
有效括号字符串：仅由 "(" 和 ")" 构成的字符串，对于每个左括号，都能找到与之对应的右括号，反之亦然。
下述几种情况同样属于有效括号字符串：
  1. 空字符串
  2. 连接，可以记作 AB（A 与 B 连接），其中 A 和 B 都是有效括号字符串
  3. 嵌套，可以记作 (A)，其中 A 是有效括号字符串
嵌套深度：类似地，我们可以定义任意有效括号字符串 s 的 嵌套深度 depth(S)：
  1. s 为空时，depth("") = 0
  2. s 为 A 与 B 连接时，depth(A + B) = max(depth(A), depth(B))，其中 A 和 B 都是有效括号字符串
  3. s 为嵌套情况，depth("(" + A + ")") = 1 + depth(A)，其中 A 是有效括号字符串
例如：""，"()()"，和 "()(()())" 都是有效括号字符串，
嵌套深度分别为 0，1，2，而 ")(" 和 "(()" 都不是有效括号字符串。

• 解题思路

func maxDepthAfterSplit(seq string) []int {
    res := make([]int, 0)
    level := 0
    for i := 0; i < len(seq); i++ {
        if seq[i] == '(' {
            level++
            res = append(res, level%2)
        } else {
            res = append(res, level%2)
            level--
        }
    }
    return res
}

# 2
func maxDepthAfterSplit(seq string) []int {
    res := make([]int, 0)
    for i := 0; i < len(seq); i++ {
        if seq[i] == '(' {
            res = append(res, i%2)
        } else {
            res = append(res, 1-i%2)
        }
    }
    return res
}

# 3
func maxDepthAfterSplit(seq string) []int {
    res := make([]int, 0)
    a, b := 0, 0
    for i := 0; i < len(seq); i++ {
        if seq[i] == '(' {
            // 谁少给谁
            if a <= b {
                a++
                res = append(res, 0)
            } else {
                b++
                res = append(res, 1)
            }
        } else {
            // 谁多减谁
            if a > b {
                a--
                res = append(res, 0)
            } else {
                b--
                res = append(res, 1)
            }
        }
    }
    return res
}

1123.最深叶节点的最近公共祖先(2)

• 题目

给你一个有根节点的二叉树，找到它最深的叶节点的最近公共祖先。
回想一下：
叶节点 是二叉树中没有子节点的节点
树的根节点的深度为0，如果某一节点的深度为d，那它的子节点的深度就是d+1
如果我们假定 A 是一组节点S的 最近公共祖先，S中的每个节点都在以 A 为根节点的子树中，
且 A的深度达到此条件下可能的最大值。
注意：本题与力扣 865 重复：
示例 1：输入：root = [3,5,1,6,2,0,8,null,null,7,4] 输出：[2,7,4]
解释：我们返回值为 2 的节点，在图中用黄色标记。
在图中用蓝色标记的是树的最深的节点。
注意，节点 6、0 和 8 也是叶节点，但是它们的深度是 2 ，而节点 7 和 4 的深度是 3 。
示例 2：输入：root = [1] 输出：[1]
解释：根节点是树中最深的节点，它是它本身的最近公共祖先。
示例 3：输入：root = [0,1,3,null,2] 输出：[2]
解释：树中最深的叶节点是 2 ，最近公共祖先是它自己。
提示：给你的树中将有1 到 1000 个节点。
树中每个节点的值都在 1 到 1000 之间。
每个节点的值都是独一无二的。

• 解题思路

func lcaDeepestLeaves(root *TreeNode) *TreeNode {
    res, _ := dfs(root, 0)
    return res
}

func dfs(root *TreeNode, level int) (*TreeNode, int) {
    if root == nil {
        return root, level
    }
    leftNode, left := dfs(root.Left, level+1)
    rightNode, right := dfs(root.Right, level+1)
    if left == right {
        return root, left + 1
    } else if left > right {
        return leftNode, left + 1
    }
    return rightNode, right + 1
}

# 2
func lcaDeepestLeaves(root *TreeNode) *TreeNode {
    if root == nil{
        return nil
    }
    left := dfs(root.Left)
    right := dfs(root.Right)
    if left == right{
        return root
    }else if left > right{
        return lcaDeepestLeaves(root.Left)
    }
    return lcaDeepestLeaves(root.Right)
}

func dfs(root *TreeNode) (int) {
    if root == nil {
        return 0
    }
    left := dfs(root.Left)
    right := dfs(root.Right)
    return 1+max(left,right)
}

func max(a, b int)int  {
    if a > b{
        return a
    }
    return b
}

1124.表现良好的最长时间段(3)

• 题目

给你一份工作时间表hours，上面记录着某一位员工每天的工作小时数。
我们认为当员工一天中的工作小时数大于8 小时的时候，那么这一天就是「劳累的一天」。
所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格 大于「不劳累的天数」。
请你返回「表现良好时间段」的最大长度。
示例 1：输入：hours = [9,9,6,0,6,6,9] 输出：3
解释：最长的表现良好时间段是 [9,9,6]。
提示：1 <= hours.length <= 10000
0 <= hours[i] <= 16

• 解题思路

func longestWPI(hours []int) int {
    arr := make([]int, 0)
    for i := 0; i < len(hours); i++ {
        if hours[i] > 8 {
            arr = append(arr, 1)
        } else {
            arr = append(arr, -1)
        }
    }
    temp := make([]int, len(hours)+1)
    for i := 1; i <= len(hours); i++ {
        temp[i] = temp[i-1] + arr[i-1]
    }
    stack := make([]int, 0)
    // 单调栈
    for i := 0; i < len(temp); i++ {
        if len(stack) == 0 || temp[stack[len(stack)-1]] > temp[i] {
            stack = append(stack, i)
        }
    }
    res := 0
    for i := len(temp) - 1; i >= 0; i-- {
        if len(stack) == 0 {
            break
        }
        for len(stack) > 0 && temp[i] > temp[stack[len(stack)-1]] {
            if i-stack[len(stack)-1] > res {
                res = i - stack[len(stack)-1]
            }
            stack = stack[:len(stack)-1]
        }
    }
    return res
}

# 2
func longestWPI(hours []int) int {
    arr := make([]int, 0)
    for i := 0; i < len(hours); i++ {
        if hours[i] > 8 {
            arr = append(arr, 1)
        } else {
            arr = append(arr, -1)
        }
    }
    temp := make([]int, len(hours)+1)
    for i := 1; i <= len(hours); i++ {
        temp[i] = temp[i-1] + arr[i-1]
    }
    res := 0
    for i := 0; i < len(hours); i++ {
        for j := i; j < len(hours); j++ {
            count := temp[j+1] - temp[i]
            if count > 0 {
                res = max(res, j-i+1)
            }
        }
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

# 3
func longestWPI(hours []int) int {
    m := make(map[int]int)
    count := 0
    res := 0
    for i := 0; i < len(hours); i++ {
        if hours[i] > 8 {
            count++
        } else {
            count--
        }
        if count > 0 {
            res = i + 1
        } else {
            if _, ok := m[count]; ok == false {
                m[count] = i
            }
            // (count-(count-1))=1>0
            if _, ok := m[count-1]; ok == true {
                res = max(res, i-m[count-1])
            }

        }
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

1129.颜色交替的最短路径(2)

• 题目

在一个有向图中，节点分别标记为0, 1, ..., n-1。这个图中的每条边不是红色就是蓝色，且存在自环或平行边。
red_edges中的每一个[i, j]对表示从节点 i 到节点 j 的红色有向边。
类似地，blue_edges中的每一个[i, j]对表示从节点 i 到节点 j 的蓝色有向边。
返回长度为 n 的数组answer，其中answer[X]是从节点0到节点X的红色边和蓝色边交替出现的最短路径的长度。
如果不存在这样的路径，那么 answer[x] = -1。
示例 1：输入：n = 3, red_edges = [[0,1],[1,2]], blue_edges = [] 输出：[0,1,-1]
示例 2：输入：n = 3, red_edges = [[0,1]], blue_edges = [[2,1]] 输出：[0,1,-1]
示例 3：输入：n = 3, red_edges = [[1,0]], blue_edges = [[2,1]] 输出：[0,-1,-1]
示例 4：输入：n = 3, red_edges = [[0,1]], blue_edges = [[1,2]] 输出：[0,1,2]
示例 5：输入：n = 3, red_edges = [[0,1],[0,2]], blue_edges = [[1,0]] 输出：[0,1,1]
提示：1 <= n <= 100
red_edges.length <= 400
blue_edges.length <= 400
red_edges[i].length == blue_edges[i].length == 2
0 <= red_edges[i][j], blue_edges[i][j] < n

• 解题思路

var redArr [][]int
var blueArr [][]int
var res []int

func shortestAlternatingPaths(n int, red_edges [][]int, blue_edges [][]int) []int {
    redArr = make([][]int, n)
    blueArr = make([][]int, n)
    for i := 0; i < len(red_edges); i++ {
        a, b := red_edges[i][0], red_edges[i][1]
        redArr[a] = append(redArr[a], b)
    }
    for i := 0; i < len(blue_edges); i++ {
        a, b := blue_edges[i][0], blue_edges[i][1]
        blueArr[a] = append(blueArr[a], b)
    }
    res = make([]int, n)
    for i := 0; i < n; i++ {
        res[i] = -1
    }
    res[0] = 0
    bfs(n, 0) // 红
    bfs(n, 1) // 蓝
    return res
}

func bfs(n int, color int) {
    visited := make([][2]bool, n)
    visited[0][color] = true
    queue := make([]int, 0)
    queue = append(queue, 0)
    count := 0
    for len(queue) > 0 {
        length := len(queue)
        for i := 0; i < length; i++ {
            node := queue[i]
            targetColor := count % 2
            if targetColor == color { //偶数次和当前颜色一致
                for i := 0; i < len(redArr[node]); i++ {
                    next := redArr[node][i]
                    if visited[next][targetColor] == false {
                        visited[next][targetColor] = true
                        if res[next] == -1 || res[next] > count+1 {
                            res[next] = count + 1
                        }
                        queue = append(queue, next)
                    }
                }
            } else {
                for i := 0; i < len(blueArr[node]); i++ {
                    next := blueArr[node][i]
                    if visited[next][targetColor] == false {
                        visited[next][targetColor] = true
                        if res[next] == -1 || res[next] > count+1 {
                            res[next] = count + 1
                        }
                        queue = append(queue, next)
                    }
                }
            }
        }
        queue = queue[length:]
        count++
    }
}

# 2
func shortestAlternatingPaths(n int, red_edges [][]int, blue_edges [][]int) []int {
    redArr, blueArr := make([][]int, n), make([][]int, n)
    for i := 0; i < len(red_edges); i++ {
        a, b := red_edges[i][0], red_edges[i][1]
        redArr[a] = append(redArr[a], b)
    }
    for i := 0; i < len(blue_edges); i++ {
        a, b := blue_edges[i][0], blue_edges[i][1]
        blueArr[a] = append(blueArr[a], b)
    }
    res := make([]int, n) // res[0] = 0
    for i := 1; i < n; i++ {
        res[i] = -1
    }
    queue, visited := make([][2]int, 0), make([][2]bool, n)
    for i := 0; i < len(redArr[0]); i++ {
        queue = append(queue, [2]int{redArr[0][i], 0})
    }
    for i := 0; i < len(blueArr[0]); i++ {
        queue = append(queue, [2]int{blueArr[0][i], 1})
    }
    count := 1
    for len(queue) > 0 {
        length := len(queue)
        for i := 0; i < length; i++ {
            node, targetColor := queue[i][0], queue[i][1]
            if res[node] == -1 {
                res[node] = count
            }
            if targetColor == 0 && visited[node][targetColor] == false {
                visited[node][targetColor] = true
                for j := 0; j < len(blueArr[node]); j++ {
                    queue = append(queue, [2]int{blueArr[node][j], 1})
                }
            }
            if targetColor == 1 && visited[node][targetColor] == false {
                visited[node][targetColor] = true
                for j := 0; j < len(redArr[node]); j++ {
                    queue = append(queue, [2]int{redArr[node][j], 0})
                }
            }
        }
        queue = queue[length:]
        count++
    }
    return res
}

1130.叶值的最小代价生成树(3)

• 题目

给你一个正整数数组arr，考虑所有满足以下条件的二叉树：
每个节点都有 0 个或是 2 个子节点。
数组arr中的值与树的中序遍历中每个叶节点的值一一对应。
（知识回顾：如果一个节点有 0 个子节点，那么该节点为叶节点。）
每个非叶节点的值等于其左子树和右子树中叶节点的最大值的乘积。
在所有这样的二叉树中，返回每个非叶节点的值的最小可能总和。这个和的值是一个32 位整数。
示例：输入：arr = [6,2,4] 输出：32
解释： 有两种可能的树，第一种的非叶节点的总和为 36，第二种非叶节点的总和为 32。
    24            24
   /  \          /  \
  12   4        6    8
 /  \               / \
6    2             2   4
提示：2 <= arr.length <= 40
1 <= arr[i] <= 15
答案保证是一个 32 位带符号整数，即小于2^31。

• 解题思路

func mctFromLeafValues(arr []int) int {
    res := 0
    stack := make([]int, 0) // 单调递减栈
    stack = append(stack, math.MaxInt32)
    for i := 0; i < len(arr); i++ {
        for len(stack) > 0 && arr[i] >= stack[len(stack)-1] { // 大于栈顶
            middle := stack[len(stack)-1] // 中间
            stack = stack[:len(stack)-1]
            left := stack[len(stack)-1]
            right := arr[i]
            res = res + middle*min(left, right)
        }
        stack = append(stack, arr[i])
    }
    for len(stack) > 2 {
        a := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        b := stack[len(stack)-1]
        res = res + a*b
    }
    return res
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

# 2
func mctFromLeafValues(arr []int) int {
    n := len(arr)
    maxArr := make([][]int, n)
    for i := 0; i < n; i++ {
        maxArr[i] = make([]int, n)
        maxValue := arr[i]
        for j := i; j < n; j++ {
            maxValue = max(maxValue, arr[j])
            maxArr[i][j] = maxValue // i到j之间的最大值
        }
    }
    dp := make([][]int, n)
    for i := 0; i < n; i++ {
        dp[i] = make([]int, n)
    }
    for j := 0; j < n; j++ {
        for i := j - 1; i >= 0; i-- {
            dp[i][j] = math.MaxInt32
            for k := i; k+1 <= j; k++ {
                // dp[i][j]代表从i到j之间的最小代价
                dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+maxArr[i][k]*maxArr[k+1][j])
            }
        }
    }
    return dp[0][n-1]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

# 3
func mctFromLeafValues(arr []int) int {
    res := 0
    stack := make([]int, 0) // 单调递减栈
    for i := 0; i < len(arr); i++ {
        for len(stack) > 0 && arr[i] >= stack[len(stack)-1] { // 大于栈顶
            middle := stack[len(stack)-1] // 中间
            stack = stack[:len(stack)-1]
            right := arr[i]
            var left int
            if len(stack) == 0 {
                left = math.MaxInt32
            } else {
                left = stack[len(stack)-1]
            }
            res = res + middle*min(left, right)
        }
        stack = append(stack, arr[i])
    }
    for len(stack) >= 2 {
        a := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        b := stack[len(stack)-1]
        res = res + a*b
    }
    return res
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

1131.绝对值表达式的最大值(2)

• 题目

给你两个长度相等的整数数组，返回下面表达式的最大值：
|arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j|
其中下标 i，j 满足0 <= i, j < arr1.length。
示例 1：输入：arr1 = [1,2,3,4], arr2 = [-1,4,5,6] 输出：13
示例 2：输入：arr1 = [1,-2,-5,0,10], arr2 = [0,-2,-1,-7,-4] 输出：20
提示：2 <= arr1.length == arr2.length <= 40000
-10^6 <= arr1[i], arr2[i] <= 10^6

• 解题思路

func maxAbsValExpr(arr1 []int, arr2 []int) int {
    /*
        |arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j|
        =  (arr1[i] + arr2[i] + i) - (arr1[j] + arr2[j] + j)
        =  (arr1[i] + arr2[i] - i) - (arr1[j] + arr2[j] - j)
        =  (arr1[i] - arr2[i] + i) - (arr1[j] - arr2[j] + j)
        =  (arr1[i] - arr2[i] - i) - (arr1[j] - arr2[j] - j)
        = -(arr1[i] + arr2[i] + i) + (arr1[j] + arr2[j] + j)
        = -(arr1[i] + arr2[i] - i) + (arr1[j] + arr2[j] - j)
        = -(arr1[i] - arr2[i] + i) + (arr1[j] - arr2[j] + j)
        = -(arr1[i] - arr2[i] - i) + (arr1[j] - arr2[j] - j)
        其中：
        A = arr1[i] + arr2[i] + i
        B = arr1[i] + arr2[i] - i
        C = arr1[i] - arr2[i] + i
        D = arr1[i] - arr2[i] - i
        结果：
        max( |arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j|)
        = max(max(A) - min(A),max(B) - min(B),max(C) - min(C), max(D) - min(D))
    */
    arr := make([][]int, 4)
    for i := 0; i < len(arr1); i++ {
        a, b := arr1[i], arr2[i]
        arr[0] = append(arr[0], a+b+i)
        arr[1] = append(arr[1], a+b-i)
        arr[2] = append(arr[2], a-b+i)
        arr[3] = append(arr[3], a-b-i)
    }
    a, b, c, d := getValue(arr[0]), getValue(arr[1]), getValue(arr[2]), getValue(arr[3])
    return max(a, max(b, max(c, d)))
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func getValue(arr []int) int {
    minValue, maxValue := arr[0], arr[0]
    for i := 0; i < len(arr); i++ {
        if arr[i] > maxValue {
            maxValue = arr[i]
        }
        if arr[i] < minValue {
            minValue = arr[i]
        }
    }
    return maxValue - minValue
}

# 2
func maxAbsValExpr(arr1 []int, arr2 []int) int {
    aMaxValue, bMaxValue, cMaxValue, dMaxValue := math.MinInt32, math.MinInt32, math.MinInt32, math.MinInt32
    aMinValue, bMinValue, cMinValue, dMinValue := math.MaxInt32, math.MaxInt32, math.MaxInt32, math.MaxInt32
    for i := 0; i < len(arr1); i++ {
        aMaxValue = max(aMaxValue, arr1[i]+arr2[i]+i)
        aMinValue = min(aMinValue, arr1[i]+arr2[i]+i)
        bMaxValue = max(bMaxValue, arr1[i]+arr2[i]-i)
        bMinValue = min(bMinValue, arr1[i]+arr2[i]-i)
        cMaxValue = max(cMaxValue, arr1[i]-arr2[i]+i)
        cMinValue = min(cMinValue, arr1[i]-arr2[i]+i)
        dMaxValue = max(dMaxValue, arr1[i]-arr2[i]-i)
        dMinValue = min(dMinValue, arr1[i]-arr2[i]-i)
    }
    a, b := aMaxValue-aMinValue, bMaxValue-bMinValue
    c, d := cMaxValue-cMinValue, dMaxValue-dMinValue
    return max(a, max(b, max(c, d)))
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

1138.字母板上的路径(1)

• 题目

我们从一块字母板上的位置(0, 0)出发，该坐标对应的字符为board[0][0]。
在本题里，字母板为board = ["abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"]，如下所示。
我们可以按下面的指令规则行动：
如果方格存在，'U'意味着将我们的位置上移一行；
如果方格存在，'D'意味着将我们的位置下移一行；
如果方格存在，'L'意味着将我们的位置左移一列；
如果方格存在，'R'意味着将我们的位置右移一列；
'!'会把在我们当前位置 (r, c) 的字符board[r][c]添加到答案中。
（注意，字母板上只存在有字母的位置。）
返回指令序列，用最小的行动次数让答案和目标target相同。你可以返回任何达成目标的路径。
示例 1：输入：target = "leet" 输出："DDR!UURRR!!DDD!"
示例 2：输入：target = "code" 输出："RR!DDRR!UUL!R!"
提示：1 <= target.length <= 100
target仅含有小写英文字母。

• 解题思路

func alphabetBoardPath(target string) string {
    res := ""
    x, y := 0, 0
    for i := 0; i < len(target); i++ {
        newX := int(target[i]-'a') / 5
        newY := int(target[i]-'a') % 5
        if x > newX {
            res = res + strings.Repeat("U", x-newX) // 优先向上：从Z往上
        }
        if y > newY {
            res = res + strings.Repeat("L", y-newY) // 优先向左：往Z走
        }
        if y < newY {
            res = res + strings.Repeat("R", newY-y) // 向右
        }
        if x < newX {
            res = res + strings.Repeat("D", newX-x) // 向下
        }
        res = res + "!"
        x, y = newX, newY
    }
    return res
}

1139.最大的以1为边界的正方形(1)

• 题目

给你一个由若干 0 和 1 组成的二维网格grid，请你找出边界全部由 1 组成的最大 正方形 子网格，并返回该子网格中的元素数量。
如果不存在，则返回 0。
示例 1：输入：grid = [[1,1,1],[1,0,1],[1,1,1]] 输出：9
示例 2：输入：grid = [[1,1,0,0]] 输出：1
提示：1 <= grid.length <= 100
1 <= grid[0].length <= 100
grid[i][j] 为0或1

• 解题思路

func largest1BorderedSquare(grid [][]int) int {
    res := 0
    arr := [100][100][2]int{}
    n, m := len(grid), len(grid[0])
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            if grid[i][j] == 0 {
                continue
            }
            if i == 0 {
                arr[i][j][0] = 1
            } else {
                arr[i][j][0] = arr[i-1][j][0] + 1 // 当前坐标上边1的长度
            }
            if j == 0 {
                arr[i][j][1] = 1
            } else {
                arr[i][j][1] = arr[i][j-1][1] + 1 // 当前坐标左边1的长度
            }
            minValue := min(arr[i][j][0], arr[i][j][1]) // 左边、上边连续1选短的
            for k := minValue; k > res; k-- {
                if arr[i][j-k+1][0] >= k && arr[i-k+1][j][1] >= k { // 判断另外2条边
                    res = k
                    break
                }
            }
        }
    }
    return res * res
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

1140.石子游戏II(2)

• 题目

亚历克斯和李继续他们的石子游戏。许多堆石子排成一行，每堆都有正整数颗石子piles[i]。
游戏以谁手中的石子最多来决出胜负。
亚历克斯和李轮流进行，亚历克斯先开始。最初，M = 1。
在每个玩家的回合中，该玩家可以拿走剩下的前X堆的所有石子，其中1 <= X <= 2M。
然后，令M = max(M, X)。
游戏一直持续到所有石子都被拿走。
假设亚历克斯和李都发挥出最佳水平，返回亚历克斯可以得到的最大数量的石头。
示例：输入：piles = [2,7,9,4,4] 输出：10
解释：如果亚历克斯在开始时拿走一堆石子，李拿走两堆，接着亚历克斯也拿走两堆。
在这种情况下，亚历克斯可以拿到 2 + 4 + 4 = 10 颗石子。 
如果亚历克斯在开始时拿走两堆石子，那么李就可以拿走剩下全部三堆石子。
在这种情况下，亚历克斯可以拿到 2 + 7 = 9 颗石子。
所以我们返回更大的 10。 
提示：1 <= piles.length <= 100
1 <= piles[i]<= 10 ^ 4

• 解题思路

func stoneGameII(piles []int) int {
    n := len(piles)
    dp := make([][]int, n+1) // dp[i][j]=>有piles[i:]，M=j的情况下得分
    for i := 0; i <= n; i++ {
        dp[i] = make([]int, n+1)
    }
    sum := 0
    for i := n - 1; i >= 0; i-- {
        sum = sum + piles[i]
        for M := 1; M <= n; M++ {
            if i+2*M >= n { // 可以全部拿走
                dp[i][M] = sum
            } else {
                for j := 1; j <= 2*M; j++ { // 尝试不同拿法，dp[i+j][max(j, M)]其中M=max(j,M)
                    dp[i][M] = max(dp[i][M], sum-dp[i+j][max(j, M)])
                }
            }
        }
    }
    return dp[0][1]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

# 2
var dp [][]int

func stoneGameII(piles []int) int {
    n := len(piles)
    dp = make([][]int, n+1)
    for i := 0; i <= n; i++ {
        dp[i] = make([]int, n+1)
    }
    for i := n - 2; i >= 0; i-- {
        piles[i] = piles[i] + piles[i+1]
    }
    return dfs(piles, 0, 1)
}

func dfs(piles []int, index, M int) int {
    if index >= len(piles) {
        return 0
    }
    if index+2*M >= len(piles) { // 可以全部拿走
        return piles[index]
    }
    if dp[index][M] > 0 {
        return dp[index][M]
    }
    res := 0
    for i := 1; i <= 2*M; i++ { // 尝试不同拿法
        res = max(res, piles[index]-dfs(piles, index+i, max(M, i)))
    }
    dp[index][M] = res
    return dp[index][M]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

1143.最长公共子序列(3)

• 题目

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。
一个字符串的 子序列 是指这样一个新的字符串：
它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
若这两个字符串没有公共子序列，则返回 0。
示例 1:输入：text1 = "abcde", text2 = "ace"  输出：3  
解释：最长公共子序列是 "ace"，它的长度为 3。
示例 2:输入：text1 = "abc", text2 = "abc" 输出：3
解释：最长公共子序列是 "abc"，它的长度为 3。
示例 3:输入：text1 = "abc", text2 = "def" 输出：0
解释：两个字符串没有公共子序列，返回 0。
提示:
    1 <= text1.length <= 1000
    1 <= text2.length <= 1000
    输入的字符串只含有小写英文字符。

• 解题思路

func longestCommonSubsequence(text1 string, text2 string) int {
    n, m := len(text1), len(text2)
    dp := make([][]int, n+1)
    for i := 0; i < n+1; i++ {
        dp[i] = make([]int, m+1)
    }
    for i := 1; i <= n; i++ {
        for j := 1; j <= m; j++ {
            if text1[i-1] == text2[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
            } else {
                dp[i][j] = max(dp[i][j-1], dp[i-1][j])
            }
        }
    }
    return dp[n][m]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

# 2
func longestCommonSubsequence(text1 string, text2 string) int {
    n, m := len(text1), len(text2)
    prev := make([]int, m+1)
    cur := make([]int, m+1)
    for i := 1; i <= n; i++ {
        for j := 1; j <= m; j++ {
            if text1[i-1] == text2[j-1] {
                cur[j] = prev[j-1] + 1
            } else {
                cur[j] = max(prev[j], cur[j-1])
            }
        }
        copy(prev, cur)
    }
    return cur[m]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

# 3
func longestCommonSubsequence(text1 string, text2 string) int {
    n, m := len(text1), len(text2)
    cur := make([]int, m+1)
    for i := 1; i <= n; i++ {
        pre := cur[0]
        for j := 1; j <= m; j++ {
            temp := cur[j]
            if text1[i-1] == text2[j-1] {
                cur[j] = pre + 1
            } else {
                cur[j] = max(cur[j], cur[j-1])
            }
            pre = temp
        }
    }
    return cur[m]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

1144.递减元素使数组呈锯齿状(2)

• 题目

给你一个整数数组nums，每次 操作会从中选择一个元素并 将该元素的值减少1。
如果符合下列情况之一，则数组A就是 锯齿数组：
每个偶数索引对应的元素都大于相邻的元素，即A[0] > A[1] < A[2] > A[3] < A[4] > ...
或者，每个奇数索引对应的元素都大于相邻的元素，即A[0] < A[1] > A[2] < A[3] > A[4] < ...
返回将数组nums转换为锯齿数组所需的最小操作次数。
示例 1：输入：nums = [1,2,3] 输出：2
解释：我们可以把 2 递减到 0，或把 3 递减到 1。
示例 2：输入：nums = [9,6,1,6,2] 输出：4
提示：1 <= nums.length <= 1000
1 <= nums[i] <= 1000

• 解题思路

func movesToMakeZigzag(nums []int) int {
    n := len(nums)
    a, b := 0, 0
    for i := 0; i < n; i++ {
        if i%2 == 0 { // 偶数下标小，如果大于左右两边数，需要减去
            left, right := 0, 0
            if i > 0 && nums[i] >= nums[i-1] {
                left = nums[i] - nums[i-1] + 1
            }
            if i < n-1 && nums[i] >= nums[i+1] {
                right = nums[i] - nums[i+1] + 1
            }
            a = a + max(left, right)
        } else { // 奇数下标小，如果大于左右两边数，需要减去
            left, right := 0, 0
            if nums[i] >= nums[i-1] {
                left = nums[i] - nums[i-1] + 1
            }
            if i < n-1 && nums[i] >= nums[i+1] {
                right = nums[i] - nums[i+1] + 1
            }
            b = b + max(left, right)
        }
    }
    return min(a, b)
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

# 2
func movesToMakeZigzag(nums []int) int {
    n := len(nums)
    a, b := 0, 0
    for i := 0; i < n; i = i + 2 { // 偶数下标小，如果大于左右两边数，需要减去
        left, right := 0, 0
        if i > 0 && nums[i] >= nums[i-1] {
            left = nums[i] - nums[i-1] + 1
        }
        if i < n-1 && nums[i] >= nums[i+1] {
            right = nums[i] - nums[i+1] + 1
        }
        a = a + max(left, right)
    }
    for i := 1; i < n; i = i + 2 { // 奇数下标小，如果大于左右两边数，需要减去
        left, right := 0, 0
        if nums[i] >= nums[i-1] {
            left = nums[i] - nums[i-1] + 1
        }
        if i < n-1 && nums[i] >= nums[i+1] {
            right = nums[i] - nums[i+1] + 1
        }
        b = b + max(left, right)
    }
    return min(a, b)
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

1145.二叉树着色游戏(2)

• 题目

有两位极客玩家参与了一场「二叉树着色」的游戏。游戏中，
给出二叉树的根节点root，树上总共有 n 个节点，且 n 为奇数，其中每个节点上的值从1 到n各不相同。
游戏从「一号」玩家开始（「一号」玩家为红色，「二号」玩家为蓝色），最开始时，
「一号」玩家从 [1, n]中取一个值x（1 <= x <= n）；
「二号」玩家也从[1, n]中取一个值y（1 <= y <= n）且y != x。
「一号」玩家给值为x的节点染上红色，而「二号」玩家给值为y的节点染上蓝色。
之后两位玩家轮流进行操作，每一回合，玩家选择一个他之前涂好颜色的节点，
将所选节点一个 未着色 的邻节点（即左右子节点、或父节点）进行染色。
如果当前玩家无法找到这样的节点来染色时，他的回合就会被跳过。
若两个玩家都没有可以染色的节点时，游戏结束。着色节点最多的那位玩家获得胜利 ✌️。
现在，假设你是「二号」玩家，根据所给出的输入，假如存在一个y值可以确保你赢得这场游戏，则返回true；
若无法获胜，就请返回 false。
示例：输入：root = [1,2,3,4,5,6,7,8,9,10,11], n = 11, x = 3 输出：True
解释：第二个玩家可以选择值为 2 的节点。
提示：二叉树的根节点为root，树上由 n 个节点，节点上的值从 1 到 n 各不相同。
n 为奇数。
1 <= x <= n<= 100

• 解题思路

var targetNode *TreeNode

func btreeGameWinningMove(root *TreeNode, n int, x int) bool {
    dfsTarget(root, x)
    // 统计根节点、目标节点左子树、目标节点右子树
    return dfs(root) > n/2 || dfs(targetNode.Left) > n/2 || dfs(targetNode.Right) > n/2
}

func dfsTarget(root *TreeNode, target int) {
    if root != nil {
        if root.Val == target {
            targetNode = root
            return
        }
        dfsTarget(root.Left, target)
        dfsTarget(root.Right, target)
    }
}

func dfs(root *TreeNode) int {
    if root == nil || root == targetNode {
        return 0
    }
    return 1 + dfs(root.Left) + dfs(root.Right)
}

# 2
var leftSum, rightSum int

func btreeGameWinningMove(root *TreeNode, n int, x int) bool {
    leftSum = 0
    rightSum = 0
    total := dfs(root, x)
    return leftSum > n/2 || rightSum > n/2 || (total-1-leftSum-rightSum) > n/2
}

func dfs(root *TreeNode, x int) int {
    if root == nil {
        return 0
    }
    left := dfs(root.Left, x)
    right := dfs(root.Right, x)
    if root.Val == x {
        leftSum = left
        rightSum = right
    }
    return 1 + left + right
}

1146.快照数组(3)

• 题目

实现支持下列接口的「快照数组」-SnapshotArray：
SnapshotArray(int length)- 初始化一个与指定长度相等的 类数组 的数据结构。初始时，每个元素都等于0。
void set(index, val)- 会将指定索引index处的元素设置为val。
int snap()- 获取该数组的快照，并返回快照的编号snap_id（快照号是调用snap()的总次数减去1）。
int get(index, snap_id)- 根据指定的snap_id选择快照，并返回该快照指定索引 index的值。
示例：输入：["SnapshotArray","set","snap","set","get"]
     [[3],[0,5],[],[0,6],[0,0]]
输出：[null,null,0,null,5]
解释：SnapshotArray snapshotArr = new SnapshotArray(3); // 初始化一个长度为 3 的快照数组
snapshotArr.set(0,5);  // 令 array[0] = 5
snapshotArr.snap();  // 获取快照，返回 snap_id = 0
snapshotArr.set(0,6);
snapshotArr.get(0,0);  // 获取 snap_id = 0 的快照中 array[0] 的值，返回 5
提示：1 <= length<= 50000
题目最多进行50000 次set，snap，和get的调用 。
0 <= index<length
0 <=snap_id <我们调用snap()的总次数
0 <=val <= 10^9

• 解题思路

type SnapshotArray struct {
    id  int
    arr [][]Snap
}

type Snap struct {
    id    int
    value int
}

func Constructor(length int) SnapshotArray {
    return SnapshotArray{
        id:  0,
        arr: make([][]Snap, length),
    }
}

func (this *SnapshotArray) Set(index int, val int) {
    // 保存的是index的操作记录
    this.arr[index] = append(this.arr[index], Snap{
        id:    this.id,
        value: val,
    })
}

func (this *SnapshotArray) Snap() int {
    id := this.id
    this.id++
    return id
}

func (this *SnapshotArray) Get(index int, snap_id int) int {
    n := len(this.arr[index])
    i := 0
    // 根据index的历史记录，找到最后1个id为snap_id的记录
    // 其中id为snap_id的记录可能有多个
    for i < n && this.arr[index][i].id <= snap_id {
        i++
    }
    if i == 0 {
        return 0
    }
    i--
    return this.arr[index][i].value
}

# 2
type SnapshotArray struct {
    id  int
    arr []map[int]int
}

func Constructor(length int) SnapshotArray {
    return SnapshotArray{
        id:  0,
        arr: make([]map[int]int, length),
    }
}

func (this *SnapshotArray) Set(index int, val int) {
    if this.arr[index] == nil {
        this.arr[index] = make(map[int]int)
    }
    this.arr[index][this.id] = val
}

func (this *SnapshotArray) Snap() int {
    id := this.id
    this.id++
    return id
}

func (this *SnapshotArray) Get(index int, snap_id int) int {
    if this.arr[index] == nil {
        return 0
    }
    for ; snap_id >= 0; snap_id-- {
        if v, ok := this.arr[index][snap_id]; ok {
            return v
        }
    }
    return 0
}

# 3
type SnapshotArray struct {
    id  int
    arr [][]Snap
}

type Snap struct {
    id    int
    value int
}

func Constructor(length int) SnapshotArray {
    nums := make([][]Snap, length)
    for i := 0; i < length; i++ {
        nums[i] = []Snap{{ // 填充0
            id:    0,
            value: 0,
        }}
    }
    return SnapshotArray{
        id:  0,
        arr: nums,
    }
}

func (this *SnapshotArray) Set(index int, val int) {
    n := len(this.arr[index])
    if this.arr[index][n-1].id == this.id {
        this.arr[index][n-1].value = val
        return
    }
    this.arr[index] = append(this.arr[index], Snap{
        id:    this.id,
        value: val,
    })
}

func (this *SnapshotArray) Snap() int {
    id := this.id
    this.id++
    return id
}

func (this *SnapshotArray) Get(index int, snap_id int) int {
    n := len(this.arr[index])
    arr := this.arr[index]
    left, right := 0, n-1
    for left < right {
        mid := left + (right-left)/2
        if snap_id <= arr[mid].id {
            right = mid
        } else {
            left = mid + 1
        }
    }
    if left == n || arr[left].id > snap_id {
        return arr[left-1].value
    }
    return arr[left].value
}

1155.掷骰子的N种方法(2)

• 题目

这里有d个一样的骰子，每个骰子上都有f个面，分别标号为1, 2, ..., f。
我们约定：掷骰子的得到总点数为各骰子面朝上的数字的总和。
如果需要掷出的总点数为target，请你计算出有多少种不同的组合情况（所有的组合情况总共有 f^d 种），
模10^9 + 7后返回。
示例 1：输入：d = 1, f = 6, target = 3 输出：1
示例 2：输入：d = 2, f = 6, target = 7 输出：6
示例 3：输入：d = 2, f = 5, target = 10 输出：1
示例 4：输入：d = 1, f = 2, target = 3 输出：0
示例 5：输入：d = 30, f = 30, target = 500 输出：222616187
提示：1 <= d, f <= 30
1 <= target <= 1000

• 解题思路

func numRollsToTarget(d int, f int, target int) int {
    dp := make([]int, target+1)
    dp[0] = 1
    for i := 0; i < d; i++ {
        next := make([]int, target+1)
        for j := 1; j <= f; j++ {
            for k := 0; k <= target-j; k++ {
                next[k+j] = (next[k+j] + dp[k]) % 1000000007
            }
        }
        dp = next
    }
    return dp[target]
}

# 2
func numRollsToTarget(d int, f int, target int) int {
    dp := make([][]int, d+1)
    for i := 0; i <= d; i++ {
        dp[i] = make([]int, target+1)
    }
    dp[0][0] = 1
    for i := 1; i <= d; i++ {
        for j := i; j <= target; j++ {
            for k := 1; k <= f; k++ {
                if j >= k {
                    dp[i][j] = (dp[i][j] + dp[i-1][j-k]) % 1000000007
                }
            }
        }
    }
    return dp[d][target]
}

1156.单字符重复子串的最大长度(1)

• 题目

如果字符串中的所有字符都相同，那么这个字符串是单字符重复的字符串。
给你一个字符串text，你只能交换其中两个字符一次或者什么都不做，然后得到一些单字符重复的子串。返回其中最长的子串的长度。
示例 1：输入：text = "ababa" 输出：3
示例 2：输入：text = "aaabaaa" 输出：6
示例 3：输入：text = "aaabbaaa" 输出：4
示例 4：输入：text = "aaaaa" 输出：5
示例 5：输入：text = "abcdef" 输出：1
提示：1 <= text.length <= 20000
text 仅由小写英文字母组成。

• 解题思路

func maxRepOpt1(text string) int {
    res := 0
    n := len(text)
    arr := [26]int{}
    for i := 0; i < n; i++ {
        v := int(text[i] - 'a')
        arr[v]++ // 统计每个字母出现的次数
    }
    for i := 0; i < n; {
        v := int(text[i] - 'a')
        countA := 0 // 统计相同的个数
        for i+countA < n && text[i] == text[i+countA] {
            countA++
        }
        j := i + countA + 1
        countB := 0 // 统计相隔1个不同字符往后连续的次数
        for j+countB < n && text[i] == text[j+countB] {
            countB++
        }
        // 2种情况
        // 1、a...axa...ay..a 可以拿1个来补齐:+1
        // 2、没有多余的补齐，可以拿第二段右侧最后一个点或者第一段左侧第一个点来补:+0
        total := min(countA+countB+1, arr[v]) // 取较少的
        res = max(res, total)                 // 更新结果
        i = i + countA                        // 窗口后移

    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

1161.最大层内元素和(2)

• 题目

给你一个二叉树的根节点root。设根节点位于二叉树的第 1 层，而根节点的子节点位于第 2 层，依此类推。
请你找出层内元素之和 最大 的那几层（可能只有一层）的层号，并返回其中最小 的那个。
示例 1：输入：root = [1,7,0,7,-8,null,null] 输出：2
解释：第 1 层各元素之和为 1，
第 2 层各元素之和为 7 + 0 = 7，
第 3 层各元素之和为 7 + -8 = -1，
所以我们返回第 2 层的层号，它的层内元素之和最大。
示例 2：输入：root = [989,null,10250,98693,-89388,null,null,null,-32127] 输出：2
提示：树中的节点数介于1和10^4之间
-10^5 <= node.val <= 10^5

• 解题思路

func maxLevelSum(root *TreeNode) int {
    res := 0
    maxValue := math.MinInt32
    if root == nil {
        return 0
    }
    queue := make([]*TreeNode, 0)
    queue = append(queue, root)
    level := 1
    for len(queue) > 0 {
        length := len(queue)
        sum := 0
        for i := 0; i < length; i++ {
            node := queue[i]
            sum = sum + node.Val
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        if sum > maxValue {
            maxValue = sum
            res = level
        }
        queue = queue[length:]
        level++
    }
    return res
}

# 2
var arr [][]int

func maxLevelSum(root *TreeNode) int {
    arr = make([][]int, 0)
    if root == nil {
        return 0
    }
    dfs(root, 0)
    res := 0
    maxValue := math.MinInt32
    for i := 0; i < len(arr); i++ {
        sum := 0
        for j := 0; j < len(arr[i]); j++ {
            sum = sum + arr[i][j]
        }
        if sum > maxValue {
            maxValue = sum
            res = i + 1
        }
    }
    return res
}

func dfs(root *TreeNode, level int) {
    if root == nil {
        return
    }
    if level == len(arr) {
        arr = append(arr, []int{})
    }
    arr[level] = append(arr[level], root.Val)
    dfs(root.Left, level+1)
    dfs(root.Right, level+1)
}

1162.地图分析(2)

• 题目

你现在手里有一份大小为 N x N 的 网格 grid，上面的每个 单元格 都用 0 和 1 标记好了。
其中 0 代表海洋，1 代表陆地，请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的。
我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：
(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。
如果网格上只有陆地或者海洋，请返回 -1。
示例 1：输入：[[1,0,1],[0,0,0],[1,0,1]] 输出：2
解释：海洋单元格 (1, 1) 和所有陆地单元格之间的距离都达到最大，最大距离为 2。
示例 2：输入：[[1,0,0],[0,0,0],[0,0,0]] 输出：4
解释：  海洋单元格 (2, 2) 和所有陆地单元格之间的距离都达到最大，最大距离为 4。
提示： 1 <= grid.length == grid[0].length <= 100
    grid[i][j] 不是 0 就是 1。

• 解题思路

var dx = []int{-1, 1, 0, 0}
var dy = []int{0, 0, -1, 1}

func maxDistance(grid [][]int) int {
    queue := make([][2]int, 0)
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[i]); j++ {
            if grid[i][j] == 1 {
                queue = append(queue, [2]int{i, j})
            }
        }
    }
    if len(queue) == 0 || len(queue) == len(grid)*len(grid[0]) {
        return -1
    }
    res := -1
    for len(queue) > 0 {
        res++
        length := len(queue)
        for i := 0; i < length; i++ {
            x1 := queue[i][0]
            y1 := queue[i][1]
            for i := 0; i < 4; i++ {
                x := x1 + dx[i]
                y := y1 + dy[i]
                if 0 <= x && x < len(grid) && 0 <= y && y < len(grid[0]) && grid[x][y] == 0 {
                    queue = append(queue, [2]int{x, y})
                    grid[x][y] = 2
                }
            }
        }
        queue = queue[length:]
    }
    return res
}

# 2
func maxDistance(grid [][]int) int {
    if len(grid) == 0 || len(grid[0]) == 0 {
        return -1
    }
    n := len(grid)
    m := len(grid[0])
    dp := make([][]int, n)
    for i := 0; i < n; i++ {
        dp[i] = make([]int, m)
    }
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            if grid[i][j] == 1 {
                dp[i][j] = 0
            } else {
                dp[i][j] = math.MaxInt32
            }
        }
    }
    // 从上往下
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            if grid[i][j] == 1 {
                continue
            }
            if i >= 1 {
                dp[i][j] = min(dp[i][j], dp[i-1][j]+1)
            }
            if j >= 1 {
                dp[i][j] = min(dp[i][j], dp[i][j-1]+1)
            }
        }
    }
    // 从下往上
    for i := n - 1; i >= 0; i-- {
        for j := m - 1; j >= 0; j-- {
            if grid[i][j] == 1 {
                continue
            }
            if i < n-1 {
                dp[i][j] = min(dp[i][j], dp[i+1][j]+1)
            }
            if j < m-1 {
                dp[i][j] = min(dp[i][j], dp[i][j+1]+1)
            }
        }
    }
    res := -1
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            if grid[i][j] == 1 {
                continue
            }
            res = max(res, dp[i][j])
        }
    }
    if res == math.MaxInt32 {
        return -1
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

1169.查询无效交易(2)

• 题目

如果出现下述两种情况，交易 可能无效：
交易金额超过 ¥1000
或者，它和另一个城市中同名的另一笔交易相隔不超过 60 分钟（包含 60 分钟整）
每个交易字符串transactions[i]由一些用逗号分隔的值组成，这些值分别表示交易的名称，时间（以分钟计），金额以及城市。
给你一份交易清单transactions，返回可能无效的交易列表。你可以按任何顺序返回答案。
示例 1：输入：transactions = ["alice,20,800,mtv","alice,50,100,beijing"]
输出：["alice,20,800,mtv","alice,50,100,beijing"]
解释：第一笔交易是无效的，因为第二笔交易和它间隔不超过 60 分钟、名称相同且发生在不同的城市。同样，第二笔交易也是无效的。
示例 2：输入：transactions = ["alice,20,800,mtv","alice,50,1200,mtv"] 输出：["alice,50,1200,mtv"]
示例 3：输入：transactions = ["alice,20,800,mtv","bob,50,1200,mtv"] 输出：["bob,50,1200,mtv"]
提示：transactions.length <= 1000
每笔交易transactions[i]按"{name},{time},{amount},{city}"的格式进行记录
每个交易名称{name}和城市{city}都由小写英文字母组成，长度在1到10之间
每个交易时间{time}由一些数字组成，表示一个0到1000之间的整数
每笔交易金额{amount}由一些数字组成，表示一个0 到2000之间的整数

• 解题思路

type Node struct {
    Name   string
    Time   int
    Amount int
    City   string
    Index  int
    Flag   bool
}

func invalidTransactions(transactions []string) []string {
    res := make([]string, 0)
    m := make(map[string][]Node)
    n := len(transactions)
    for i := 0; i < n; i++ {
        arr := strings.Split(transactions[i], ",")
        name, city := arr[0], arr[3]
        t, _ := strconv.Atoi(arr[1])
        amount, _ := strconv.Atoi(arr[2])
        m[name] = append(m[name], Node{Name: name, Time: t,
            Amount: amount, City: city, Index: i,
        })
    }
    for _, v := range m {
        sort.Slice(v, func(i, j int) bool {
            return v[i].Time < v[j].Time
        })
        for i := 0; i < len(v); i++ {
            if v[i].Amount > 1000 {
                v[i].Flag = true
            }
            for j := i + 1; j < len(v); j++ {
                if v[j].Time-v[i].Time <= 60 {
                    if v[i].City != v[j].City {
                        v[i].Flag = true
                        v[j].Flag = true
                    }
                } else {
                    break
                }
            }
        }
    }
    for _, v := range m {
        for i := 0; i < len(v); i++ {
            if v[i].Flag == true {
                res = append(res, transactions[v[i].Index])
            }
        }
    }
    return res
}

# 2
type Node struct {
    Name   string
    Time   int
    Amount int
    City   string
}

func invalidTransactions(transactions []string) []string {
    res := make([]string, 0)
    arr := make([]Node, 0)
    n := len(transactions)
    for i := 0; i < n; i++ {
        temp := strings.Split(transactions[i], ",")
        name, city := temp[0], temp[3]
        t, _ := strconv.Atoi(temp[1])
        amount, _ := strconv.Atoi(temp[2])
        arr = append(arr, Node{Name: name, Time: t, Amount: amount, City: city})
    }
    for i := 0; i < n; i++ {
        if arr[i].Amount > 1000 {
            res = append(res, transactions[i])
            continue
        }
        for j := 0; j < n; j++ {
            if i == j {
                continue
            }
            if arr[i].Name == arr[j].Name && arr[i].City != arr[j].City &&
                abs(arr[i].Time-arr[j].Time) <= 60 {
                res = append(res, transactions[i])
                break
            }
        }
    }
    return res
}

func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

1171.从链表中删去总和值为零的连续节点(4)

• 题目

给你一个链表的头节点head，请你编写代码，反复删去链表中由 总和值为 0 的连续节点组成的序列，
直到不存在这样的序列为止。
删除完毕后，请你返回最终结果链表的头节点。
你可以返回任何满足题目要求的答案。
（注意，下面示例中的所有序列，都是对ListNode对象序列化的表示。）
示例 1：输入：head = [1,2,-3,3,1] 输出：[3,1]
提示：答案 [1,2,1] 也是正确的。
示例 2：输入：head = [1,2,3,-3,4] 输出：[1,2,4]
示例 3：输入：head = [1,2,3,-3,-2] 输出：[1]
提示：给你的链表中可能有 1 到1000个节点。 
对于链表中的每个节点，节点的值：-1000 <= node.val <= 1000.

• 解题思路

func removeZeroSumSublists(head *ListNode) *ListNode {
    m := make(map[int]*ListNode)
    res := head
    sum := 0
    for cur := head; cur != nil; cur = cur.Next {
        sum = sum + cur.Val
        if sum == 0 { // 当前都为0
            res = cur.Next
            m = make(map[int]*ListNode)
            continue
        }
        if _, ok := m[sum]; ok == false {
            m[sum] = cur
            continue
        }
        // 出现重复
        first := m[sum]
        tempSum := sum
        for temp := first.Next; temp != cur; temp = temp.Next {
            tempSum = tempSum + temp.Val
            delete(m, tempSum)
        }
        first.Next = cur.Next
    }
    return res
}

# 2
func removeZeroSumSublists(head *ListNode) *ListNode {
    res := &ListNode{Next: head}
    for cur := res; cur != nil; {
        sum := 0
        for temp := cur.Next; temp != nil; temp = temp.Next {
            sum = sum + temp.Val
            if sum == 0 {
                cur.Next = temp.Next // 调整指针
            }
        }
        cur = cur.Next
    }
    return res.Next
}

# 3
func removeZeroSumSublists(head *ListNode) *ListNode {
    res := &ListNode{Next: head}
    m := make(map[int]*ListNode)
    sum := 0
    for cur := res; cur != nil; cur = cur.Next {
        sum = sum + cur.Val
        m[sum] = cur
    }
    sum = 0
    for cur := res; cur != nil; cur = cur.Next {
        sum = sum + cur.Val
        cur.Next = m[sum].Next
    }
    return res.Next
}

# 4
func removeZeroSumSublists(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    sum := 0
    for cur := head; cur != nil; cur = cur.Next {
        sum = sum + cur.Val
        if sum == 0 {
            return removeZeroSumSublists(cur.Next)
        }
    }
    head.Next = removeZeroSumSublists(head.Next)
    return head
}

1177.构建回文串检测(1)

• 题目

给你一个字符串s，请你对s的子串进行检测。
每次检测，待检子串都可以表示为queries[i] = [left, right, k]。
我们可以 重新排列 子串s[left], ..., s[right]，并从中选择 最多 k项替换成任何小写英文字母。
如果在上述检测过程中，子串可以变成回文形式的字符串，那么检测结果为true，否则结果为false。
返回答案数组answer[]，其中answer[i]是第i个待检子串queries[i]的检测结果。
注意：在替换时，子串中的每个字母都必须作为 独立的 项进行计数，
也就是说，如果s[left..right] = "aaa"且k = 2，我们只能替换其中的两个字母。
（另外，任何检测都不会修改原始字符串 s，可以认为每次检测都是独立的）
示例：输入：s = "abcda", queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]] 输出：[true,false,false,true,true]
解释：queries[0] : 子串 = "d"，回文。
queries[1] :子串 = "bc"，不是回文。
queries[2] :子串 = "abcd"，只替换 1 个字符是变不成回文串的。
queries[3] :子串 = "abcd"，可以变成回文的 "abba"。 也可以变成 "baab"，先重新排序变成 "bacd"，然后把 "cd" 替换为 "ab"。
queries[4] :子串 = "abcda"，可以变成回文的 "abcba"。
提示：1 <= s.length,queries.length<= 10^5
0 <= queries[i][0] <= queries[i][1] <s.length
0 <= queries[i][2] <= s.length
s 中只有小写英文字母

• 解题思路

func canMakePaliQueries(s string, queries [][]int) []bool {
    n := len(s)
    arr := make([]int, n+1)
    cur := 0
    for i := 0; i < n; i++ {
        value := int(s[i] - 'a')
        cur = cur ^ (1 << value)
        arr[i+1] = cur
    }
    res := make([]bool, len(queries))
    for i := 0; i < len(queries); i++ {
        a, b, c := queries[i][0], queries[i][1], queries[i][2]
        status := arr[b+1] ^ arr[a]
        if bits.OnesCount(uint(status)) <= 2*c+1 { // 奇数次字母的个数，重新排列后最多允许2*c+1个
            res[i] = true
        }
    }
    return res
}

1186.删除一次得到子数组最大和(2)

• 题目

给你一个整数数组，返回它的某个非空 子数组（连续元素）在执行一次可选的删除操作后，所能得到的最大元素总和。
换句话说，你可以从原数组中选出一个子数组，并可以决定要不要从中删除一个元素（只能删一次哦），
（删除后）子数组中至少应当有一个元素，然后该子数组（剩下）的元素总和是所有子数组之中最大的。
注意，删除一个元素后，子数组 不能为空。
请看示例：
示例 1：输入：arr = [1,-2,0,3] 输出：4
解释：我们可以选出 [1, -2, 0, 3]，然后删掉 -2，这样得到 [1, 0, 3]，和最大。
示例 2：输入：arr = [1,-2,-2,3] 输出：3
解释：我们直接选出 [3]，这就是最大和。
示例 3：输入：arr = [-1,-1,-1,-1] 输出：-1
解释：最后得到的子数组不能为空，所以我们不能选择 [-1] 并从中删去 -1 来得到 0。
     我们应该直接选择 [-1]，或者选择 [-1, -1] 再从中删去一个 -1。
提示：1 <= arr.length <= 10^5
-10^4 <= arr[i] <= 10^4

• 解题思路

func maximumSum(arr []int) int {
    n := len(arr)
    dp := make([][2]int, n)
    dp[0][0] = arr[0] // 不删
    dp[0][1] = 0      // 删除
    res := dp[0][0]   // 长度为1，不删除
    for i := 1; i < n; i++ {
        dp[i][0] = max(dp[i-1][0]+arr[i], arr[i])
        dp[i][1] = max(dp[i-1][1]+arr[i], dp[i-1][0])
        res = max(res, max(dp[i][0], dp[i][1]))
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

# 2
func maximumSum(arr []int) int {
    n := len(arr)
    a := arr[0] // 不删
    b := 0      // 删除
    res := a    // 长度为1，不删除
    for i := 1; i < n; i++ {
        a, b = max(a+arr[i], arr[i]), max(b+arr[i], a)
        res = max(res, max(a, b))
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

1190.反转每对括号间的子串(2)

• 题目

给出一个字符串s（仅含有小写英文字母和括号）。
请你按照从括号内到外的顺序，逐层反转每对匹配括号中的字符串，并返回最终的结果。
注意，您的结果中 不应 包含任何括号。
示例 1：输入：s = "(abcd)" 输出："dcba"
示例 2：输入：s = "(u(love)i)" 输出："iloveu"
示例 3：输入：s = "(ed(et(oc))el)" 输出："leetcode"
示例 4：输入：s = "a(bcdefghijkl(mno)p)q" 输出："apmnolkjihgfedcbq"
提示：0 <= s.length <= 2000
s 中只有小写英文字母和括号
我们确保所有括号都是成对出现的

• 解题思路

func reverseParentheses(s string) string {
    arr := []byte(s)
    stack := make([]int, 0)
    for i := 0; i < len(s); i++ {
        if s[i] == '(' {
            stack = append(stack, i)
        } else if s[i] == ')' {
            reverse(arr, stack[len(stack)-1], i)
            stack = stack[:len(stack)-1]
        }
    }
    s = string(arr)
    s = strings.ReplaceAll(s, "(", "")
    s = strings.ReplaceAll(s, ")", "")
    return s
}

func reverse(arr []byte, i, j int) {
    for i < j {
        arr[i], arr[j] = arr[j], arr[i]
        i++
        j--
    }
}

# 2
func reverseParentheses(s string) string {
    stack := make([]int, 0)
    m := make(map[int]int)
    for i := 0; i < len(s); i++ {
        if s[i] == '(' {
            stack = append(stack, i)
        } else if s[i] == ')' {
            last := stack[len(stack)-1]
            m[i] = last
            m[last] = i
            stack = stack[:len(stack)-1]
        }
    }
    dir := 1
    res := make([]byte, 0)
    for i := 0; i < len(s); i = i + dir {
        if s[i] == '(' || s[i] == ')' {
            i = m[i]   // 从反方向遍历
            dir = -dir // 变换方向，+1/-1
        } else {
            res = append(res, s[i])
        }
    }
    return string(res)
}

1191.K次串联后最大子数组之和(1)

• 题目

给你一个整数数组 arr 和一个整数 k。
首先，我们要对该数组进行修改，即把原数组 arr 重复 k 次。
    举个例子，如果 arr = [1, 2] 且 k = 3，那么修改后的数组就是 [1, 2, 1, 2, 1, 2]。
然后，请你返回修改后的数组中的最大的子数组之和。
注意，子数组长度可以是 0，在这种情况下它的总和也是 0。
由于 结果可能会很大，所以需要 模（mod） 10^9 + 7 后再返回。 
示例 1：输入：arr = [1,2], k = 3 输出：9
示例 2：输入：arr = [1,-2,1], k = 5 输出：2
示例 3：输入：arr = [-1,-2], k = 7 输出：0
提示：
    1 <= arr.length <= 10^5
    1 <= k <= 10^5
    -10^4 <= arr[i] <= 10^4

• 解题思路

func kConcatenationMaxSum(arr []int, k int) int {
    cur := 0
    sum := 0
    res := 0
    for i := 0; i < len(arr); i++ {
        sum = sum + arr[i]
        cur = max(cur+arr[i], arr[i])
        res = max(res, cur)
    }
    for i := 0; i < len(arr); i++ {
        cur = max(cur+arr[i], arr[i])
        res = max(res, cur)
    }
    if sum <= 0 {
        return res % 1000000007
    }
    return (res + (k-2)*sum) % 1000000007
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

1101-1200-Hard

1147.段式回文(2)

• 题目

段式回文 其实与 一般回文 类似，只不过是最小的单位是 一段字符而不是 单个字母。
举个例子，对于一般回文 "abcba" 是回文，而 "volvo" 不是，但如果我们把"volvo" 分为 "vo"、"l"、"vo" 三段，
则可以认为 “(vo)(l)(vo)” 是段式回文（分为 3 段）。
给你一个字符串text，在确保它满足段式回文的前提下，请你返回 段 的最大数量k。
如果段的最大数量为k，那么存在满足以下条件的a_1, a_2, ..., a_k：
每个a_i都是一个非空字符串；
将这些字符串首位相连的结果a_1 + a_2 + ... + a_k和原始字符串text相同；
对于所有1 <= i <= k，都有a_i = a_{k+1 - i}。
示例 1：输入：text = "ghiabcdefhelloadamhelloabcdefghi" 输出：7
解释：我们可以把字符串拆分成 "(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)"。
示例 2：输入：text = "merchant" 输出：1
解释：我们可以把字符串拆分成 "(merchant)"。
示例 3：输入：text = "antaprezatepzapreanta" 输出：11
解释：我们可以把字符串拆分成 "(a)(nt)(a)(pre)(za)(tpe)(za)(pre)(a)(nt)(a)"。
示例 4：输入：text = "aaa" 输出：3
解释：我们可以把字符串拆分成 "(a)(a)(a)"。
提示：text仅由小写英文字符组成。
1 <= text.length <= 1000

• 解题思路

func longestDecomposition(text string) int {
    n := len(text)
    if n <= 1 {
        return n
    }
    for i := 1; i <= n/2; i++ {
        if text[:i] == text[n-i:] {
            return 2 + longestDecomposition(text[i:n-i])
        }
    }
    return 1
}

# 2
func longestDecomposition(text string) int {
    n := len(text)
    if n <= 1 {
        return n
    }
    res := 0
    left, right := 0, n
    for left < right {
        for k := 1; ; k++ {
            if k > (right-left)/2 { // 长度超过剩下的1/2
                res++
                return res
            }
            if text[left:left+k] == text[right-k:right] {
                res = res + 2 // 可以切割，长度+2
                left = left + k
                right = right - k
                break
            }
        }
    }
    return res
}

1187.使数组严格递增

题目

给你两个整数数组arr1 和 arr2，返回使arr1严格递增所需要的最小「操作」数（可能为 0）。
每一步「操作」中，你可以分别从 arr1 和 arr2 中各选出一个索引，
分别为i 和j，0 <=i < arr1.length和0 <= j < arr2.length，然后进行赋值运算arr1[i] = arr2[j]。
如果无法让arr1严格递增，请返回-1。
示例 1：输入：arr1 = [1,5,3,6,7], arr2 = [1,3,2,4] 输出：1
解释：用 2 来替换 5，之后 arr1 = [1, 2, 3, 6, 7]。
示例 2：输入：arr1 = [1,5,3,6,7], arr2 = [4,3,1] 输出：2
解释：用 3 来替换 5，然后用 4 来替换 3，得到 arr1 = [1, 3, 4, 6, 7]。
示例3：输入：arr1 = [1,5,3,6,7], arr2 = [1,6,3,3] 输出：-1
解释：无法使 arr1 严格递增。
提示：1 <= arr1.length, arr2.length <= 2000
0 <= arr1[i], arr2[i] <= 10^9

解题思路

go