阿里笔试 20210308

第一题

$n$ 张卡片，每个卡片有一个正整数值，按从小到大排序，每个卡片值唯一。
从第一张卡片开始，要求数字连续，要求找到第 k 个不存在的卡片
比如 $1 2 4 6 9$
第一个不存在的卡片是 $3$
第二个是 $5$
第三个是 $7$
第四个是 $8$
第五个是 $10$
第六个是 $11$
……

LeetCode 1539.第 k 个缺失的正整数

和上面的题目类似，不过笔试里要求是从第一个数开始不连续，而 LeetCode 是从 1 开始（区别在于代码里num := 1和num := arr[0] + 1）

大概思路就是从前往后枚举数字，判断它在不在序列中即可，如果枚举的数已经大于所有数字的时候，直接计算出结果（如果继续枚举会超时）
（理论上来说，如果用一个变量缓存上一次判断的数组位置，可能比二分查找更快）

func findKthPositive(arr []int, k int) int {
    n := len(arr)

    count := 0
    num := 1 // arr[0] + 1
    for count < k {
        if num <= arr[n-1] {
            idx := sort.SearchInts(arr, num)
            if idx < n && arr[idx] == num {
                num++
                continue
            }
            count++
            num++
        } else {
            num += k - count
            count = k
            break
        }
    }

	return num - 1
}

第二题

第二题是 $m$ 个任务， $n$ 个工人，要求达到 $p$ 收益
每个任务需要消耗 $c[i]$ 个工人，获取 $v[i]$ 的收益

求所有满足条件的方案数（模 $1e9+7$ ）

LeetCode 879. 盈利计划

这道题本身不难，起码总体思路是有的，但是时间问题，没写出来（甚至暴力骗分都没骗到）

首先，从题目看，又是工人（花费）又是收益（价值），标准的背包问题。不过它要求的是方案数，虽然不是常见的背包，但是大思路不变。

第一步，找出来转移的变量
- $i$ : 当前的任务
- $j$ : 已使用的工人数
- $k$ : 已获得的收益
第二步，确定转移方程
按照背包的思路，有 $dp[i][j][k] = \sum{ dp[i-1][j-cnt][k-val] }$
其中 $cnt$ 表示当前方案需要的人数， $val$ 表示当前方案的收益

第三步，写出循环

for i := 0; i<m; i++ {
    cnt := count[i]
    val := val[i]
    for j:=0; j<n; j++ {
        for k:=0; k<p; k++ {
            dp[i][j][k] += dp[i-1][j-cnt][k-val]
        }
    }
}

这部分给出了大致的思路，这一步相对来说比较好思考，但是显然直接这么写不行，因为边界完全没考虑。
我们需要一个简单的例子，来做一个模拟

设定如下得情况：
最多有 $5$ , 最少要求获取 $3$ 的利润
任务 1: 需要 2 个人，收益 2
任务 2: 需要 2 个人，收益 3

首先，建立一个 $(5+1) \times (3+1)$ 的二维数组，每一个任务的 DP 结果
起初，没有任何任务，应该只有“消耗 $0$ 个人、收益为 $0$ 的 $dp[0][0] = 1$ ”

$\begin{matrix} & \bm{0} & \bm{1} & \bm{2} & \bm{3} \\ \bm{0} & 1 & 0 & 0 & 0 \\ \bm{1} & 0 & 0 & 0 & 0 \\ \bm{2} & 0 & 0 & 0 & 0 \\ \bm{3} & 0 & 0 & 0 & 0 \\ \bm{4} & 0 & 0 & 0 & 0 \\ \bm{5} & 0 & 0 & 0 & 0 \\ \end{matrix}$

然后开始处理第一个任务，可以通过消耗 $2$ 个人获得 $2$ 个收益，也即 $dp[i][j] = dp[i-2][j-2]$
整个范围里，只有 $dp[0][0]$ 使得 $dp[2][2] = 1$

