1.无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
class Solution(object):
def lengthOfLongestSubstring_1(self, s):
"""
:type s: str
:rtype: int
"""
# 存储历史循环中最长的子串长度
max_len = 0
# 判断传入的字符串是否为空
if s is None or len(s) == 0:
return max_len
# 定义一个字典，存储不重复的字符和字符所在的下标
str_dict = {}
# 存储每次循环中最长的子串长度
one_max = 0
# 记录最近重复字符所在的位置+1
start = 0
for i in range(len(s)):
# 判断当前字符是否在字典中和当前字符的下标是否大于等于最近重复字符的所在位置
if s[i] in str_dict and str_dict[s[i]] >= start:
# 记录当前字符的值+1
start = str_dict[s[i]] + 1
# 在此次循环中，最大的不重复子串的长度
one_max = i - start + 1
# 把当前位置覆盖字典中的位置
str_dict[s[i]] = i
# 比较此次循环的最大不重复子串长度和历史循环最大不重复子串长度
max_len = max(max_len, one_max)
return max_len
def lengthOfLongestSubstring_2(self, s):
"""
:type s: str
:rtype: int
"""
res = ''
maxlen = 0
for str in s:
if str not in res:
res += str
else:
maxlen = max(maxlen, len(res))
index = res.index(str)
res = res[index + 1:] + str
return max(maxlen, len(res))
if __name__ == '__main__':
sol = Solution()
print(sol.lengthOfLongestSubstring_1("bbbbb"))
print(sol.lengthOfLongestSubstring_1("keydgwdykpv"))
print(sol.lengthOfLongestSubstring_1("pwwkew"))
print(sol.lengthOfLongestSubstring_1("abcabcbb"))
2.最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"
示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明:
所有输入只包含小写字母 a-z 。
class Solution:
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
res = ""
if len(strs) == 0:
return ""
for each in zip(*strs): # zip()函数用于将可迭代对象作为参数，将对象中对应的元素打包成一个个元组，然后返回由这些元组组成的列表
if len(set(each)) == 1: # 利用集合创建一个无序不重复元素集
res += each[0]
else:
return res
return res
if __name__ == '__main__':
sol = Solution()
print(sol.longestCommonPrefix(["flower","flow","flight"]))
print(sol.longestCommonPrefix(["dog","racecar","car"]))
3.字符串的排列
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
换句话说，第一个字符串的排列之一是第二个字符串的子串。
示例1:
输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").
示例2:
输入: s1= "ab" s2 = "eidboaoo"
输出: False
注意：
输入的字符串只包含小写字母
两个字符串的长度都在 [1, 10,000] 之间
def checkInclusion(self, s1, s2):
"""
:type s1: str
:type s2: str
:rtype: bool
"""
if len(s1) > len(s2):
return False
list1 = [0 for i in range(26)]
print(list1)
list2 = [0 for i in range(26)]
for i in range(len(s1)):
list1[ord(s1[i]) - ord('a')] += 1
list2[ord(s2[i]) - ord('a')] += 1
count = 0
for i in range(26):
if list1[i] == list2[i]:
count += 1
for i in range(len(s2) - len(s1)):
r = ord(s2[i + len(s1)]) - ord('a')
l = ord(s2[i]) - ord('a')
if count == 26:
return True
list2[r] += 1
if list2[r] == list1[r]:
count += 1
elif list2[r] == list1[r] + 1:
count -= 1
list2[l] -= 1
if list2[l] == list1[l]:
count += 1
elif list2[l] == list1[l] - 1:
count -= 1
return count == 26
if __name__ == '__main__':
sol = Solution()
print(sol.checkInclusion("ab","eidbaooo"))
4.字符串相乘
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
示例 1:
输入: num1 = "2", num2 = "3"
输出: "6"
示例 2:
输入: num1 = "123", num2 = "456"
输出: "56088"
说明：
num1 和 num2 的长度小于110。
num1 和 num2 只包含数字 0-9。
num1 和 num2 均不以零开头，除非是数字 0 本身。
不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。
class Solution:
def multiply(self, num1, num2):
"""
:type num1: str
:type num2: str
:rtype: str
"""
return str(eval(num1+'*'+num2))
if __name__ == '__main__':
sol = Solution()
print(sol.multiply(num1 = "123", num2 = "456"))
5.翻转字符串里的单词
给定一个字符串，逐个翻转字符串中的每个单词。
示例:
输入: "the sky is blue",
输出: "blue is sky the".
说明:
无空格字符构成一个单词。
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
进阶: 请选用C语言的用户尝试使用 O(1) 空间复杂度的原地解法。
class Solution(object):
def reverseWords(self, s):
"""
:type s: str
:rtype: str
"""
return " ".join(s.split()[::-1]
if __name__ == '__main__':
sol = Solution()
print(sol.reverseWords("the sky is blue"))
6.简化路径
给定一个文档 (Unix-style) 的完全路径，请进行路径简化。
例如，
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"
边界情况:
你是否考虑了 路径 = "/../" 的情况？
在这种情况下，你需返回 "/" 。
此外，路径中也可能包含多个斜杠 '/' ，如 "/home//foo/" 。
在这种情况下，你可忽略多余的斜杠，返回 "/home/foo" 。
class Solution(object):
def simplifyPath(self, path):
"""
:type path: str
:rtype: str
"""
stack = []
path = [p for p in path.split('/') if p]
print(path)
for f in path:
if f == '.':
continue
elif f == '..':
if stack:
stack.pop()
else:
stack.append(f)
return '/' + '/'.join(stack)
if __name__ == '__main__':
sol = Solution()
print(sol.simplifyPath("/a/./b/../../c/"))
#我们首先使用path.split('/')将字符串切开，然后判断path.split('/')中每个元素。如果=='.'，我们继续判断下一个。如果=='..'，我们len(stack) != 0，弹出一个元素。否则我们将这个元素添加到stack中。
7.复原IP地址
给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
示例:
输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]
class Solution(object):
def restoreIpAddresses(self, s):
"""
:type s: str
:rtype: List[str]
"""
ans = []
self.helper(ans, s, 4, [])
return ['.'.join(x) for x in ans]
def helper(self, ans, s, k, temp):
if len(s) > k*3:
return
if k == 0:
ans.append(temp[:])
else:
for i in range(min(3,len(s)-k+1)):
if i==2 and int(s[:3]) > 255 or i > 0 and s[0] == '0':
continue
self.helper(ans, s[i+1:], k-1, temp+[s[:i+1]])
