阿里笔试 20210308

第一题

nn 张卡片，每个卡片有一个正整数值，按从小到大排序，每个卡片值唯一。
从第一张卡片开始，要求数字连续，要求找到 第 k 个不存在的卡片
比如 124691 2 4 6 9
第一个不存在的卡片是 33
第二个是 55
第三个是 77
第四个是 88
第五个是 1010
第六个是 1111
……

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
}

第二题

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

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

LeetCode 879. 盈利计划

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

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

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

  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]
          }
      }
  }
  

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

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

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

0123010001000020000300004000050000 \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}

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

0123010001000020010300004000050000 \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}

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

0123010001000020011300004000150000 \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}

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

得到 1+1=21+1=2

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

笔试总结

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

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