1. 剑指 Offer 38. 字符串的排列
输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
示例：
输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]
解法1. 递归
class Solution:
def permutation(self, s: str) -> List[str]:
# # 字符串的全排列
result = []
def perm(s_dir, one = ''):
if s_dir:
buff = [] # 遍历所有字符，不处理 相同字符。
for i, x in enumerate(s_dir):
if x not in buff:
perm(s_dir[:i] + s_dir[i+1:], one+x)
buff.append(x)
else: # 找到最后， 相当于 叶子节点
# if one not in result: # 如果在这里判断，会超时
result.append(one)
return
perm(s)
return result
2. 剑指 Offer 45. 把数组排成最小的数
输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
示例 1:
输入: [10,2]
输出: "102"
示例 2:
输入: [3,30,34,5,9]
输出:"3033459"提示:
0 < nums.length <= 100
说明:
输出结果可能非常大，所以你需要返回一个字符串而不是整数
拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0
解法1: 快速排序
class Solution:
def minNumber(self, nums: List[int]) -> str:
# 本质上是个 排序
# 排序规则： x+y>y+x: y小
# y+x > x +y, x小
nums_str = [str(item) for item in nums]
def one_sort(nums, start, end):
# 一趟排序
i = start
j = end
while i < j:
# 从右往左扫描
while i<j and nums[i] + nums[j] < nums[j] + nums[i]:
j -= 1
if i < j:
nums[i], nums[j] = nums[j], nums[i]
i = i + 1
# 从左往右扫描
while i < j and nums[i] + nums[j] < nums[j] + nums[i]: #
i += 1
if i < j:
nums[i], nums[j] = nums[j], nums[i]
j = j - 1
return i
# 快速排序算法
def quick_sort(nums, start, end):
if start < end:
p = one_sort(nums, start, end)
# print(nums)
quick_sort(nums, start, p-1)
quick_sort(nums, p+1, end)
quick_sort(nums_str, 0, len(nums_str)-1)
return ''.join(nums_str)
3. 139. 单词拆分
给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
示例 2：
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
注意你可以重复使用字典中的单词。
示例 3：
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
解法1: 动态规划
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
# 从s出发考虑， s中字符 划分后 是否都出现在wordDict
# 采用 动态规划（不太熟练），遍历字符串; 很巧妙; 从字典开始匹配 递归超时
dp = [0]*(len(s)+1)
dp[0] = 1
for i in range(1, len(s)+1):
for j in range(i):
if dp[j] == 1 and s[j:i] in wordDict:
dp[i] = 1 # 从i 可以开始新的匹配了
break
return dp[i] == 1
4. 140. 单词拆分 II
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。
说明：
分隔时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例：
输入:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
输出:
[
"pine apple pen apple",
"pineapple pen apple",
"pine applepen apple"
]
解释: 注意你可以重复使用字典中的单词。
解法1: 递归 （超时）+ 投机取巧
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
wordDict = sorted(wordDict)
# any(): 可迭代对象中 若全为Fasle， 则返回False, 否则True;
# all(): 可迭代对象中 若全为True, 则返回True, 否则Flase
# 若想 句子中所有单词都在词典中， 句子中的 字母 必须都在 词典中出现的字符中；
# 若 出现词典中 没出现过字符，则 必定不能组成句子；
if any([i not in set("".join(wordDict)) for i in s]): # 全为False，any 返回false
return [] # 通过有点 投机取巧了；
# 递归 超时
result = []
def digui(s, wordDict, ju=''):
if not s:
result.append(ju.strip())
for item in wordDict:
item_len = len(item)
if s[0:0+item_len] == item: # 匹配成功
digui(s[0+item_len:], wordDict, ju + ' ' + item)
return
digui(s, wordDict)
return result
此题有个测试用例 很恶心：（去掉句子中b 依然超时）
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]
解法2: 从单词的角度去遍历， 也是投机取巧
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
dp = [0]*(len(s)+1)
dp[0] = 1
s_len = len(s)
if not all([item in set(''.join(wordDict)) for item in s]):
return []
# 递归
result = []
def digui(s, wordDict, ss=''): #
if not s:
result.append(ss.strip())
s_len = len(s)
start = 0
for i in range(s_len + 1):
if s[start: start+i] in wordDict:
digui(s[start+i:], wordDict, ss + ' ' + s[start: start+i])
return
digui(s, wordDict, '')
return result
5. 20. 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
解法1 ：
class Solution:
def isValid(self, s: str) -> bool:
if not s:
return True
qu_dict = {'(': ')', ')':'(', '{':'}', '}': '{', '[':']', ']':'['}
# 括号匹配， 先进后出， 后入先出
result = []
for item in s:
if item in [')', '}', ']'] and qu_dict[item] in result:
# 可以进去， 是否消除
if len(result) > 0 and result[-1] == qu_dict[item]:
result.pop()
else:
result.append(item)
elif item in ['(', '{', '[']: # 直接进 不消除
result.append(item)
else:
return False
if result:
return False
return True
解法2: 大神的奇思妙想, 直接替换
class Solution:
def isValid(self, s: str) -> bool:
while '()' in s or '[]' in s or '{}' in s:
s = s.replace('()', '')
s = s.replace('[]', '')
s = s.replace('{}', '')
if s:
return False
return True
6. 3. 无重复字符的最长子串
剑指 Offer 48. 最长不含重复字符的子字符串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串
解法1: 自创， 思路后续补
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
max_length = 0
zichuan = []
for item in s:
zichuan.append(item)
if item in zichuan[:-1]:
item_index = zichuan.index(item)
zichuan = zichuan[item_index+1:] # 去掉前面重复的
max_length = max(max_length, len(zichuan))
return max_length
解法2: 官方 滑动窗口
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
# 官方解法 滑动窗口， 找 从头开始， 以每个字符开始 对应的 最长子串（没有重复字符）， 比较长度 找到最大的；
s_len = len(s)
nk, max_len = -1, 0 # nk表示滑动窗口右侧，-1表示还没移动
sets = set() # 哈希表, 判断是否 重复字符
for i in range(s_len):
if i != 0:
sets.remove(s[i-1]) # 开始指针下移一步
while nk+1 < s_len and s[nk+1] not in sets:
sets.add(s[nk+1])
nk = nk + 1
# 出现重复的值了, 就是 i~nk 没有重复字符的 最长字串
max_len = max(max_len, nk-i+1)
return max_len
7. 394. 字符串解码
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
示例 1：
输入：s = "3[a]2[bc]"
输出："aaabcbc"
解法1:
class Solution:
def decodeString(self, s: str) -> str:
### 简单在 所有数字 只表示重复次数k， 数字只表示重复；
res = []
for item in s:
if item == "]": # 遇到"]" 回溯
ress = ""
while res and res[-1] != '[': # 方括号内部字母
ress = res.pop()+ress
res.pop() # 输出[
# 得到方括号前的数字
nums = ""
while res and res[-1].isdigit():
nums = res.pop()+nums
if nums:
res.append(int(nums) * ress)
else:
res.append(ress)
else:
res.append(item)
# print(res)
return "".join(res)
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
