Jianming Shi

JianmingS@outlook.com

0%

发表于 更新于 分类于 阅读次数：

问题

需要克隆一个对象

原型模式

创建对象的克隆（例如：python中的copy）

Demo

背景 && 需求

克隆对象

代码

1
2
3
4
5
6
7
import copy

def demo():
    info1 = dict(name='123', books=['book1', 'book2'])
    info2 = copy.deepcopy(info1)
    print(f'info1: {id(info1)}, name: {id(info1["name"])}, books: {id(info1["books"])}')
    print(f'info2: {id(info2)}, name: {id(info2["name"])}, books: {id(info2["books"])}')

输出

info1: 4540133696, name: 4538957168, books: 4540422336
info2: 4538883840, name: 4538957168, books: 4540493376

发表于 分类于 阅读次数：

解题思路

按层遍历树即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return root

        layer_nodes = [root]
        while layer_nodes:
            next_layer_nodes = []
            layer_nodes_len = len(layer_nodes)
            for i, node in enumerate(layer_nodes):
                if i == layer_nodes_len - 1:
                    node.next = None
                else:
                    node.next = layer_nodes[i+1]
                if node.left:
                    next_layer_nodes.append(node.left)
                if node.right:
                    next_layer_nodes.append(node.right)
            layer_nodes = next_layer_nodes
            
        return root

发表于 更新于 分类于 阅读次数：

解题思路

深搜，生成括号

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def __init__(self):
        self.n = None
        self.ans = []

    def generateParenthesis(self, n: int) -> List[str]:
        self.n = n
        self.ans = []
        self.solve('', 0, 0)
        return self.ans

    def solve(self, s, left, right):
        if len(s) == self.n*2:
            self.ans.append(s)
            return

        if left < self.n:
            self.solve(s+'(', left+1, right)

        if right < left:
            self.solve(s+')', left, right+1)

发表于 更新于 分类于 阅读次数：

问题

1、创建的对象复杂，需要由多个部分组成，且这些这些部分需要按照特定顺序完成
2、希望构造与表示解耦

建造者模式

可以创建一个由多个部分（这些部分按特定顺序完成）组成的对象

Demo

背景&&需求

披萨订购应用程序
支持订购2种披萨：Margarita披萨、CreamyBacon披萨
制作披萨需4个步骤：1、准备面团；2、加调味汁；3、加配料；4、烤

代码

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
# !/usr/bin/python3
# -*- coding: utf-8 -*-
from enum import Enum
import time


class PizzaProgress(Enum):
    queued = 1
    preparation = 2
    baking = 3
    ready = 4


class PizzaDough(Enum):
    thin = 1  # 薄的
    thick = 2  # 厚的


class PizzaSauce(Enum):
    tomato = 1
    creme_fraiche = 2


class PizzaTopping(Enum):
    mozzarella = 1  # 奶酪
    ham = 2  # 火腿
    mushrooms = 3  # 蘑菇
    double_mozzarella = 4
    oregano = 5


class Pizza:
    def __init__(self, name):
        self.name = name
        self.dough = None  # 面团
        self.sauce = None  # 调味汁
        self.topping = []  # 配料

    def __str__(self):
        return self.name


class MargaritaBuilder:
    def __init__(self):
        self.pizza = Pizza('margarita')
        self.progress = PizzaProgress.queued
        self.baking_time = 1  # 烤1s

    def prepare_dough(self):
        print('prepare dough for margarita')
        self.progress = PizzaProgress.preparation
        self.pizza.dough = PizzaDough.thin
        print('done with dough')

    def add_sauce(self):
        print('add sauce to margarita')
        self.pizza.sauce = PizzaSauce.tomato
        print('done with sauce')

    def add_topping(self):
        print('add topping to margarita')
        topping_items = [
            PizzaTopping.double_mozzarella,
            PizzaTopping.oregano
        ]
        self.pizza.topping.append([item for item in topping_items])
        print('done with topping')

    def bake(self):
        self.progress = PizzaProgress.baking
        print('baking margarita...')
        time.sleep(self.baking_time)
        self.progress = PizzaProgress.ready
        print('margarita ready')


class CreamyBaconBuilder:
    def __init__(self):
        self.pizza = Pizza('creamy bacon')
        self.progress = PizzaProgress.queued
        self.baking_time = 2  # 烤2s

    def prepare_dough(self):
        print('prepare dough for creamy bacon')
        self.progress = PizzaProgress.preparation
        self.pizza.dough = PizzaDough.thick
        print('done with dough')

    def add_sauce(self):
        print('add sauce to creamy bacon')
        self.pizza.sauce = PizzaSauce.creme_fraiche
        print('done with sauce')

    def add_topping(self):
        print('add topping to creamy bacon')
        topping_items = [
            PizzaTopping.mozzarella,
            PizzaTopping.ham
        ]
        self.pizza.topping.append([item for item in topping_items])
        print('done with topping')

    def bake(self):
        self.progress = PizzaProgress.baking
        print('baking creamy bacon...')
        time.sleep(self.baking_time)
        self.progress = PizzaProgress.ready
        print('creamy bacon ready')


