字符串

1. 反转字符串

编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

1
2
3
4
5
输入:["h","e","l","l","o"]
输出:["o","l","l","e","h"]

输入:["H","a","n","n","a","h"]
输出:["h","a","n","n","a","H"]

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
s[:] = s[::-1]

class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
s.reverse()

2. 整数反转

给出一个32位有符号的整数,你需要将这个整数中的每一位上的数字进行反转。

1
2
3
4
5
6
7
8
输入: 123
输出: 321

输入: -123
输出: -321

输入: 120
输出: 21

实现思路
反转整数从一个数的最后以为开始,一次向前遍历,每次反转整数依次左移一位,并取出一位数作为新的数的个位数。

  • 记录temp = res*10 + x % 10
  • 然后比较 temp / 10 和 res 是否相等,如果相等则表明没有溢出,否则溢出直接返回0
  • 最后将temp赋值给res,并令 x /= 10去掉最后一位,继续反转之前的数字

代码实现

1
2
3
4
5
6
7
8
9
10
11
class Solution:
def reverse(self, x: int) -> int:
temp_x = x if x > 0 else -x
result = 0
while temp_x:
temp_result = result * 10 + temp_x % 10
if temp_result < -2**31 or temp_result > 2**31 - 1:
return 0
result = temp_result
temp_x = int(temp_x / 10)
return result if x > 0 else -result

3. 字符串中的第一个唯一字符

给定一个字符串,找到它的第一个不重复的字符,并返回它的索引。如果不存在,则返回 -1。

1
2
3
4
5
s = "leetcode"
返回 0.

s = "loveleetcode",
返回 2.

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
def firstUniqChar(self, s: str) -> int:
if not s.isalpha():
return -1
count = dict()
for c in s:
if c in count:
count[c] += 1
else:
count[c] = 1
for i in range(len(s)):
if count[s[i]] == 1:
return i
return -1

# 一个简洁的代码
class Solution:
def firstUniqChar(self, s: str) -> int:
letters='abcdefghijklmnopqrstuvwxyz'
index=[s.index(l) for l in letters if s.count(l) == 1]
return min(index) if len(index) > 0 else -1

4. 有效的字母异位词

给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。

1
2
3
4
5
输入: s = "anagram", t = "nagaram"
输出: true

输入: s = "rat", t = "car"
输出: false

实现思路
统计两个字符串中各个字母出现的次数,相同则返回True,否则返回False

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
count_1 = collections.Counter(s)
count_2 = collections.Counter(t)
return operator.eq(count_1, count_2)

class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s)!= len(t):
return False
c = set(s)
for i in c:
if s.count(i) != t.count(i):
return False
return True

5. 验证回文字符串

给定一个字符串,验证它是否是回文串,只考虑字母数字字符,可以忽略字母的大小写。
说明:本题中,我们将空字符串定义为有效的回文串

代码实现

1
2
3
4
class Solution:
def isPalindrome(self, s: str) -> bool:
s = [i.lower() for i in s if i.isalpha() or i.isdigit()]
return s == s[::-1]

6. 字符串转整数

请你来实现一个 atoi 函数,使其能将字符串转换成整数。

首先,该函数会根据需要丢弃无用的开头空格字符,直到寻找到第一个非空格的字符为止。

当我们寻找到的第一个非空字符为正或者负号时,则将该符号与之后面尽可能多的连续数字组合起来,作为该整数的正负号;假如第一个非空字符是数字,则直接将其与之后连续的数字字符组合起来,形成整数。

该字符串除了有效的整数部分之后也可能会存在多余的字符,这些字符可以被忽略,它们对于函数不应该造成影响。

注意:假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时,则你的函数不需要进行转换。

在任何情况下,若函数不能进行有效的转换时,请返回 0。

说明:

