KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode



Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Example 1:

Input: nums = [3,2,3]
Output: 3


Example 2:

Input: nums = [2,2,1,1,1,2,2]
Output: 2


Constraints:

n == nums.length 1 <= n <= 5 * 10<sup>4</sup>
-2<sup>31</sup> <= nums[i] <= 2<sup>31</sup> - 1

*Follow-up: Could you solve the problem in linear time and in O(1) space?

题目大意：

求数组中的众数

解题思路：

编程之美的水王法

解题步骤：

N/A

注意事项：

  1. Python代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    def majorityElement(self, nums: List[int]) -> int:
    	candidate, count = 0, 0
    	for i in range(len(nums)):
    		if count == 0:
    			candidate = nums[i]
    			count += 1
    			continue
    		if nums[i] == candidate:
    			count += 1
    		else:
    			count -= 1
    	return candidate

算法分析：

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

Posted on Edited on Disqus:

LeetCode



You are given an inclusive range [lower, upper] and a sorted unique integer array nums, where all elements are in the inclusive range.

A number x is considered missing if x is in the range [lower, upper] and x is not in nums.

Return the smallest sorted list of ranges that cover every missing number exactly. That is, no element of nums is in any of the ranges, and each missing number is in one of the ranges.

Each range [a,b] in the list should be output as:

"a->b" if a != b "a" if a == b

Example 1:

Input: nums = [0,1,3,50,75], lower = 0, upper = 99
Output: [“2”,”4->49”,”51->74”,”76->99”]
Explanation: The ranges are:
[2,2] –> “2”
[4,49] –> “4->49”
[51,74] –> “51->74”
[76,99] –> “76->99”


Example 2:

Input: nums = [-1], lower = -1, upper = -1
Output: []
Explanation: There are no missing ranges since there are no missing numbers.


Constraints:

-10<sup>9</sup> <= lower <= upper <= 10<sup>9</sup> 0 <= nums.length <= 100
lower <= nums[i] <= upper All the values of nums are unique.

题目大意：

给定一个范围[lower, upper]和数组表示这个范围有的数，求缺失数范围

解题思路：

简单题。也是数学题
公式为:

1
[nums[i-1] + 1, nums[i] - 1]

解题步骤：

N/A

注意事项：

  1. 缺失数范围公式为[nums[i-1] + 1, nums[i] - 1], 需要一个函数来处理若范围内仅含一个数或多个数的情况
  2. 题目条件lower, upper在数组范围之外，所以不妨将lower, upper加到数组中，同一处理，但是由于lower和upper表示缺失数，而数组表示含有数。所以将lower - 1和upper + 1加到数组
  3. 数组可能为空，要特别处理Line 3

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def findMissingRanges(self, nums: List[int], lower: int, upper: int) -> List[str]:
	if not nums: # remember
		return [self.get_missing_str(lower, upper)]
	res = []
	nums.insert(0, lower - 1)
	nums.append(upper + 1)
	for i in range(1, len(nums)):
		# [nums[i-1] + 1, n - 1]
		if nums[i - 1] + 1 <= nums[i] - 1:
			res.append(self.get_missing_str(nums[i - 1] + 1, nums[i] - 1))
	return res
	
def get_missing_str(self, start, end):
	if start == end:
		return str(start)
	else:
		return str(start) + '->' + str(end)

算法分析：

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

Posted on Edited on Disqus:

LeetCode



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:

Input: n = 00000000000000000000000000001011
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three ‘1’ bits.


Example 2:

Input: n = 00000000000000000000000010000000
Output: 1
Explanation: The input binary string 00000000000000000000000010000000 has a total of one ‘1’ bit.


Example 3:

Input: n = 11111111111111111111111111111101
Output: 31
Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one ‘1’ bits.


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?

题目大意：

求二进制上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



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:



Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]


Example 2:

Input: root = [1,null,3]
Output: [1,3]


Example 3:

Input: root = []
Output: []


Constraints:

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

题目大意：

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

解题思路：

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



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:

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.


Example 2:

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.


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.

题目大意：

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

解题思路：

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

解题步骤：

N/A

注意事项：

  1. 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)

Free mock interview