202. Happy Number

Description

Write an algorithm to determine if a number is “happy”.

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example:

1
2
3
4
5
6
7

Input: 19
Output: true
Explanation: 
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

Idea

Since, there will be a repeated loop. We can use set() to save the repeated numbers.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution(object):
    def isHappy(self, n):
        """
        :type n: int
        :rtype: bool
        """
        set_ = set()
        while n not in set_:
            set_.add(n)
            tmp = 0
            while n > 0:
                bit = n % 10
                tmp += bit * bit
                n /= 10
            n = tmp
            
        return 1 in set_

138. Copy List with Random Pointer

Description

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Idea

Clone problem is always involved with hashmap which store the mapping from original nodes to new nodes.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

# Definition for singly-linked list with a random pointer.
# class RandomListNode(object):
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None

class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: RandomListNode
        :rtype: RandomListNode
        """
        if not head:
            return None

        # copy node (label) and create the mapping
        cur = head
        map_ = {}
        while cur:
            map_[cur] = RandomListNode(cur.label)
            cur = cur.next
            
        # traverse raw list and copy the relation (next and random)
        cur = head
        while cur:
            if cur.next:
                map_[cur].next = map_[cur.next]
            if cur.random:
                map_[cur].random = map_[cur.random]
            cur = cur.next
        
        return map_[head]

5. Longest Palindromic Substring

Description

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

1
2
3

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Idea

This is interval dp problem. Thus, we should build up a 2-d dp matrix to store information:
dp[i][j] represent whether s[i:j+1] is a palindromic substring or not.

Notice that ‘aa’ and ‘aca’ is palindromic string.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        dp = [[False] * len(s) for _ in range(len(s))]

        max_len = 0
        max_index = (0, 0)
    
        for j in range(len(s)):  # very naive traverse range
            for i in range(0, j + 1):
                if s[i] == s[j] and (j - i <= 2 or dp[i + 1][j - 1]): # j - i <= 2 is the base case in each row, say 'aa' (j = i + 1) or 'a' (j = i)
                    dp[i][j] = True
                if dp[i][j] and j - i + 1 > max_len:
                    max_len = j - i + 1
                    max_index = (i, j)
        print max_index
        return s[max_index[0]:max_index[1] + 1]

148. Sort List

Description

Sort a linked list in O(n log n) time using constant space complexity.
Example 1

1
2

Input: 4->2->1->3
Output: 1->2->3->4

Idea

merge sort, divide and conquer

Code

body

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

def sortList(self, head):
    """
    :type head: ListNode
    :rtype: ListNode
    """
    # base case:
    if head is None or head.next is None:
        return head
    
    # divide
    mid = self.findMid(head)
    next_head = mid.next
    mid.next = None
    sorted_left = self.sortList(head)
    sorted_right = self.sortList(next_head)

    # conquer
    res = self.merge(sorted_left, sorted_right)
    return res

find middle: fast and slow pointer

1
2
3
4
5
6
7
8
9
10

def findMid(self, head):
    if head is None:
        return None
    runner = head
    walker = head
    while runner.next and runner.next.next:
    # error while walker.next and runner.next.next:
        walker = walker.next
        runner = runner.next.next
    return walker

merge

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

def merge(self, head1, head2):
    dummy = ListNode(0)
    cur = dummy
    p1 = head1
    p2 = head2

    # perform the normal case
    while p1 and p2:
        if p1.val < p2.val:
            cur.next = ListNode(p1.val)
            p1 = p1.next
        else:
            cur.next = ListNode(p2.val)
            p2 = p2.next
        cur = cur.next

    # handle the rest list
    if p1:
        cur.next = p1
    if p2:
        cur.next = p2
    return dummy.next

14. Longest Common Prefix

Description

Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string “”.
Example 1:

1
2

Input: ["flower","flow","flight"]
Output: "fl"

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if not strs or len(strs) == 0:
            return ""
        
        for i, strs_ in enumerate(zip(*strs)):
            if len(set(strs_)) > 1:
                return strs[0][:i]
    
        return min(strs)

Python

zip(*)

1
2
3

arr = ["flower","flow","flight"]
for group in zip(*arr):
    print(group)

(‘f’, ‘f’, ‘f’)
(‘l’, ‘l’, ‘l’)
(‘o’, ‘o’, ‘i’)
(‘w’, ‘w’, ‘g’)
zip(*) unpack

min()

1

print(min(arr))

flight

这几天RSS (Robotics Science and System) 大会在CMU召开，蹭了几个Poster Session和一些大佬交流了下。最惊喜的是看到了男神田渊栋，还和他合了一张影。感觉CMU真是学术的圣地呀。也许现在自己没有资格进去，但是我总感觉未来有一天，会和他们站在同一个平台上，平等的较量和交流。和他们的交流讨论探讨时，一些东西一点点的浸润到自己的心田，自己的思维，自己的气魄里面。我相信，会有那么一天的。毕竟，自己的人生才刚刚开始。哈哈哈，还是好好做好手头上的事情，先上岸才行呀~

然后，想想自己从四月份开始写博客到现在也po了50多的内容。感觉有一篇净土能宣泄内心的躁动还是挺好的。自己的不甘，自己的抱负，自己的落寞，自己的苦楚，自己写给自己看，自己和自己说，自己为自己喝彩。

关于，找工作还是读博，未来的方向是什么我也不知道，但是白天research，晚上刷题投简历的过程，让我开始有一点点感觉了。总之，还是坚持吧。想来这个过程还是挺有意思的，哈哈哈~

突然想起男神知乎上面的po的“关于<<棋魂>>”里面的话：
“油管上的歌，转着转着又到了《棋魂》系列。我很早以前就看过这部动画，可以说是第一部让人流泪的动画。《棋魂》里，有人天份奇高又有助力于是终成正果，有人鞠躬尽瘁却与胜利失之交臂，有人在放弃后终于又鼓起勇气继续追求，有人纵横多年却在引退之时看到广阔天地。

下的是棋，问的是道，求的是梦，见的是人心。

还记得在故事一开始，进藤光在依靠佐为赢了塔矢亮之后，随口说出“围棋嘛，随便下着玩玩就好了”，塔矢亮听到这句话时的表情。这样无奈，彷徨，不甘，绝望，却又带着羡慕还有挣扎的表情，这样的表情，真心追求过梦想的人，曾体会过在无法逾越的高墙面前抓破头皮的绝望的人，在现实的夹缝中苦苦挣扎想要做得更好的人，想要出人头地却无奈随波逐流的人，我想，都可以带着颤抖的心和抽泣的脸去理解。然而，纵然带着平庸天份，纵然淹没在茫茫人海，还是有那么一群人，在嘲讽中渐渐改进，在孤独中反省内心，在失败中不停尝试，在奋斗的道路上一点点前行。”

也许现在我只是一个分母，但是，我还是会慢慢不停的尝试，一点点前行，谢谢你们，遇到你们真好

1
2
3
4

我知道，你们惊艳的presentation背后，是艰辛的付出，是不断的：尝试->失败->总结->尝试->失败->总结->....->好像是对的，但其实还是错了->尝试->失败->总结 ... 所以，对我来说，我还有很长很长的路要走。

怀揣着这份不甘，希冀能和你们相遇，所谓：求道之人，不问寒暑

Recently, I found that bash script is very useful to perform some tasks. Thus, I write a summary of it.

Resources

There’s a tutorial.

Simple Example

1
2
3
4
5

#!/bin/bash
for i in {1..400}; 
do
    echo item: $i
done

1
2
3
4
5

#!/bin/bash
for ((i=1;i<=100;i++)); 
do 
   echo $i
done

SGD 的发展：

• whole pipeline:

  1. 计算当前梯度：$g_t = \nabla f(w_t)$
  2. 根据历史记录计算一阶动量和二阶动量：$m_t = \phi (g_1, g_2, …, g_t)$，$V_t = \psi (g_1, g_2, …, g_t)$
  3. 计算当前时刻下降的梯度：$\eta = \alpha \frac{m_t}{\sqrt{V_t}}$
  4. 根据下降梯度进行更新：$w_{t + 1} = w_t - \eta_t$

• SGD:

  • pipeline:
    1. 计算当前梯度：$g_t = \nabla f(w_t)$
    2. 根据历史记录计算一阶动量和二阶动量：$m_t = g_t$，$V_t = I^2$
    3. 计算当前时刻下降的梯度：$\eta = \alpha \frac{m_t}{\sqrt{V_t}} = \alpha g_t$
    4. 根据下降梯度进行更新：$w_{t + 1} = w_t - \alpha g_t$
  • 问题：
    trapped in local valley and can be unstable

• SGD with Momentum

  • idea:
    to overcome the trapped problem and unstable problem, the Momentum is brought in.
  • pipeline:
    1. 计算当前梯度：$g_t = \nabla f(w_t)$
    2. 根据历史记录计算一阶动量和二阶动量：$m_t = \beta_1 m_{t - 1}+ (1 - \beta_1) g_t$，$V_t = I^2$
    3. 计算当前时刻下降的梯度：$\eta = \alpha \frac{m_t}{\sqrt{V_t}} = \alpha (\beta_1 m_{t - 1}+ (1 - \beta_1) g_t)$
    4. 根据下降梯度进行更新：$w_{t + 1} = w_t - \alpha (\beta_1 m_{t - 1}+ (1 - \beta_1) g_t)$

• SGD with Nesterov Acceleration

  • pipeline:
    1. 计算当前梯度：$g_t = \nabla f(w_t - \alpha \frac{m_{t - 1}}{\sqrt{V_{t - 1}}})$
    2. 根据历史记录计算一阶动量和二阶动量：$m_t = \beta_1 m_{t - 1}+ (1 - \beta_1) g_t$，$V_t = I^2$
    3. 计算当前时刻下降的梯度：$\eta = \alpha \frac{m_t}{\sqrt{V_t}} = \alpha (\beta_1 m_{t - 1}+ (1 - \beta_1) g_t)$
    4. 根据下降梯度进行更新：$w_{t + 1} = w_t - \alpha (\beta_1 m_{t - 1}+ (1 - \beta_1) g_t)$

• AdaGrad
  开始考虑二阶动量(嘛个鸡，不就是加速度吗。。。。很朴素。。。就像电动力学里面的电场的展开项，我二阶了就电偶极矩了。。。)，考虑二阶量也很好理解，描述问题会更精准一点，但是会有额外的计算量的cost

  1. 计算当前梯度：$g_t = \nabla f(w_t)$
  2. 根据历史记录计算一阶动量和二阶动量：$m_t = \phi (g_1, g_2, …, g_t)$，$V_t = \sum_{\tau=1}^t g_{\tau}^2$
  3. 计算当前时刻下降的梯度：$\eta = \alpha \frac{m_t}{\sqrt{V_t}} = \frac{\alpha}{\sqrt{V_t}} m_t$

  4. 根据下降梯度进行更新：$w_{t + 1} = w_t - \eta_t$

     你看这里 lr：$\frac{\alpha}{\sqrt{V_t}}$ 是自适应的，$V_t = \sum_{\tau=1}^t g_{\tau}^2$，是递增，lr则会递减，如果lr下降的太快，提前converge，那global optimal可能就没有被探索到

• AdaDelta / RMSProp
  $V_t = \psi (g_1, g_2, …, g_t) = \sum_{\tau=1}^t g_{\tau}^2 \rightarrow V_t = \psi (V_{t - 1}, g_{t}) = \beta_2 V_{t - 1} + (1 - \beta_2) g_{t}^2$ 不是只考虑全部历史，考虑前一次对本次的影响有点像Markov Chain

• Adam
  简单说，就是把上面方法都整合了一遍：

  谈到这里，Adam和Nadam的出现就很自然而然了——它们是前述方法的集大成者。我们看到，SGD-M在SGD基础上增加了一阶动量，AdaGrad和AdaDelta在SGD基础上增加了二阶动量。
  把一阶动量和二阶动量都用起来，就是Adam了——Adaptive + Momentum。
  （引自: https://zhuanlan.zhihu.com/p/32230623）

  SGD的一阶动量：
  $m_t = \phi (m_{t - 1}, g_{t}) = \beta_1 m_{t - 1} + (1 - \beta_1) g_{t}$
  加上AdaDelta的二阶动量：
  $V_t = \psi (V_{t - 1}, g_{t}) = \beta_2 V_{t - 1} + (1 - \beta_2) g_{t}^2$

• Bayesian Optimization：

• 总结：
  可以算是”万能”的，但对于特定的模型，不一定是最优的解法。更好的解法比如针对SVM的SMO算法、针对含隐变量的模型的EM算法等等。（from 王赟(yun第一声)）
  补充一点在数值分析里的结论…（虽然讨论的不是神经网络，但本质上还是求函数的极值点梯度下降法的问题在于，当很接近极值点的时候，下一步搜索的方向和之前搜索的方向correlation太高，会表现出在原地转圈的形状，每一步的改进量越来越小为了避免这一点才引出了共轭梯度法，要求新的搜索方向和之前每一步的搜索方向正交。
  (作者：匿名用户 链接：https://www.zhihu.com/question/38677354/answer/85324507）

  RNN

344. Reverse String

Description

Write a function that takes a string as input and returns the string reversed.

Example:
Given s = “hello”, return “olleh”.

Code

class Solution(object):
def reverseString(self, s):
“””
:type s: str
:rtype: str
“””
length = len(s)
if length < 2:
return s
strings_lst = []
for i in reversed(range(0,length)):
strings_lst.append(s[i])
return ‘’.join(strings_lst)

Python

reversed() Parameters
The reversed() method takes a single parameter:

seq - sequence that should be reversed
Could be an object that supports sequence protocol (len() and getitem() methods) as tuple, string, list or range
Could be an object that has implemented reversed()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# for string
seqString = 'Python'
print(list(reversed(seqString)))

# for tuple
seqTuple = ('P', 'y', 't', 'h', 'o', 'n')
print(list(reversed(seqTuple)))

# for range
seqRange = range(5, 9)
print(list(reversed(seqRange)))

# for list
seqList = [1, 2, 4, 3, 5]
print(list(reversed(seqList)))

# result:
['n', 'o', 'h', 't', 'y', 'P']
['n', 'o', 'h', 't', 'y', 'P']
[8, 7, 6, 5]
[5, 3, 4, 2, 1]

461. Hamming Distance

Description

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.
Example:

1
2
3
4
5
6
7
8
9
10

Input: x = 1, y = 4

Output: 2

Explanation:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑

The above arrows point to positions where the corresponding bits are different.

Idea

It’s involved with bits, which bring bit operations into my mind. — xor

Code

1
2
3
4
5
6
7
8

class Solution(object):
    def hammingDistance(self, x, y):
        """
        :type x: int
        :type y: int
        :rtype: int
        """
        return bin(x ^ y).count('1')

Python

bin() example:

1
2
3
4
5

number = 5
print('The binary equivalent of 5 is:', bin(number))

# result:
The binary equivalent of 5 is: 0b101

count() example:

1
2
3
4
5
6
7

aList = [123, 'xyz', 'zara', 'abc', 123];
print "Count for 123 : ", aList.count(123)
print "Count for zara : ", aList.count('zara')

# result:
Count for 123 :  2
Count for zara :  1