Category Archives: Aha moments

Coding is not a game for me, which is painful but along with implicit happiness.

Maximum Product of Word Lengths

Posted on by
Reply
Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.
Example 1:

Input: ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16 Explanation: The two words can be "abcw", "xtfn".

Example 2:

Input: ["a","ab","abc","d","cd","bcd","abcd"]
Output: 4 Explanation: The two words can be "ab", "cd".

Example 3:

Input: ["a","aa","aaa","aaaa"]
Output: 0 Explanation: No such pair of words.

Find All Numbers Disappeared in an Array

Posted on by
Reply
Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements of [1, n] inclusive that do not appear in this array.
Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.
Example:

Input:
[4,3,2,7,8,2,3,1]
Output:
[5,6]

刚一看到这道题是Medium难度的时候，我觉得Leetcode高估了这道题。但是后面O(1)空间和O(n)时间发现还是没有那么容易的。

seen = list()
result = list()
for item in nums:
if item in seen:
    result += [item]
    seen += [item]
else:
    seen += [item]
return result

这种方法按理说是可以过的 (虽然不符合题目对空间复杂度的要求)，但是在Leetcode平台上，我发现这种方法会超时(TLE)

res = []
for x in nums:
    if nums[abs(x) - 1] < 0:
        res.append(abs(x))
    else:
        nums[abs(x) - 1] *= -1
return res

想了十分钟之后，我发现我貌似想不出什么好方法了，于是看了一下Discuss里大佬的解法。
这个解法真的是Awesome！在保证了O(n)时间的前提下，完美利用之前的空间做了一次Hash。只能说想出这个方法的人是个小天才了！(这里是Disscuss的帖子地址)

生命游戏

Posted on by
Reply

It is an immemorial game which I really hope you can enjoy.

#coding: utf-8
import time
import numpy as np
import subprocess
class LifeSpace:
    def __init__(self, name, israndom, size_x, size_y):
        self.name = name
        self.israndom = israndom
        self.size = (size_x, size_y)
        self.iter_times = 0
        self.Z = Z = np.random.randint(0, 2, self.size)
    def iterate(self):
        # Count neighbours
        N = (self.Z[0:-2, 0:-2] + self.Z[0:-2, 1:-1] + self.Z[0:-2, 2:] +
             self.Z[1:-1, 0:-2]                      + self.Z[1:-1, 2:] +
             self.Z[2:  , 0:-2] + self.Z[2:  , 1:-1] + self.Z[2:  , 2:])
        # Apply rules
        birth = (N == 3) & (self.Z[1:-1, 1:-1] == 0)
        survive = ((N == 2) | (N == 3)) & (self.Z[1:-1, 1:-1] == 1)
        self.Z[...] = 0
        self.Z[1:-1, 1:-1][birth | survive] = 1
        # Iterate update
        self.iter_times += 1
    def get_Z_status(self):
        print("--"*(self.size[0]/2) + str(self.iter_times)  + "--"*(self.size[0]/2))
        line = ''
        for i in self.Z:
            for j in i: line += "■" if j == 1 else "□"
            print line
            line = ''
    def process(self, iter_time):
        for i in range(iter_time):
            self.iterate()
            self.get_Z_status()
            time.sleep(0.3)
            subprocess.call("clear")
if __name__ == "__main__":
    newspace = LifeSpace("Elf", True, 15, 30)
    newspace.process(1000)

BTW, You can also find it at Github.

由爬楼梯问题引发的思考

Posted on by
Reply

这两天鱼神要去面Google，居然破天荒的准备了起来。 昨天晚上他突然给我发了一道Leetcode上的Easy题 —— 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?
Note: Given n will be a positive integer.

因为在学习动态规划的时候，这道题就是用来入门的，所以一拿到这道题，应该很自然的就可以想到动态规划的方法。 状态转移方程为：ways[n] = ways[n – 1] + ways[n – 2] 然后套路的发现这个形式长的居然和斐波那契数列一摸一样（对！没错，这题就是套着斐波那契出的。）所以就产生下面的几种解法：
Method 1: 递归求解

class Solution(object):
    def climbStairs(self, n):
        if n == 1 or n <= 0:
            return 1
        return climbStairs(n-1) + climbStairs(n-2)

Method 2: 非递归求解

class Solution(object):
    def climbStairs(self, n):
        a = b = 1
        for x in range(2, n + 1):
            a, b = b, a + b 
        return b

Method 3：通项公式求解

class Solution(object):
    def climbStairs(self, n):
        sqrt5 = math.sqrt(5)
        Phi = (1 + sqrt5) / 2
        phi = (1 - sqrt5) / 2
        return int((Phi ** (n + 1) - phi ** (n + 1)) / sqrt5)

Method 4: 杨辉三角叠加法

class Solution(object):
    def c(self, m, n):
        x = 1
        for i in xrange(m-n+1, m+1):
            x *= i
        for i in xrange(2, n+1):
            x /= i
        return x
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        result = 0
        for i in range(0, n/2+1):
            result += self.c(n-i, i)
        return result


隐写术

Posted on by
Reply

我们知道，图片上的每一个像素点都是由（r, g, b）三个颜色通道组成的，轻微的改动其中的像素值肉眼并无法察觉。利用这一点，我们就可以在图片中隐写大量的信息。

在the First Lady of the Internet的图片中，三个通道都隐写了信息，我们可以通过python的Pillow库进行图片处理，从而得到隐写的内容。
BTW， 女神原图有福利 (~.~)

from PIL import Image
import matplotlib.pyplot as plt
img = Image.open('1.png')
pix = img.load()
for i in range(img.size[0]):
    for j in range(img.size[1]):
        (r, g, b) =  pix[i, j]
        pix[i, j] = (0, 0, r%2*255)
img.show()

最后，放一张鹅厂Alloy Team女神小兰的图吧，至于福利怎么找，我猜你应该懂的。

struggle

Posted on by
Reply

周五下单订了一块带OLED的单片机模块，加钱寄了SF，于是周六就收到了东西。
之前用Python很快的就实现了整个算法，觉得还挺简单的。但是换到用C写就出了很多问题，没有了方便调用的库，所有的东西都得自己写。
于是我愉快地肝了一个通宵，终于手拍出了没有任何依赖的Hmac-sha1。以现在的情况来看，一切运转良好，只需要再加上一个RTC的功能就可以正常工作了。
另外，这个板子还自带Wifi和蓝牙的功能，打算等回家了试一试。
没有奇迹，全靠拼命。