KK's blog

Amazon Prime Free Trial

This Prime Day, save up to 70% on speakers, smart TVs, smart watches and more!

Blink Outdoor Camera - Early Prime Day Deals

Ads by Amazon

LeetCode 921 Minimum Add to Make Parentheses Valid

Posted on 2022-03-16 Edited on 2026-06-03 Disqus:

LeetCode

<div>

A parentheses string is valid if and only if:

It is the empty string,
It can be written as AB (A concatenated with B), where A and B are valid strings, or
It can be written as (A), where A is a valid string.

You are given a parentheses string s. In one move, you can insert a parenthesis at any position of the string.

For example, if s = "()))", you can insert an opening parenthesis to be "(**(**)))" or a closing parenthesis to be "())**)**)".

Return the minimum number of moves required to make s valid.

Example 1:

<pre>Input: s = "())" Output: 1 </pre>

Example 2:

<pre>Input: s = "(((" Output: 3 </pre>

Constraints:

1 <= s.length <= 1000
s[i] is either '(' or ')'.

</div>

题目大意：

最小加括号数使得配对

Stack解题思路(推荐)：

跟Leetcode 1249一样。括号题优先考虑用Stack。此题将下标存于stack中，stack留下的是不合法括号下标，也就是需要删除的

LeetCode 1249 Minimum Remove to Make Valid Parentheses 求一个最优解 Medium, Stack LeetCode 921 Minimum Add to Make Parentheses Valid 求一个最优解 Medium, Stack LeetCode 301 Remove Invalid Parentheses 求所有最优解 Hard，此题答案包含上题, BFS

解题步骤：

注意事项：

Python代码：

def minAddToMakeValid(self, s: str) -> int:
	stack, res = [], ''
	for i in range(len(s)):
		if s[i] == '(':
			stack.append(i)
		elif stack and s[stack[-1]] == '(' and s[i] == ')':  # remember
			stack.pop()
		elif s[i] == ')':
			stack.append(i)
	return len(stack)

算法分析：

时间复杂度为O(n)，空间复杂度O(n)

统计算法II解题思路：

