leetcode 20. 有效的括号

发表于 2021-06-23 分类于 leetcode 阅读次数：

解题思路

使用 “栈” 模拟即可

代码

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for char in s:
            if not stack:
                stack.append(char)
                continue

            if stack[-1] == '(' and char == ')':
                stack.pop()
            elif stack[-1] == '{' and char == '}':
                stack.pop()
            elif stack[-1] == '[' and char == ']':
                stack.pop()
            else:
                stack.append(char)

        return not stack

leetcode 322. 零钱兑换

发表于 2021-06-20 分类于 leetcode 阅读次数：

解题思路

状态：
dp[i] = 组成金额i需要的最小金币数

方程：
dp[i] = min(dp[i - coin[x]]) + 1
0<=x<len(coins)

代码

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float('INF')] * (amount + 1)
        dp[0] = 0
        for i in range(1, amount + 1):
            for coin in coins:
                if coin > i:
                    continue
                dp[i] = min(dp[i], dp[i-coin] + 1)
        return dp[amount] if dp[amount] != float('INF') else -1

leetcode 277. 搜寻名人

发表于 2021-06-14 分类于 leetcode 阅读次数：

解题思路

“名人” 定义：
其他所有 n - 1 个人都认识他/她，而他/她并不认识其他任何人

若a不认识b => b一定不是名人，a可能是名人
若a认识c => a一定不是名人，c可能不是名人

时间复杂度

O(n)

调用 knows 的最大次数为 3 * n

代码

# The knows API is already defined for you.
# return a bool, whether a knows b
# def knows(a: int, b: int) -> bool:

class Solution:
    def findCelebrity(self, n: int) -> int:
        candidate = 0

        for i in range(n):
            if knows(candidate, i):
                candidate = i
        
        for i in range(candidate):
            if knows(candidate, i) or not knows(i, candidate):
                return -1
        
        for i in range(candidate+1, n):
            if not knows(i, candidate):
                return -1
        
        return candidate

leetcode 98. 验证二叉搜索树

发表于 2021-06-05 分类于 leetcode 阅读次数：

解题思路

判断每个节点的值是否在 (l, r) 范围内（开区间）

代码

# 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 isValidBST(self, root: TreeNode) -> bool:
        return self.solve(root)
    
    def solve(self, root, lower=-float('INF'), upper=float('INF')):
        if not root:
            return True
        
        if not (lower < root.val < upper):
            return False

        if not self.solve(root.left, lower, root.val):
            return False

        if not self.solve(root.right, root.val, upper):
            return False
        
        return True

leetcode 62. 不同路径

发表于 2021-06-05 更新于 2021-06-06 分类于 leetcode 阅读次数：

解题思路

定义状态：
dp[i][j] := 从 (0, 0) 走到 (i, j) 不同的路径数目

动态规划转移方程：
dp[i][j] = dp[i][j-1] + dp[i-1][j]

状态压缩：
dp[j] += dp[j-1]

代码

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [0 for i in range(n)]
        dp[0] = 1

        for row in range(m):
            for col in range(n):
                if col == 0:
                    continue
                dp[col] += dp[col-1]
        
        return dp[n-1]

leetcode 56. 合并区间

发表于 2021-06-03 更新于 2021-06-05 分类于 leetcode 阅读次数：

解题思路

遍历数组，比较元素区间即可

代码

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        ret = []
        new_intervals = sorted(intervals, key=lambda x: x[0])
        left, right = new_intervals[0]

        for a, b in new_intervals[1:]:
            if right >= b:
                continue

            if right >= a:
                right = b
            else:
                ret.append([left, right])
                left = a
                right = b
        
        ret.append([left, right])
        return ret

【工厂模式】抽象工厂

发表于 2021-05-30 分类于设计模式阅读次数：

问题

一个对象的创建，依赖于多个不同的工厂方法，如何使这个对象的创建更容易呢？

工厂方法

将多个工厂方法组合在一起，作为一个抽象工厂

Demo

背景&&需求

根据用户年龄，决定玩儿童游戏（青蛙吃虫子），还是成人游戏（巫师对抗怪物）

代码

class Frog:
    def __init__(self, name):
        self.name = name
    
    def __str__(self):
        return self.name

    def interact_with(self, obstacle):
        act = obstacle.action()
        msg = f'{self} the Frog encounters {obstacle} and {act}!'
        print(msg)
    
class Bug:
    def __str__(self):
        return 'a bug'
    
    def action(self):
        return 'eats it'

# 抽象工厂（创建青蛙、虫子）
class FrogWorld:
    def __init__(self, name):
        print(self)
        self.player_name = name
    
    def __str__(self):
        return '------ Frog World ------'

    # 工厂方法
    def make_character(self):
        return Frog(self.player_name)

    # 工厂方法
    def make_obstacle(self):
        return Bug()


