KK's blog

LeetCode 588 Design In-Memory File System

Posted on 2021-12-16 Edited on 2022-03-15 Disqus:

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:

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”

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.

题目大意：

设计文件系统

解题思路：

如数据库系统的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 1041 Robot Bounded In Circle

Posted on 2021-12-16 Disqus:

LeetCode

On an infinite plane, a robot initially stands at (0, 0) and faces north. The robot can receive one of three instructions:

"G": go straight 1 unit; "L": turn 90 degrees to the left;
"R": turn 90 degrees to the right.

The robot performs the instructions given in order, and repeats them forever.

Return true if and only if there exists a circle in the plane such that the robot never leaves the circle.

Example 1:

Input: instructions = “GGLLGG”
Output: true
Explanation: The robot moves from (0,0) to (0,2), turns 180 degrees, and then returns to (0,0).
When repeating these instructions, the robot remains in the circle of radius 2 centered at the origin.

Example 2:

Input: instructions = “GG”
Output: false
Explanation: The robot moves north indefinitely.

Example 3:

Input: instructions = “GL”
Output: true
Explanation: The robot moves from (0, 0) -> (0, 1) -> (-1, 1) -> (-1, 0) -> (0, 0) -> …

Constraints: 1 <= instructions.length <= 100
* instructions[i] is 'G', 'L' or, 'R'.

题目大意：

循环按模式走是否回到原点

解题思路：

数学题，很难证明。定理是，只要按照给定模式走完，若回到原点或最后方向不是向北，都能回到原点

解题步骤：

N/A

注意事项：

Python代码：

def isRobotBounded(self, instructions: str) -> bool:
	DIRECTION_CONVERT_LEFT = {
		(0, 1): (-1, 0),
		(-1, 0): (0, -1),
		(0, -1): (1, 0),
		(1, 0): (0, 1),
	}
	DIRECTION_CONVERT_RIGHT = {
		(0, 1): (1, 0),
		(1, 0): (0, -1),
		(0, -1): (-1, 0),
		(-1, 0): (0, 1),
	}
	path, direction, position = instructions, (0, 1), (0, 0)
	for char in path:
		if char == 'L':
			direction = DIRECTION_CONVERT_LEFT[direction]
		elif char == 'R':
			direction = DIRECTION_CONVERT_RIGHT[direction]
		else:
			position = (position[0] + direction[0], position[1] + direction[1])
	return True if position == (0, 0) or direction != (0, 1) else False

算法分析：

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

LeetCode 680 Valid Palindrome II

Posted on 2021-12-16 Edited on 2021-12-19 Disqus:

LeetCode

Given a string s, return true if the s can be palindrome after deleting at most one character from it.

Example 1:

Input: s = “aba”
Output: true

Example 2:

Input: s = “abca”
Output: true
Explanation: You could delete the character ‘c’.

Example 3:

Input: s = “abc”
Output: false

Constraints:

1 <= s.length <= 105 s consists of lowercase English letters.

题目大意：

删除一个字符变成回文字符串

解题思路：

暴力法是O(n^2)，要优化到O(n)且这是关于元素之间的关系，考虑用Two pointers

解题步骤：

N/A

注意事项：

当发现不相等的字符，不能简单认为s[i + 1] == s[j]就觉得应该删除左边字符，因为可能是刚好相等，如bddbd，第一个b和倒数第二个b相等，如果删除第一个b，就会得到False，所以应该删除左边字符和删除右边字符同时都要试

Python代码：

def validPalindrome(self, s: str) -> bool:
	i, j = 0, len(s) - 1
	while i < j:
		if s[i] != s[j]:
			if self.is_palindrome(s[i + 1:j + 1]) or self.is_palindrome(s[i:j]):
				return True
			else:
				return False
		i += 1
		j -= 1
	return True
	
def is_palindrome(self, s):
	return s == s[::-1]

算法分析：

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

LeetCode 811 Subdomain Visit Count

Posted on 2021-12-15 Edited on 2022-02-06 Disqus:

LeetCode

A website domain "discuss.leetcode.com" consists of various subdomains. At the top level, we have "com", at the next level, we have "leetcode.com" and at the lowest level, "discuss.leetcode.com". When we visit a domain like "discuss.leetcode.com", we will also visit the parent domains "leetcode.com" and "com" implicitly.

A count-paired domain is a domain that has one of the two formats "rep d1.d2.d3" or "rep d1.d2" where rep is the number of visits to the domain and d1.d2.d3 is the domain itself.

For example, "9001 discuss.leetcode.com" is a count-paired domain that indicates that discuss.leetcode.com was visited 9001 times.

Given an array of count-paired domains cpdomains, return an array of the count-paired domains of each subdomain in the input. You may return the answer in any order.

Example 1:

Input: cpdomains = [“9001 discuss.leetcode.com”]
Output: [“9001 leetcode.com”,”9001 discuss.leetcode.com”,”9001 com”]
Explanation: We only have one website domain: “discuss.leetcode.com”.
As discussed above, the subdomain “leetcode.com” and “com” will also be visited. So they will all be visited 9001 times.

