【腾讯面试题】熊出没
苦逼的码农
共 3633字,需浏览 8分钟
· 2021-07-04
牛牛码特
13:14
85%
微信(116)
相亲相爱一家熊🐻
我发现一个山洞,里面有好多苹果🍎,看起来很好吃的样子~
不过我们只能从洞口和洞尾拿苹果,我们来比比看谁拿的苹果重量最大吧~
好啊好啊
那我们赶快去山洞吧!
深度优先递归法
func CanFistBearWin(nums []int) bool {
return picker(0, len(nums)-1, nums) >= 0
}
// i, j 表示当前子问题中,山洞左右从哪里开始
func picker(i, j int, nums []int) int {
if i == j {
return nums[i]
}
head := nums[i] - picker(i+1, j, nums)
end := nums[j] - picker(i, j-1, nums)
return max(head, end)
}
记忆化递归法
可以看到,图上是有重复子问题的,那我们完全可以将子问题的解答记录下来。等到后面再遇到的时候,直接返回结果,而不用再递归下去,这样就可以节约大量时间了。
动态规划法
0号位置对应的dp[0][0]就是其苹果的重量,我们从1号位置开始,对每个位置往前递推:
func CanFistBearWin(nums []int) bool {
// 提前计算数组长度,避免反复消耗
length := len(nums)
dp := make([][]int, length)
// 子数组初始化
for i := 0; i < length; i++ {
dp[i] = make([]int, length)
// 左右在一个点的情况,取了这个苹果即可
dp[i][i] = nums[i]
}
// j表示山洞右侧位置
for j := 1; j < length; j++ {
// i表示山洞左侧位置
for i := j-1; i >= 0; i-- {
head := nums[i] - dp[i+1][j]
end := nums[j] - dp[i][j-1]
dp[i][j] = max(head, end)
}
}
return dp[0][length-1] >= 0
}
果不其然,成功拿到了苹果,熊熊开心地跳起了舞
评论
热搜第一,腾讯又一游戏停运了!
腾讯又有一款游戏要停运了。最近,腾讯游戏宣布:由于游戏的代理协议即将到期,《食物语》将于2024年6月18日11:00停止在中国大陆地区的运营。并且这次的停运话题一度冲上热搜榜第一位,引发网友热议。据了解,《食物语》是一款中华美食拟人的国风女性向RPG养成手游,于2019年9月份公开测试,运营至今已
逆锋起笔
0
【送书福利】《Java面试八股文:高频面试题与求职攻略一本通》
先来唠唠最近粉丝面试回来跟我聊天,基本上都提到一个点,在面试过程中八股文占比很高(八股文70%、项目20%、10%算法)除了一些搞算法突出的厂除外。其实现在很多厂八股都是逐渐深入的方式来问,所以大家在学习的过程中,针对一些重点的内容,最好深入去学习,不然还是比较难应对这种追问式的问题。最近刚好从一位
Java后端技术
0
是谁还在坚持用 QQ?腾讯回应:好冷漠...
转自:电脑报近日,“仍有5亿人坚持用QQ”的话题登上微博热搜,引发网友热议。根据腾讯财报,截至2023年第三季度,QQ智能终端月活跃用户数为5.58亿,仅占微信四成。但换个角度看,作为一款25岁的元老级社交应用,QQ破5亿的月活仍然是很多社交App羡慕的存在,超过了微博和知乎总和。只是在用户增量上,
dotNET全栈开发
10
腾讯开始收费,这软件的良心操作彻底没了
腾讯作为互联网巨头,也曾出品过不少良心软件,比如QQ影音就因安装包小、CPU占用少、界面简洁无广告无插件等备受用户喜爱。但因为没有合适的赚钱盈利模式,QQ影音逐渐要被腾讯放弃。腾讯文档也因其实用性,受到不少办公族用户的关注。其实对于微信用户来说,腾讯文档还有许多鲜为人知的使用技巧。比如,我们在微信里
逆锋起笔
10
腾讯开始收费,这软件的良心操作彻底没了
转自:电脑报腾讯作为互联网巨头,也曾出品过不少良心软件,比如QQ影音就因安装包小、CPU占用少、界面简洁无广告无插件等备受用户喜爱。但因为没有合适的赚钱盈利模式,QQ影音逐渐要被腾讯放弃。腾讯文档也因其实用性,受到不少办公族用户的关注。其实对于微信用户来说,腾讯文档还有许多鲜为人知的使用技巧。比如,
dotNET全栈开发
10
腾讯云4月8日故障复盘及情况说明
4月8日15点23分,腾讯云团队收到告警信息,云API服务处于异常状态;随即在腾讯云工单、售后服务群以及微博等渠道开始大量出现腾讯云控制台登录不上的客户反馈。经过故障定位发现,客户登录不上控制台正是由云API异常所导致。云API是云上统一的开放接口集合,客户可以通过API以编程方式管理和操控云端资源
码农编程进阶笔记
10
面试题:toString()、String.valueOf、(String)强转,有啥区别?
点击关注上方“Stephen”,设为“置顶或星标”,第一时间送达干货一、前言相信大家在日常开发中这三种方法用到的应该很多,尤其是前两种,经常在开发的时候,随心所欲,想用哪个用哪个,既然存在,那就应该有它存在的道理,那么什么情况下用哪个呢?二、代码实例1、基本类型(1)基本类型没有toString()
Stephen
0
腾讯云 4.8 故障原因曝光:因 API 新版本兼容性不够和配置数据灰度机制不足
2024 年 4 月 8 日 15 点 23 分,腾讯云团队收到告警信息,云 API 服务处于异常状态;随即在腾讯云工单、售后服务群以及微博等渠道开始大量出现腾讯云控制台登录不上的客户反馈。经过故障定位发现,客户登录不上控制台正是由云 API 异常所导致。云 API 是云上统一的开放接口集合,客户可
开源Linux
10