Leetcode 【553、609、856、1003、1023】
Leetcode 【553、609、856、1003、1023】
题目描述：【Math】553. Optimal Division
解题思路：
这道题是给一个数组，各个数字连除，通过加括号，使得除操作的结果最大。刚开始想着是遍历所有加括号的方式，然后求出最大结果。但是，发现加括号的规律很麻烦。
后来又重新读了一下题目，发现数组中的数字取值是 [2,1000]。就这说明，如果我们不加括号，n1/n2/n3/n4/n5 只会越除越小。那么加括号如何保证最大结果呢？其实很简单，我们只需要在第二个数到最后一个数加括号即可，得到 n1/(n2/n3/n4/n5)，因为 n2/n3/n4/n5 是能过够获得的最小的除数因子，然后 n1 作为被除数，除以一个最小的除数，当然能获得最大的结果。
因此，此题转变为格式化输出的问题。这是一道数学题~
Python3 实现：
class Solution:
def optimalDivision(self, nums: List[int]) -> str:
if len(nums) == 1:
return str(nums[0])
elif len(nums) == 2:
return str(nums[0]) + "/" + str(nums[1])
else: # 在第二个数前到最后一个数后加括号就是答案
ans = str(nums[0]) + "/(" # 拼接答案
for i in range(1, len(nums) - 1):
ans += str(nums[i]) + "/"
ans += str(nums[-1]) + ")"
return ans最后一个 else 也可以直接写成：
return "%s/(%s)" % (str(nums[0]), '/'.join(nums[1:]))题目描述：【Hash Table】609. Find Duplicate File in System
解题思路：
这道题是给一个字符串数组，每一项包括文件路径、文件名、文件内容。要求找到所有重复的文件（至少两个），按照文件内容分组，每个分组的内容是各个重复文件的路径。
看到题目很容易想到利用字典来存储，字典的键为文件内容，字典的值是一个列表，保存重复文件的各个路径（相当于字典中每一项是一个分组）。最后，返回字典中所有列表长度 >= 2 的值就是结果（重复文件分组至少为两个）。
Python3 实现：
class Solution:
def findDuplicate(self, paths: List[str]) -> List[List[str]]:
dic = dict()
for path in paths:
items = path.split(" ")
directory = items[0] # 根目录
for i in range(1, len(items)):
ind = items[i].find('(')
content = items[i][ind+1:-1] # 文件内容
if content not in dic: # 构造分组，键为文件内容，值为文件路径
dic[content] = [directory+"/"+items[i][:ind]]
else:
dic[content].append(directory+"/"+items[i][:ind])
return [v for v in dic.values() if len(v) >= 2] # 长度>=2的是一个分组题目描述：【Stack】856. Score of Parentheses
解题思路：
这道题是给一个平衡括号字符串，给了三个规则来计算平衡字符串的分数。首先很容易想到用栈来解决。因为我们要计算得分，所以栈中存储 '(' 是没有意义的，我们可以在栈中存储得分。
做法是：从左到右遍历字符串 S，当我们遇到 '(' 时，就在栈中压入 0。遇到 ')' 时，如果栈顶是 0，相当于得到一个 "()"，计分为 1，并把 1 压入栈中；如果栈顶不是 0，我们通过循环把栈中非零数一个个取出来，同时累加这些非零数。所有非零数取出来后，这个累加的结果再乘以 2 就是最终的当前的得分。遍历完成后，栈中一定只剩下几个非零数，对它们求和就是最后的总得分。
举个例子，对于 S = "(()(()))(()()())"，我们栈中的变化情况是：[0] -> [0 0] -> [0 1] -> [0 1 0] -> [0 1 0 0] -> [0 1 0 1] -> [0 1 2] （取出非零数 1，然后乘以 2）-> [6] （取出非零数 1、2 累加，然后乘以 2）-> [6 0] -> [6 0 0] -> [6 0 1] -> [6 0 1 0] -> [6 0 1 1] -> [6 0 1 1 0] -> [6 0 1 1 1] -> [6 6]（取出非零数 1、1、1 累加，然后乘以 2）。因此，当遍历完 S 后，栈中剩下的一定是非零数 [6 6]，这些非零数满足规则 2 （AB），因此对它们求和就是最终的答案 12。
Python3 实现：
class Solution:
def scoreOfParentheses(self, S: str) -> int:
stack = []
for s in S:
if s == '(':
stack.append(0)
else:
t = 0 # 累加值
v = stack.pop()
while v != 0: # 找出非零数进行累加
t += v
v = stack.pop()
stack.append(max(t*2, 1)) # 将累加值或者1压入栈中
return sum(stack) # 将栈中结果求和就是最后的分数
print(Solution().scoreOfParentheses("(()(()))(()()())")) # 12题目描述：【String、Stack】1003. Check If Word Is Valid After Substitutions
解题思路：
这道题给了一个有效字符串 "abc"，然后定义有效字符串 V，V 划分成 X 和 Y 两部分，并且满足 X + "abc" + Y （X、Y可以为空）。求给一个字符串，看它是否是有效的。
方法1（朴素解法，可能超时）：
因为有效字符串一定包括 "abc"，因此直接的想法是遍历字符串，然后连续三个字符是 "abc" 就将其删除，然后将索引重新置 0，从头再次遍历寻找。这样时间复杂度为 O(n^2)，提交会超时。后来发现有效字符串一定是以 'a' 开头，以 'c' 结尾，因此加了个判断，AC 了。算是投机取巧吧，这种方法不建议。
Python3 实现：
class Solution:
def isValid(self, S: str) -> bool:
if S[0] != 'a' or S[-1] != 'c': # 提前终止
return False
i = 0
while i < len(S) - 2:
if S[i:i+3] == "abc":
S = S[:i] + S[i+3:] # 拼接的时间复杂度为O(n)
i = 0 # 从索引0开始继续寻找
else:
i += 1
if len(S) == 0:
return True
else:
return False方法2 （栈，时间复杂度和空间复杂度均为 O(n)）：
方法1每次删除字符串 "abc" 的时间复杂度为 O(n)（采取拼接的方式删除 "abc"），且每次索引位置回退为 0，效率很低。因此，可以想到使用栈来记录状态。如果栈中有 "abc"，就出三次栈，弹出 "abc"，且这种做法索引不需要回退。最后，栈为空说明是一个有效串，时间复杂度和空间复杂度均为 O(n)。
Python3 实现：
class Solution:
def isValid(self, S: str) -> bool:
stack = []
for s in S:
stack.append(s)
if stack[-1:-4:-1] == ['c','b','a']: # 如果栈中有"abc"，出三次栈
stack.pop(); stack.pop(); stack.pop()
return len(stack) == 0方法3（str.replace("abc", "") 的巧妙使用）：
方法1使用拼接的方式来删除字符串 "abc" 的时间复杂度为 O(n)，效率很低。其实，在字符串操作中，有一个方法 str.replace("abc", "") 同样可以进行字符串的删除，效率比拼接的方式高。并且，str.replace("abc", "") 可以一次性替换字符串中所有 "abc" 为空串。
因此，当我们操作多次 str.replace("abc", "")后，如果字符串长度为 0，说明是一个有效串；如果前后两次操作 str.replace("abc", "") 字符串长度不变化，说明不是一个有效串，返回 False 即可。
这种方法击败了 97% 的提交，效率很高。
Python3 实现：
class Solution:
def isValid(self, S: str) -> bool:
if S[0] != 'a' or S[-1] != 'c': # 提前终止
return False
last_len = len(S) # 前后两次字符串的长度
while True:
if len(S) == 0:
return True
S = S.replace("abc", "") # 删除当前字符串中所有"abc"字串
if last_len == len(S): # 前后两次长度不变化，不是有效串
return False
else:
last_len = len(S)题目描述：【String】1023. Camelcase Matching
解题思路：
这道题是给一个字典和模式串，从字典中找出模糊匹配模式串的所有单词。但是除了模式串本身，其他匹配的字符都是小写字母。
这道题最直接的想法就是字典中的每个单词和模式串逐个字符比对即可。只不过有很多细节再需要注意：
- 如果单词 query 的每个位置 i，如果 query 当前字符 query[i] 和模式串位置 j 的字符 pattern[i] 相等，则 j 向后移动一位；如果 j 等于 pattern 的长度，说明模式串可以匹配当前单词，但是还要注意单词后面的字符不能有大写字母，如果有大写字母，则还是不满足题意。
- 如果 query[i] 是小写字母，则跳过继续向后搜寻；
- 其他情况 query[i] 均不满足模式串。
- 遍历完 query 后，j 有可能小于 pattern 长度，如 query = "F"，pattern = "FB"，因此还要判断如果 j < len(pattern)，不满足题意。
因此，这道题没有什么技巧，就是要认真考虑模糊匹配的各种情况，防止出错。
Python3 实现：
class Solution:
def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:
ans = []
for query in queries:
j = 0 # 模式串匹配位置
flag = True # 标记匹配成功还是失败
for i in range(len(query)):
if query[i] == pattern[j]:
j += 1
if j == len(pattern):
if len(query[i+1:]) > 0 and query[i+1:].islower() == False: # 单词后面的字符必须是小写
flag = False
break
elif 'a' <= query[i] <= 'z':
continue
else:
flag = False
break
if j < len(pattern): # 单词长度可能小于模式串长度
flag = False
ans.append(flag)
return ans