Example 2:

Input: cpdomains = [“900 google.mail.com”, “50 yahoo.com”, “1 intel.mail.com”, “5 wiki.org”]
Output: [“901 mail.com”,”50 yahoo.com”,”900 google.mail.com”,”5 wiki.org”,”5 org”,”1 intel.mail.com”,”951 com”]
Explanation: We will visit “google.mail.com” 900 times, “yahoo.com” 50 times, “intel.mail.com” once and “wiki.org” 5 times.
For the subdomains, we will visit “mail.com” 900 + 1 = 901 times, “com” 900 + 50 + 1 = 951 times, and “org” 5 times.

Constraints: 1 <= cpdomain.length <= 100
1 <= cpdomain[i].length <= 100 cpdomain[i] follows either the "repi d1i.d2i.d3i" format or the "repi d1i.d2i" format.
repi is an integer in the range [1, 104]. d1i, d2i, and d3i consist of lowercase English letters.

题目大意：

统计所以domain和子域名个数

解题思路：

遍历每个domain，将domain和个数存入dict，再对domain按点号break，将每个sub-domain存入dict

解题步骤：

N/A

注意事项：

Line 64根据题意倒转统计，Line 65记得非空时候加点号

Python代码：

def subdomainVisits(self, cpdomains: List[str]) -> List[str]:
	domain_to_count = collections.defaultdict(int)
	for pair_str in cpdomains:
		pair = pair_str.split(' ')
		count = int(pair[0])
		domain = pair[1]
		subdomain = ''
		for segment in domain.split('.')[::-1]:
			subdomain = segment + ('.' + subdomain if subdomain else '')
			domain_to_count[subdomain] += count
	return ['{} {}'.format(_count, _domain) for _domain, _count in domain_to_count.items()]

算法分析：

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

LeetCode 1326 Minimum Number of Taps to Open to Water a Garden

Posted on 2021-12-15 Disqus:

LeetCode

There is a one-dimensional garden on the x-axis. The garden starts at the point 0 and ends at the point n. (i.e The length of the garden is n).

There are n + 1 taps located at points [0, 1, ..., n] in the garden.

Given an integer n and an integer array ranges of length n + 1 where ranges[i] (0-indexed) means the i-th tap can water the area [i - ranges[i], i + ranges[i]] if it was open.

Return the minimum number of taps that should be open to water the whole garden, If the garden cannot be watered return -1.

Example 1:

Input: n = 5, ranges = [3,4,1,1,0,0]
Output: 1
Explanation: The tap at point 0 can cover the interval [-3,3]
The tap at point 1 can cover the interval [-3,5]
The tap at point 2 can cover the interval [1,3]
The tap at point 3 can cover the interval [2,4]
The tap at point 4 can cover the interval [4,4]
The tap at point 5 can cover the interval [5,5]
Opening Only the second tap will water the whole garden [0,5]

Example 2:

Input: n = 3, ranges = [0,0,0,0]
Output: -1
Explanation: Even if you activate all the four taps you cannot water the whole garden.

Example 3:

Input: n = 7, ranges = [1,2,1,0,2,1,0,1]
Output: 3

Example 4:

Input: n = 8, ranges = [4,0,0,0,0,0,0,0,4]
Output: 2

Example 5:

Input: n = 8, ranges = [4,0,0,0,4,0,0,0,4]
Output: 1

Constraints:

1 <= n <= 104 ranges.length == n + 1
* 0 <= ranges[i] <= 100

题目大意：

用多少个水龙头覆盖整个花园

解题思路：

两个难点，此题类似于jump game，这一层某个水龙头浇到最远点的水龙头也就是这一层的水龙头，这是难点一。
难点二是跟jump game不同，这题可以往前跳，也就是如例子中，点2表示从1跳到3，因为它的范围是1. 所以要重新计算每个水龙头的起点=它的左半范围起点

解题步骤：

N/A

注意事项：

第一步转化成jump game，jump game每个数值都是长度。若左半范围起点小于等于0，所有这些水龙头归结到起点0，长度为i + ranges[i], 其余情况是ranges[i] * 2
完全用jump game的程序

Python代码：

def minTaps(self, n: int, ranges: List[int]) -> int:
	end, next_end, res = 0, 0, 0
	nums = [0] * len(ranges)
	for i in range(len(ranges)):
		if i - ranges[i] <= 0:
			nums[0] = max(nums[0], ranges[i] + i)
		else:
			nums[i - ranges[i]] = max(nums[i - ranges[i]], ranges[i] * 2)

	for i in range(len(nums) - 1): # remember
		if i <= end:  # -3 <= 0
			next_end = max(next_end, i + nums[i])  # 3
		if i == end:
			end = next_end
			res += 1
	return res if next_end >= len(nums) - 1 else -1

算法分析：

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