leetcode

Permutations

Permutations 排列

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        self.dfs(nums, [], res)
        return res
    def dfs(self, nums, path, res):
        print '----------------BEGIN------------------'
        print 'nums =', nums
        if not nums:
            res.append(path)
            print 'res append =', res
        for i in xrange(len(nums)):
            print 'i = %d' % i
            print 'nums[:%d] =' % i, nums[:i], '+ nums[%d:] =' % (i + 1), nums[i+1:]
            print 'path =', path, '+ nums[%d] =' % i, nums[i]
            print 'res =', res
            self.dfs(nums[:i] + nums[i+1:], path+[nums[i]], res)
            print '----------------END-----------------\n'

output

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
In [432]: s = Solution(); print s.permute([1, 2])
----------------BEGIN------------------
nums = [1, 2]
i = 0
nums[:0] = [] + nums[1:] = [2]
path = [] + nums[0] = 1
res = []
----------------BEGIN------------------
nums = [2]
i = 0
nums[:0] = [] + nums[1:] = []
path = [1] + nums[0] = 2
res = []
----------------BEGIN------------------
nums = []
res append = [[1, 2]]
----------------END-----------------
----------------END-----------------
i = 1
nums[:1] = [1] + nums[2:] = []
path = [] + nums[1] = 2
res = [[1, 2]]
----------------BEGIN------------------
nums = [1]
i = 0
nums[:0] = [] + nums[1:] = []
path = [2] + nums[0] = 1
res = [[1, 2]]
----------------BEGIN------------------
nums = []
res append = [[1, 2], [2, 1]]
----------------END-----------------
----------------END-----------------
[[1, 2], [2, 1]]

Recursive, insert first number anywhere

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        for i in range(len(nums)):
            for p in self.permute(nums[1:]):
                res.append(p[:i] + [nums[0]] + p[i:])
        return nums and res or [[]]

Recursive, take any number as first

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        for i, n in enumerate(nums):
            for p in self.permute(nums[:i] + nums[i+1:]):
                res.append([n] + p)
        return res or [[]]

Reduce, insert next number anywhere

1
2
3
4
5
6
7
8
9
class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        return reduce(lambda P, n: [p[:i] + [n] + p[i:]
                                for p in P for i in range(len(p)+1)],
                  nums, [[]])

One-Liners in Python

leet code

leetcode

Generate Parentheses

Generate Parentheses

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def generateParenthesis(self, n, open=0):
        """
        :type n: int
        :rtype: List[str]
        """
        if n == 0: return [')'*open]
        if open == 0:
            return ['(' + x for x in self.generateParenthesis(n - 1, 1)]
        else:
            return [')' + x for x in self.generateParenthesis(n, open - 1)] + ['(' + x for x in self.generateParenthesis(n - 1, open + 1)]
1
2
3
4
5
6
7
example for n = 2
else left branch:
( -> () -> ()( -> ()()
else right branch:
( -> (( -> (())

leet code

leetcode

Top K Frequent Elements

Top K Frequent Elements

  • You may assume k is always valid, 1 ≤ k ≤ number of unique elements.

  • Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        ret = {}
        res = []
        for x in nums:  # O(n)
            if x not in ret:
                ret[x] = 1
            else:
                ret[x] += 1
        for key, value in sorted(ret.iteritems(), key=lambda (k,v): (v,k), reverse=True)[:k]:  # O(n log n)
            res.append(key)
        return res

O(n) + O(n log n) = O(n log n)

result

1
2
3
4
5
6
7
8
In [221]: nums = [1,1,1,2,2,3]
In [222]: k = 2
In [241]: s = Solution()
In [242]: s.topKFrequent(nums, k)
Out[242]: [1, 2]

How to sort a Python dict (dictionary) by keys or values

『Python CoolBook：heapq』数据结构和算法_heapq堆队列算法&容器排序

Python使用heapq实现小顶堆（TopK大）、大顶堆（BtmK小）

使用heapq构建最小堆和最大堆

leet code

leetcode

Sum of Two Integers

Sum of Two Integers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def getSum(self, a, b):
        """
        :type a: int
        :type b: int
        :rtype: int
        """
        # 32 bits integer max
        MAX = 0x7FFFFFFF
        # 32 bits interger min
        MIN = 0x80000000
        # mask to get last 32 bits
        mask = 0xFFFFFFFF
        
        while b != 0:
            # ^ get different bits and & gets double 1s, << moves carry
            a, b = (a ^ b) & mask, ((a & b) << 1) & mask
        
        # if a is negative, get a's 32 bits complement positive first
        # then get 32-bit positive's Python complement negative
        return a if a <= MAX else ~(a ^ mask)

~ x

Returns the complement of x - the number you get by switching each 1 for a 0 and each 0 for a 1. This is the same as -x - 1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
In [204]: mask = 0xFFFFFFFF
In [205]: a = -1
In [206]: bin(a ^ mask)
Out[206]: '-0b100000000000000000000000000000000'
In [207]: bin(~(a ^ mask))
Out[207]: '0b11111111111111111111111111111111'
In [208]: (~(a ^ mask))
Out[208]: 4294967295
In [209]: 2 ** 32
Out[209]: 4294967296

负数的二进制表示方法

BitwiseOperators

leet code

leetcode

Product of Array Except Self

Product of Array Except Self

1.without division

2.O(n)

3.with constant space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        ret = []
        n = len(nums)
        
        tmp = 1
        for i in range(0, n):
            ret.append(tmp)
            tmp *= nums[i]
        
        tmp = 1
        for i in range(n - 1, -1, -1):
            ret[i] *= tmp
            tmp *= nums[i]
        
        return ret

result

1
2
In [53]: s = Solution(); s.productExceptSelf([1, 2, 3, 4])
Out[53]: [24, 12, 8, 6]

leet code