KK's blog

每天积累多一些

0%

Posted on Disqus:

LeetCode



Given a string s, return true if a permutation of the string could form a palindrome.

Example 1:

Input: s = “code”
Output: false


Example 2:

Input: s = “aab”
Output: true


Example 3:

Input: s = “carerac”
Output: true


Constraints:

1 <= s.length <= 5000 s consists of only lowercase English letters.

题目大意：

字符串的任一全排列是否存在回文字符串

解题思路：

数学题，也就是统计字符频率，奇数频率的字符最多有1个

解题步骤：

N/A

注意事项：

  1. 统计字符频率，奇数频率的字符最多有1个

Python代码：

1
2
3
def canPermutePalindrome(self, s: str) -> bool:
	char_to_count = collections.Counter(s)
	return False if len([count for count in char_to_count.values() if count % 2 == 1]) > 1 else True

算法分析：

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

Posted on Disqus:

LeetCode



There is a row of n houses, where each house can be painted one of three colors: red, blue, or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by an n x 3 cost matrix costs.

For example, costs[0][0] is the cost of painting house 0 with the color red; costs[1][2] is the cost of painting house 1 with color green, and so on…

Return the minimum cost to paint all houses.

Example 1:

Input: costs = [[17,2,17],[16,16,5],[14,3,19]]
Output: 10
Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue.
Minimum cost: 2 + 5 + 3 = 10.


Example 2:

Input: costs = [[7,6,2]]
Output: 2


Constraints: costs.length == n
costs[i].length == 3 1 <= n <= 100
* 1 <= costs[i][j] <= 20

题目大意：

排屋相邻不同色地涂色(3色)的最低成本

解题思路：

低频题。最值且涉及数值考虑用DP。由于相邻不能同色，所以是多状态DP，有3个状态，不妨多用一维表示，第二维只有3值。
dp[i][j]定义为第i间屋涂上第j色的最低总费用，递归式为

1
dp[i][j] = min(dp[i-1][(j+1)%3] + costs[i-1][j], dp[i-1][(j+2)%3] + costs[i-1][j])

解题步骤：

N/A

注意事项：

  1. 递归5步曲，多1，初始，多1，少1，答案。记得第一步初始化数组多1

Python代码：

1
2
3
4
5
6
7
# dp[i][j] = min(dp[i-1][(j+1)%3] + costs[i-1][j], dp[i-1][(j+2)%3] + costs[i-1][j])
def minCost(self, costs: List[List[int]]) -> int:
	dp = [[0] * 3 for _ in range(len(costs) + 1)]
	for i in range(1, len(dp)):
		for j in range(3):
			dp[i][j] = min(dp[i - 1][(j + 1) % 3] + costs[i - 1][j], dp[i - 1][(j + 2) % 3] + costs[i - 1][j])
	return min(dp[-1][0], dp[-1][1], dp[-1][2])

算法分析：

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

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

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

Free mock interview