Algorithm

每日一题-字符串乘积

[每日一题] (字符串乘积)
Given a list of words, return the maximum numerical product value of two words length, where the two words don’t share any common letters.
For this example, [cat, dog, day, space, telephone]
cat->3 and telephone->9, return 3X9=27

解题思路


这题暂时没什么好的思路，唯一想到可以优化的地方就是可以使用bit manipulation来判断字符是否重复。
可以使用32为二进制数来代表每个单词(假设26个字母), 判断字符是否重复时就直接与运算判断是否为0。
剩下的用Brute Force

Python:
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
#!/usr/bin/env python
# -*- coding:utf-8 -*-
words = ["cat", "dog", "day", "space", "telephone"]
class Solution(object):
    def wordMul(self, words):
        n = len(words)
        bit = [0 for i in xrange(n)] # binary number for each word
        wl = [len(words[i]) for i in xrange(n)] # length of each word
        self.produceBit(words, bit, wl)
        maximum = 0
        for i in xrange(n-1):
            for j in xrange(i, n):
                if bit[i] & bit[j] == 0:
                    maximum = max(maximum, wl[i] * wl[j])
        return maximum
    def produceBit(self, words, bit, wl):
        alpha = "abcdefghijklmnopqrstuvwxyz"
        dict = {}
        for i in xrange(len(alpha)):
            dict[alpha[i]] = i 
        for i in xrange(len(words)):
            for j in xrange(wl[i]):
                d = dict[words[i][j]]
                bit[i] = bit[i] | 1 << d


Algorithm

每日一题-石之游戏

[每日一题] (石之游戏)
n堆石头排成一行，你每次可以把相邻的2堆石头聚成1堆，聚合后的石头数会成为你的分数的一部分。
问当进行n-1次，所有石头聚成一堆后，怎么使得总分最小。
例子: [3, 4, 3]
  第一次 3+4=7 -> [7, 3]
  第二次 (7) + 7 + 3 = 17 -> [17]
  总分17最少。

Follow-up(Google onsite): 变成一个环

解题思路


使用动态规划,思路可参考算法导论的矩阵链乘法。
状态转移矩阵:
  p[i][j] = min[p[i][k] + p[k+1][j] + s[i][j]] (i<=k<=j)
  s[i][j] = s[i][k] + s[k+1][j]
其中p[i][j]表示从i合并到j所得的最小分数，s[i][j]表示从i合并到j所得出的数

Python:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#!/usr/bin/env 
# -*- coding:utf-8 -*-
"""
时间复杂度 O(n^3)
"""
stone = [16,11,7,17,11,7,9,2,17,20,22,7,5,17,6,14,21,2,9,2,15,20,14,6,12,16,9,8,14,5,1,12,4,19,5,14,22,20,13,12,19,14,3,6,17,21,13,17,8,9,18,1,8,12,5,20,2,7,14,22,14,7,12,20,22,2,13,15,9,14,20,13,3,18,8,10,20,10,18,21]
N = len(stone) 
class Solution(object):
    def stoneGame(self, stone, N):
        p = [[0 for i in xrange(N)] for j in xrange(N)] # p[i][j]代表合并i到j的最优解
        s = [[0 if i != j else stone[i] for i in xrange(N)] for j in xrange(N)] # s[i][j]代表合并i到j后生成的值
        for l in xrange(1, N): # 循环N-1次， 每次得到长度为l+1的石头堆的最优解
            for i in xrange(N-l):
                j = i + l # 计算当前尾部j
                p[i][j] = None
                for k in xrange(i, j):
                    if p[i][j] == None:
                        s[i][j] = s[i][k] + s[k+1][j]
                        p[i][j] = p[i][k] + p[k+1][j] + s[i][j]
                    else:
                        p[i][j] = min(p[i][j], p[i][k] + p[k+1][j] + s[i][j])
        return p[0][N-1] # p[0][N-1]代表合并0到N-1的最优解，即为答案