type
status
date
slug
summary
tags
category
icon
password
Last edited time
Apr 28, 2024 09:45 AM
快手游戏春招笔试题-开发B卷题解
📝 主旨内容
走方格(线性DP)
给定一个包含一个整数的M*N的矩阵，请找出一条从左上角到右下角的路径，使得路径上的数字总和最大，每次只能向下或者向右移动一步，初始位置在grid[0][0]
例如如下的矩阵
1 | 2 | 3 |
4 | 5 | 6 |
7 | 8 | 9 |
最大路径为：1+4+7+8+9=29
补充：
1≤M,N≤200
-1000≤grid[i][j]≤1000
示例：
输入：
[-143,145,423,-618,476,-869,573,850,629], 3, 3
输出:
1957
输入：
[-421,-445,-698,517,-347,-171,-254,825,921], 3, 3
输出:
1588
简单DP，需要注意方格内含有负数，初始化需要赋最小值上去，否则可能会从边缘开始走
帕鲁的最大效率(01背包)
小快的庄园有m个单位的容量，小快现在有n只帕鲁，第i只帕鲁需要v[i]单位的生存空间，第i只帕鲁的生产效率是e[i]，小快庄园的最大生产效率是多少？
示例：
输入：
15, 5, [4,5,6,7,8], [5,6,7,8,9]
输出：
18
输入：
150, 10, [10,20,30,40,50,60,70,80,90,100], [20,30,40,50,60,70,80,90,100,110]
输出：
200
01背包裸题，把生存空间看成物品的体积，生产效率看成是物品的价值即可
滑动窗口的最大值(滑动窗口)
给定一个长度为n的整数数组，大小为k的滑动窗口从数组的最左侧移动到数组的最右侧，滑动窗口每次只向右移动一位。请使列1用一次数组遍历，输出每个滑动窗口中的最大值。
输入描述
第一行，正整数n和正整数k，k<=n
第二行，n个整数
输出描述
每个滑动窗口的最大值依次输出，空格分隔。
示例
输入
输出
滑动窗口裸题，单调队列解决，使得队列内是单调递减的，每次入队先看队尾是否符合递减的条件否则出队，其次再检测队头是否需要出队，每次滑动过后队头就是答案(弹队头没什么好解释的，弹队尾使得队列内单调递减，一个很简单的解释是，只要是当前较大的元素入队了，之前进来的比我小的元素是永无出头之日，而且寿命也更短，所以说每次确保当然入队的是最小值即可)
🤗 总结归纳
总的来说还是比较简单的，几乎都是裸题，也需要有其他题目的原因，还是说游戏开发的问题
📎 参考文章
- 作者:ziuch
- 链接:https://ziuch.com/article/Kuaishou-Game-Spring-Recruitment-Test
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。