KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode

<div>

Write a function that takes an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight).

Note:

  • Note that in some languages, such as Java, there is no unsigned integer type. In this case, the input will be given as a signed integer type. It should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned.
  • In Java, the compiler represents the signed integers using 2's complement notation. Therefore, in Example 3, the input represents the signed integer. -3.

Example 1:

<pre>Input: n = 00000000000000000000000000001011 Output: 3 Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits. </pre>

Example 2:

<pre>Input: n = 00000000000000000000000010000000 Output: 1 Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit. </pre>

Example 3:

<pre>Input: n = 11111111111111111111111111111101 Output: 31 Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one '1' bits. </pre>

Constraints:

  • The input must be a binary string of length 32.

Follow up: If this function is called many times, how would you optimize it?</div>

题目大意：

求二进制上1的个数

解题思路：

用n & n - 1来去掉最左的1

解题步骤：

N/A

注意事项：

  1. 用n & n - 1来去掉最左的1

Python代码：

1
2
3
4
5
6
def hammingWeight(self, n: int) -> int:
	count = 0
	while n:
		n = n & (n - 1)
		count += 1
	return count

算法分析：

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

Posted on Edited on Disqus:

LeetCode

<div>

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example 1:

<pre>Input: root = [1,2,3,null,5,null,4] Output: [1,3,4] </pre>

Example 2:

<pre>Input: root = [1,null,3] Output: [1,3] </pre>

Example 3:

<pre>Input: root = [] Output: [] </pre>

Constraints:

  • The number of nodes in the tree is in the range [0, 100].
  • -100 <= Node.val <= 100

</div>

题目大意：

二叉树从右看的节点列表。

解题思路：

BFS按层访问的最后一个

解题步骤：

N/A

注意事项：

  1. 需要知道最后一个，所以引入i，不能用enumerate，只能用len
  2. deque([root])不是deque(root)

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def rightSideView(self, root: TreeNode) -> List[int]:
	if not root:
		return []
	res = []
	queue = collections.deque([root])
	while queue:
		i, len_q = 0, len(queue) # remember
		for _ in range(len_q):
			node = queue.popleft()
			if i == len_q - 1:
				res.append(node.val)
			if node.left:
				queue.append(node.left)
			if node.right:
				queue.append(node.right)
			i += 1
	return res

算法分析：

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

Posted on Edited on Disqus:

LeetCode

<div>

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [a<sub>i</sub>, b<sub>i</sub>] indicates that you must take course b<sub>i</sub> first if you want to take course a<sub>i</sub>.

  • For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

Example 1:

<pre>Input: numCourses = 2, prerequisites = [[1,0]] Output: true Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible. </pre>

Example 2:

<pre>Input: numCourses = 2, prerequisites = [[1,0],[0,1]] Output: false Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible. </pre>

Constraints:

  • 1 <= numCourses <= 10<sup>5</sup>
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= a<sub>i</sub>, b<sub>i</sub> < numCourses
  • All the pairs prerequisites[i] are unique.

</div>

题目大意：

课程有先修课要求，求是否可以完成所有课程

解题思路：

跟LeetCode 210 Course Schedule II几乎一样，此题求可否完成，那题求课程顺序。区别在于return那一句返回bool还是res

解题步骤：

N/A

注意事项：

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
	in_degree = [0] * numCourses
	graph = [[] for _ in range(numCourses)]
	for li in prerequisites:
		in_degree[li[0]] += 1
		graph[li[1]].append(li[0])
	queue = collections.deque([i for i in range(len(in_degree)) if in_degree[i] == 0])
	res = []
	while queue:
		node = queue.popleft()
		res.append(node)
		for neighbor in graph[node]:
			in_degree[neighbor] -= 1
			if in_degree[neighbor] == 0:
				queue.append(neighbor)
	return numCourses == len(res)

算法分析：

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

Posted on Edited on Disqus:

LeetCode

<div>

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

  • WordDictionary() Initializes the object.
  • void addWord(word) Adds word to the data structure, it can be matched later.
  • bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.

Example:

<pre>Input ["WordDictionary","addWord","addWord","addWord","search","search","search","search"] [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]] Output [null,null,null,null,false,true,true,true]

Explanation WordDictionary wordDictionary = new WordDictionary(); wordDictionary.addWord("bad"); wordDictionary.addWord("dad"); wordDictionary.addWord("mad"); wordDictionary.search("pad"); // return False wordDictionary.search("bad"); // return True wordDictionary.search(".ad"); // return True wordDictionary.search("b.."); // return True </pre>

