一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 402|回复: 0
收起左侧

[算法题] LeetCode | 279. Perfect Squares

[复制链接] |试试Instant~ |关注本帖
zhugejunwei 发表于 2016-8-29 05:29:44 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 zhugejunwei 于 2016-8-28 16:37 编辑

今天我想聊聊 LeetCode 上的第279题-Perfect Squares,花了挺长时间的,试了很多方法,作为一个算法新手,个人感觉这题很好,对我的水平提升很有帮助。我在这里和大家分享一下我的想法。下面是题目:

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ... ) which sum to n. For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13,return 2 because 13 = 4 + 9.

大致意思就是,“给一个正数 n, 找到和为 n 的平方数, 给出最少的平方数个数”。
BFS
我刚开始想到的是用 BFS,经过一番实践,感觉代码是对的,但是 Time Limit Exceeded。毕竟用了 2 层循环。于是我就找了个字典(Dictionary)来存已经算过的节点,比如一个很大的数 n,有很大几率 n - i * i 这个节点和后面算出来的 m - j * j 是相等的。那么就不再重新计算。但是,还是超时了。这部分代码2个小时前被我扔了,我就不在这里重新写了。
Lagrange's four-square theorem
这里算是完全用数学知识解决了这个问题。不知道四平方和定理的请参考 wikipedia。话说童鞋们最好看英文版的 wiki,别翻译成中文比较好。我也不说英文更专业,虽然好像就是这么回事 == 因为有个公式非常重要,而解这题全靠这个公式:

                               
登录/注册后可看大图
这个定理就是讲,任何数都可以由4个平方数组成,即 n = a^2 + b^2 + c^2 + d^2,所以这题的答案已经限定在了 [1,4] 之间。
而上面这个公式的发明者-Adrien-Marie Legendre 又补充了这个定理:除了满足以上这个公式的数以外的任何数都可以由3个平方数组成。所以,这个答案又可以缩小范围了。范围都已经缩小到 [1,3] 了,我们开始求解。
先排除4个的情况:
   
while myN & 3 == 0 {        
myN >>= 2   
}   
if myN % 8 == 7 {        
return 4   
}

因为1和2的情况比较容易排除,先把1和2的排除。

var index = Int(sqrt(Double(n)))    while index > 0 {        
let tmp = Double(n - index * index)        
let sqrtTmp = Int(sqrt(tmp))        
if n == sqrtTmp * sqrtTmp + index * index {            
return sqrtTmp == 0 ? 1 : 2        
}      
index -= 1   
}
上面的代码就是说,如果一个数由2个平方数组成,如果其中一个平方数是0,那么就是1,如果不是0,那就是2。
剩下的就是3了,直接 return 3 就行了。在知道这个数学公式的情况下,这个方法还是很简单的。
DP
我刚刷题没几天,对于 DP 的推理过程还不是很熟练,琢磨了好久。一旦琢磨出来了,又觉得好简单,换一题,又可以琢磨一年。lol
初级的 DP 的使用方式差不多就是 Recursion + Memorization,就是递归和缓存。这里我们用一个数组来存储已经算过的数的最少平方数的个数 (记作 minNum)。从1开始算(从0也没事)。
这里我们分2层来算,外层循环是计算从1到 n的各个数的最少平方数 minNum, 存入到数组中,数组的 index 表示数 n,里面的 val 表示 minNum。关键是求每个数的 minNum。这里我们用到递归,核心代码就是:

let tmp = val - i * i  minNum = min(minNum, tmp == 0 ? 1 : 1+sta.record[tmp])  

tmp 表示 val 减去一个平方数剩下的数,如果 tmp 等于 0,就表示 val 等于 i * i,即它由1个平方数组成;如果 tmp != 0,就那么我们就需要求以 tmp 为 val 的 minNum,也就是 tmp2 = tmp - i * i ,这个 tmp2 就相当于之前的 tmp。为了求 tmp 的 minNum,我们需要计算出 从1到 sqrt(val) 之间所有的可能值,然后取最小值。最后将那个最小值存放到数组中。最终代码就是

func numSquares(n: Int) -> Int {      
var record = [0,1]   
while record.count <= n {        
var val = record.count, minNum = record.count      
for i in 1...Int(sqrt(Double(val))) {            
let tmp = val - i * i            
minNum = min(minNum, tmp == 0 ? 1 : 1+record[tmp])        
}        
record.append(minNum)   
}   
return record[n]}

但是跑了之后又发现,我特喵的没错啊,怎么时间又是这么长,1400ms。如果拿个稍微大点的数放到 playground 里跑一跑就会发现,循环次数还是挺多的。所以这里就需要考虑到把数组存成 static,而 swift 是没法在 function 里直接申明 static var n = 1 的,我们需要把 static 放在 class/struct 里,参见 SO 大神的解答,还有官方 doc
可以把这个 struct 放在 class Solution 里面,也可以放在外面,最后时间是 60ms 左右。从 1400 到 60,还是可以的。

struct sta {      static var record = [0,1]}

也许从短短这么一篇文章你就已经看出来了一些 swift 语言的特点,最大的特点就是类型安全。求个根都要Int(sqrt(Double(n))),我以前是用 C++ 的,遇到这种情况还是有点膈应的。但其实 swift 的优点绝对是可以让我安全无视这些小麻烦的,其实习惯了之后就感觉是更方便,更安全了。
以让我安全无视这些小麻烦的,其实习惯了之后就感觉是更方便,更安全了。

文章同步发在我的博客中,喜欢的可以订阅我的博客
欢迎转载,转载请注明出处





本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 11:00

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表