分类目录归档：技术文章

Java References

Java一共有四种强弱不同的引用，按照级别由高到低分别是：StrongReference、SoftReference、WeakReference、PhantomReference。
为了不重复造轮子，还是直接贴这篇文章中的一小段吧：查看出处
Java从1.2版本开始引入了4种引用，这4种引用的级别由高到低依次为：
强引用 > 软引用 > 弱引用 > 虚引用
⑴强引用（StrongReference）
强引用是使用最普遍的引用。如果一个对象具有强引用，那垃圾回收器绝不会回收它。当内存空间不足，Java虚拟机宁愿抛出OutOfMemoryError错误，使程序异常终止，也不会靠随意回收具有强引用的对象来解决内存不足的问题。
⑵软引用（SoftReference）
如果一个对象只具有软引用，则内存空间足够，垃圾回收器就不会回收它；如果内存空间不足了，就会回收这些对象的内存。只要垃圾回收器没有回收它，该对象就可以被程序使用。软引用可用来实现内存敏感的高速缓存。
软引用可以和一个引用队列（ReferenceQueue）联合使用，如果软引用所引用[……]

继续阅读

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条回复

这篇文章主要讨论三个问题：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],
]

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

public class Solution {

public List<List<Integer>> combine(int n, int k) {

List<List<Integer>> result =new ArrayList<List<Integer>>();

func(1, new ArrayList(), result, n, k);

return result;

}

/**

* 递归计算K个n长度的for循环

public void func(int x, List<Integer> list, List<List<Integer>> result, int n, int k){

if(list.size() == k){

result.add(list);

return;

}

for(int a=x;a<=n;a++){

list.add(a);

func(a+1, new ArrayList(list), result, n, k);

list.remove(list.size() -1);

}

return;

}

[……]

继续阅读

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?

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

public class Solution {

public static int count = 0;

public int climbStairs(int n) {

func(0, n);

return count;

}

//func(0,n)

public void func(int x, int n){

if(x == n){

count++;

}else if(x < n){

func(x+1, n);

func(x+2, n);

}

return;

}

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

public class Solution {

//'cause it only climbs 1 or 2 steps one time，so distinct ways of step n is the sum of ( n -1 ) and (n - 2)

public int climbStairs(int n) {

if(n <= 0){

return 0;

}

if(n <= 2){

return n;

}

int sum = 0;

int pre = 1;

int cur = 2;

for(int i=2; i<n; i++){

sum = pre + cur;

pre = cur;

cur = sum;

}

return sum;

}

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

继续阅读

永远的热河路

A man can be destroyed but Not Defeated.

分类目录归档：技术文章

Java References

Perfect Squares

浅谈可重入性及其他

Combinations

Climbing Stairs