KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode



Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Example 1:



Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).


Example 2:



Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.


Example 3:



Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.


Constraints:

The number of the nodes in the list is in the range [0, 10<sup>4</sup>]. -10<sup>5</sup> <= Node.val <= 10<sup>5</sup>
pos is -1 or a valid index in the linked-list.

*Follow up: Can you solve it using O(1) (i.e. constant) memory?

题目大意：

求LL是否存在循环

解题思路：

快慢指针。若存在循环就一定会相遇，这是显然的。

解题步骤：

N/A

注意事项：

  1. 不涉及删除，所以不需要哟用到fake_node，但循环中先走再判断。

Python代码：

1
2
3
4
5
6
7
def hasCycle(self, head: ListNode) -> bool:
	fast, slow= head, head
	while fast and fast.next:
		fast, slow = fast.next.next, slow.next
		if fast == slow: # meets again
			return True
	return False

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.

Do not modify the linked list.

Example 1:



Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.


Example 2:



Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.


Example 3:



Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.


Constraints:

The number of the nodes in the list is in the range [0, 10<sup>4</sup>]. -10<sup>5</sup> <= Node.val <= 10<sup>5</sup>
pos is -1 or a valid index in the linked-list.

*Follow up: Can you solve it using O(1) (i.e. constant) memory?

题目大意：

求LL是否存在循环，若存在返回循环起点

解题思路：

先用快慢指针找到相遇点，然后将slow指针移回fake_head起点，同速度移动直到相遇即为所求

证明：

A为起点，B为快慢指针相遇点，假设长度分别为z, y, x

1
2
3
4
5
fast在相遇时走过的距离为: z + x + y + y, 比slow多走一圈  
slow在相遇时走过的距离为: z + y  
由于fast速度是slow的两倍，所以相遇时，同一时间内，走过的距离也是两倍。
z + x + y + y = 2 * (z + y)
x = z得证

解题步骤：

N/A

注意事项：

  1. 不涉及删除，所以不需要哟用到fake_node，但循环中先走再判断。
  2. 循环可能不存在，此时返回None

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
def detectCycle(self, head: ListNode) -> ListNode:
	fast, slow= head, head
	while fast and fast.next:
		fast, slow = fast.next.next, slow.next
		if fast == slow: # meets again
			break
	if not fast or not fast.next:
		return None # remember
	slow = head
	while fast != slow:
		fast, slow = fast.next, slow.next
	return fast

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Given an m x n binary matrix filled with 0‘s and 1‘s, find the largest square containing only 1‘s and return its area.

Example 1:



Input: matrix = [[“1”,”0”,”1”,”0”,”0”],[“1”,”0”,”1”,”1”,”1”],[“1”,”1”,”1”,”1”,”1”],[“1”,”0”,”0”,”1”,”0”]]
Output: 4


Example 2:



Input: matrix = [[“0”,”1”],[“1”,”0”]]
Output: 1


Example 3:

Input: matrix = [[“0”]]
Output: 0


Constraints:

m == matrix.length n == matrix[i].length
1 <= m, n <= 300 matrix[i][j] is '0' or '1'.

题目大意：

求子正方形矩阵全是1的最大面积

解题思路：

求最值且是矩阵考虑用DP，但公式比较难写。
dp[i][j]为以(i-1, j-1)为右下端点的正方形的边长
递归式：

1
2
dp[i][j] = min{dp[i-1][j-1], dp[i-1][j], dp[i][j-1]} + 1 if matrix[i][j] == 1
         = 0                                             otherwise

解题步骤：

严格遵守DP的5点注意事项

注意事项：

  1. 严格遵守DP的5点注意事项。初始值是0，表示第一行或第一列的点的边长最多只能为1.
  2. 输入是字符，所以比较是否1时候用字符比较

Python代码：

1
2
3
4
5
6
7
8
9
10
11
# dp[i][j] = min{dp[i-1][j-1], dp[i-1][j], dp[i][j-1]} + 1 if matrix[i][j] == 1
#          = 0                                             otherwise
def maximalSquare(self, matrix: List[List[str]]) -> int:
	dp = [[0 for _ in range(len(matrix[0]) + 1)] for _ in range(len(matrix) + 1)] # remember 0 not 1 or float(inf)
	# dp[0][0] = 0
	res = 0
	for i in range(1, len(dp)):
		for j in range(1, len(dp[0])):
			dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1 if matrix[i - 1][j - 1] == '1' else 0 # remember '1' not 1
			res = max(res, dp[i][j])
	return res * res

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Given the head of a singly linked list, return true if it is a palindrome.

Example 1:



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


Example 2:



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


Constraints:

The number of nodes in the list is in the range [1, 10<sup>5</sup>]. 0 <= Node.val <= 9

Follow up: Could you do it in O(n) time and O(1) space?

题目大意：

求一个LL是否回文

解题思路：

快慢指针 + Stack

解题步骤：

N/A

注意事项：

  1. 快慢指针找到中点，找的同时，慢指针所有节点入栈。慢指针继续走，比较stack节点和慢指针节点。
  2. 不涉及删除，所以不需要哟用到fake_node
  3. 中位数可能有1-2个。奇偶问题，若fast指向节点(另一情况是None), 表明是奇数个，slow在第二个循环前多走一步，跳过最中间的节点

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def isPalindrome(self, head: ListNode) -> bool:
	fast, slow = head, head
	stack = []
	while fast and fast.next:
		stack.append(slow)
		slow = slow.next
		fast = fast.next.next
	if fast:
		slow = slow.next
	while slow:
		if stack.pop().val != slow.val:
			return False
		slow = slow.next
	return True

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Write an efficient algorithm that searches for a target value in an m x n integer matrix. The matrix has the following properties:

Integers in each row are sorted in ascending from left to right. Integers in each column are sorted in ascending from top to bottom.

Example 1:



Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Output: true


Example 2:



Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
Output: false


Constraints:

m == matrix.length n == matrix[i].length
1 <= n, m <= 300 -10<sup>9</sup> <= matrix[i][j] <= 10<sup>9</sup>
All the integers in each row are sorted in ascending order. All the integers in each column are sorted in ascending order.
* -10<sup>9</sup> <= target <= 10<sup>9</sup>

题目大意：

矩阵按行按列有序，求是否存在target

解题思路：

矩阵有序题有3道：
LeetCode 074 Search a 2D Matrix 每一行有序，下一行的首元素大于上一行的尾元素 + 找target
LeetCode 240 Search a 2D Matrix II 按行按列有序 + 找target
LeetCode 378 Kth Smallest Element in a Sorted Matrix 按行按列有序 + 找第k大
矩阵结构方面，第一道每一行都是独立，所以可以独立地按行按列做二分法
后两道，矩阵二维连续，所以解法都是类BFS，从某个点开始，然后比较它相邻的两个点。出发点不同，第二道在近似矩阵中点(右上角或左下角)，第三道在左上角出发。

解题步骤：

N/A

注意事项：

  1. 从右上角出发，比较左和下节点。

Python代码：

1
2
3
4
5
6
7
8
9
10
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
	i, j = 0, len(matrix[0]) - 1
	while i < len(matrix) and j >= 0:
		if matrix[i][j] == target:
			return True
		if target < matrix[i][j]:
			j -= 1
		else:
			i += 1
	return False

算法分析：

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

Free mock interview