假设我们的环境只能存储 32 位大小的有符号整数,那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围,qing返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution:
def myAtoi(self, str: str) -> int:
str = str.strip()
if len(str) == 0:
return 0
sign, res = 1, '0'
if str[0] == '+':
str = str[1:]
elif str[0] == '-':
str = str[1:]
sign = -1
if len(str) == 0:
return 0
for i in str:
if i.isdigit():
res += i
else:
break
res = sign * int(res)
if res > 2**31 - 1:
return 2**31 - 1
elif res < -2**31:
return -2**31
else:
return res

# 正则表达式
class Solution:
def myAtoi(self, str_in):
str = str.strip()
str = re.findall('(^[\+\-0]*\d+)\D*', str)

try:
result = int(''.join(str))
MAX_INT = 2147483647
MIN_INT = -2147483648
if result > MAX_INT > 0:
return MAX_INT
elif result < MIN_INT < 0:
return MIN_INT
else:
return result
except:
return 0

7. 实现 strStr()

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回-1。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if len(needle.strip()) == 0:
# needle为空或者是空字符串的时候应该返回0
return 0
n = len(needle)
m = len(haystack)
for i in range(m):
if haystack[i] == needle[0] and i + n <= m:
if haystack[i:i+n] == needle:
return i
return -1

class Solution:
def strStr(self, haystack: str, needle: str) -> int:
return haystack.index(needle) if needle in haystack else -1

class Solution:
def strStr(self, haystack: str, needle: str) -> int:
return haystack.find(needle)

class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if needle is None or needle=="":
return 0
else:
if needle in haystack:
return haystack.index(needle)
else:
return -1

8. 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 “”。

1
2
3
4
5
6
输入: ["flower","flow","flight"]
输出: "fl"

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
"""
只需要比较逐个字母ASCII码值,谁先出现小于的话,则为最小值
"""
if not strs:
return ''
min_str = min(strs)
max_str = max(strs)
for i, c in enumerate(min_str):
if c != max_str[i]:
return min_str[:i]
return min_str

9. 报数

报数序列是一个整数序列,按照其中的整数的顺序进行报数,得到下一个数。其前五项如下:

1
2
3
4
5
1.     1
2. 11
3. 21
4. 1211
5. 111221

1 被读作 "one 1" (“一个一”) , 即 11
11 被读作 "two 1s" (“两个一”), 即 21
21 被读作 "one 2", "one 1" (”一个二” , “一个一”) , 即 1211

给定一个正整数 n(1 ≤ n ≤ 30),输出报数序列的第 n 项。
注意:整数顺序将表示为一个字符串。

1
2
3
4
5
输入: 1
输出: "1"

输入: 4
输出: "1211"

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution:
def countAndSay(self, n: int) -> str:
if n == 1:
return '1'
elif n == 2:
return '11'
else:
pre = '11'
for i in range(3, n+1): # 外层循环
res, cnt = '', 1
for j in range(1, len(pre)): # 循环前一次的报数
if pre[j - 1] == pre[j]: # 当前的字符和前一个字符相同,则需要记一次数
cnt += 1
else: # 否则进行新的拼接和重置计数
res = res + str(cnt) + pre[j - 1]
cnt = 1
# 完成最后一个元素的拼接
res = res + str(cnt) + pre[j]
# 执行下一轮循环前将res变成前一次的报数
pre = res
return res

class Solution:
def countAndSay(self, n: int) -> str:

if n == 1:
return '1' # 递归出口
s = self.countAndSay(n-1)
res, count = '', 0
for i in range(len(s)):
count += 1
if i == len(s) - 1 or s[i] != s[i+1]: # 最后一个字符串要提前终止
res += str(count)
res += s[i]
count = 0
return res

class Solution:
def countAndSay(self, n: int) -> str:
nums = '1'
for _ in range(1, n):
a = nums[0]
count = 0
L_Nums = ''
for num in nums:
if a == num:
count += 1
else:
L_Nums = L_Nums + str(count) + str(a)
a = num
count = 1
if count:
L_Nums = L_Nums + str(count) + str(a)
nums = L_Nums

return nums