class Waiter:
    def __init__(self):
        self.builder = None

    def construct_pizza(self, builder):
        self.builder = builder
        steps = [
            builder.prepare_dough,
            builder.add_sauce,
            builder.add_topping,
            builder.bake
        ]
        [step() for step in steps]

    @property
    def pizza(self):
        return self.builder.pizza


if __name__ == '__main__':
    waiter = Waiter()
    waiter.construct_pizza(MargaritaBuilder())
    pizza = waiter.pizza
    print(f'Enjoy {pizza}!')

    print('-----------------------')

    waiter.construct_pizza(CreamyBaconBuilder())
    pizza = waiter.pizza
    print(f'Enjoy {pizza}!')

输出

prepare dough for margarita
done with dough
add sauce to margarita
done with sauce
add topping to margarita
done with topping
baking margarita…
margarita ready
Enjoy margarita!

prepare dough for creamy bacon
done with dough
add sauce to creamy bacon
done with sauce
add topping to creamy bacon
done with topping
baking creamy bacon…
creamy bacon ready
Enjoy creamy bacon!

发表于 分类于 阅读次数：

解题思路

1、将会议时间数组排序：
按start从小到大排序，当start相同时，按end从小到大排序
2、根据会议时间顺序依次安排房间：
记录每个房间释放的时间，若即将安排的会议start早于最小的释放时间，则需要新房间，否则更新房间的释放时间

贪心关键点：将 “即将安排的会议start” 与 “最小的释放时间” 做比较，尽可能避免冲突

关于贪心，可参考：https://www.jianshu.com/p/ab89df9759c8

时间复杂度

O(N*logN) N：会议时间数组长度

详细分析：
1、python sorted时间复杂度：O(N*logN)

关于sorted时间复杂度，可参考：https://www.cnblogs.com/clement-jiao/p/9243066.html

2、最坏情况下N个会议均冲突，此时heappop[0]时间复杂度：O(1)，heappush时间复杂度：O(logN)，故总的时间复杂度为O(N*logN)

关于heapq操作的时间复杂度，可参考：https://www.coder.work/article/97172

空间复杂度

O(N) N：会议时间数组长度

详细分析
1、最坏情况下N个会议均冲突，heap_queue需要存储N个数据

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        heap_queue = []

        for start, end in sorted(intervals, key=lambda item: (item[0], item[1])):
            if not heap_queue:
                heapq.heappush(heap_queue, end)
                continue
            if start >= heap_queue[0]:
                heapq.heappop(heap_queue)
            heapq.heappush(heap_queue, end)
            
        return len(heap_queue)

发表于 分类于 阅读次数：

解题思路

“二分查找”
注意考虑 3 种情况：
1、nums[l] < nums[mid]
2、nums[l] > nums[mid]
3、nums[l] == nums[mid]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l = 0
        r = len(nums) - 1
        while l <= r:
            mid = (l+r) >> 1
            if target == nums[mid]:
                return mid
            if nums[l] <= nums[mid]:
                if nums[l] <= target < nums[mid]:
                    r = mid - 1
                else:
                    l = mid + 1
            else:
                if nums[mid] < target <= nums[r]:
                    l = mid + 1
                else:
                    r = mid - 1
        return -1

发表于 更新于 分类于 阅读次数：

解题思路

解法1

超大数组

预先开出max(key)的空间，确保每个key都有一个单独的索引

解法2

拉链数组

超大数组会占用的空间太大，可以将输入的数据分桶，每个桶的数据动态增长

分桶方法

推荐使用质数取余进行分桶

使用质数取余分桶的原因

只要输入的数据足够随机，是否用质数取模无所谓的；
但是实际输入的数据一般是有规律的，如果使用合数取余，当合数和数据存在非1的约数，
那数据只会被分桶到约数的倍数，违背了尽量使各个桶之间的元素数近似相等的原则。
参考：
https://www.zhihu.com/question/20806796/answer/21359160
https://blog.csdn.net/xp178171640/article/details/102929544

代码

解法1

1
2
3
4
5
6
7
8
9
10
11
12
13
class MyHashMap:

    def __init__(self):
        self.hash_map = [-1 for _ in range(10**6 + 10)]

    def put(self, key: int, value: int) -> None:
        self.hash_map[key] = value

    def get(self, key: int) -> int:
        return self.hash_map[key]

    def remove(self, key: int) -> None:
        self.hash_map[key] = -1

解法2

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
class MyHashMap:

    def __init__(self):
        self.bucket_size = 1009 # 质数
        self.hash_map = [[] for _ in range(self.bucket_size)]
    
    def get_bucket_index(self, key):
        return key % self.bucket_size

    def put(self, key: int, value: int) -> None:
        bucket_index = self.get_bucket_index(key)
        for existed_map in self.hash_map[bucket_index]:
            if existed_map[0] == key:
                existed_map[1] = value
                return
        self.hash_map[bucket_index].append([key, value])
        
    def get(self, key: int) -> int:
        bucket_index = self.get_bucket_index(key)
        for existed_key, existed_val in self.hash_map[bucket_index]:
            if existed_key == key:
                return existed_val
        return -1

    def remove(self, key: int) -> None:
        bucket_index = self.get_bucket_index(key)
        for index, existed_map in enumerate(self.hash_map[bucket_index]):
            if existed_map[0] == key:
                self.hash_map[bucket_index].pop(index)
                return

