月度归档:2015年10月

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.

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

继续阅读

浅谈可重入性及其他

这篇文章主要讨论三个问题:1.什么是可重入性 2.什么是可重入锁 3.什么是ReentrantLock
首先为什么会讨论可重入性呢?大家知道java中有一个非常常用的类库叫ReentrantLock,中文翻译成可重入锁,每次看到这个翻译我的第一反应就是什么是可重入锁?为什么要这么命名呢?那么什么是ReentrantLock呢?Oracle的官方文档给出的解释是这样的:

A reentrant mutual exclusion Lock with the same basic behavior and semantics as the implicit monitor lock accessed using synchronized methods and statements, but with extended capabilities.

意思就是ReentrantLock和synchronized关键字所起的基本作用是一样的,但是提供了更多的扩展功能。看了这个解释并没有解答我的困惑,官方文档并没有解释什么是可重入锁,只是说了ReentrantLock提供了更多的功能。那么什么[……]

继续阅读

Combinations

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

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)之和。为什么呢?因为每次只能走一步或者两步!因此,代码如下:

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

继续阅读