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

微软、Google等面试题

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

 
 
 

日志

 
 

程序员面试题精选100题(72)-第k个符号[算法]  

2018-02-27 16:23:35|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

问题:我们在第一行写下一个0。在接下来的每一行,都把上一行的0替换成01,把1替换成10。因此前4行如下:

第1行:0

第2行:01

第3行:0110

第4行:01101001

输入整数N(1<=N<=30)和K(1<=K<=2^(N-1)),求第N行第K个字符是什么?N和K都从1开始计数。


分析:这是LeetCode的第779题。


首先,我们注意到的是按照题目的规则,每一行的长度是呈指数增长的。N的最大值可以到30,那么第30行的长度是2^29,即有512M个字符。我们如果试图生成每N行,再求出第K个字符,看起来空间开销是很大的。


解法一:

 

可以通过分析每一行并找出字符的规律,从而找出更好的办法。首先,注意到可以把每一行平均分成两半,前一半正好和前一行的内容相同。例如,第4行的前半段0110正好是第三行的内容。

 

如果再仔细观察,我们还能发现每一行的后半段是前半段二进制取反的结果。如果我们把第4行的前半段0110看成是二进制,它按位取反(即~0110)的结果是1001,正好是第4行的后半段。

 

因此,我们可以这样递归地求第N行的第K个字符:首先判断第K个字符位于第N行的前半段还是后半段。如果是位于前半段,那么它就是第N-1行的第K个字符;如果位于后半段,那么它就是第N-1行第K-2^(N-2)个字符的取反结果。

 

基于这个思路,我们不难写出如下代码:


程序员面试题精选100题(72)-第k个符号[算法] - 何海涛 - 微软、Google等面试题

 

由于每一次调用N减去1,递归调用的深度为O(N),因此时间复杂度可空间复杂度都是O(N)

 

解法二: 

我们注意到题目的规则是把上一行的一个字符替换成两个字符,因此,每一行的第2K-1个字符和第2K个字符都是替换上一行的第K个字符得到的。按照从0替换成01、1替换成10的规则,每一行的第2K-1个字符和上一行的第K个字符相同,而第2K个字符和上一行的第K个字符相反。同时上一行的第K个字符和当前行的第K个字符相同(因为第K个字符一定位于前半段)。


于是我们把问题转换成,如果K是偶数,那么它和第K/2个字符相反;如果K是奇数,那么它和(K+1)/2个字符相同。根据这个规律也很容易写出递归代码:

程序员面试题精选100题(72)-第k个符号[算法] - 何海涛 - 微软、Google等面试题 

在上述代码中,每一次递归调用都把K除以2,因此递归的深度是O(logK),时间复杂度和空间复杂度也都是O(logK)。由于K的最大值2^(N-1),因此这种思路的复杂度和第一种方法实际上是一样的。


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

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

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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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