反轉(zhuǎn)字符串
2021-03-24
編寫(xiě)一個(gè)函數(shù)，其作用是將輸入的字符串反轉(zhuǎn)過(guò)來(lái)。輸入字符串以字符數(shù)組 char[] 的形式給出。
不要給另外的數(shù)組分配額外的空間，你必須原地修改輸入數(shù)組、使用 O(1) 的額外空間解決這一問(wèn)題。
你可以假設(shè)數(shù)組中的所有字符都是 ASCII 碼表中的可打印字符。
方法一：切片、reverse
s.reverse()
s = s[::-1]
方法二：雙指針，對(duì)稱交換
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]
整數(shù)反轉(zhuǎn)
2021-03-24
給你一個(gè) 32 位的有符號(hào)整數(shù) x ，返回將 x 中的數(shù)字部分反轉(zhuǎn)后的結(jié)果。
如果反轉(zhuǎn)后整數(shù)超過(guò) 32 位的有符號(hào)整數(shù)的范圍 [?2^31, 2^31 ? 1] ，就返回 0。
假設(shè)環(huán)境不允許存儲(chǔ) 64 位整數(shù)（有符號(hào)或無(wú)符號(hào)）。
先反轉(zhuǎn)數(shù)，再判斷數(shù)是否在范圍內(nèi)。
方法一：將x%10，放到數(shù)組中，然后再組合起來(lái)。
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
方法二：整數(shù)轉(zhuǎn)字符串，字符串反轉(zhuǎn)。
def reverse(self, x: int) -> int:
a = str(x)
if a[0] == '-':
# a[1:][::-1] 先取從除首位以外的數(shù)，然后反轉(zhuǎn)
result = '-' + a[1:][::-1]
else:
result = a[::-1]
result = int(result)
if result < -2 ** 31 or result > 2 ** 31 - 1:
return 0
return result
字符串中的第一個(gè)唯一字符
2021-03-25
給定一個(gè)字符串，找到它的第一個(gè)不重復(fù)的字符，并返回它的索引。如果不存在，則返回 -1。
解法：遍歷字符，記錄每個(gè)字符出現(xiàn)的次數(shù)到字典中。再遍歷字典，如果值為1，則key為第一個(gè)唯一字符。返回該字符的位置。
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
給定兩個(gè)字符串 s 和 t ，編寫(xiě)一個(gè)函數(shù)來(lái)判斷 t 是否是 s 的字母異位詞。
方法一：統(tǒng)計(jì)每個(gè)字符串中字符出現(xiàn)的次數(shù)
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
方法二：兩個(gè)字符串排序，然后看兩個(gè)字符串是否一樣
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
驗(yàn)證回文串
2021-03-26
給定一個(gè)字符串，驗(yàn)證它是否是回文串，只考慮字母和數(shù)字字符，可以忽略字母的大小寫(xiě)。
方法一：雙指針。一個(gè)從前向后一個(gè)從后向前，遇到非字母、數(shù)字就跳過(guò)。如果兩個(gè)指針?biāo)傅淖址坏?，則不是回文。
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
字符串轉(zhuǎn)換整數(shù) (atoi)
2021-03-28
請(qǐng)你來(lái)實(shí)現(xiàn)一個(gè) myAtoi(string s) 函數(shù)，使其能將字符串轉(zhuǎn)換成一個(gè) 32 位有符號(hào)整數(shù)（類似 C/C++ 中的 atoi 函數(shù)）。
解法：
1、去掉前置空格
2、判斷是正數(shù)還是負(fù)數(shù)
3、獲取數(shù)字
4、判斷數(shù)字大小是否超過(guò)范圍
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
實(shí)現(xiàn) strStr()
2021-03-28
給定一個(gè) haystack 字符串和一個(gè) needle 字符串，在 haystack 字符串中找出 needle 字符串出現(xiàn)的第一個(gè)位置 (從0開(kāi)始)。如果不存在，則返回 -1。
解法：雙指針。一個(gè)遍歷字符A，一個(gè)遍歷字符B。如果A[index1]等于B[index2]，兩個(gè)指針各加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
外觀數(shù)列
2021-03-29
給定一個(gè)正整數(shù) n ，輸出外觀數(shù)列的第 n 項(xiàng)。
「外觀數(shù)列」是一個(gè)整數(shù)序列，從數(shù)字 1 開(kāi)始，序列中的每一項(xiàng)都是對(duì)前一項(xiàng)的描述。
你可以將其視作是由遞歸公式定義的數(shù)字字符串序列：
解法：雙指針。
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
最長(zhǎng)公共前綴
2021-03-29
編寫(xiě)一個(gè)函數(shù)來(lái)查找字符串?dāng)?shù)組中的最長(zhǎng)公共前綴。
如果不存在公共前綴，返回空字符串 ""。
解法：將strs[0]作為前綴，然后和之后的每一個(gè)字符做比較。遇到不一樣的字符，則將當(dāng)前位置作為前綴的長(zhǎng)度。若長(zhǎng)度為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]