$\begin{matrix} & \bm{0} & \bm{1} & \bm{2} & \bm{3} \\ \bm{0} & 1 & 0 & 0 & 0 \\ \bm{1} & 0 & 0 & 0 & 0 \\ \bm{2} & 0 & 0 & 1 & 0 \\ \bm{3} & 0 & 0 & 0 & 0 \\ \bm{4} & 0 & 0 & 0 & 0 \\ \bm{5} & 0 & 0 & 0 & 0 \\ \end{matrix}$

对于第二个任务，可以通过消耗 $2$ 个人，获得 $3$ 个收益，也即 $dp[i][j] = dp[i-2][j-3]$
有 $dp[2][3] = dp[0][0] = 1$ 和 $dp[4][5] = dp[2][2] = 1$
但是这里有一个需要注意的问题是，实际收益可能超过 $p$ （也即上面的第二种情况），应该将其统计到 $dp[i][p]$ 中（ $dp[4][3]$ ）

$\begin{matrix} & \bm{0} & \bm{1} & \bm{2} & \bm{3} \\ \bm{0} & 1 & 0 & 0 & 0 \\ \bm{1} & 0 & 0 & 0 & 0 \\ \bm{2} & 0 & 0 & 1 & 1 \\ \bm{3} & 0 & 0 & 0 & 0 \\ \bm{4} & 0 & 0 & 0 & 1 \\ \bm{5} & 0 & 0 & 0 & 0 \\ \end{matrix}$

最后，我们需要的是，所有少于人数 $n$ ，并且达到收益 $p$ 的方案数目，所有大于等于 $p$ 的都被归于 $p$ 中，因此我们只需要遍历所有的人数即可

得到 $1+1=2$

这道题中，需要考虑的点，就在于上面提到的收益溢出的处理。在遍历 $k$ 时，可以遍历 $[val, p+val]$ ，因为所有大于 $p$ 的都被归为 $p$ ，所以当前任务最大能达到的就是 $p+val$ 。
在写入时，取 $min(k, p)$ 即可

for k := p + val; k >= val; k-- {
    kk := min(p, k)
    dp[j][kk] = (dp[j][kk] + dp[j-cnt][k-val]) % mod
}

const mod = 1e9 + 7

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

func profitableSchemes(n int, minProfit int, group []int, profit []int) int {
    m := len(group)
    p := minProfit

	// dp[i][j][k]
	// TODO: i 可以省略

	// 前 i 个任务，在使用 j 个人，收益为 k 的 方案数
	// 溢出的部分设定为 n 和 p
	dp := make([][]int, n+1)
    for j:=0; j<=n; j++ {
		dp[j] = make([]int, p+1)
	}

	// 第 i 个任务的状态，应该完全来自于任务 i-1
	// 如果选了当前任务，则 ↓
	// dp[i][j][k] = sum{ dp[i-1][j-cnt][k-val] }
    dp[0][0] = 1
	for i := 0; i < m; i++ {
		cnt := group[i]
		val := min(profit[i], p)
		for j := n; j >= cnt; j-- {
			for k := p + val; k >= val; k-- {
                kk := min(p, k)
				dp[j][kk] = (dp[j][kk] + dp[j-cnt][k-val]) % mod
			}
		}

        // for j:=0; j<=n; j++ {
		//     fmt.Println(dp[j])
        // }
        // fmt.Println()
	}

	res := 0
	for j := 0; j <= n; j++ {
		res += dp[j][p] % mod
	}
	return res % mod
}

笔试总结

严格来说题目不算难，但是第二题细节需要逻辑清晰才行。而实际笔试中，第二题基本上只有半个小时多一点的时间，读题、数据输入、简单验证思路，大概就需要十分钟。最后反而想去用暴力骗分反而耽误了不少时间。如果把当时的时间用在手推一下样例的话，应该有概率做出来的。

这波输在心态上，如果是线下做题，可能就慢慢推了，老想着骗分反而亏了