分类目录归档:leetcode

Perfect Squares

点击量:264

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.

这题是个经典的动态规划(Dynamic Programming)问题,当前问题的解决依赖于子问题的答案。以前上算法选修课的时候这快内容是必讲的,但是当时对这个问题一知半解,感觉好难啊,就算当时懂了过了一段时间又忘了。然而DP却是算法里面最基本也最常用的技能,必须掌握!于是去网上搜了一些资料,发现好像也没那么难,结合例子很好理解,学完这块内容基本的DP问题就可以解决了。
动态规划-从新手到专家
这篇文章说的详细了,自己在这里只记录下一些要点,以供日后回忆。
1.什么是动态规划
动态规划是一种求解多阶段决策过程的最优解算法,含有[……]

继续阅读

Combinations

点击量:147

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.
For example,
If n = 4 and k = 2, a solution is:

[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

这题没有什么特别的思路吧,递归遍历。代码如下:

Climbing Stairs

点击量:144

You are climbing a stair case. It takes n steps to reach to the top.Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

思路:这个题目第一反应是用递归去计算,于是有了下面的代码:

这样的思路最简单,但是仔细看看就会发现,递归里有很多重复计算,而且当n很大时,这种方法的函数堆栈压的太深,栈溢出导致效率很低。
那么就得换一种思路了,其实到达第n级楼梯的步数(f(n))就等于前一级楼梯的步数f(n – 1) 和前二级楼梯的步数f(n -2)之和。为什么呢?因为每次只能走一步或者两步!因此,代码如下:

这种方式没有递归,非常快。