KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode



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:

Input: expression = “2-1-1”
Output: [0,2]
Explanation:
((2-1)-1) = 0
(2-(1-1)) = 2


Example 2:

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


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].

题目大意：

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

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

Posted on Edited on Disqus:

LeetCode



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:

Input: s = “anagram”, t = “nagaram”
Output: true


Example 2:

Input: s = “rat”, t = “car”
Output: false


Constraints:

`1 <= s.length, t.length <= 5 104*sandt` consist of lowercase English letters.

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

题目大意：

验证变位词

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

简单题

解题步骤：

N/A

注意事项：

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

Posted on Edited on Disqus:

LeetCode



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:

Input: wordsDict = [“practice”, “makes”, “perfect”, “coding”, “makes”], word1 = “coding”, word2 = “practice”
Output: 3


Example 2:

Input: wordsDict = [“practice”, “makes”, “perfect”, “coding”, “makes”], word1 = “makes”, word2 = “coding”
Output: 1


Constraints:

`1 <= wordsDict.length <= 3 104*1 <= wordsDict[i].length <= 10*wordsDict[i]consists of lowercase English letters. *word1andword2are inwordsDict. *word1 != word2`

题目大意：

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

解题思路：

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

解题步骤：

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

Posted on Edited on Disqus:

LeetCode



We can shift a string by shifting each of its letters to its successive letter.

For example, "abc" can be shifted to be "bcd".

We can keep shifting the string to form a sequence. For example, we can keep shifting "abc" to form the sequence: "abc" -> "bcd" -> ... -> "xyz".

Given an array of strings strings, group all strings[i] that belong to the same shifting sequence. You may return the answer in any order.

Example 1:

Input: strings = [“abc”,”bcd”,”acef”,”xyz”,”az”,”ba”,”a”,”z”]
Output: [[“acef”],[“a”,”z”],[“abc”,”bcd”,”xyz”],[“az”,”ba”]]


Example 2:

Input: strings = [“a”]
Output: [[“a”]]


Constraints:

1 <= strings.length <= 200 1 <= strings[i].length <= 50
* strings[i] consists of lowercase English letters.

题目大意：

将单词按等偏移量分组

解题思路：

单词分组题，设计一个id。组内的每个单词里字母之间的差值是一致的，如abd, wxz, 差值分别为1和2，这是同一组。

解题步骤：

N/A

注意事项：

  1. 求每个单词每个字母之间的差值，用下滑线连接作为id。注意差值可能为负数，所以要取mod变正
  2. 单一字母单词，不存在偏移量，id为空，所以代码不需要特殊处理

Python代码：

1
2
3
4
5
6
7
8
def groupStrings(self, strings: List[str]) -> List[List[str]]:
	res = collections.defaultdict(list)
	for s in strings:
		_id = ''
		for j in range(1, len(s)):
			_id += str((ord(s[j]) - ord(s[j - 1])) % 26) + '_'
		res[_id].append(s)
	return list(res.values())

算法分析：

时间复杂度为O(nm)，空间复杂度O(1), n为单词个数, m为单词最长长度。

Posted on Edited on Disqus:

LeetCode



Given an m x n binary grid grid where each 1 marks the home of one friend, return the minimal total travel distance.

The total travel distance is the sum of the distances between the houses of the friends and the meeting point.

The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

Example 1:



Input: grid = [[1,0,0,0,1],[0,0,0,0,0],[0,0,1,0,0]]
Output: 6
Explanation: Given three friends living at (0,0), (0,4), and (2,2).
The point (0,2) is an ideal meeting point, as the total travel distance of 2 + 2 + 2 = 6 is minimal.
So return 6.


Example 2:

Input: grid = [[1,1]]
Output: 1


Constraints:

m == grid.length n == grid[i].length
1 <= m, n <= 200 grid[i][j] is either 0 or 1.
There will be *at least two friends in the grid.

题目大意：

矩阵中1表示朋友的位置，求最佳见面位置，所有朋友到这个位置曼哈顿距离最短。

解题思路：

这是数学题也是非高频题。如果是一维，求最佳位置，是所有朋友位置的中点，也就是左边朋友和右边朋友的数量是一样。求距离也就是用相向双指针，求每对点的距离。
推广到二维，同理，x和y坐标是独立的。分别求距离即可。

解题步骤：

N/A

注意事项：

  1. 用相向双指针，求每对点的距离

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def minTotalDistance(self, grid: List[List[int]]) -> int:
	x_coordinates, y_coordinates = [], []
	for i in range(len(grid)):
		for j in range(len(grid[0])):
			if grid[i][j] == 1:
				x_coordinates.append(i)
				y_coordinates.append(j)
	x_coordinates.sort()
	y_coordinates.sort()
	res = 0
	left, right = 0, len(y_coordinates) - 1
	while left < right:
		res += y_coordinates[right] - y_coordinates[left]
		left += 1
		right -= 1

	left, right = 0, len(x_coordinates) - 1
	while left < right:
		res += x_coordinates[right] - x_coordinates[left]
		left += 1
		right -= 1
	return res

算法分析：

时间复杂度为O(nlogn)，空间复杂度O(n), n为矩阵的长边大小

Free mock interview