最近已经开始紧张的期末复习了，但是看到大家都在进行编程训练，为今年九月找工作做准备，我的心不能定。因为我知道，英国的成绩对我无意义，但是编程能力是我以后吃饭的家伙，我绝对不能落下。
之前一直在上普林斯顿的算法课。最后三周的课，每次上耗时太长，实在抽不出时间，而且自己已经明显过了之前的那种良好状态，很难再静下心听几个小时的，算法，课了。而且这个课对自己帮助到底有多大。说不清楚。之前的所有作业都是自己写的，但是现在回想起来好像都忘得差不多了，很难过。一定会找个时间把之前学过的东西都复习一遍的！
于是乎，决定开始刷题 + CS61B. 他们相对来说更加轻松点，而且对于找工作的帮助，功利的来说，更大点。以后每天至少刷一道题目，这个要求并不高吧。开始吧。
![]()
Paste_Image.png
我的解决：
public class Solution {
public boolean isHappy(int n) {
int pHead = n;
int pTail = n;
int sum = 0;
while (sum != 1) {
pHead = getSum(pHead);
if (pHead == 1)
return true;
pTail = getSum(getSum(pTail));
if (pHead == pTail)
return false;
sum = pHead;
}
return true;
}
private int getSum(int n) {
int sum = 0;
int digit = n % 10;
int residual = n / 10;
while (residual != 0) {
sum += digit * digit;
digit = residual % 10;
residual = residual / 10;
}
sum += digit * digit;
return sum;
}
public static void main(String args[]) {
Solution test = new Solution();
System.out.println(test.isHappy(12));
}
}
这个题目并不难，或者说，唯一的难点在于。如何判断这个数不是happy。
如果这个数不happy，那么他就会一直在循环里跑，然后计算机就会崩溃掉。
所以必须有个方法来检测某个数不happy.
于是我找了一个数 12
12
5
25
29
85
89
145
42
20
4
16
37
58
89
我发现其实他们是严格遵守映射关系的。于是乎，如果一个数不happy,那么，他的映射关系链上一定存在循环，比如这里的 89.就出现了循环，然后他会在这个循环链里按照规定的关系一直循环下去。所以， 12 是 不happy的。
那么，现在问题就归结到，如果判断，这个映射链是否循环呢？如何判断现在出来的这个数，在之前是否出现过呢？
网上最多的做法是，设置一个hash table，然后把这些数都放在hash table 中。那么, 89 也会在这个哈希表里有自己的位置。当第二次89出现时，按照哈希映射，他也会找到哈希表中相应的位置，然后发现这个位置被人占了。就知道，发生循环了。
但是哈希表也有他的问题。首先是，他得额外占内存来存放哈希表。而且加入起始输入的数是 1000000000. 哈希表（数列）就会触发resize()功能，让哈希表扩展到这么大，但是之后就直接判断出，该数是happy的，那么这么大的数列就只存放了这么一个数字，太浪费空间了。
下面我给出我网上找的别人写的用哈希表实现的代码。没有多大难度，都是利用Java写好的类。
public class Solution {
public boolean isHappy(int n) {
int newN = 0;
HashSet<Integer> set = new HashSet<Integer>();
while(!set.contains(n)){
set.add(n);
newN = 0;
while(n != 0){
newN += (n % 10) * (n % 10);
n /= 10;
}
n = newN;
if(n == 1) return true;
}
return false;
}
}
我后来看人的评论，发现了一个更好的方法。
他们使用了一个算法，叫做，Floyd's cycle-finding algorithm
这个算法的模型是：
def floyd(f, x0):
# Main phase of algorithm: finding a repetition x_i = x_2i
# The hare moves twice as quickly as the tortoise and
# the distance between them increases by 1 at each step.
# Eventually they will both be inside the cycle and then,
# at some point, the distance between them will be
# divisible by the period λ.
tortoise = f(x0) # f(x0) is the element/node next to x0.
hare = f(f(x0))
while tortoise != hare:
tortoise = f(tortoise)
hare = f(f(hare))
也就是用两个指针指着这个逻辑链，一开始都只在头部，比如说12.
然后头指针会指向下一个结点，5.判断下。
尾指针会指向以此刻位置为基准的，之后的第二个结点，即25.判断下尾指针和头指针是否相等，若相等，则说明存在循环。return false.
然后头指针指向25，尾指针指向85.。。
以此循环。。。
然后参考的网址是，
http://en.wikipedia.org/wiki/Cycle_detection
当然，这个算法的原理我是不懂得。但的确很好用哈。工程师吗，那理论家的理论当作工具用就行了，原理这些事，交给理论家吧。他们反正也是闲着没事干的。
**
最后做下总结，这次作业，收获在于学习了Floyd's cycle-finding algorithm算法，即如何判断一个映射链中是否存在循环，是采用两个指针实现的。
**
Leetcode的第一次就这么完成了。希望可以坚持下去。
写这篇文章正好学习了一些markdown语法，感觉很好用啊！掌握了这么一门语法，以后就不需要word了。。。加粗什么的直接代码实现，方便快捷高效！
学校的复习压力很重。但是自己现在为了考试学习电气的东西，很没有热情，而且觉得是浪费时间。但是叶也说得挺对的。当我没有选择，只能做一件事时，就把他当作提高自己学习能力的一件事来做吧。
Good luck, Richado!
My code:
public class Solution {
public boolean isHappy(int n) {
if (n <= 0) {
return false;
}
HashSet<Integer> set = new HashSet<Integer>();
set.add(n);
while (n != 1) {
n = helper(n);
if (set.contains(n)) {
return false;
}
set.add(n);
}
return true;
}
private int helper(int n) {
int base = 10;
int ret = 0;
while (n > 0) {
ret += (n % 10) * (n % 10);
n = n / 10;
}
return ret;
}
}
比较简单。
上面说的其实就是快慢指针。但是快慢指针存在的问题是，有一些重复操作啊。
这是我踏入 Leetcode 的第一题。想想都过了一年半了。自己的水平，也早就比那时候强了太多。但反而更加感觉到自己的渺小。
继续努力吧，希望自己能有个好运气。
Anyway, Good luck, Richardo! -- 09/21/2016