发表于 分类于 阅读次数：

解题思路

解法1

深搜，即可生成字母的数字组合

解法2

利用python3内置函数，生成笛卡尔积

代码

解法1

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
class Solution:
    def __init__(self) -> None:
        self.num_chars_mapping = {
            2: ['a', 'b', 'c'],
            3: ['d', 'e', 'f'],
            4: ['g', 'h', 'i'],
            5: ['j', 'k', 'l'],
            6: ['m', 'n', 'o'],
            7: ['p', 'q', 'r', 's'],
            8: ['t', 'u', 'v'],
            9: ['w', 'x', 'y', 'z']
        }

    def letterCombinations(self, digits: str) -> List[str]:
        return [] if not digits else self.combinate(0, digits)

    def combinate(self, index, s, combinations=[]):
        if index >= len(s):
            return combinations

        chars = self.num_chars_mapping[int(s[index])]
        if index == 0:
            combinations = chars
        else:
            tmp = []
            for combination in combinations:
                for char in chars:
                    tmp.append(combination+char)
            combinations = tmp

        return self.combinate(index+1, s, combinations)

解法2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def __init__(self) -> None:
        self.num_chars_mapping = {
            2: ['a', 'b', 'c'],
            3: ['d', 'e', 'f'],
            4: ['g', 'h', 'i'],
            5: ['j', 'k', 'l'],
            6: ['m', 'n', 'o'],
            7: ['p', 'q', 'r', 's'],
            8: ['t', 'u', 'v'],
            9: ['w', 'x', 'y', 'z']
        }

    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        groups = [self.num_chars_mapping[int(digit)] for digit in digits]
        return [''.join(item) for item in itertools.product(*groups)]

发表于 分类于 阅读次数：

解题思路

模拟 “整数” 转换为 “英文”
注意：100 转换结果为 One Hundred

代码

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
class Solution:
    def numberToWords(self, num: int) -> str:
        if num == 0:
            return 'Zero'
        
        result = ''

        billion = num // 1000000000
        million = (num % 1000000000) // 1000000
        thousand = (num % 1000000) // 1000
        rest = num % 1000

        if billion:
            result += self.three(billion) + ' Billion'
        if million:
            result += result and ' ' or ''
            result += self.three(million) + ' Million'
        if thousand:
            result += result and ' ' or ''
            result += self.three(thousand) + ' Thousand'
        if rest:
            result += result and ' ' or ''
            result += self.three(rest)
        
        return result

    def three(self, num):
        hundred = num // 100
        rest = num % 100
        if hundred and rest:
            return self.one(hundred) + ' Hundred ' + self.two(rest)
        if not hundred and rest:
            return self.two(rest)
        if hundred and not rest:
            return self.one(hundred) + ' Hundred'
        
    def one(self, num):
        switcher = {
            1: 'One',
            2: 'Two',
            3: 'Three',
            4: 'Four',
            5: 'Five',
            6: 'Six',
            7: 'Seven',
            8: 'Eight',
            9: 'Nine'
        }
        return switcher.get(num)

    def two(self, num):
        if num < 10:
            return self.one(num)
        if num < 20:
            return self.two_less_20(num)
        else:
            tenner = num // 10
            rest = num % 10
            return rest and self.ten(tenner) + ' ' + self.one(rest) or self.ten(tenner)
    
    def two_less_20(self, num):
        switcher = {
            10: 'Ten',
            11: 'Eleven',
            12: 'Twelve',
            13: 'Thirteen',
            14: 'Fourteen',
            15: 'Fifteen',
            16: 'Sixteen',
            17: 'Seventeen',
            18: 'Eighteen',
            19: 'Nineteen'
        }
        return switcher.get(num)

    def ten(self, num):
        switcher = {
            2: 'Twenty',
            3: 'Thirty',
            4: 'Forty',
            5: 'Fifty',
            6: 'Sixty',
            7: 'Seventy',
            8: 'Eighty',
            9: 'Ninety'
        }
        return switcher.get(num)

发表于 分类于 阅读次数：

解题思路

按层遍历二叉树即可

代码

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        ret = []
        if not root:
            return ret
        
        is_from_left = True
        queue = collections.deque()
        queue.append(root)
        while queue:
            tmp_queue = collections.deque()
            val_list = []

            while queue:
                node = queue.popleft()
                if is_from_left:
                    val_list.append(node.val)
                else:
                    val_list.insert(0, node.val)

                if node.left:
                    tmp_queue.append(node.left)
                if node.right:
                    tmp_queue.append(node.right)

            ret.append(val_list)
            is_from_left = not is_from_left
            queue = tmp_queue
        return ret