美团后台笔试感受附编程题思路【已更新代码】

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

	return b
}

// 思路：
// 条件1：每次分配的时候试卷必须够
// 条件2：最后分配的时候，不能改到自己组的卷，也就是自己的卷必须已经被前面的组改过了
// 得出目标条件：
// 1. 将试卷数最多的组作为第一组，以满足条件1
// 2. 第一组的试卷总数必须少于等于其余所有组的试卷数总和，以满足条件2
func Paper() {
	var n int
	for {
		_, err := fmt.Scan(&n)
		if err == io.EOF {
			break
		} else {
			// 流式处理，O(1)的空间复杂度
			sum := 0 // 所有试卷的总和
			maxAmount := 0 // 试卷最多的组的试卷数
			temp := 0 // 临时变量，用于接收输入
			for i := 0; i < n; i++ {
				fmt.Scan(&temp)
				maxAmount = max(maxAmount, temp) // 记住试卷最多的组的试卷数
				sum += temp // 将所有试卷加起来，得到总试卷数
			}

			if maxAmount > sum-maxAmount {
				fmt.Println("No")
			} else {
				fmt.Println("Yes")
			}
		}
	}
} 

// 求序列的和的辅助函数
func sumSlice(s []int) int {
	sum := 0
	for i := 0; i < len(s); i++ {
		sum += s[i]
	}

	return sum
}

func ShiftWindow() {
	var n int
	for {
		_, err := fmt.Scan(&n)
		if err == io.EOF {
			break
		} else {
			seq := make([]int, n)
			for i := 0; i < n; i++ {
				fmt.Scan(&seq[i])
			}

			var k int
			fmt.Scan(&k)

			// 从长的序列开始找，一旦找到，就必定是最长的，后面不用继续找了
			found := false
			for windowSize := n; windowSize >= 1 && !found; windowSize-- {
				// 优化点：序列和不需要每次都计算，只需要第一次计算，
				// 后面的和，根据固定长度的滑动窗口原理，只需要减去第一项，
				// 并加上原序列的最后一项的下一项，就可以得到下一个序列的和。
				// 可以自行脑补滑动窗口:D
				// 如果我不优化这里，有的数据会跑出92%，优化完就可以100%了

				// 第一次，需要计算序列和
				ss := sumSlice(seq[0:windowSize])
				for i := 0; i <= n-windowSize; i++ {

					if i != 0 { // 不是第一次，就不需要从头加了，可以根据上一次的滑动窗口序列和计算出来
						ss -= seq[i-1]
						ss += seq[i+windowSize-1]
					}

					if ss%k == 0 { // 只要找到的可以马上停止了
						fmt.Println(windowSize)
						found = true
						break
					}
				}
			}

			if !found { // 没找到，打印个0吧
				fmt.Println(0)
			}
		}
	}
}