KK's blog

LeetCode

<div>

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

Example 1:

<pre>Input: head = [1,2,2,1] Output: true </pre>

Example 2:

<pre>Input: head = [1,2] Output: false </pre>

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?</div>

题目大意：

求一个LL是否回文

解题思路：

快慢指针 + Stack

解题步骤：

N/A

注意事项：

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

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)

算法II解题思路Recursion：

dfs(node)表示从这个点开始是否对称LL，这里利用后序遍历的方法，先走到头，在回溯时候通过一个global的left=left.next一个个比较

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13

def isPalindrome(self, head: Optional[ListNode]) -> bool:
	left = head
	def dfs(node):
		nonlocal left
		if not node:
			return True
		if not dfs(node.next):
			return False
		if left.val != node.val:
			return False
		left = left.next
		return True
	return dfs(head)

算法III解题思路反转LL：

找到中点后反转后半，然后前半和后半的每个节点逐一比较。最后恢复后半的顺序

LeetCode

<div>

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:

<pre>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 </pre>

Example 2:

<pre>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 </pre>

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>

</div>

题目大意：

矩阵按行按列有序，求是否存在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)

LeetCode

<div>

Given an array of strings wordsDict and two different strings that already exist in the array word1 and word2, return the shortest distance between these two words in the list.

Example 1:

<pre>Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "coding", word2 = "practice" Output: 3 </pre>

Example 2:

<pre>Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding" Output: 1 </pre>

Constraints:

• 1 <= wordsDict.length <= 3 * 10<sup>4</sup>
• 1 <= wordsDict[i].length <= 10
• wordsDict[i] consists of lowercase English letters.
• word1 and word2 are in wordsDict.
• word1 != word2

</div>

题目大意：

求单词列表中给定的两个单词的最短下标距离

解题思路：

同向双指针，扫一遍。贪婪法，肯定相邻，所以扫一遍

解题步骤：

N/A

注意事项：

1. 同向双指针，分别指向两单词，计算结果时必须是找到才比较

Python代码：

1
2
3
4
5
6
7
8
9
10
11

def shortestDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:
	p1 = p2 = -1
	res = float('inf')
	for i, word in enumerate(wordsDict):
		if word == word1:
			p1 = i
		if word == word2:
			p2 = i
		if p1 != -1 and p2 != -1:
			res = min(res, abs(p1 - p2))
	return res

算法分析：

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

算法思路II：

同向双指针，取出每个单词的所有下标L1, L2,双指针比较，类似于merge sort的merge

LeetCode

<div>

Given a string expression of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. You may return the answer in any order.

Example 1:

<pre>Input: expression = "2-1-1" Output: [0,2] Explanation: ((2-1)-1) = 0 (2-(1-1)) = 2 </pre>

Example 2:

<pre>Input: expression = "23-45" Output: [-34,-14,-10,-10,10] Explanation: (2*(3-(45))) = -34 ((23)-(45)) = -14 ((2(3-4))5) = -10 (2((3-4)5)) = -10 (((23)-4)*5) = 10 </pre>

Constraints:

• 1 <= expression.length <= 20
• expression consists of digits and the operator '+', '-', and '*'.
• All the integer values in the input expression are in the range [0, 99].

</div>

题目大意：

给定一个字符串含数字和加减乘除，求所有加括号方法得到的结果

Catalan解题思路(推荐)：

求所有结果，用DFS，由于需要左右递归，双边递归，所以用Catalan法模板

解题步骤：

N/A

注意事项：

1. 终止条件返回是一个list
2. Python中用eval来计算字符串运算结果返回值为整数，所以归纳左右递归结果要用str转为字符串

Python代码：

1
2
3
4
5
6
7
8
9
10
11

def diffWaysToCompute(self, expression: str) -> List[int]:
	if expression.isdigit():
		return [int(expression)] # remember to use list
	res = []
	for i, char in enumerate(expression):
		if char not in '+-*/':
			continue
		left_res = self.diffWaysToCompute(expression[:i])
		right_res = self.diffWaysToCompute(expression[i + 1:])
		res += [eval(str(_l) + char + str(_r)) for _l in left_res for _r in right_res] # remember eval and str
	return res

算法分析：

时间复杂度Catalan数为O(C[n] += C[i-1]*C[n-i])，空间复杂度O(1)

记忆性搜索算法II解题思路：

大致同上，只不过加入记忆性搜索算法，但优化不算大

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

def diffWaysToCompute2(self, expression) -> List[int]:
	return self.dfs(expression, {})

def dfs(self, expression: str, cache) -> List[int]:
	if expression.isdigit():
		return [int(expression)] # remember to use list
	if expression in cache:
		return cache[expression]
	res = []
	for i, char in enumerate(expression):
		if char not in '+-*/':
			continue
		left_res = self.dfs(expression[:i], cache)
		right_res = self.dfs(expression[i + 1:], cache)
		res += [eval(str(_l) + char + str(_r)) for _l in left_res for _r in right_res] # remember eval and str
	cache[expression] = res
	return res

LeetCode

<div>

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

<pre>Input: s = "anagram", t = "nagaram" Output: true </pre>

Example 2:

<pre>Input: s = "rat", t = "car" Output: false </pre>

Constraints:

• 1 <= s.length, t.length <= 5 * 10<sup>4</sup>
• s and t consist of lowercase English letters.

Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?

</div>

题目大意：

验证变位词

频率法解题思路(推荐)：

简单题

解题步骤：

N/A

注意事项：

Python代码：

1
2

def isAnagram2(self, s: str, t: str) -> bool:
	return collections.Counter(s) == collections.Counter(t)

算法分析：

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

排序法算法II解题思路：

Python代码：

1
2

def isAnagram(self, s: str, t: str) -> bool:
	return sorted(s) == sorted(t)

算法分析：

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