0. 概述

相对来说，本周的题目还是偏简单的，但是，第 4 题由于本人的悟性不高，所以没有 get 到它的点最终也是没有做出来，也是有点遗憾。

图 1：Leetcode 第 22 场周赛排名

Q1：两个数组间的距离值

这道题还是一个简单的上手题啦，所以，直接按照题目意思来就好了：

[[email protected]]# cat Q1.go
func findTheDistanceValue(arr1 []int, arr2 []int, d int) int {
    var (
        i, j, rst int
        length1 = len(arr1)
        length2 = len(arr2)
    )

    for i = 0;i < length1; i++ {
        fail := true
        for j = 0;j < length2; j++ {
            if abs(arr1[i] - arr2[j]) <= d {
                fail = false
            }
        }
        if fail {
            rst ++
        }
    }

    return rst
}

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

Q2：安排电影院座位

这道题乍看之下有点难度，所以我先跳过了，后面回来认真看一下，其实也不是很难（有些小技巧），因为题目的 N 规模很大，所以肯定不能直接按照题目意思写的，所以出路还是反向来。

这里我分析了一下，其实每排座位就只有 4 种座位情况：

于是我就先贪心一把，假设所有的都是第 3 种情况，如果遇到一些座位被人占了，那么就减掉一个就好了。当然，可能出现一种特殊的情况就是怎么确定情况 2，我维护了一个数组用来监视这种情况：

[[email protected]]# cat Q2.go
import (
    "fmt"
    "sort"
)

func maxNumberOfFamilies(n int, reservedSeats [][]int) int {
    var (
        i int
        reMap = map[int]bool{}
        sliceMap = map[int]bool{}
        reSlice = []int{}
        length = len(reservedSeats)
        rst = 2 * n
    )

    for i = 0;i < length; i++ {
        if  reservedSeats[i][1] == 1 ||  reservedSeats[i][1] == 10 {
            continue
        }
        var seat = 0
        if reservedSeats[i][1] > 3 && reservedSeats[i][1]  < 8{
seat = 1
        } else if reservedSeats[i][1] > 7 {
            seat = 2
        }
        if _, exists := sliceMap[3 * reservedSeats[i][0]  + seat]; !exists{
            reSlice = append(reSlice, 3 * reservedSeats[i][0] + seat)
            sliceMap[3 * reservedSeats[i][0]  + seat] = true
        }
        switch reservedSeats[i][1] {
        case 2:
            fallthrough
        case 3:
            fallthrough
        case 4:
            fallthrough
        case 5:
            if _, exist := reMap[reservedSeats[i][0]*2]; !exist{
                reMap[reservedSeats[i][0]*2] = true
                rst -=1
            }
        case 6:
            fallthrough
        case 7:
            fallthrough
        case 8:
            fallthrough
        case 9:
            if _, exists := reMap[reservedSeats[i][0]*2+1] ; !exists{
                reMap[reservedSeats[i][0]*2+1] = true
                rst -=1
            }
        }
    }
    sort.Ints(reSlice)
    length = len(reSlice)
    fmt.Println(reSlice)
    for i = 0;i < length; i++ {
        if reSlice[i] % 3 == 0 {
            // first
            if i + 1 < length {
                if reSlice[i+1] == reSlice[i]+2{
                    rst += 1
                }
            }
        }
    }
    return rst
}

Q3：将整数按权重排序

这道题很简单，唯一我觉得的难点就是对于 1000 个数，怎么在排序的时候尽可能减少计算，所以我预先打好了一个表。。。

[[email protected]]# cat Q3.go
var weightMap = map[int]int{
    217 : 27 ,
    418 : 41 ,
    530 : 124 ,
    952 : 37 ,
    351 : 82 ,
    ... ...
}
func getKth(lo int, hi int, k int) int {
    var (
        i int
        length = hi-lo+1
        ary = make([]int, length)
    )
    for i = 0;i < length; i++ {
        ary[i] = lo+i
    }
    sort.Slice(ary, func(i, j int) bool {
        if weightMap[ary[i]] == weightMap[ary[j]] {
            return ary[i] < ary[j]
        }
        return weightMap[ary[i]] < weightMap[ary[j]]
    })

    return ary[k-1]
}

Q4：3n 块披萨

这道题懂的人很简单，不懂的人会很仆街，我就是那个不懂的人。我在比赛的时候用的是贪心，每次都是找相邻 3 个数中，中间数在这三个数中占权重最大的那个数，然后这个方法并不能取得最优值，只能在一些情况下取得次优值。

然后看别人的解释，发现这道题的核心就是：只要不是相邻的数，就有方法可以同时取到他们，因为相邻的肯定是取不到了，所以这样子问题就简单了，从数组中找出 K 个不相邻的数，求他们的最大值，这里我用了 DP：

[[email protected]]# cat Q4.go
func maxSizeSlices(slices []int) int {
    return max(
        maxSizeSlices2(slices[:len(slices)-1]),
        maxSizeSlices2(slices[1:]),
    )
}

func maxSizeSlices2(slices []int) int {
    var (
        i, j,currMax, prevMax int
        length                = len(slices)
        dp                    = make([][]int, len(slices) / 3 +1)
    )
    for i = 0;i < len(dp); i++ {
        dp[i] = make([]int, length)
    }
    for i = 0;i < length; i++ {
        dp[0][i] = slices[i]
        if dp[0][i] > currMax {
            currMax = dp[0][i]
        }
    }
    for i = 1; i < len(dp); i++ {
        prevMax = 0
        for j = 0; j < length; j++ {
            if j >= 2 {
                prevMax = max(dp[i-1][j-2], prevMax)
            }
            dp[i][j] = slices[j] + prevMax
            if dp[i][j] > currMax {
                currMax = dp[i][j]
            }
        }
    }

    return currMax
}

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