注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

微软、Google等面试题

剑指Offer:名企面试官精讲典型编程题

 
 
 

日志

 
 

程序员面试题精选100题(68)-删掉再赚到[算法]  

2018-01-23 03:46:51|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
问题:给你一个整数数组nums,你可以在数组上做如下操作:你可以选择任意一个数字nums[i]把它删掉并赚到nums[i]个点。此后,你必须删除数组中所有值为nums[i]-1nums[i]+1的数字。你最开始有0个点。请问你如此执行操作最多能从数组上赚到多少个点?假设数组中的数字在[1, 10000]的范围之内。

例如假设输入数组nums为[2, 2, 3, 3, 3, 4],你最多可以赚到9个点。你的最佳方案是删掉一个3赚到3个点。此时需要删掉所有的2和4。接下来你可以再删掉一个3赚到3个点。由于所有的2和4都已经删掉了,你不需要再删除更多的数字。然后你再删掉最后一个3再赚到3个点。因此你一共赚到9个点。

分析:这是LeetCode第759题。


数组nums中的数字都是在[1,10000]的范围之内。这个范围不算太大。因此我们可以创建一个长度为10001的数组vals。该数组中下标为m的数值为原数组nums中所有值为m的数字的和(数值m可能在数组nums中出现0次、一次或者多次)


根据题目的规则,如果我们赚到数组nums中值为m的点数,那么我们将不能赚到所有值为m-1和m+1的点数。那么在数组vals中如果我们赚到了下标为m的数字对应的点数,那么就不能赚到下标为m-1和m+1的数字对应的点数。

 

如果我们用函数f(i)表示在数组vals中前i个数字中最多能够赚到的点数,f(i)=max(f(i-1), vals[i]+f(i-2))。这是一个典型的可以用动态规划求解的问题。

 

由于我们只需要保存f(i-1)和f(i-2)的值就能球的f(i)的值,因此我们在求解过程中只需要使用两个变量存储之前子问题的解即可。

 

这个思路对应的Java代码如下所示:

程序员面试题精选100题(68)-删掉再赚到[算法] - 何海涛 - 微软、Google等面试题

 

在上述代码中有两个for循环。第一个for循环的执行次数为数组nums的长度,时间复杂度为O(n)。第二个for循环的执行次数为数组vals的长度即常数10001,时间复杂度是O(1)。因此总的时间复杂度为O(n)。我们创建了一个常数长度的数组vals,以及使用了若干变量,总的空间复杂度是O(1)


举一反三:

本题实质上LeetCode198题(House Robber)的变种。LeetCode198题中,小偷不能到两栋相邻的房子里进行偷窃。如果我们把房子里的财物的价值用数组表示,也就是如果他偷得了数组中第i个数字的财物,就不能偷得数组中第i-1i+1个数字的财物。我们把LeetCode740题中的nums转换成vals之后,两个题目就一样了。


本文转载自微信公众号青云算法扫描下面的二维码,关注“青云算法”微信公众号,学习更多高频算法面试题的解法。

程序员面试题精选100题(65)-每天的温度[算法] - 何海涛 - 微软、Google等面试题

  评论这张
 
阅读(439)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018