这周的双周竞赛算法考察得也不是那么强，其中最后一道数学题没有做出来，主要原因还是第三道题脑子短路了，一直 OOM，最后只剩下 5 分钟来思考第 4 题。而且一下子的思路就错了，导致最终悲剧。

Q1. 根据数字二进制下 1 的数目排序

这道题比较简单，主要还是需要将原来数组的值转换成 1 的个数，并且要注意 1 个数相同的情况下的处理：

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

type q1 struct {
    origin int
    count1 int
}

func sortByBits(arr []int) []int {
    var (
        i      int
        length = len(arr)
        newArr = make([]q1, length)
    )

    for i = 0; i < length; i++ {
        newArr[i] = q1{
            origin: arr[i],
            count1: count1(arr[i]),
        }
    }

    sort.Slice(newArr, func(i, j int) bool {
        if newArr[i].count1 == newArr[j].count1 {
            return newArr[i].origin < newArr[j].origin
        }
        return newArr[i].count1 < newArr[j].count1
    })

    for i = 0; i < length; i++ {
        arr[i] = newArr[i].origin
    }
    return arr
}
func count1(n int) (rst int) {
    for n != 0 {
        if n&1 != 0 {
            rst++
        }
        n >>= 1
    }
    return
}

Q2. 每隔 n 个顾客打折

这道题扎一看上去很复杂，但是，经过上次的经验之后我冷静了许多，描述越复杂，题目越简单，所以，直接写：

[[email protected]]# cat Q2.go
type Cashier struct {
    count         int
    discount      int
    discountCount int
    prices        map[int]int
}

func Constructor(n int, discount int, products []int, prices []int) Cashier {
    c := Cashier{
        count:         0,
        discount:      discount,
        discountCount: n,
        prices:        map[int]int{},
    }
    for i := 0; i < len(products); i++ {
        c.prices[products[i]] = prices[i]
    }
    return c
}

func (this *Cashier) GetBill(product []int, amount []int) (rtn float64) {
    this.count++
    total := 0
    for i := 0; i < len(product); i++ {
        total += this.prices[product[i]] * amount[i]
    }
    if this.count%this.discountCount == 0 {
        rtn = float64(total) * float64(100-this.discount) / 100
    } else {
        rtn = float64(total)
    }
    return
}

Q3. 包含所有三种字符的子字符串数目

这道题目我是用 DP 解答的，DP 有两条公式，分别代表的含义为：

DP1[n]：以字母 s[n] 开头的子串
DP2[n]：不包含字母 s[n] 的子串

那么推导公式为：

DP2[n] = DP1[n-1] + DP2[n-1]

这里 DP1[n] 怎么求是我这种解法的难点，假设 s[n:] 是包含 3 个字符的字符串，那么，以 s[n] 开头的子串有最多有几种可能性就取决于 s[n:n+x] 包含3个字符时，x 的最小值，我就在求这个 x 的时候载了，最后醒悟过来，可以每次遍历的时候直接记录。

这里之所以取决于 x 是因为假设这么一个字符串：abccccccc，主要包含前 3 个字符，后面能接几个字符就有几种可能：

abc
abcc
abccc
abcccc
abccccc
abcccccc
... ...

所以代码可以这么写：

[[email protected]]# cat Q3.go
func numberOfSubstrings(s string) int {
    var (
        i        int
        length   = len(s)
        dp1      = make([]int, length)
        dp2      = make([]int, length)
        charsIdx = []int{length, length, length}
    )
    charsIdx[s[length-1]-'a'] = length - 1
    charsIdx[s[length-2]-'a'] = length - 2

    for i = length - 3; i >= 0; i-- {
        charsIdx[s[i]-'a'] = i
        dp2[i] = dp1[i+1] + dp2[i+1]
        maxIdx := maxInt3(charsIdx[0], charsIdx[1], charsIdx[2])
        dp1[i] = length - maxIdx
    }

    return dp1[0] + dp2[0]
}

func maxInt3(a, b, c int) int {
    if a < b {
        a = b
    }
    if a < c {
        return c
    }
    return a
}

Q4. 有效的快递序列数目

这是一道纯数学题，我一开始就想错了，我往火车进出站的情况去考虑了，当然，最后5分钟就翻车了。这里我看了别人的解答，很简单，就是一个排列数，公式为：

f[n] = f[n-1] * n * (2*n-1)

所以代码就很简单了：

[[email protected]]# cat Q4.go
var MaxN = 1000000007

func countOrders(n int) int {
    var (
        i  int
        dp = make([]int, n+1)
    )
    dp[1] = 1
    for i = 2; i < n+1; i++ {
        //f(n) = f(n - 1) * n * (2n - 1).
        dp[i] = dp[i-1] * i * ((i << 1) - 1)
        if dp[i] > MaxN {
            dp[i] %= MaxN
        }
    }
    return dp[n]
}

update @ 2020-02-23 10:09

有时间自己来推导一下公式，既然是排列组合的题目，那么就考虑插入法来算，假设已经知道了 （n - 1）个快递的时候有 F(n-1) 种方式，那么选取其中任何一种，用于放置第 N 个快递的取件，那么就可能有 2(n-1) + 1 个位置可以放：

图 1：取件可能放置的位置

假设取件放在 Li 位置上，那么送件就存在 (2n-i) 种可能，这里送件不能在取件之前，所以，总共存在：

图 2：一种情况可能存在取件送件的可能性

归纳一下就是：n * (2 * n - 1)

所以总共就是 F(n） = F(n-1) * n * (2 * n - 1)