KK's blog

每天积累多一些

0%

Posted on Disqus:

LeetCode



Given a binary tree root, a node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X.

Return the number of good nodes in the binary tree.

Example 1:



Input: root = [3,1,4,3,null,1,5]
Output: 4
Explanation: Nodes in blue are good.
Root Node (3) is always a good node.
Node 4 -> (3,4) is the maximum value in the path starting from the root.
Node 5 -> (3,4,5) is the maximum value in the path
Node 3 -> (3,1,3) is the maximum value in the path.


Example 2:



Input: root = [3,3,null,4,2]
Output: 3
Explanation: Node 2 -> (3, 3, 2) is not good, because “3” is higher than it.


Example 3:

Input: root = [1]
Output: 1
Explanation: Root is considered as good.


Constraints:

The number of nodes in the binary tree is in the range [1, 10^5]. Each node’s value is between [-10^4, 10^4].

题目大意：

一个节点是good表示该节点从root到自己的路径上，所有节点都小于等于自己。求二叉树的good节点个数

解题思路：

统计左右子树的good节点个数，最重要是引入类似于min, max验证BST，引入path_max来记录路径上的最大值，只要该节点值大于path_max就是good节点。DFS返回good节点个数

解题步骤：

N/A

注意事项：

  1. 引入path_max来记录路径上的最大值

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
def goodNodes(self, root: TreeNode) -> int:
	return self.dfs(root, float('-inf'))

def dfs(self, root, path_max):
	if not root:
		return 0
	left = self.dfs(root.left, max(root.val, path_max))
	right = self.dfs(root.right, max(root.val, path_max))
	res = left + right
	if path_max <= root.val:
		res += 1
	return res

算法分析：

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

Posted on Disqus:

LeetCode



Given an integer n, return any array containing n unique integers such that they add up to 0.

Example 1:

Input: n = 5
Output: [-7,-1,1,3,4]
Explanation: These arrays also are accepted [-5,-1,1,2,3] , [-3,-1,2,-2,4].


Example 2:

Input: n = 3
Output: [-1,0,1]


Example 3:

Input: n = 1
Output: [0]


Constraints:

* 1 <= n <= 1000

题目大意：

给定n，求n个数的数组使得数组和为0

解题思路：

Easy题，只要将相反数放入数组即可

解题步骤：

N/A

