反转字符串
2021-03-24
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
方法一：切片、reverse
s.reverse()
s = s[::-1]
方法二：双指针，对称交换
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
n = len(s)
for i in range(n//2):
s[i],s[n-1-i] = s[n-1-i],s[i]
整数反转
2021-03-24
给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−2^31, 2^31 − 1] ，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。
先反转数，再判断数是否在范围内。
方法一：将x%10，放到数组中，然后再组合起来。
def reverse(self, x: int) -> int:
a = 1
if x < 0:
x = -x
a = -1
result = 0
while x > 0:
result = result*10 + x%10
x = x//10
result = result * a
if result < -2**31 or result > 2**31-1:
return 0
return result
方法二：整数转字符串，字符串反转。
def reverse(self, x: int) -> int:
a = str(x)
if a[0] == '-':
# a[1:][::-1] 先取从除首位以外的数，然后反转
result = '-' + a[1:][::-1]
else:
result = a[::-1]
result = int(result)
if result < -2 ** 31 or result > 2 ** 31 - 1:
return 0
return result
字符串中的第一个唯一字符
2021-03-25
给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
解法：遍历字符，记录每个字符出现的次数到字典中。再遍历字典，如果值为1，则key为第一个唯一字符。返回该字符的位置。
def firstUniqChar(self, s: str) -> int:
sd = dict()
for i in range(len(s)):
sd[s[i]] = sd.get(s[i], 0)+1
for i,key in enumerate(sd):
if sd[key] == 1:
return i
return -1
有效的字母异位词
2021-03-26
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
方法一：统计每个字符串中字符出现的次数
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
fre_s = collections.Counter(s)
fre_t = collections.Counter(t)
return fre_s == fre_t
方法二：两个字符串排序，然后看两个字符串是否一样
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
sa = list(s)
st = list(t)
sa.sort()
st.sort()
for i in range(len(s)):
if sa[i] != st[i]:
return False
return True
验证回文串
2021-03-26
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
方法一：双指针。一个从前向后一个从后向前，遇到非字母、数字就跳过。如果两个指针所指的字符不等，则不是回文。
def isPalindrome(self, s: str) -> bool:
s= s.lower()
start = 0
end = len(s)-1
while start < end:
if not (s[start].isalpha() or s[start].isdigit()):
start += 1
continue
if not (s[end].isalpha() or s[end].isdigit()):
end -= 1
continue
if s[start] != s[end]:
return False
start += 1
end -= 1
return True
字符串转换整数 (atoi)
2021-03-28
请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。
解法：
1、去掉前置空格
2、判断是正数还是负数
3、获取数字
4、判断数字大小是否超过范围
def myAtoi(self, s: str) -> int:
s = s.lstrip()
if len(s) == 0:
return 0
res = 0
a = 1
index = 0
if s[index] == '-':
a = -1
index += 1
elif s[index] == '+':
a= 1
index += 1
while index < len(s):
if s[index].isdigit():
res = res*10 + int(s[index])
else:
break
index += 1
res = res*a
if res < -2**31:
res = -2**31
elif res > 2**31-1:
res = 2**31-1
return res
实现 strStr()
2021-03-28
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
解法：双指针。一个遍历字符A，一个遍历字符B。如果A[index1]等于B[index2]，两个指针各加1。如果不相等，index1回到从相等处+1的位置，index2重置为0.
def strStr(self, haystack: str, needle: str) -> int:
if len(needle) == 0:
return 0
if len(haystack) < len(needle):
return -1
index1 = 0
index2 = 0
while index1 < len(haystack) and index2 < len(needle):
if haystack[index1] == needle[index2]:
index1 += 1
index2 += 1
else:
index1 = index1 - index2 +1
index2 = 0
if index2 == len(needle):
return index1 - index2
return -1
外观数列
2021-03-29
给定一个正整数 n ，输出外观数列的第 n 项。
「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。
你可以将其视作是由递归公式定义的数字字符串序列：
解法：双指针。
def countAndSay(self, n: int) -> str:
num = '1'
for i in range(1, n):
index = 0
count = 0
cur = num[0]
now = ''
while index < len(str(num)):
if cur == num[index]:
count += 1
else:
now += str(count)
now += cur
cur = num[index]
count = 1
index += 1
now += str(count)
now += cur
num = now
return num
最长公共前缀
2021-03-29
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
解法：将strs[0]作为前缀，然后和之后的每一个字符做比较。遇到不一样的字符，则将当前位置作为前缀的长度。若长度为0，则不存在公共前缀。
def longestCommonPrefix(self, strs: List[str]) -> str:
if len(strs) == 0:
return ""
length = len(strs[0])
for i in range(1, len(strs)):
j = 0
while j < length and j < len(strs[i]):
if strs[0][j] != strs[i][j]:
length = j
break
j += 1
length = min(length, len(strs[i]))
if length == 0:
return ""
return strs[0][:length]
网友评论