Algorithm

每日一题-A+B-

[每日一题] (A+B-)
给出两个字符串,s1和s2。s2中的+表示前面的字符重复2次，-代表前面的字符重复4次。问题是求s1中有多少个连续或不连续的s2。
例子: s1 = “aaabbbb” , s2 = “a+b-“
输出: 3

解题思路


使用动态规划。具体思路说起来有点绕…总之算是一个比较麻烦的动态规划题。

用n数组存储到当前位置为止有多少个n子串，用n_1数组存储到当前位置为止有多少个n-1子串
状态转移函数是n[i] = n[i-1] + n_1[i-1] + n_1[i-2] + … + n_1[2]或n_1[4]，大概就是这个意思

代码没有经过很多测试，可能会有bug

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#!/usr/bin/env python
# -*- coding:utf-8 -*-
#s1 = "aabbbbaacc"
#s2 = "a+b-c+"
#s1 = "aaabababbaabbccc"
#s2 = "a+b-c+"
#s1 = "aababaaabaaab"
#s1 = "aabaabaabcc"
#s2 = "a+b+c+"
#s1 = "waeginsapnaabangpisebbasepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc"
#s2 = "a+b+c-"
s1 = "wweqwqaabddakswbbcc"
s2 = "a+b+"
class Solution(object):
    def aPlusbPlus(self, s1, s2):
        pre = {} # 记录当前字符的前一字符
        index = {} # 记录当前字符位置
        count = {} # 记录当前字符找了几个
        bound = {} # 记录当前字符要找几个
        p = None
        for i in xrange(len(s2)/2):
            pre[s2[i*2]] = p
            index[s2[i*2]] = 0
            count[s2[i*2]] = 0
            bound[s2[i*2]] = 2 if s2[i*2+1] == '+' else 4
            p = s2[i*2]
        n_1 = [[0, 0] for i in xrange(len(s1))]
        n = [[0, 0] for i in xrange(len(s1))]
        for i in xrange(len(s1)):
            c = s1[i]
            if c in index.keys():
                if c == s2[0]: # 当前字符为s2首字符
                    count[c] += 1
                    sum = 1
                    for j in xrange(bound[c]):
                        sum *= count[c] - j
                    n[i] = [sum / bound[c], c]
                    n_1[i] = [0, c]
                    index[c] = i
                else:
                    count[c] += 1
                    n_1[i] = [n[index[pre[c]]][0], c]
                    if count[c] < bound[c]:
                        n[i] = [0, c]
                    else :
                        n[i] = [n[index[c]][0], c]
                        count1, j = count[c] - 1, i-1
                        while count1 >= bound[c]-1 and j >= 0:
                            if n_1[j][1] == c:
                                n[i][0] += n_1[j][0]
                                count1 -= 1
                            j -= 1
                    index[c] = i
        return n[index[s2[len(s2)-2]]][0]

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

每日一题-Trap_Water

[每日一题] (Trapping Rain Water II)
Trapping Rain Water II
Given n x m non-negative integers representing an elevation map 2d where the area of each cell is 1 x 1, compute how much water it is able to trap after raining.
Example
Given 5*4 matrix

[12,13,0,12]
[13,4,13,12]
[13,8,10,12]
[12,13,12,12]
[13,13,13,13]
return 14.

解题思路


使用最小堆
1.对矩形的四周建堆
2.对于堆中每一元素，查探其四邻域中未查探的位置
3.如果h小于当前值，则更新水池容量，并将该位置加入堆中
4.如果h大于等于当前值，则直接加入堆中
最小堆中每次取的元素为当前水池中最短边的长度，如果每次寻找时发现了比最短边低的位置，则可以将水导入（更新水池容量），否则直接将该位置加入到水池中形成新的边缘

笔记

  最小堆的题目的特征(不断找最小)，对Python中的最小堆的使用

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
26
27
28
29
30
31
32
33
34
35
36
37
#!/usr/bin/env 
# -*- coding:utf-8 -*-
import heapq
M = [[12, 13, 0, 12], [13, 4, 13, 12], [13, 8, 10, 12], [12, 13, 12, 12], [13, 13, 13, 13]]
class Solution(object):
    def trapWater(self, M):
        heap = []
        heapq.heapify(heap)
        d = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        n = len(M)
        m = len(M[0])
        visit = [[0 for i in xrange(m)] for I in xrange(n)]
        res = 0
        for i in xrange(n):
            for I in xrange(m):
                if i == 0 or I == 0 or i == n-1 or I == m-1:
                    heapq.heappush(heap, (M[i][I], i, I))
                    visit[i][I] = 1
        while heap != []:
            this = heapq.heappop(heap)
            for i in xrange(4):
                h = this[0]
                nr = this[1] + d[i][0]
                nl = this[2] + d[i][1]
                if nr < 0 or nl < 0 or nr >= n or nl >= m:
                    continue
                if visit[nr][nl] == 1:
                    continue
                visit[nr][nl] = 1
                tmp = M[nr][nl]
                if tmp < h:
                    res += h - tmp
                    tmp = h
                heapq.heappush(heap, (tmp, nr, nl))
        return res