Constraints:

  • 1 <= word.length <= 500
  • word in addWord consists lower-case English letters.
  • word in search consist of  '.' or lower-case English letters.
  • At most 50000 calls will be made to addWord and search.

</div>

题目大意：

设计一个数据结构支持加单词和查找单词。查找单词支持dot查询，表示配对任意字符

解题思路：

第一时间想到Trie，但难点在如果支持dot。一般Trie实现只支持单一单词查询，但是此题需要搜索所有可能节点。所以要将search加入TrieNode参数且转成DFS

解题步骤：

N/A

注意事项：

  1. search加入TrieNode参数且转成DFS
  2. 终止条件第二个用TrieNode为空而不是用is_end

Python代码：

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
class WordDictionary(TestCases):

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

    def addWord(self, word: str) -> None:
        it = self.head
        for i in range(len(word)):
            it = it.children[word[i]]
        it.is_end = True

    def search(self, word: str) -> bool:
        return self.search_one_node(word, self.head)

    def search_one_node(self, word, trie_node) -> bool:
        if not word and trie_node.is_end:
            return True
        if not word or not trie_node: # remember not trie_node
            return False
        if word[0] == '.':
            for child_node in trie_node.children.values():
                if self.search_one_node(word[1:], child_node):
                    return True
            return False
        if word[0] not in trie_node.children:
            return False
        return self.search_one_node(word[1:], trie_node.children[word[0]])

class TrieNode:

    def __init__(self):
        self.children = collections.defaultdict(TrieNode)  # {}
        self.is_end = False

算法分析：

search中不含dot时间复杂度为O(n), 含dot时间复杂度为<code>O(26<sup>n</sup>)</code>，空间复杂度O(1), n为搜索单词长度.

Posted on Edited on Disqus:

LeetCode

<div>

A valid IP address consists of exactly four integers separated by single dots. Each integer is between 0 and 255 (inclusive) and cannot have leading zeros.

  • For example, "0.1.2.201" and "192.168.1.1" are valid IP addresses, but "0.011.255.245", "192.168.1.312" and "192.168@1.1" are invalid IP addresses.

Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s. You are not allowed to reorder or remove any digits in s. You may return the valid IP addresses in any order.

Example 1:

<pre>Input: s = "25525511135" Output: ["255.255.11.135","255.255.111.35"] </pre>

Example 2:

<pre>Input: s = "0000" Output: ["0.0.0.0"] </pre>

Example 3:

<pre>Input: s = "101023" Output: ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"] </pre>

Constraints:

  • 0 <= s.length <= 20
  • s consists of digits only.

</div>

题目大意：

给定一个数字字符串，求以分解成合法IP的所有解。IP每段范围是0-255且不能有前缀0，如06

解题思路：

求所有解，所以用DFS

解题步骤：

N/A

注意事项：

  1. 用DFS模板，属于结果分组型DFS，dfs函数有k。
  2. 两个限制条件，不能含leading zero和数字范围在255内

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def restoreIpAddresses(self, s: str) -> List[str]:
	path, res = [], []

	def dfs(s, start, path, res):
		if len(path) == 4 and start == len(s):
			res.append('.'.join(path))
			return
		if len(path) == 4 and start < len(s):
			return
		for i in range(start, min(len(s), start + 3)):
			segment = s[start: i + 1]
			if not segment.isdigit():
				continue
			if int(segment) > 255:
				continue
			if len(segment) > 1 and segment[0] == '0':
				continue
			path.append(segment)
			dfs(s, i + 1, path, res)
			path.pop()
	
	dfs(s, 0, path, res)

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def restoreIpAddresses(self, s: str) -> List[str]:
	res = []
	self.dfs(s, 0, [], res, 4)
	return res

def dfs(self, s, st, path, res, k):
	if st == len(s) and k == 0:
		res.append('.'.join(path))
		return
	if st == len(s) or k == 0:
		return
	for i in range(st, min(st + 3, len(s))):
		segment = s[st:i + 1]
		if len(segment) > 1 and segment[0] == '0': # no leading 0
			continue
		if int(segment) > 255: # remember
			continue
		path.append(segment)
		self.dfs(s, i + 1, path, res, k - 1)
		path.pop()

算法分析：

时间复杂度为O(1)，空间复杂度O(1), 由于IP固定是4个部分，每个部分最多3位，所以乘法原理第一个dot的选择有三个位置，其他两个dot如此类推，3x3x3=27

Free mock interview