leetcode

Sort Colors

Sort Colors

Nice Version - 36ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        i, j = 0, 0
        for k in range(len(nums)):
            v = nums[k]
            #print('i=%d, j=%d, v=%d--------' % (i, j, v))
            nums[k] = 2
            #print(nums)
            if v < 2:
                nums[j] = 1
                j += 1
            #print(nums)
            if v == 0:
                nums[i] = 0
                i += 1
            #print(nums)
            #print('i=%d, j=%d-------------\n' % (i, j))

test code

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
In [27]: a = [2,0,2,1,1,0]
In [28]: s = Solution(); s.sortColors(a)
i=0, j=0, v=2--------
[2, 0, 2, 1, 1, 0]
[2, 0, 2, 1, 1, 0]
[2, 0, 2, 1, 1, 0]
i=0, j=0-------------
i=0, j=0, v=0--------
[2, 2, 2, 1, 1, 0]
[1, 2, 2, 1, 1, 0]
[0, 2, 2, 1, 1, 0]
i=1, j=1-------------
i=1, j=1, v=2--------
[0, 2, 2, 1, 1, 0]
[0, 2, 2, 1, 1, 0]
[0, 2, 2, 1, 1, 0]
i=1, j=1-------------
i=1, j=1, v=1--------
[0, 2, 2, 2, 1, 0]
[0, 1, 2, 2, 1, 0]
[0, 1, 2, 2, 1, 0]
i=1, j=2-------------
i=1, j=2, v=1--------
[0, 1, 2, 2, 2, 0]
[0, 1, 1, 2, 2, 0]
[0, 1, 1, 2, 2, 0]
i=1, j=3-------------
i=1, j=3, v=0--------
[0, 1, 1, 2, 2, 2]
[0, 1, 1, 1, 2, 2]
[0, 0, 1, 1, 2, 2]
i=2, j=4-------------
In [29]: a
Out[29]: [0, 0, 1, 1, 2, 2]

leet code

leetcode

Game of Life

Game of Life

another solution - 36ms

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
class Solution:
    def gameOfLife(self, board):
        """
        :type board: List[List[int]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        if not board or not board[0]: return
        m, n = len(board), len(board[0])
        for i, row in enumerate(board):
            for j, ele in enumerate(row):
                count = 0
                for a in range(max(0, i - 1), min(i + 2, m)):
                    for b in range(max(0, j - 1), min(j + 2, n)):
                        # skip i, j itself, (a, b) is (i, j)'s eight neighbors
                        # should count current_alive(1) and formerly_alive(2)
                        if (a, b) != (i, j) and 1 <= board[a][b] <= 2:
                            count += 1
                if board[i][j] == 0:
                    if count == 3:
                        board[i][j] = 3
                else:
                    if count < 2 or count > 3:
                        board[i][j] = 2
        for i in range(m):
            for j in range(n):
                if board[i][j] == 2:
                    board[i][j] = 0
                elif board[i][j] == 3:
                    board[i][j] = 1

test code

1
2
3
4
5
6
In [16]: in_arr = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
In [17]: s = Solution(); s.gameOfLife(in_arr)
In [18]: in_arr
Out[18]: [[0, 0, 0], [1, 0, 1], [0, 1, 1], [0, 1, 0]]

leet code

康威生命游戏

leetcode

Insert Delete GetRandom O(1)

Insert Delete GetRandom O(1)

dict+list Version - 80 ms

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
import random
class RandomizedSet(object):
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.data = []
        self.idxs = {}
        self.cnt = 0
    def insert(self, val):
        """
        Inserts a value to the set. Returns true if the set did not already contain the specified element.
        :type val: int
        :rtype: bool
        """
        if val in self.idxs:
            return False
        else:
            self.data.append(val)
            self.idxs[val] = self.cnt
            self.cnt += 1
            return True
    def remove(self, val):
        """
        Removes a value from the set. Returns true if the set contained the specified element.
        :type val: int
        :rtype: bool
        """
        if val in self.idxs:
            idx, value = self.idxs[val], self.data[-1]
            self.idxs[value], self.data[idx] = idx, value
            self.data.pop()
            self.idxs.pop(val, 0)
            self.cnt -= 1
            return True
        else:
            return False
    def getRandom(self):
        """
        Get a random element from the set.
        :rtype: int
        """
        return random.choice(self.data)
# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()

leet code

leetcode

Maximum Subarray

Maximum Subarray

one solution - 24ms

1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        for i in range(1, len(nums)):
            if nums[i-1] > 0:
                nums[i] += nums[i-1]
        return max(nums)

another solution - 44ms

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums: return 0
        cur_sum = max_sum = nums[0]
        for num in nums[1:]:
            cur_sum = max(num, cur_sum + num)
            max_sum = max(max_sum, cur_sum)
        return max_sum

test code

1
2
3
4
In [470]: s = Solution(); t = s.maxSubArray([-2,1,-3,4,-1,2,1,-5,4])
In [471]: t
Out[471]: 6

leet code

leetcode

Group Anagrams

Group Anagrams

dict solution - 172ms

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        ret = {}
        for s in sorted(strs):
            key = tuple(sorted(s))
            ret[key] = ret.get(key, []) + [s]
        return ret.values()

defaultdict solution - 128ms

1
2
3
4
5
6
7
import collections
class Solution(object):
	def groupAnagrams(self, strs):
	    groups = collections.defaultdict(list)
	    for s in strs:
	        groups[tuple(sorted(s))].append(s)
	    return map(sorted, groups.values())

itertools solution - 156ms

1
2
3
4
import itertools
class Solution(object):
	def groupAnagrams(self, strs):
	    return [sorted(g) for _, g in itertools.groupby(sorted(strs, key=sorted), sorted)]

test code

1
2
3
4
In [460]: s = Solution(); t = s.groupAnagrams(["eat","tea","tan","ate","nat","bat"])
In [461]: t
Out[461]: [['bat'], ['ate', 'eat', 'tea'], ['nat', 'tan']]

leet code

Python中collections.defaultdict()使用

理解 Python 语言中的 defaultdict