美团笔试 2023-03-25场

美团笔试 2023-03-25场

第1题

给定需要入栈的数组，但何时出栈未知，判断提供的出栈顺序是否合法。

LeetCode原题（946. Validate Stack Sequences），略过。

但是，为什么我甚至连数组都复用了还是卡了两个TLE？？？

代码（82% TLE）

package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	var stack = make([]int, 0)
	l := 0
	var m, out int
	var ins = []int{}
	for i := 0; i < n; i++ {
		fmt.Scan(&m)
		if len(ins) < m {
			ins = make([]int, m)
		}
		l = 0
		stack = stack[:0]
		for j := 0; j < m; j++ {
			fmt.Scan(&ins[j])
		}
		k := 0
		for j := 0; j < m; j++ {
			fmt.Scan(&out)
			for k < m && (l == 0 || stack[l-1] != out) {
				stack = append(stack, ins[k])
				l++
				k++
			}
			if l > 0 && stack[l-1] == out {
				stack = stack[:l-1]
				l--
			}
		}
		if l > 0 {
			fmt.Println("No")
		} else {
			fmt.Println("Yes")
		}
	}
}

第2题

选糖果，但是有限制，拿了当前糖果i，那么i+1，i+2，i-1，i-2都不能拿了。求最多能拿多少钱的糖？

LeetCode原题的变种（213. House Robber II），直接给出递推方程和边界条件，代码就不给了：

\[\begin{aligned} dp[i][0] &= \max(dp[i-1][0], dp[i-1][1]) \\ dp[i][1] &= dp[i-2][0] + w_i \end{aligned}\]

边界条件：

\[\begin{aligned} dp[0][0] &= 0 \\ dp[0][1] &= w_0 \\ dp[1][0] &= w_0 \\ dp[1][1] &= w_1 \\ \end{aligned}\]

代码（AC）

package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)

	dp := make([][2]int, n)

	var w int
	for i := 0; i < n; i++ {
		fmt.Scan(&w)
		if i == 0 {
			dp[i][0] = 0
			dp[i][1] = w
			continue
		}
		dp[i][0] = max(dp[i-1][0], dp[i-1][1])
		if i >= 2 {
			dp[i][1] = dp[i-2][0] + w
		} else {
			dp[i][1] = w
		}
	}

	fmt.Println(max(dp[n-1][0], dp[n-1][1]))
}

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

第3题

给定不同重量的巧克力，多次查询，设定拿的重量上限时能拿多少块？

思路

• 巧克力重量排序，然后使用前缀和prefix：

    {1,2,2,5,4} 	# 巧克力重量，排序后{1,2,2,4,5}
  {0,1,3,5,9,14}	# 前缀和，统计拿k（下标）块时最小重量
  

• 二分查找：

  1. 如果当前下标i对应的正好是该查询的重量上限w，那么直接返回下标i（prefix[i] == w）
  2. 否则，当前下标对应的重量是超出查询的重量的，那么返回i-1（prefix[i] > w）

卡了一下，甚至想用贪心和堆去解，发现不用，我是傻逼。

代码（AC）

package main

import (
	"fmt"
	"sort"
)

func main() {
	var n, m int
	fmt.Scan(&n, &m)
	as := make([]float64, n+1)

	var a float64
	for i := 0; i < n; i++ {
		fmt.Scan(&a)
		as[i+1] = as[i] + a*a
	}

	var q float64
	for i := 0; i < m; i++ {
		fmt.Scan(&q)
		idx := sort.SearchFloat64s(as, q)
		if i != 0 {
			fmt.Print(" ")
		}
		if idx <= n && as[idx] == q {
			fmt.Printf("%d", idx)
		} else {
			fmt.Printf("%d", idx-1)
		}
	}
	fmt.Println()
}

第4题

给一个字符串形如：aaa=bbb;ccc=ddd;eee=/f/f/f;，每个元素<key>=<value>;，解析这些元素。给出key的值，在字符串中查找对应的value，没有则返回EMPTY。

美团这难度错位给我整不会，直接调函数分割就完事了。

代码（AC）

package main

import (
	"fmt"
	"strings"
)

func main() {
	var str string
	fmt.Scan(&str)
	strs := strings.Split(str, ";")
	n := len(strs)
	if strs[n-1] == "" {
		strs = strs[:n-1]
		n--
	}
	m := map[string]string{}
	for _, s := range strs {
		tmp := strings.IndexByte(s, '=')
		m[s[:tmp]] = s[tmp+1:]
	}

	var q int
	fmt.Scan(&q)
	var s string
	for i := 0; i < q; i++ {
		fmt.Scan(&s)
		if ans, ok := m[s]; ok {
			fmt.Println(ans)
		} else {
			fmt.Println("EMPTY")
		}
	}
}

第5题

小美吃糖，但是不能连续两天吃，但是的但是，小美意志不坚定，有k次机会不遵循规则，求最多能拿多少价值的糖果。

糖果题，稍稍有点小难度，但是由于第2题的铺垫难度直线下降。

基本思想还是DP，但是是三维：

1. 一维为遍历到了第i个糖果，一维为当前剩下k个机会反悔，一维为取或者不取两个状态state，状态方程：

   \[\begin{aligned} dp[i][k][0] &= max(dp[i-1][k][0],dp[i-1][k][1]) \\ dp[i][k][1] &= max(dp[i-1][k][0],dp[i-1][k+1][1])+w_i \end{aligned}\]

2. 化简掉一维i：

   \[\begin{aligned} dp[k][0] &= max(dp[k][0],dp[k][1]) \\ dp[k][1] &= max(dp[k][0],dp[k+1][1])+w_i \end{aligned}\]

   注意！同时更新dp[k][0]和dp[k][1]，不然数据会污染。

3. 其实state这一维也可以优化掉，但是不易于理解（懒）。

代码

package main

import "fmt"

func main() {
	var n, k int
	fmt.Scan(&n, &k)
	dp := make([][2]int, k+1)

	var w int
	fmt.Scan(&w)
	dp[k][0] = 0
	dp[k][1] = w
	for i := 1; i < n; i++ {
		fmt.Scan(&w)
		for j := 0; j < k; j++ {
			dp[j][0], dp[j][1] = max(dp[j][0], dp[j][1]), max(dp[j][0], dp[j+1][1])+w
		}
		dp[k][0], dp[k][1] = max(dp[k][0], dp[k][1]), dp[k][0]+w
	}

	ans := 0
	for i := 0; i <= k; i++ {
		ans = max(ans, max(dp[i][0], dp[i][1]))
	}

	fmt.Println(ans)
}

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