class Wizard:
    def __init__(self, name):
        self.name = name
    
    def __str__(self):
        return self.name

    def interact_with(self, obstacle):
        act = obstacle.action()
        msg = f'{self} the Wizard battles against {obstacle} and {act}!'
        print(msg)

class Ork:
    def __str__(self):
        return 'an evil ork'
    
    def action(self):
        return 'kills it'


# 抽象工厂（创建巫师、怪物）
class WizardWorld:
    def __init__(self, name):
        print(self)
        self.player_name = name
    
    def __str__(self):
        return '------ Wizard World ------'

    # 工厂方法
    def make_character(self):
        return Wizard(self.player_name)

    # 工厂方法
    def make_obstacle(self):
        return Ork()


class Game:
    def __init__(self, factory):
        self.hero = factory.make_character()
        self.obstacle = factory.make_obstacle()
    
    def play(self):
        self.hero.interact_with(self.obstacle)

if __name__=="__main__":
    name = 'user'
    age = int(input('please input age: '))
    game = age < 18 and FrogWorld or WizardWorld
    Game(game(name)).play()

输出

please input age: 18
—— Wizard World ——
user the Wizard battles against an evil ork and kills it!

please input age: 10
—— Frog World ——
user the Frog encounters a bug and eats it!

leetcode 297. 二叉树的序列化与反序列化

发表于 2021-05-29 分类于 leetcode 阅读次数：

思路

前序遍历序列化二叉树为字符串
前序遍历反序列化字符串为二叉树
注意叶子节点的处理

时间复杂度

O(n) n为节点数

空间复杂度

O(n) n为节点数

代码

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        if not root:
            return 'None'
        return f'{root.val},{self.serialize(root.left)},{self.serialize(root.right)}'
        

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        def build_tree(node_list):
            if not node_list:
                return

            node = node_list.pop(0)
            if node == 'None':
                return
                
            root = TreeNode(node)
            root.left = build_tree(node_list)
            root.right = build_tree(node_list)
            return root

        return build_tree(data.split(','))
        

# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))

leetcode 1822. 数组元素积的符号

发表于 2021-05-26 分类于 leetcode 阅读次数：

解题思路

数组中存在0，结果为0。否则，奇数个负数，结果为-1；偶数个负数结果为1

时间复杂度

O(n)

空间复杂度

O(1)

代码

class Solution:
    def arraySign(self, nums: List[int]) -> int:
        sign = 1
        is_zero = False

        for num in nums:
            if num == 0:
                is_zero = True
                break
            if num < 0:
                sign *= -1

        return not is_zero and sign or 0

【工厂模式】工厂方法

发表于 2021-05-21 更新于 2021-07-17 分类于设计模式阅读次数：

问题

创建对象的代码在许多不同的地方，导致难以跟踪应用中创建的对象

工厂方法

基于单一的函数创建对象：根据传入参数，创建出想要的对象。
（外部不需要知道对象的实现细节）

Demo

背景&&需求

XXX数据存储于XML文件和JSON文件中，目前需要获取XXX数据

代码

import os
import json
import xml.etree.ElementTree as etree

class JSONDataExtractor:
    def __init__(self, file_path):
        self.data = dict()
        with open(file_path, mode='r', encoding='utf-8') as f:
            self.data = json.load(f)
        
    @property
    def parsed_data(self):
        return self.data

    
class XMLDataExtractor:
    def __init__(self, file_path):
        self.tree = etree.parse(file_path)

    @property
    def parsed_data(self):
        return self.tree


def data_extractor_factory(file_path):
    if file_path.endswith('json'):
        extractor = JSONDataExtractor
    elif file_path.endswith('xml'):
        extractor = XMLDataExtractor
    else:
        raise ValueError(f'Cannot extract data from {file_path}')
    return extractor(file_path)


def extract_data(file_path):
    factory_obj = None
    try:
        factory_obj = data_extractor_factory(file_path)
    except ValueError as e:
        print(e)
    return factory_obj


if __name__=="__main__":
    root_path = '/20210523'
    # 获取存储在json中的数据
    factory = extract_data(os.path.join(root_path, 'test.json'))
    print(f'JSON Data={factory and factory.parsed_data}\n')

    # 获取存储在xml中的数据
    factory = extract_data(os.path.join(root_path, 'test.xml'))
    print(f'XML Data={factory and factory.parsed_data}\n')

    # 获取存储在ini中的数据，会报异常
    factory = extract_data(os.path.join(root_path, 'test.ini'))
    print(f'Abnormal Data={factory and factory.parsed_data}')

输出

JSON Data=[{‘title’: ‘Ha’}]

XML Data=<xml.etree.ElementTree.ElementTree object at 0x7fcd15d79a60>

Cannot extract data from 20210523/test.ini
Abnormal Data=None