类似于Leetcode 032 Longest Valid Parentheses的统计算法。用这两种情况来写即可： ()), )(. 若左括号数left出现负数，根据第一个规律，重设left，计入res

Python代码：

def minAddToMakeValid2(self, s: str) -> int:
	left, res = 0, 0
	for char in s:
		if char == '(':
			left += 1
		else:
			left -= 1
			if left < 0:
				res += 1
				left = 0
	return res + abs(left)

算法分析：

时间复杂度为O(n)，空间复杂度O(1)

LeetCode 588 Design In-Memory File System

Posted on 2022-03-15 Edited on 2026-06-03 Disqus:

LeetCode

<div>

Design a data structure that simulates an in-memory file system.

Implement the FileSystem class:

FileSystem() Initializes the object of the system.
List<String> ls(String path)
- If path is a file path, returns a list that only contains this file's name.
- If path is a directory path, returns the list of file and directory names in this directory.The answer should in lexicographic order.
void mkdir(String path) Makes a new directory according to the given path. The given directory path does not exist. If the middle directories in the path do not exist, you should create them as well.
void addContentToFile(String filePath, String content)
- If filePath does not exist, creates that file containing given content.
- If filePath already exists, appends the given content to original content.
String readContentFromFile(String filePath) Returns the content in the file at filePath.

Example 1:

<pre>Input ["FileSystem", "ls", "mkdir", "addContentToFile", "ls", "readContentFromFile"] [[], ["/"], ["/a/b/c"], ["/a/b/c/d", "hello"], ["/"], ["/a/b/c/d"]] Output [null, [], null, null, ["a"], "hello"]

Explanation FileSystem fileSystem = new FileSystem(); fileSystem.ls("/"); // return [] fileSystem.mkdir("/a/b/c"); fileSystem.addContentToFile("/a/b/c/d", "hello"); fileSystem.ls("/"); // return ["a"] fileSystem.readContentFromFile("/a/b/c/d"); // return "hello" </pre>

Constraints:

1 <= path.length, filePath.length <= 100
path and filePath are absolute paths which begin with '/' and do not end with '/' except that the path is just "/".
You can assume that all directory names and file names only contain lowercase letters, and the same names will not exist in the same directory.
You can assume that all operations will be passed valid parameters, and users will not attempt to retrieve file content or list a directory or file that does not exist.
1 <= content.length <= 50
At most 300 calls will be made to ls, mkdir, addContentToFile, and readContentFromFile.

</div>

题目大意：

设计文件系统

解题思路：

如数据库系统的B+树一样，用Trie

解题步骤：

N/A

注意事项：

TrieNode含children和files，都是dict，只能是目录节点。因为不知道最后一个路劲部分是文件还是目录，所以ls里面需要遍历直到倒数第二个节点，再判断是哪种情况。另一个种设计是采取is_file, content，既可以是目录节点也可以是文件节点，本文采取前者
ls:题目要求目录可以含目录和文件。两种情况：若是文件，返回[文件]含在一个list中；若是目录，返回它下面的目录+文件
ls:返回结果要排序
ls:输入path可以是/或/a/b，所以/要特殊化处理，只能是目录，所以只有一种情况：目录和文件
_dir而不是dir, path而不是filepath，注意变量要用同一个

Python代码：

class Solution(TestCases):

    def __init__(self):
        self.root = TrieNode()

    def ls(self, path: str) -> List[str]:  # req remember /a not /a/
        if path == '/':
            return sorted(list(self.root.children.keys()) + list(self.root.files.keys())) # remember

        dirs = path[1:].split('/')
        it = self._ls(dirs[:-1])
        if dirs[-1] in it.files:
            return [dirs[-1]]
        else: # return files if no dir, no mixed types in same dir
            return sorted(list(it.children[dirs[-1]].children.keys()) + list(it.children[dirs[-1]].files.keys()))

    def mkdir(self, path: str) -> None:
        path = path[1:]
        dirs = path.split('/') # [a,b,c]
        self._mkdir(dirs)

    def addContentToFile(self, filePath: str, content: str) -> None:
        filePath = filePath[1:]
        dirs = filePath.split('/') # [a,b,c]
        it = self._mkdir(dirs[:-1])
        filename = dirs[-1]
        if filename not in it.files:
            it.files[filename] = ''
        it.files[filename] += content

    def readContentFromFile(self, filePath: str) -> str:
        filePath = filePath[1:]
        dirs = filePath.split('/')  # [a,b,c]
        it = self._ls(dirs[:-1])
        return it.files[dirs[-1]]

    def _ls(self, dirs):
        it = self.root
        for _dir in dirs:
            it = it.children[_dir]
        return it

    def _mkdir(self, dirs):
        it = self.root
        for _dir in dirs:
            it = it.children[_dir]
        return it

class TrieNode:

    def __init__(self):
        self.children = collections.defaultdict(TrieNode)
        self.files = collections.defaultdict(str) # use dict coz filename can't be duplicate and faster for lookup

算法分析：

时间复杂度为O(n)，空间复杂度O(n), n为路径长度

LeetCode 706 Design HashMap

Posted on 2022-03-15 Edited on 2026-06-03 Disqus:

LeetCode

<div>

Design a HashMap without using any built-in hash table libraries.

Implement the MyHashMap class:

MyHashMap() initializes the object with an empty map.
void put(int key, int value) inserts a (key, value) pair into the HashMap. If the key already exists in the map, update the corresponding value.
int get(int key) returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
void remove(key) removes the key and its corresponding value if the map contains the mapping for the key.

Example 1:

<pre>Input ["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"] [[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]] Output [null, null, null, 1, -1, null, 1, null, -1]

Explanation MyHashMap myHashMap = new MyHashMap(); myHashMap.put(1, 1); // The map is now [[1,1]] myHashMap.put(2, 2); // The map is now [[1,1], [2,2]] myHashMap.get(1); // return 1, The map is now [[1,1], [2,2]] myHashMap.get(3); // return -1 (i.e., not found), The map is now [[1,1], [2,2]] myHashMap.put(2, 1); // The map is now [[1,1], [2,1]] (i.e., update the existing value) myHashMap.get(2); // return 1, The map is now [[1,1], [2,1]] myHashMap.remove(2); // remove the mapping for 2, The map is now [[1,1]] myHashMap.get(2); // return -1 (i.e., not found), The map is now [[1,1]] </pre>

Constraints:

0 <= key, value <= 10<sup>6</sup>
At most 10<sup>4</sup> calls will be made to put, get, and remove.

</div>

题目大意：

设计HashMap

LL解题思路(推荐)：

大学学到的方法，用Array实现，将key mod prime num找到index插入。难点在于冲突处理，这里用chaining方法，也就是LL

解题步骤：

N/A

注意事项：

迭代LL时候，每种方法put, get, remove都不同。put只能迭代到最后一个不能到None，因为要从尾部加入。 get正常一个个迭代。remove要从parent也就是it.next迭代因为要删除节点。

Python代码：

class MyHashMap(TestCases):

    def __init__(self):
        self.key_space = 997
        self.buckets = [ListNode(-1, -1) for _ in range(self.key_space)]

    def put(self, key: int, value: int) -> None:
        index = key % self.key_space
        it = self.buckets[index]
        while it:
            if it.key == key:
                it.val = value
                return
            if not it.next:
                break
            it = it.next
        it.next = ListNode(key, value)

    def get(self, key: int) -> int:
        index = key % self.key_space
        it = self.buckets[index]
        while it:
            if it.key == key:
                return it.val
            it = it.next
        return -1

    def remove(self, key: int) -> None:
        index = key % self.key_space
        it = self.buckets[index]
        while it.next:
            if it.next.key == key:
                tmp = it.next
                it.next, tmp.next = it.next.next, None
                return
            it = it.next


class ListNode:

    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.next = None

算法分析：

时间复杂度为O(k)，空间复杂度O(n), k为冲突数

数组算法II解题思路：

较容易实现，remove复杂度稍差，但是最差情况也是同上

Python代码：

class MyHashMap(TestCases):

    def __init__(self):
        self.key_space = 997
        self.buckets = [[] for _ in range(self.key_space)]

    def put(self, key: int, value: int) -> None:
        index = key % self.key_space
        for i, [_key, _val] in enumerate(self.buckets[index]):
            if _key == key:
                self.buckets[index][i] = [key, value]
                return
        self.buckets[index].append([key, value])

    def get(self, key: int) -> int:
        index = key % self.key_space
        for _key, _val in self.buckets[index]:
            if _key == key:
                return _val
        return -1

    def remove(self, key: int) -> None:
        index = key % self.key_space
        for i, [_key, _val] in enumerate(self.buckets[index]):
            if _key == key:
                self.buckets[index].pop(i)
                return

算法分析：

时间复杂度为O(k)，空间复杂度O(n), k为冲突数

LeetCode 432 All O one Data Structure

Posted on 2022-03-14 Edited on 2026-06-03 Disqus:

LeetCode

<div>

Design a data structure to store the strings' count with the ability to return the strings with minimum and maximum counts.

Implement the AllOne class:

AllOne() Initializes the object of the data structure.
inc(String key) Increments the count of the string key by 1. If key does not exist in the data structure, insert it with count 1.
dec(String key) Decrements the count of the string key by 1. If the count of key is 0 after the decrement, remove it from the data structure. It is guaranteed that key exists in the data structure before the decrement.
getMaxKey() Returns one of the keys with the maximal count. If no element exists, return an empty string "".
getMinKey() Returns one of the keys with the minimum count. If no element exists, return an empty string "".

Example 1:

<pre>Input ["AllOne", "inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey", "getMinKey"] [[], ["hello"], ["hello"], [], [], ["leet"], [], []] Output [null, null, null, "hello", "hello", null, "hello", "leet"]

Explanation AllOne allOne = new AllOne(); allOne.inc("hello"); allOne.inc("hello"); allOne.getMaxKey(); // return "hello" allOne.getMinKey(); // return "hello" allOne.inc("leet"); allOne.getMaxKey(); // return "hello" allOne.getMinKey(); // return "leet" </pre>

Constraints:

1 <= key.length <= 10
key consists of lowercase English letters.
It is guaranteed that for each call to dec, key is existing in the data structure.
At most 5 * 10<sup>4</sup> calls will be made to inc, dec, getMaxKey, and getMinKey.

</div>

题目大意：

设计数据结构，使其支持增加或减少一个单词的频数，最大或最小单词的频数。注意最小频数不能为0

解题思路：

这个频数有点似LRU的分层思路，加入self.max_freq, 其他操作都可以实现，但是dec操作不能达到O(1), 因为若某个最小频数单词从1变成0，需要检索频率到下一个有节点的层。
改进就是要将频率的的值连起来，所以参考LRU，map的key是频率，value是node，node中含有freq，形成一个环。而node含有该频率对应的单词set，inc/dec就是将单词移动另一个node中

解题步骤：

N/A

注意事项：

与LRU区别: map的key是频率，node含有频率和单词set，数据结构加入key_to_count。LL是从最大频率到最小频率
inc操作将节点从原频率node移到下一个频率node，若新node不存在，调用append_before. 然后从原频率node的单词set中删除该单词，若set为空，删除此node以及map中的entry
dec与inc类似，但要注意频率变成0的情况：不移到新的node，且从key_to_count中删除该单词

Python代码：

class AllOne(TestCases):

    def __init__(self):
        self.freq_to_node = {}
        self.head = ListNode(0)
        self.tail = ListNode(0)
        self.head.next, self.tail.prev = self.tail, self.head
        self.key_to_count = collections.defaultdict(int)

    def inc(self, key: str) -> None:
        count = self.key_to_count[key]
        old_node = self.freq_to_node[count] if count in self.freq_to_node else self.tail
        count += 1
        if count not in self.freq_to_node:
            self.freq_to_node[count] = self.append_before(old_node)
        new_node = self.freq_to_node[count]
        new_node.key_set.add(key)
        self.key_to_count[key] = count

        count -= 1
        if count in self.freq_to_node and key in self.freq_to_node[count].key_set:
            self.freq_to_node[count].key_set.remove(key)
            if len(self.freq_to_node[count].key_set) == 0:
                self.remove_node(self.freq_to_node[count])
                self.freq_to_node.pop(count) # remember

    def dec(self, key: str) -> None:
        count = self.key_to_count[key]
        old_node = self.freq_to_node[count] if count in self.freq_to_node else self.head
        count -= 1
        if count > 0: # remember
            if count not in self.freq_to_node:
                self.freq_to_node[count] = self.append_after(old_node)
            new_node = self.freq_to_node[count]
            new_node.key_set.add(key)
            self.key_to_count[key] = count
        else:
            self.key_to_count.pop(key)

        count += 1
        if count in self.freq_to_node and key in self.freq_to_node[count].key_set:
            self.freq_to_node[count].key_set.remove(key)
            if len(self.freq_to_node[count].key_set) == 0:
                self.remove_node(self.freq_to_node[count])
                self.freq_to_node.pop(count)

    def getMaxKey(self) -> str:
        node = self.head.next
        return '' if node == self.tail else next(iter(node.key_set))

    def getMinKey(self) -> str:
        node = self.tail.prev
        return '' if node == self.head else next(iter(node.key_set))

    def append_before(self, node):
        new_node = ListNode(node.freq + 1)
        predecessor, successor = node.prev, node
        predecessor.next, new_node.prev = new_node, predecessor
        new_node.next, successor.prev = successor, new_node
        return new_node

    def append_after(self, node):
        new_node = ListNode(node.freq - 1)
        predecessor, successor = node, node.next
        predecessor.next, new_node.prev = new_node, predecessor
        new_node.next, successor.prev = successor, new_node
        return new_node

    def remove_node(self, node):
        predecessor, successor = node.prev, node.next
        predecessor.next, successor.prev = successor, predecessor
        node.prev, node.next = None, None


class ListNode:
    def __init__(self, freq=0, next=None, prev=None):
        self.key_set = set()
        self.freq = freq
        self.next = next
        self.prev = prev

算法分析：

时间复杂度为O(1)，空间复杂度O(n)

DP

Posted on 2022-03-08 Edited on 2026-07-01 Disqus:

典型递归式
单序列或匹配型DP模板
数值到个数DP模板(最常考)
区间型DP模板
压缩空间
打印路径

典型递归式：

单序列型(与一个或多个前状态有关)
硬币个数(数值型)： dp[i] = min(dp[i], dp[i - j] + 1)
偷房子： dp[i] = max(dp[i-1], dp[i-2] + nums[i - 1])
LIS： dp[i] = max(dp[i], dp[j] + 1) 1 <= j < i
Work break： dp[i] |= dp[j] and s[j:i] in word_set, 0 <= j < i

坐标型DP(与上、左等两个前状态有关)

1	dp[n][m] = max{1, min(dp[n+1][m], dp[n][m+1]) - dungeon[n][m]}

匹配型(与上、左、左上等三个前状态有关)

1 2	正则： dp[i][j] = dp[i-1][j-1] && (p[j-1] == . \|\| s[i-1] == p[j-1]) OR ((dp[i-1][j] && (s[i-1] == p[j-2] \|\| p[j-2] == .)) \|\| dp[i][j-2]) && p[j-1] == *

区间型(与该区间内以k为划分的两个子区间有关)

1	dp[i][j] = max{dp[i][m] + nums[i]×nums[m]×nums[j] + dp[m][j]}, i < m < j

多状态型DP(DP有多个终止状态)

dp = dp     if s[i] = '0'
   = dp + 1 if s[i] = '1'
   
dp2 = min(dp2 + 1, dp + 1)     if s[i] = '0'
    = min(dp2, dp)             if s[i] = '1'

解题步骤：

DP五部曲

[初始化]dp数组n+1
dp初始值也就是基本条件
[实现]定义状态和递归式
[答案] 如dp[-1]
[优化]是否可以用滚动内存优化空间

单序列或匹配型DP模板

实现注意事项(5点)：

[多1][初始化]初始化矩阵，dp是原长度加1。因为令边界计算方便. 遍历从多少开始，取决于前状态多少个，若递归式含dp[i-1],从1开始，如果dp[i-2]就从2开始.数值型DP，如硬币个数DP长度是数值amount，不是数组长度。Python用dp = [[0 for _ in range(M)] for _ in range(N)], M为col数，再row数
[特殊初始值]是第一步的完善，若一维初始化dp0，若为矩阵，初始化dp[0][0]以及上和左边界。求个数dp[0] = 1, 求最值, dp[0] = 0因为递归式含+1
[多1]跳过初始值，i从1循环到len(dp)而不是len(s), 因为用了dp[0]占位。若不用占位法，就要用if语句判断第一位的边界。大部分递归式含i-1项，所以绝大部分从1开始，从什么开始取决于递归式，这也受第二步的影响
[少1]用到原数组s时候是s[i - 1]而不是s[i], 因为用了dp[0]占位。实现时候递归式和条件要合法，保证边界内，如dp[i - t] => i - t >=0和s[i - 1 - dp[i - 1] - 1]，见最长括号数
[答案]不一定是dp[-1]，如果以某位结束的答案而不是累积结果，一般就用max_len

累积DP递归公式

1	dp[n] = max(dp[n - 1], f)

Python代码：

def dp(self, s):
	dp = [False] * (len(s) + 1)
	dp[0] = True
	for i in range(1, len(dp)):
		...
	return dp[-1]

算法分析：

时间复杂度为O(n)，空间复杂度O(n)。

应用题型：

LeetCode 139 Word Break
LeetCode 044 Wildcard Matching
LeetCode 010 Regular Expression Matching

数值到个数DP模板(最常考)

求个数DP是比较简单的DP，但也是比较常考的。一般DP是前n个，这里是用数值，这点还是有点难的。

递归公式

1	dp[n + num[i]] = dp[n], n = [1, tgt], i = [0, len(nums) - 1]

注意事项：

dp[i + nums[j]] += dp[i] 而不是dp[i] + 1
dp[0] = 1表示数值为0，可以不用任何数就能获得，所以是1种
i从0开始，因为此题递归式用相加i + nums[j]，而不是相减
nums先排序，否则如[3, 1, 2, 4]，返回dp[1] = 0, 但应该是dp[1] = 1
**上述4点注意事项只有1和2。**数

def dp(self, nums, target):
	nums.sort() # remember
	dp = [0] * (target + 1)
	dp[0] = 1 # remember
	for i in range(len(dp)):
		for j in range(len(nums)):
			if i + nums[j] > target:
				break
			dp[i + nums[j]] += dp[i] # remember no +1
	return dp[-1]

应用题型：

LeetCode 377 Combination Sum IV
LeetCode 198 House Robber

一个变体是求最小个数

递归公式

1	dp[n + coins[i]] = min{dp[n + coins[i]], dp[n] + 1}, n = [1, tgt], i = [0, len(nums) - 1]

不同之处：

递归式是dp[i] + 1
dp初始值为最大值，而且dp[0] = 0

def dp(self, coins: List[int], amount: int) -> int:
	coins.sort()
	dp = [float('inf')] * (amount + 1)
	dp[0] = 0
	for i in range(len(dp)):
		for j in range(len(coins)):
			if i + coins[j] > amount:
				break
			dp[i + coins[j]] = min(dp[i + coins[j]], dp[i] + 1)
	return dp[-1] if dp[-1] < float('inf') else -1  # remember

应用题型：

LeetCode 322 Coin Change
LeetCode 871 Minimum Number of Refueling Stops

算法分析：

时间复杂度为O(n*target)，空间复杂度O(n)。

区间型DP模板

k循环从1还是从2开始取决于递归式

def dp(self, s: str) -> int:
	# init dp array
	for k in range(1, len(s)):
		for i in range(len(s) - k):
			j = i + k
			# dp formula
	return dp[0][-1]

应用题型：

LeetCode 516 Longest Palindromic Subsequence
LeetCode 312 Burst Balloons

压缩空间

若递归式和上一行有关，绝大部分属于此情况，就可以用两行，原数量列来处理

与标准模板不同之处：

行个数为2
i仍然是遍历到所有行，所以不能用len(dp),而是len(text1) + 1.
dp行不用i，而是i % 2

def longestCommonContinuous(self, text1: str, text2: str) -> int:
	dp = [[0 for _ in range(len(text2) + 1)] for _ in range(2)]
	res = 0
	for i in range(1, len(text1) + 1):
		for j in range(1, len(dp[0])):
			if text1[i - 1] == text2[j - 1]:
				dp[i % 2][j] = dp[(i - 1) % 2][j - 1] + 1
				res = max(res, dp[i % 2][j])
	return res

应用题型：

Karat 002 Longest Common Continuous Subarray
LeetCode 063 Unique Paths II

打印路径

三种类型：

LCA: Karat 002 Longest Common Continuous Subarray res = history1[i - dp[i][j]:i]
LIS: LeetCode 300 Longest Increasing Subsequence LeetCode 368 Largest Divisible Subset
LCS: LeetCode 1143 Longest Common Subsequence

LIS过程：

path跟dp数组一样大，记录回溯跳转j -> i路径path[i - 1] = j - 1
记录回溯开始点if res == dp[i]: biggest_pos = i - 1
循环长度为res, 从biggest_pos开始

Python代码：

def print_path(self, nums, path[:biggest_pos + 1], dp_value = res):
	pos, res = len(path) - 1, []
	for _ in range(dp_value):
		res.append(nums[pos])
		pos = path[pos]
	return res[::-1]

LCS:

path和dp一样，不用特别数组
从右下到左上，若上或左值一样，向此方向移动，直到左和上少一，此时res -= 1

Python代码：

longest, res = dp[-1][-1], ''
while m >= 0 and n >= 0:
	if dp[m - 1][n] == longest:
		m -= 1
	elif dp[m][n - 1] == longest:
		n -= 1
	else:
		res += text1[m - 1]
		longest -= 1
		m -= 1
		n -= 1