Algorithm

每日一题-Best_Time_to_Buy_and_Sell_Stock_with_Cooldown

[每日一题] (Best Time to Buy and Sell Stock with Cooldown)
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)

解题思路


本题使用动态规划，解题思路类似于抢劫问题。使用3个变量free, cool, have来存储当前位置的最优解。
free用来存储到当前位置，状态为空闲时的最优解
have用来存储到当前位置，状态为持有股票时的最优解
cool用来存储到当前位置，状态为正在冷却时的最优解

状态转移矩阵为：
free = max(free, cool) # 当前free的最优解由上一时间free的最优解和cool的最优解得出
have = max(have, free-p) # 当前have的最优解由上一时间持有股票时的最优解和上一时间空闲而这一时间购买股票的最优解得出
cool = have + p #当前cool的最优解由上一时间持有股票的最优解再在这一时间卖出得出

Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#!/usr/bin/env 
# -*- coding:utf-8 -*-
"""
时间复杂度 O(n)
"""
prices = [1, 2, 3, 0, 2]
class Solution(object):
  def maxProfit(self, prices):
    """
    :type prices: List[int]
    :rtype: int
    """
    free = 0
    have = cool = float('-inf')
    for p in prices:
        free, have, cool = max(free, cool), max(have, free-p), have+p
    return max(free, cool)

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