字符串"/>
Task04:字符串
Task04:字符串
- 1. 视频题目
- 1.1 验证回文串
- 1.1.1 描述
- 1.1.2 代码
- 1.1.3 总结
- 1.2 翻转字符串里的单词
- 1.2.1 描述
- 1.2.2 代码
- 1.2.3 总结
- 2. 作业题目
- 2.1 验证回文字符串 Ⅱ
- 2.1.1 描述
- 2.1.2 代码
- 2.1.3 总结
- 2.2 Excel表列名称
- 2.2.1 描述
- 2.2.1 代码
- 2.2.3 总结
- 2.3 字符串解码
- 2.3.1 描述
- 2.3.2 代码
- 2.3.3 总结
1. 视频题目
1.1 验证回文串
1.1.1 描述
给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。
说明:本题中,我们将空字符串定义为有效的回文串。
示例 1:
输入: “A man, a plan, a canal: Panama”
输出: true
解释:“amanaplanacanalpanama” 是回文串
示例 2:
输入: “race a car”
输出: false
解释:“raceacar” 不是回文串
提示:
1 <= s.length <= 2 * 105
字符串 s 由 ASCII 字符组成
1.1.2 代码
理论上来说应该上双指针,一个在前一个在后,同时开始扫描
如果遇到字母就比较,相同的继续扫描,不同的就跳出报错
如果遇到空格或者逗号一类的,直接继续向下扫描,遇到字母再停下比较
其中有必要注意一下python
语言当中对于字符床的几个函数的用法
isdigit
是纯数字,isalpha
是纯字母,isalnum
是数字和字母混合
如果isalnum
单独遇到纯数字的串或者是纯字母的串也是True
下面的解法取巧了,直接取字母,然后反转对比,因为回文串正反相同
class Solution:def isPalindrome(self, s: str) -> bool:sgood = "".join(ch.lower() for ch in s if ch.isalnum())return sgood == sgood[::-1]
1.1.3 总结
isdigit
是纯数字,isalpha
是纯字母,isalnum
是数字和字母混合
如果isalnum
单独遇到纯数字的串或者是纯字母的串也是True
回文串正反相同,所以可以直接反转串然后用API
进行比较
1.2 翻转字符串里的单词
1.2.1 描述
给你一个字符串 s ,逐个翻转字符串中的所有 单词 。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。
说明:
输入字符串 s 可以在前面、后面或者单词间包含多余的空格。
翻转后单词间应当仅用一个空格分隔。
翻转后的字符串中不应包含额外的空格。
示例 1:
输入:s = “the sky is blue”
输出:“blue is sky the”
示例 2:
输入:s = " hello world "
输出:“world hello”
解释:输入字符串可以在前面或者后面包含多余的空格,但是翻转后的字符不能包括。
示例 3:
输入:s = “a good example”
输出:“example good a”
解释:如果两个单词间有多余的空格,将翻转后单词间的空格减少到只含一个。
示例 4:
输入:s = " Bob Loves Alice "
输出:“Alice Loves Bob”
示例 5:
输入:s = “Alice does not even like bob”
输出:“bob like even not does Alice”
提示:
1 <= s.length <= 104
s 包含英文大小写字母、数字和空格 ’ ’
s 中 至少存在一个 单词
进阶:
请尝试使用 O(1) 额外空间复杂度的原地解法。
1.2.2 代码
如果用额外空间的话,应该是建立一个栈,然后去扫描原数组
从头开始,去除多余的空格,再遇到空格证明单词结束
然后将单词压入栈内,继续扫描原数组内后续的其他单词
等到全部扫描结束,从栈顶依次取出元素,以空格相连接
如果用API
的话,就是split()
再reversed
class Solution:def reverseWords(self, s: str) -> str:return " ".join(reversed(s.split()))
1.2.3 总结
很多语言的API
都支持join
、split()
和reversed
2. 作业题目
2.1 验证回文字符串 Ⅱ
2.1.1 描述
给定一个非空字符串 s,最多删除一个字符。判断是否能成为回文字符串。
示例 1:
输入: s = “aba”
输出: true
示例 2:
输入: s = “abca”
输出: true
解释: 你可以删除c字符。
示例 3:
输入: s = “abc”
输出: false
提示:
1 <= s.length <= 105
s 由小写英文字母组成
2.1.2 代码
思路基本延续上面的验证回文串,只不过条件是可以删去一个字符
那就是遇到字符不相等的时候,分别删除一下左右,看看哪个操作可能相等
class Solution:def validPalindrome(self, s: str) -> bool:def checkPalindrome(low, high):i, j = low, highwhile i < j:if s[i] != s[j]:return Falsei += 1j -= 1return Truelow, high = 0, len(s) - 1while low < high:if s[low] == s[high]: low += 1high -= 1else:return checkPalindrome(low + 1, high) or checkPalindrome(low, high - 1)return True
2.1.3 总结
删除的这一个字符可能是左边的也可能是右边的,都要尝试
2.2 Excel表列名称
2.2.1 描述
给你一个整数 columnNumber ,返回它在 Excel 表中相对应的列名称。
例如:
A -> 1
B -> 2
C -> 3
…
Z -> 26
AA -> 27
AB -> 28
…
示例 1:
输入:columnNumber = 1
输出:“A”
示例 2:
输入:columnNumber = 28
输出:“AB”
示例 3:
输入:columnNumber = 701
输出:“ZY”
示例 4:
输入:columnNumber = 2147483647
输出:“FXSHRXW”
提示:
1 < = c o l u m n N u m b e r < = 2 31 − 1 1<= columnNumber <= 2^{31} - 1 1<=columnNumber<=231−1
2.2.1 代码
看起来就是一个进制转换的问题,但是因为偏移了一位,题解看着头大
假设现在表格当中的某一列的列名是ABCD
的这四个字母,则其意义如下:
A | B | C | D |
---|---|---|---|
1 ∗ 2 6 3 1*26^3 1∗263 | 2 ∗ 2 6 2 2*26^2 2∗262 | 3 ∗ 2 6 1 3*26^1 3∗261 | 4 ∗ 2 6 0 4*26^0 4∗260 |
一般来说,每一位字母所代表数字,都遵循 a i + 2 6 i − 1 a_i+26^{i-1} ai+26i−1这个格式
对于通常的26
进制, a i a_i ai的取值范围是0~25
,但此时为1~26
,有1
位的偏移
所以说,也就是说,余数为0
代表Z
,余数为1
代表A
,所以要在取余前-1
,校正位置
还是上面的例子,其数值为 1 ∗ 2 6 3 + 2 ∗ 2 6 2 + 3 ∗ 2 6 1 + 4 ∗ 2 6 0 1*26^3+2*26^2+3*26^1+4*26^0 1∗263+2∗262+3∗261+4∗260 ,直接对26
取余为4
4
代表的是D
,在1~26
的情况下,也就是对于A
有3
位的偏移,所以需要-1
但是需要先-
再取余,因为这样可以使得余数在0~25
之间,刚好就是相对于A
的偏移量
如果是先取余再-
的话,会使得A~Z
余数变为0,1...,24,-1
,不便于基于A
计算字母的值
每次-1
后计算余数,针对的都是当前的最后一位,这个-1
不会对其他位置的数字造成影响
因为每个字母遵循 a i + 2 6 i − 1 a_i+26^{i-1} ai+26i−1,题目给的数值columnNumber
也就是这个格式的和
所以每次的-1
,只会影响最右边的 a i a_i ai,也就是 a 0 a_0 a0,不会影响其他位置的数字
每当求出 a 0 a_0 a0对应的字母之后,都需要用//
去除这一位,再去-1
计算新的 a 0 a_0 a0
class Solution:def convertToTitle(self, columnNumber: int) -> str:ans = list()while columnNumber > 0:columnNumber -= 1ans.append(chr(columnNumber % 26 + ord("A")))columnNumber //= 26return "".join(ans[::-1])
2.2.3 总结
继续以上面的例子进行说明, a i + 2 6 i − 1 a_i+26^{i-1} ai+26i−1, 1 ∗ 2 6 3 + 2 ∗ 2 6 2 + 3 ∗ 2 6 1 + 4 ∗ 2 6 0 1*26^3+2*26^2+3*26^1+4*26^0 1∗263+2∗262+3∗261+4∗260
在这样的格式下,即便有偏移量,那也影响的是每一个 a i a_i ai,而且相互之间不影响
也就是说只需要每一次求 a 0 a_0 a0的时候,-1
再求余就可以映射到0~25
,不影响其他位
2.3 字符串解码
2.3.1 描述
给定一个经过编码的字符串,返回它解码后的字符串。
编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。
此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入。
示例 1:
输入:s = “3[a]2[bc]”
输出:“aaabcbc”
示例 2:
输入:s = “3[a2[c]]”
输出:“accaccacc”
示例 3:
输入:s = “2[abc]3[cd]ef”
输出:“abcabccdcdcdef”
示例 4:
输入:s = “abc3[cd]xyz”
输出:“abccdcdcdxyz”
提示:
1 <= s.length <= 30
s 由小写英文字母、数字和方括号 ‘[]’ 组成
s 保证是一个 有效 的输入。
s 中所有整数的取值范围为 [1, 300]
2.3.2 代码
本题比较复杂的,主要是括号套括号的情况,不过我们先从一般的开始
假设没有套括号,那我们应该是分为两部分,一个是数字,一个是字符串
数字可能不止一位,所以要考虑读到第二位数字时,给第一位数字进位
如果读到左括号[
,那就是开始了字符串,读到]
是字符串终止
将此次的重复次数,乘上需要重复的字符串,连上之前的字符串即可
现在考虑回题目本身,如果出现了括号套括号,那应该先处理括号内
得到括号内的结果后,才能结合前面的重复次数,做本次字符串的重复
所以如果有内括号,那我们需要记住之前的字符串,以及本次的重复次数
当内括号的字符串处理完毕之后,再根据数字重复字符串并且拼接
括号还有可能套三层的情况,也就是先记录的结果后处理,这就是栈啊
如果一般化来说,那就是每次遇到[
就把重复次数
和之前的字符串
压栈
然后处理括号内的情况,即读取字符串,读到]
再取栈顶,重复并拼接
如果在[
之后再遇到[
,那就是继续压栈,直到遇到]
才弹出栈顶,结束一对[]
class Solution:def decodeString(self, s: str) -> str:stack = []# 栈,用于处理括号套括号的情况res = ""# 用于存储当前重复的字符串multi = 0# 用于存储字符串重复的次数for c in s:if c == '[':stack.append([multi, res])res, multi = "", 0# 将之前的字符串,和这次字符串重复的次数存起来elif c == ']':cur_multi, last_res = stack.pop()res = last_res + cur_multi * res# 重复此次的字符串,并连接之前的字符串elif '0' <= c <= '9':multi = multi * 10 + int(c)# 如果数字不止一位,那就进位叠加else:res += c# 用于存储当前的字符串return res
2.3.3 总结
如果字符串的数字不止一位,要考虑读到第二位数字时,给第一位数字进位
有括号套括号,而且优先处理括号内,可以考虑将之前的数据压入栈中
听起来有点像是括号匹配的进阶版,[
压栈,遇到]
就弹栈顶匹配
更多推荐
Task04:字符串
发布评论