这周周赛题目难度整体上一般，但是，第 4 题因为对于这种博弈的题目思绪不清，所以就是不会做，当然，最后的名词也不会很好啦。

图 1：Leetcode 周赛 183 排名

Q1：非递增顺序的最小子序列

作为上手题目，这道题目还是比较简单的，很明显，其实就是找最大的几个数，他们的和可以超过其他数的和（其实就是总和减去最大几个数的和）即可：

[[email protected]]# cat Q1.go
import "sort"

func minSubsequence(nums []int) []int {
    var (
        i, sum, tmp int
        tmpSlice []int
        length = len(nums)
    )
    sort.Slice(nums, func(i, j int) bool {
        return nums[i] > nums[j]
    })
    for i = 0;i < length; i++ {
        sum += nums[i]
    }
    for i = 0;i < length; i++ {
        tmp += nums[i]
        tmpSlice = append(tmpSlice, nums[i])
        if tmp > sum-tmp {
            return tmpSlice
        }
    }
    return tmpSlice
}

Q2：将二进制表示减到 1 的步骤数

这到题目看上去也是很简单，但是，我还是被拌了一下，其实就是最后一位是 “1” 时，其实需要 2 步才能清掉，其他情况（0 以及包含进位之后是 2 都只需要一步即可），所以代码为：

[[email protected]]# cat Q2.go
func numSteps(s string) int {
    var (
        val    uint8
        i, rst int
        over   bool
        length = len(s)
    )

    for i = length - 1; i > 0; i-- {
        rst++
        val = s[i]
        if over {
            val += uint8(1)
        }
        switch val {
        case '0':
            fallthrough
        case '2':
            continue
        case '1':
            over = true
            rst++
        }
    }

    if over {
        rst++
    }

    return rst
}

Q3：最长快乐字符串

这道题目的核心在于怎么分配不同的字符，这里我想的策略是：

这里我每次选择之后都重新对字符数量做了一个排序：

[[email protected]]# cat Q3.go
import "sort"

type obj struct {
    char uint8
    num  int
}

func longestDiverseString(a int, b int, c int) (rst string) {
    var (
        objs          = []obj{
            obj{char: 'a', num: a},
            obj{char: 'b', num: b},
            obj{char: 'c', num: c},
        }
        rstBytes = []uint8{}
    )
    sort.Slice(objs, func(i, j int) bool {
        return objs[i].num > objs[j].num
    })

    for true {
        if len(rstBytes) == 0 {
            switch objs[0].num {
            case 1:
                objs[0].num -= 1
                rstBytes = append(rstBytes, objs[0].char)
            default:
                objs[0].num -= 2
                rstBytes = append(rstBytes, objs[0].char)
                rstBytes = append(rstBytes, objs[0].char)
            }
        } else {
            if objs[0].char == rstBytes[len(rstBytes)-1] {
                if objs[0].num - objs[1].num >= 0 {
                    switch objs[1].num {
                    case 0:
                        return string(rstBytes)
                    case 1:
                        fallthrough
                    default:
                        objs[1].num -= 1
                        rstBytes = append(rstBytes, objs[1].char)
                    }
                } else {
                    switch objs[1].num {
                    case 0:
                        return string(rstBytes)
                    case 1:
                        objs[1].num -= 1
                        rstBytes = append(rstBytes, objs[1].char)
                    default:
                        objs[1].num -= 2
                        rstBytes = append(rstBytes, objs[1].char)
                        rstBytes = append(rstBytes, objs[1].char)
                    }
                }
            } else {
                switch objs[0].num {
                case 0:
                    return string(rstBytes)
                case 1:
                    objs[0].num -= 1
                    rstBytes = append(rstBytes, objs[0].char)
                default:
                    objs[0].num -= 2
                    rstBytes = append(rstBytes, objs[0].char)
                    rstBytes = append(rstBytes, objs[0].char)
                }
            }
        }
        sort.Slice(objs, func(i, j int) bool {
            return objs[i].num > objs[j].num
        })
    }
    return string(rstBytes)
}

Q4：石子游戏 III

这道题我尝试了一下递归的解法，但是因为在我的思路里面总是考虑之 Alice 和 Bob 的身份转换，所以最终代码总是写不对。看了一下别人的思路，别人不关注具体的第 i 堆是被谁取走的，而是关注，当用户从第 i 堆开始取时，他可以得到的最大值是多少。

这样思路就比较明确了，可以用 dp 进行，假设玩家在第 i 位做选择，那么他可以选择：

这里取走 x 堆存在这么一个关系：dp[i] + dp[i+x] = sum[i:n]，也就是说，如果你选择了 i +x，那么另外一个玩家必定是总和减去 dp[i+x] 的数值。

因为 0 的位置是 Alice 先选，所以，Alice 是否取胜就看 dp[0] 是否和总和 Sum 之间的关系：

[[email protected]]# cat Q4.go
import "math"

func stoneGameIII(stoneValue []int) string {
    var (
        i, j, sum int
        length    = len(stoneValue)
        // dp[i]：玩家从第 i 位开始取时可能取到的最大值
        dp = make([]int, length+1)
    )
    dp[length] = 0
    for i = length - 1; i >= 0; i-- {
        dp[i] = math.MinInt32
        sum += stoneValue[i]
        for j = i; j < i+3 && j < length; j++ {
            dp[i] = max(dp[i], sum-dp[j+1])
        }
    }

    if dp[0] > sum-dp[0] {
        return "Alice"
    } else if dp[0]*2 == sum {
        return "Tie"
    } else {
        return "Bob"
    }
}

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