Leetcode 【524、767、1053、1079】
Leetcode 【524、767、1053、1079】
问题描述：【Two Pointers】524. Longest Word in Dictionary through Deleting
解题思路：
这道题是给一个字符串s和一个单词数组，找到数组里面最长的单词，该单词可以通过删除s的某些字符来得到。如果答案不止一个，返回长度最长且字典序最小的单词。如果答案不存在，返回空字符串。
双指针法。对于单词数组中的每个单词 word，字符串 s 和 word 逐字符比较向后滑动。word 如果能滑到最后，说明可以由 s 删除字符得到，这时更新最大长度。如果下一个 word 的最大长度和上一个 word 最大长度一样，则比较它们的字典序，选取较小的字典序（ans = min(ans, word) 即可，ans 为上一个结果）。
时间复杂度为 O(len(d)*len(s))，d 为单词数组长度，s 为字符串的长度；空间复杂度为 O(1)。
Python3 实现：
class Solution:
def findLongestWord(self, s: str, d: List[str]) -> str:
ans = ""
max_len = 0
for word in d:
if len(s) < len(word) or len(word) == 0: continue
j = 0
for i in range(len(s)):
if s[i] == word[j]: # 对应字符相同
j += 1
if j == len(word):
if len(word) > max_len:
ans = word
max_len = len(word)
elif len(word) == max_len: # 长度相同，保留最小字典序的word
ans = min(ans, word)
break # 该word判断完成，终止循环
return ans问题描述：【Sort、Heap】767. Reorganize String
解题思路：
这道题是给一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。
首先可以得知，如果某字符的次数超过 (len(S)+1) // 2，那么一定不可以重构字符串，返回空串。
方法1（Sort）：
以 S = "acbaa" 为例，先按照 S 的每个字母出现的次数从大到小排列，得到一个列表，如 A = ['a','a','a','b','c']，然后建立一个和 S 相同长度的列表 ans = [None] * len(S)，将 A 中的字符按顺序先安排在 ans 的偶数位置上（ans = ['a',None, 'a', None, 'a']），偶数位置放满后，将剩下一半数字放在奇数位置上。这样即可实现相邻字母不同。
更一般的，如 S = "aaabbbccce"，我们将会得到 ans = ['a','b','a','c','a','c','b','c','b','e']。
Python3 实现：
class Solution:
def reorganizeString(self, S: str) -> str:
N = len(S)
A = []
for (cnt, s) in sorted([(S.count(s), s) for s in set(S)], reverse=True): # 按字母次数从大到小排列
if cnt > (N + 1) // 2: return "" # 任何一个字符的出现次数不能超过(N+1)//2
A.extend(s * cnt)
ans = [None] * N
ans[::2], ans[1::2] = A[:(N+1)//2], A[(N+1)//2:] # 将A中前一半字符安排在偶数位置上，后一半安排在奇数位置上
return "".join(ans)方法2（Heap）：
按照字母出现的次数建立大根堆（实际上可以转化为按照字母出现的次数的负值建立小根堆，即 (-次数, 字母)）。然后，每次从堆里面取出两个元素，依次加入到结果 ans 中，并将它们对应的次数减 1。如果不为 0，重新放入堆中。
这其实是一种贪婪的策略，每次取出的两个元素肯定是不相邻的。
例如，S = "abcaa"，我们建立的堆的过程为：
(-3, 'a') (-2, 'a') (-1, 'a')
/ \ -> / ->
(-1, 'b') (-1, 'c') (-1, 'c') - 先取出两个元素，(-3, 'a') 和 (-1, 'b')，加入到结果 ans = "ab"，然后次数各减 1，得到 (-2, 'a') 和 (0, 'b')。因为 'a' 不为 0，因此加入到堆中继续判断；
- 再取出两个元素，(-2, 'a') 和 (-1, 'c')，加入到结果 ans = "abac"，然后次数各减 1，得到 (-1, 'a') 和 (0, 'c')。因为 'a' 不为 0，因此加入到堆中继续判断；
- 堆中元素数量小于 2，终止判断，将最后的一个字符 'a' 加入到结果，ans = "abaca"，即得到了正确的答案。
Python3 实现：
import heapq
class Solution:
def reorganizeString(self, S: str) -> str:
N = len(S)
heap = []
for s in set(S):
cnt = S.count(s)
if cnt > (N + 1) // 2:
return ""
heapq.heappush(heap, (-cnt, s)) # 建立小根堆（-次数，字母）
ans = ""
while len(heap) >= 2: # 堆中至少有两个元素
cnt1, s1 = heapq.heappop(heap) # 每次取出堆顶两个元素
cnt2, s2 = heapq.heappop(heap)
ans += s1 + s2 # 依次加入的结果
cnt1 += 1 # 次数减少（存的是负值）
cnt2 += 1
if cnt1 < 0: # 次数没有减少到0重新加入堆中
heapq.heappush(heap, (cnt1, s1))
if cnt2 < 0:
heapq.heappush(heap, (cnt2, s2))
if len(heap) == 1: #如果S长度为奇数
ans += heapq.heappop(heap)[1]
return ans问题描述：【Math】1053. Previous Permutation With One Swap
解题思路：
这道题是给一个正整数数组 A，返回可在一次交换（交换两数字 A[i] 和 A[j] 的位置）后得到的、按字典序排列小于 A 的最大可能排列。
这道题做了好久，前面提交了几次都 WA，就放下了。过了一周后再看这道题，突然有了思路，很快 AC 了。而且弄明白题意后，代码很简单。
很明显，这道题需要找规律。我们先观察以下几组输入输出数据：
[1,1,5] -> [1,1,5] [1,9,4,6,7] -> [1,7,4,6,9] [1,9,4,6,10] -> [1,6,4,9,10] [3,1,1,3] -> [1,3,1,3] [9,3,2,2,3] -> [9,2,3,2,3] [8,5,7,2,4] -> [8,5,4,2,7]
由此，我们观察到规律，需要交换的第一个位置 first 是从右到左遍历的第一个逆序对 A[i] > A[j] 中 i 的位置（如 [8,5,7,2,4] 中从右到左遍历第一个逆序对为 7 > 2，则交换的第一个位置就是 first = 2）。如果不存在逆序对，说明原序列非严格递增（如 [1,1,5]），直接返回原数组即可。第二个交换的位置 second 是从 first 的下一个位置开始，小于 A[first] 且最靠近 A[first] 的最大值的索引位置（如 [1,9,4,6,10] 中，first = 1，小于 A[1] = 9 的最大值为 6，其对应索引 second = 3；再比如 [3,1,1,3] 中，first = 0，小于 A[0] = 3 的最大值是 1，但是要选择最靠近 A[first] 的 1，即 second = 1 而不是 2）。最后，交换 first 和 second 位置的元素即可得到答案。时间复杂度为 O(n)。
Python3 实现：
class Solution:
def prevPermOpt1(self, A: List[int]) -> List[int]:
switch = -1 # 第一个数交换的位置
for i in range(len(A) - 1, 0, -1):
if A[i] < A[i-1]:
switch = i - 1
break
if switch == -1: # 升序，不交换
return A
second_max = ind = 0 # 第二个数及其交换的位置
for i in range(switch + 1, len(A)):
if second_max < A[i] < A[switch]: # 小于A[switch]且离A[switch]的最大值
second_max, ind = A[i], i
A[switch], A[ind] = A[ind], A[switch] # 交换两个位置的元素
return A问题描述：【BFS】1079. Letter Tile Possibilities
解题思路：
这道题是给一个字符串，返回所有非空字母序列的数目。
看到数据范围为 <= 7，因此用回溯法去做，对不同长度的字母序列进行全排列，并保存到集合中（去重）。
Python3 实现：
class Solution:
def numTilePossibilities(self, tiles: str) -> int:
def search(k, path):
for i in range(N):
if not b[i]:
path += tiles[i]
b[i] = True
ans.add(path) # 不同长度的字母序列都保存
if k != N:
search(k+1, path)
b[i] = False
path = path[:-1]
ans = set() # 防止重复
N = len(tiles)
b = [False] * len(tiles)
search(1, "")
return len(ans)还可以使用 Python 中 itertools 中自带的 permutations(str/list, k) 函数进行全排列统计，一行代码即可搞定：
class Solution:
def numTilePossibilities(self, tiles: str) -> int:
return sum(len(set(itertools.permutations(tiles, i))) for i in range(1, len(tiles) + 1))其中，itertools.permutations(tiles, i) 得到不同长度的全排列，set 去重，len 取返回集合的长度，sum 对不同长度的序列求和。