行业知识
【Leetcode】字符串 string
-
题目汇总
能完���：14/38/43/58/66/68/125/165/242/344/434/451/506/520/521/524/535/541/557/657/686/
（）要优化：12/389/415/482/
不会做：8/214(x)/299/522/553/592/647/696
（）-
基础操作总结
字符串赋值
#多行赋值str = '''smileaaasmileaaaasmileaaaaa'''#包含'的赋值str = 'smileaaa\'s blog'
去除字符串中的空格：
1.str.strip() #去除开头或结尾的空格2.str.lstrip() #去除开头的空格3.str.rstrip() #去除结尾的空格4.str.replace(" ","") #通过替换去除所有空格5."".join(a.split()) #先按空格拆分后再进行拼接判断字符串中字符类型
1.str[i].isdigit() #判断字符串中的数字2.str[i].isalpha() #判断字符串中的字母3.str[i].isalnum() #判断字符串中的数字和字母#可搭配filter使用：''.join(filter(str.isalnum, str(s)))4.str[i].isupper() #判断字符串中的大小写
字符和ASCII码的转换：
ord(str) #字符转ASCII码chr(str) #ASCII码转字符
字符大小写的转换：
1.str.capitalize() #首字母大写2.str.upper() #全部大写3.str.lower() #全部小写4.str.swapcase() #大小写互换
join函数：
#str = 'smile' list = ['a', 'a','a']1.str.join(list) out: asmileasmilea #中插的方式2.''.join(list(str)+list) out: smileaaa #拼接的方式#list = [1,2,3]1.str="".join([str(i) for i in list])2.str="".join(map(str,list1))
-
基础知识总结
1.有限状态机 8
2.正则表达式 8 592
3.Manacher 214 查找一个字符串的最长回文子串的线性方法 ×
4.KMP 214 在一个字符串 S 内查找一个模式串 P 的出现位置 ×
5.计数器Counter 299 451
#统计元素数量后返回一个字典，keys为元素，values为元素个数，items成对获取from collections import Counterstr = 'smileaaa'dic = Counter(str)dic ({'a': 3, 's': 1, 'm': 1, 'i': 1, 'l': 1, 'e': 1}) #默认按数量排序dic.keys() (['s', 'm', 'i', 'l', 'e', 'a'])dic.values() ([1, 1, 1, 1, 1, 3])dic.items() ([('s', 1), ('m', 1), ('i', 1), ('l', 1), ('e', 1), ('a', 3)])sorted(dic.items(), key=lambda s: (-s[1])) #根据统计次数降序排序for key, val in dic.items(): #遍历6.动态规划 647
7.字符串是不可变类型，无法通过索引值进行修改，使用replace()是生成新的字符串；
要在原字符串上修改可以先list(str)，再"".join(list) （运行速度更快，节省空间--待核实）
1/2/6补充内容见：http://t.csdnimg.cn/IxhCV
-
优化思路
12
罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。
I-1 V-5 X-10 L-50 C-100 D-500 M-1000
例如， 罗马数字 2 写做 II 。12 写做 XII 。 27 写做 XXVII。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例。这个特殊的规则只适用于以下六种情况：
- I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
- X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
- C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给你一个整数，将其转为罗马数字。
思路一：创建阿拉伯数字和罗马数字之间的对应表，把4和9都纳入，即1900/1000=1=M，(1900%1000)/900=CM，得到MCM
class Solution: def intToRoman(self, num: int) -> str: tmp = ( (1000, 'M'), (900, 'CM'), (500, 'D'), (400, 'CD'), (100, 'C'), (90, 'XC'), (50, 'L'), (40, 'XL'), (10, 'X'), (9, 'IX'), (5, 'V'), (4, 'IV'), (1, 'I')) ret = "" for i, j in tmp: p = num // i if p: ret += j * p num -= p * i return ret
思路二：题目给出数字范围最大为3999，可以列举所有位上的数字可能
class Solution(object): def intToRoman(self, num): I = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"] X = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"] C = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"] M = ["", "M", "MM", "MMM"] return M[num // 1000] + C[(num % 1000) // 100] + X[(num % 100) // 10] + I[num % 10]
389
给定两个字符串 s 和 t ，它们只包含小写字母。字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。请找出在 t 中被添加的字母。
思路一：使用sorted保证s和t的排序相同，遍历s的判断对应位置的字符是否相同，若遍历结束仍未return，则添加的字母为t[-1]
trick：s和t的字符串长度仅差1，可在排序后的s末尾添加' '，然后利用zip函数同步遍历s和t
class Solution(object): def findTheDifference(self, s, t): """ :type s: str :type t: str :rtype: str """ if s == '': return t else: s, t = sorted(s), sorted(t) for i in range(len(s)): if s[i] != t[i] and s[i] == t[i+1]: return t[i] return t[-1]class Solution: def findTheDifference(self, s, t): s, t = sorted(s) + [' '], sorted(t) for c1, c2 in zip(s, t): if c1 != c2: return c2
思路二：对出现过的字符计数，作差即得结果
from collections import Counterclass Solution(object): def findTheDifference(self, s, t): a = Counter(s) # {'a':1, 'b':1, 'c':1, 'd':1, 'f':1} b = Counter(t) # {'a':1, 'b':1, 'c':1, 'd':1, 'e':1, 'f':1} c = list(b - a) # {'e'} return c[0]思路三：仅有被添加的字符出现奇数次（异或^） 字符不能参与逻辑运算，需要转换成ASCII码
class Solution: def findTheDifference(self, s, t): res = 0 for c in s+t: res = res ^ ord(c) return chr(res)
思路四：计算s和t的ASCII码求和结果，差值强转字符得到输出结果
（需要考虑求和值是否溢出，涉及字符串的数值运算—415，或者考虑只计算对应位上的差值结果—与方法一相似）
415
给定两个字符串形式的非负整数 num1 和 num2 ，计算它们的和并同样以字符串形式返回。
思路一：将较短的字符串交换到 num1 ，倒序遍历 num1 ，并与 num2 的对应位置和进位符号计算求和结果，根据结果更新进位符号；遍历结束，取出 num2 未遍历部分和进位符号计算求和，最后进行结果拼接得到输出；
class Solution(object): def addStrings(self, num1, num2): """ :type num1: str :type num2: str :rtype: str """ if len(num1) > len(num2): num1, num2 = num2, num1 flag = 0 out = [] for i in range(len(num1)): summ = int(num1[-i-1]) + int(num2[-i-1]) + flag if summ
思路二：在较短字符串的前置位补零至两字符串长度相等，取对应位置和进位符号计算求和结果，根据结果更新进位符号；遍历结束后只需要判断进位符号；
优化点：补零需要一次循环，对应位置相加也需要一次循环，这两个 !!循环可合并!!；
更新进位符号可用整除//和取余%
class Solution: def addStrings(self, num1: str, num2: str) -> str: res = "" i, j, carry = len(num1) - 1, len(num2) - 1, 0 while i >= 0 or j >= 0: #取最长长度，缺值赋0 n1 = int(num1[i]) if i >= 0 else 0 n2 = int(num2[j]) if j >= 0 else 0 tmp = n1 + n2 + carry carry = tmp // 10 #进位符用除 res = str(tmp % 10) + res #求和值用取余 i, j = i - 1, j - 1 return "1" + res if carry else res #处理最后的进位符
482
给定一个许可密钥字符串 s，仅由字母、数字字符和破折号组成。字符串由 n 个破折号分成 n + 1 组。我们想要重新格式化字符串 s，使每一组包含 k 个字符，除了第一组，它可以比 k 短，但仍然必须包含至少一个字符。此外，两组之间必须插入破折号，并且应该将所有小写字母转换为大写字母。返回 重新格式化的许可密钥 。
去除破折号转为大写：
1.s = (''.join(s.split('-'))).upper()
2.s = s.replace('-', '').upper()
思路一：原地修改，第一组长度为len(s)%k，此后每隔k个字符（取余结果相同）插入一次破折号；由于插入符号引起位置改变，需要调整指针；
class Solution(object): def licenseKeyFormatting(self, s, k): """ :type s: str :type k: int :rtype: str """ s = (''.join(s.split('-'))).upper() start = len(s) % k i = len(s)-1 while i > 0: if i % k == start: s = s[:i]+'-'+s[i:] i -= 1 return s思路二（优化点）：!!倒序插入!! 非原地修改时可用for循环中的step来控制长度
class Solution: def licenseKeyFormatting(self, s: str, k: int) -> str: s = s.upper().replace('-', '')[::-1] nub = 0 res = '' for i in range(0, len(s), k): res += s[i:i+k] + '-' return res[::-1].lstrip('-')-
解题思路
8
请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。
函数 myAtoi(string s) 的算法如下：
- 读入字符串并丢弃无用的前导空格
- 检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
- 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
- 将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
- 如果整数数超过 32 位有符号整数范围 [−2^31, 2^31−1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −2^31 的整数应该被固定为 −2^31 ，大于 2^31−1 的整数应该被固定为 2^31−1 。
- 返回整数作为最终结果。
丢弃前导空格：str.lstrip()
思路一：开启读数的情况：1.正负号；2.默认正号的第一个非零数值（仅第一个0需要手动跳过，后续0对计算无影响）；
结束读数的情况：开启读数后遇到第一个非数字字符
截断数值：1.不考虑溢出（python），记下结束读数的位置直接切片后强转，然后条件判断）
2.考虑溢出，就在读数时同步转换（优化点），在切换读数时判断是否可能溢出；
class Solution(object): def myAtoi(self, s): """ :type s: str :rtype: int """ s = s.lstrip() i, sign, out = 1, 1, 0 INT_MAX=2**31-1 INT_MIN=-2**31 if not s:return out if not ((s[0]>='0' and s[0]'0' and s[0]INT_MAX%10): return INT_MAX elif (out(-INT_MIN)%10): return INT_MIN else:out = out*10+sign*int(s[i]) i = i + 1 return out
补充：负数的除法和取余规律与正数不同
a = -2147483648//10 = -214748365 #向下取b = -(-(-2147483649))//10 = -214748364#可以通过添加符号得到预期结果
思路二：有限状态机
思路三：正则表达式
299
你在和朋友一起玩 猜数字 游戏，该游戏规则如下：
写出一个秘密数字，并请朋友猜这个数字是多少。朋友每猜测一次，你就会给他一个包含下述信息的提示：
- 猜测数字中有多少位属于数字和确切位置都猜对了（称为 "Bulls"，公牛），
- 有多少位属于数字猜对了但是位置不对（称为 "Cows"，奶牛）。也就是说，这次猜测中有多少位非公牛数字可以通过重新排列转换成公牛数字。
给你一个秘密数字 secret 和朋友猜测的数字 guess ，请你返回对朋友这次猜测的提示。
提示的格式为 "xAyB" ，x 是公牛个数， y 是奶牛个数，A 表示公牛，B 表示奶牛。
请注意秘密数字和朋友猜测的数字都可能含有重复数字。
思路一：先统计数字正确的个数，并根据位置信息分为公牛还是奶牛
数字正确的个数：使用计数器，取 secret 和 guess 中相同字符数量的最小值之和（优化点）取交集
位置正确的个数：对应位置相减，得0的数量
class Solution(object): def getHint(self, secret, guess): """ :type secret: str :type guess: str :rtype: str """ from collections import Counter s = Counter(secret) g = Counter(guess) AB, A = 0, 0 for i, j in g.items(): #数量正确 AB += min(s[i], j) #AB = sum(s & g).values() 交集 s & g 并集 s | g 差集 s - g for i, j in zip(secret, guess): #位置正确 if i == j: A += 1 return str(A)+'A'+str(AB-A)+'B'
思路二：同时遍历secret和guess，字符相等时记为公牛，字符不等时储存在各自的0-9数组中；母牛个数为各自数组中的最小值之和；
class Solution: def getHint(self, secret: str, guess: str) -> str: bulls = 0 cntS, cntG = [0] * 10, [0] * 10 for s, g in zip(secret, guess): if s == g: bulls += 1 else: cntS[int(s)] += 1 cntG[int(g)] += 1 cows = sum(min(s, g) for s, g in zip(cntS, cntG)) return f'{bulls}A{cows}B'522
给定字符串列表 strs ，返回其中 最长的特殊序列 的长度。如果最长特殊序列不存在，返回 -1 。
特殊序列 定义如下：该序列为某字符串 独有的子序列（即不能是其他字符串的子序列）。
s 的 子序列可以通过删去字符串 s 中的某些字符实现。
思路一：1.长度排序，如果最长字符串仅有一个，则输出该长度（最长特殊序列为其本身）；
2.如果最长字符串有多个，先在同长度上遍历找有没有相等的字符串（因为存在排序，相等字符串就在相邻位置，减少一层循环）；
3.若没有则输出该长度，若有则切换到下一长度，此时需要加入当前字符串是否是上一长度字符串的子串的判断；
4.遍历全部长度结束仍未输出，返回-1；
class Solution(object): def findLUSlength(self, strs): """ :type strs: List[str] :rtype: int """ strs = sorted(strs, key=lambda x:len(x),reverse=True) if len(strs[0]) > len(strs[1]): return len(strs[0]) else: for i,val in enumerate(strs): flag = 0 length = len(val) for j,vall in enumerate(strs): if length > len(vall):break #遍历到下一长度了,结束 elif i == j: continue #遍历元素本身,跳过 else: #判断val是不是vall的子串 m = n = 0 while m
trick：用continue跳过字符本身；设置flag记录本轮遍历子串情况
553
给定一正整数数组 nums，nums 中的相邻整数将进行浮点除法。例如， [2,3,4] -> 2 / 3 / 4 。
例如，nums = [2,3,4]，我们将求表达式的值 "2/3/4"。
但是，你可以在任意位置添加任意数目的括号，来改变算数的优先级。你需要找出怎么添加括号，以便计算后的表达式的值为最大值。
以字符串格式返回具有最大值的对应表达式。
分析：要求除法的计算结果最大，即分母越大分子越小，且题目给出的数组元素均>=2，所以除法操作只会使值变小；因此需要先通过除法将分母减小，保持分母不变即可得到答案——更像一道脑筋急转弯...
class Solution(object): def optimalDivision(self, nums): """ :type nums: List[int] :rtype: str """ length = len(nums) if length == 1: return str(nums[0]) elif length == 2: return str(nums[0])+'/'+str(nums[1]) else: out = str(nums[0]) for i in range(1,length): out= out+'/'+str(nums[i]) out=out[:out.index('/')+1]+'('+ out[out.index('/')+1:]+')' return out中插'/'可以用到join：'/'.join(map(str, nums[1:])) 这里还需要搭配map将数值变成字符
当数组元素可
-
-
-
-