注意事项：

  1. Python代码：

    1
    2
    3
    4
    5
    6
    7
    8
    def sumZero(self, n: int) -> List[int]:
    	res = []
    	if n % 2 == 1:
    		res.append(0)
    	for i in range(n // 2):
    		res.append(i + 1)
    		res.append(-i - 1)
    	return res

算法分析：

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

Posted on Disqus:

LeetCode



Given two integers a and b, return any string s such that:

s has length a + b and contains exactly a 'a' letters, and exactly b 'b' letters, The substring 'aaa' does not occur in s, and
The substring 'bbb' does not occur in s.

Example 1:

Input: a = 1, b = 2
Output: “abb”
Explanation: “abb”, “bab” and “bba” are all correct answers.


Example 2:

Input: a = 4, b = 1
Output: “aabaa”


Constraints: 0 <= a, b <= 100
* It is guaranteed such an s exists for the given a and b.

题目大意：

给定两个整数代表ab的个数，生成一个字符串，字符串ab频数不能超过这2个数，不能有连续的aaa, bbb, 求此种字符串的最大长度

解题思路：

参考LeetCode 1405 Longest Happy String, 此题不用heap因为只有两种字符

解题步骤：

N/A

注意事项：

  1. 不能连续的处理

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def strWithout3a3b(self, a: int, b: int) -> str:
	res = ''
	while a > 0 or b > 0:
		if a > b:
			if len(res) > 1 and res[-2] == res[-1] == 'a':
				res += 'b'
				b -= 1
			else:
				res += 'a'
				a -= 1
		else:
			if len(res) > 1 and res[-2] == res[-1] == 'b':
				res += 'a'
				a -= 1
			else:
				res += 'b'
				b -= 1
	return res

算法分析：

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

Posted on Disqus:

LeetCode



A string s is called happy if it satisfies the following conditions:

s only contains the letters 'a', 'b', and 'c'. s does not contain any of "aaa", "bbb", or "ccc" as a substring.
s contains at most a occurrences of the letter 'a'. s contains at most b occurrences of the letter 'b'.
s contains at most c occurrences of the letter 'c'.

Given three integers a, b, and c, return the longest possible happy string. If there are multiple longest happy strings, return any of them. If there is no such string, return the empty string "".

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: a = 1, b = 1, c = 7
Output: “ccaccbcc”
Explanation: “ccbccacc” would also be a correct answer.


Example 2:

Input: a = 7, b = 1, c = 0
Output: “aabaa”
Explanation: It is the only correct answer in this case.


Constraints: 0 <= a, b, c <= 100
* a + b + c > 0

题目大意：

给定三个整数代表abc的个数，生成一个字符串，字符串abc频数不能超过这3个数，不能有连续的aaa, bbb, ccc, 求此种字符串的最大长度

解题思路：

由第一个例子看出，先尽量用频数最多的字符，直到连续3个为止，然后再用次多的，如此反复做。这里用到最多和次多，所以考虑用Heap

解题步骤：

N/A

注意事项：

  1. 每次选频数最高的字符，但若此字符已连续3次，选次高的，用heap。
  2. 大于0的频数才加入到heap Line 4和Line 17
  3. heapreplace等于heappop次高的和heappush最高的。既然要有次高，heap就不能为空

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def longestDiverseString(self, a: int, b: int, c: int) -> str:
	res = ''
	heap = []
	if a > 0: # remember
		heapq.heappush(heap, (-a, 'a'))
	if b > 0:
		heapq.heappush(heap, (-b, 'b'))
	if c > 0:
		heapq.heappush(heap, (-c, 'c'))
	while heap:
		count, char = heapq.heappop(heap)
		if len(res) > 1 and res[-2] == res[-1] == char:
			if not heap:
				break
			count, char = heapq.heapreplace(heap, (count, char))
		res += char
		if count + 1:
			heapq.heappush(heap, (count + 1, char))
	return res

算法分析：

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

Posted on Disqus:

LeetCode



A string s is called good if there are no two different characters in s that have the same frequency.

Given a string s, return the minimum number of characters you need to delete to make s good.

The frequency of a character in a string is the number of times it appears in the string. For example, in the string "aab", the frequency of 'a' is 2, while the frequency of 'b' is 1.

Example 1:

Input: s = “aab”
Output: 0
Explanation: s is already good.


Example 2:

Input: s = “aaabbbcc”
Output: 2
Explanation: You can delete two ‘b’s resulting in the good string “aaabcc”.
Another way it to delete one ‘b’ and one ‘c’ resulting in the good string “aaabbc”.


Example 3:

Input: s = “ceabaacb”
Output: 2
Explanation: You can delete both ‘c’s resulting in the good string “eabaab”.
Note that we only care about characters that are still in the string at the end (i.e. frequency of 0 is ignored).


Constraints:

1 <= s.length <= 10<sup>5</sup> s contains only lowercase English letters.

题目大意：

给定一个字符串，求最小删除次数使得字符串的每一种字符频率不同

解题思路：

按题意求解，若遇到频率相同的字符，就将其减一，也就是删除一个字符，使得它不再与其他字符频率相同直到0. 关键在用一个unique_count的set来记录频数

解题步骤：

N/A

注意事项：

  1. 用一个unique_count的set来记录频数

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
def minDeletions(self, s: str) -> int:
	char_to_count = collections.Counter(s)
	unique_count = set()
	res = 0
	for char, count in char_to_count.items():
		cur_count = count
		while cur_count in unique_count:
			cur_count -= 1
			res += 1
		if cur_count > 0:
			unique_count.add(cur_count)
	return res

算法分析：

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

Free mock interview