2018-09-13

Subsets

Slow Version

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        n, res = len(nums), list()
        for i in xrange(2**n):
            res.append(filter(lambda x: x is not None, map(lambda x, y: y if (int(x) * y or y == 0 and int(x) != 0) else
 None, list(bin(i)[2:].zfill(n)), nums)))
        return res

BitwiseOperators Version

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        nums.sort()
        STDOUT = True
        for i in xrange(1 << len(nums)):
            if STDOUT: print 'i =', i
            tmp = []
            for j in xrange(len(nums)):
                if STDOUT: print '{0:03b}'.format(i), '&', '{0:03b}'.format(1 << j), '->', i & 1 << j
                if i & 1 << j:
                    if STDOUT: print 'pick', '{0:03b}'.format(1 << j), nums, 'j =', j, 'target', nums[j]
                    tmp.append(nums[j])
            if STDOUT: print 'i = {0:03b}'.format(i), 'tmp =', tmp
            res.append(tmp)
        return res

output

In [748]: s = Solution(); print s.subsets([1, 2, 3])
i = 0
000 & 001 -> 0
000 & 010 -> 0
000 & 100 -> 0
i = 000 tmp = []
i = 1
001 & 001 -> 1
pick 001 [1, 2, 3] j = 0 target 1
001 & 010 -> 0
001 & 100 -> 0
i = 001 tmp = [1]
i = 2
010 & 001 -> 0
010 & 010 -> 2
pick 010 [1, 2, 3] j = 1 target 2
010 & 100 -> 0
i = 010 tmp = [2]
i = 3
011 & 001 -> 1
pick 001 [1, 2, 3] j = 0 target 1
011 & 010 -> 2
pick 010 [1, 2, 3] j = 1 target 2
011 & 100 -> 0
i = 011 tmp = [1, 2]
i = 4
100 & 001 -> 0
100 & 010 -> 0
100 & 100 -> 4
pick 100 [1, 2, 3] j = 2 target 3
i = 100 tmp = [3]
i = 5
101 & 001 -> 1
pick 001 [1, 2, 3] j = 0 target 1
101 & 010 -> 0
101 & 100 -> 4
pick 100 [1, 2, 3] j = 2 target 3
i = 101 tmp = [1, 3]
i = 6
110 & 001 -> 0
110 & 010 -> 2
pick 010 [1, 2, 3] j = 1 target 2
110 & 100 -> 4
pick 100 [1, 2, 3] j = 2 target 3
i = 110 tmp = [2, 3]
i = 7
111 & 001 -> 1
pick 001 [1, 2, 3] j = 0 target 1
111 & 010 -> 2
pick 010 [1, 2, 3] j = 1 target 2
111 & 100 -> 4
pick 100 [1, 2, 3] j = 2 target 3
i = 111 tmp = [1, 2, 3]
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

leet code

https://wiki.python.org/moin/BitwiseOperators

2018-09-12

leetcode

First Unique Character in a String

one line version

class Solution(object):
    def firstUniqChar(self, s):
        """
        :type s: str
        :rtype: int
        """
        return min([s.find(c) for c in string.ascii_lowercase if s.count(c)==1] or [-1])

slow version

from collections import OrderedDict
class Solution(object):
    def firstUniqChar(self, s):
        """
        :type s: str
        :rtype: int
        """
        res = -1
        hash_dict = OrderedDict()
        for i in range(len(s)):
            if s[i] in hash_dict:
                hash_dict[s[i]] = (hash_dict[s[i]][0] + 1, i)
            else:
                hash_dict[s[i]] = (0, i)
        for v in hash_dict.values():
            if v[0] == 0:
                res = v[1]
        return res

output

In [604]: import string
In [605]: s = Solution(); print s.firstUniqChar('loveleetcode')
2

leet code

2018-09-10

leetcode

4Sum II

class Solution(object):
    def fourSumCount(self, A, B, C, D):
        """
        :type A: List[int]
        :type B: List[int]
        :type C: List[int]
        :type D: List[int]
        :rtype: int
        """
        hashtable = {}
        for a in A:
            for b in B:
                if a + b in hashtable:
                    hashtable[a + b] += 1
                else:
                    hashtable[a + b] = 1
        counter = 0
        for c in C:
            for d in D:
                if -(c + d) in hashtable:
                    counter += hashtable[-(c + d)]
        return counter

collections.Counter version

class Solution(object):
    def fourSumCount(self, A, B, C, D):
        """
        :type A: List[int]
        :type B: List[int]
        :type C: List[int]
        :type D: List[int]
        :rtype: int
        """
        import collections
        AB = collections.Counter(a+b for a in A for b in B)
        return sum(AB[-c-d] for c in C for d in D)

output

In [490]: A=[1,2]
     ...: B=[-2,-1]
     ...: C=[-1,2]
     ...: D=[0,2]
     ...:
In [491]: s = Solution(); print s.fourSumCount(A, B, C, D)
2

8.3. collections — High-performance container datatypes

Python标准库——collections模块的Counter类

Python：使用Counter进行计数统计及collections模块

不可不知的Python模块: collections

leet code

2018-09-09

leetcode

Best Time to Buy and Sell Stock II

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        import sys
        res, last = 0, sys.maxint
        len_prices = len(prices)
        for i in range(len_prices):
            profit, last = prices[i] - last if prices[i] > last else 0, prices[i]
            res += profit
        return res

output

1 2	In [488]: s = Solution(); print s.maxProfit([7,1,5,3,6,4]) 7

leet code

2018-09-08

leetcode

Permutations

Roman to Integer

Great Version

class Solution(object):
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        res, p = 0, 'I'
        DICT = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
        for x in s[::-1]:
            res, p = res - DICT[x] if DICT[x] < DICT[p] else res + DICT[x], x
        return res

Ugly Version

class Solution(object):
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        res = []
        LEFT = {'IV': 4, 'IX': 9, 'XL': 40, 'XC': 90, 'CD': 400, 'CM': 900}
        DICT = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
        list_s = list(s)
        len_s = len(s)
        i = 0
        while True:
            if i == len_s - 1:
                res.append(DICT[list_s[i]])
                break
            elif i + 1 < len_s:
                left = list_s[i] + list_s[i + 1]
                if left in LEFT:
                    res.append(LEFT[left])
                    i += 2
                else:
                    res.append(DICT[list_s[i]])
                    i += 1
            else:
                break
        # print res
        return sum(res)

output

1 2	In [476]: s = Solution(); print s.romanToInt('MCDLXXVI') 1476

leet code