KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode



Given the head of a singly linked list, reverse the list, and return the reversed list.

Example 1:



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


Example 2:



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


Example 3:

Input: head = []
Output: []


Constraints:

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

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

题目大意：

反转LL

解题思路：

简单题，但是经典题。循环体为，左方一个单独节点，右方为一个LL，将LL的首节点指向单独节点

LeetCode 206 Reverse Linked List 反转整个LL
LeetCode 092 Reverse Linked List II 反转部分LL，此题更加一般化

模板：
不断将end直接后面的节点加到start直接后面
start(group n) -> NodeA （新状态） -> … -> end(group n+1) -> NodeA （前状态） -> …

  1. 找出start和end，start为反转部分的前一个，end为反转部分的首个节点
  2. 循环删除end直接后，再加入到start直接后

    Python代码：

    1
    2
    3
    4
    5
    6
    start, end = fake_head, head
    while <反转链表长度>:
    	# delete the node
    	moved_node, end.next = end.next, end.next.next
    	# insert the moved_node
    	start.next, moved_node.next = moved_node, start.next

解题步骤：

N/A

注意事项：

  1. 利用模板，由于首节点会变，所以引入fake_node
  2. 空节点的处理

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
def reverseList(self, head: ListNode) -> ListNode:
	if not head:
		return None
	fake_head = ListNode(0)
	fake_head.next = head
	start, end = fake_head, head
	while end.next:
		# delete the node
		moved_node, end.next = end.next, end.next.next
		# insert the moved_node
		start.next, moved_node.next = moved_node, start.next
	return fake_head.next

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Given an integer n, return the number of prime numbers that are strictly less than n.

Example 1:

Input: n = 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.


Example 2:

Input: n = 0
Output: 0


Example 3:

Input: n = 1
Output: 0


Constraints:

`0 <= n <= 5 106`

题目大意：

求n内的素数个数

解题思路：

排除法：知道一个素数后删除它的倍数，剩下的就是下一个素数

解题步骤：

N/A

注意事项：

  1. 开一个prime大小数组，初始值为True表示是素数。
  2. 题目要求素数小于n，所以不含n
  3. 提高效率：i遍历到n开方+1，删除的数不能超过n(一开始写没有break导致TLE), 最后用sum统计比for循环效率高点

Python代码：

1
2
3
4
5
6
7
8
9
10
def countPrimes(self, n: int) -> int:
	if n < 2:
		return 0
	primes = [True] * n # remember less than n
	primes[0] = primes[1] = False
	for i in range(2, int(math.sqrt(n)) + 1):
		if primes[i]:
			for j in range(i * 2, n, i): # starting from i rather than 2
				primes[j] = False
	return sum(primes)

算法分析：

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

Posted 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 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



Given an array, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]


Example 2:

Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]


Constraints:

1 <= nums.length <= 10<sup>5</sup> -2<sup>31</sup> <= nums[i] <= 2<sup>31</sup> - 1
0 <= k <= 10<sup>5</sup>

Follow up: Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
* Could you do it in-place with O(1) extra space?

题目大意：

数组原地向右旋转k位

解题思路：


证明如上图，比如[1,2,3,4,5,6,7]中，A = [1,2,3,4], B = [5,6,7]先整体reverse再分别reverse。

解题步骤：

N/A

注意事项：

  1. k会大于数组大小，所以取mod
  2. Python中reverse一个sublist，方法先取sublist再倒转

Python代码：

1
2
3
4
5
def rotate(self, nums: List[int], k: int) -> None:
	k = k % len(nums) # remember
	nums[:] = nums[::-1]
	nums[:k] = nums[:k][::-1] # remember how to reverse sublist
	nums[k:] = nums[k:][::-1]

算法分析：

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

Free mock interview