字符串
1. 判断两个字符串是否是：同字母异序词
LeetCode 242. Valid Anagram (Easy)
使用列表实现的哈希表存储s串字符出现的次数，遍历t串字符，对哈希表中的字符进行减法操作，如果出现负数，那么字符数量不匹配，返回False，如果遍历完成不返回False，那么字符串是匹配的，返回True。
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t): return False
hashMap = [0 for _ in range(26)]
for ch in s:
hashMap[ord(ch)-97] += 1
for ch in t:
hashMap[ord(ch)-97] -= 1
if hashMap[ord(ch)-97] < 0:
return False
return True
2. 可构成回文串的最大长度
LeetCode 409. Longest Palindrome (Easy)
回文串一定是轴对称的。也就是中间的串可以单独出现，两边的串一定是成对出现的。那么出现偶数次的字符一定可以构成回文串。出现奇数次的字符，将其进行减一操作也可以放在两边。最后在中间添加一个奇数个字符即可构成最长串。
class Solution:
def longestPalindrome(self, s: str) -> int:
res, Odd = 0, 0
hashMap = [0 for _ in range(52)]
for ch in s:
hashMap[ord(ch)-97] += 1
for item in hashMap:
if item % 2 == 0:
res += item
else:
res += item - 1
Odd = 1
return res if Odd == 0 else res + 1
3. 同构字符串判断
LeetCode 205. Isomorphic Strings (Easy)
s串中的字符映射到t串中的对应位置字符上去。相同的字符不能映射到不同的字母上去如:
s = 'foo', t = 'bar'; f -> b, o -> a, o -> b发生冲突。但是s = 'bar', t = 'foo': b -> f, a -> o, r -> o.这种情形就不能利用哈希表的单向查找来解决。下面给出的解法是通过两次相反的遍历操作来规避这样的问题。两次遍历都没发生上述情形，则返回True。（这里使用的是时间换空间的方法，我觉得应该还有空间换时间的方法来解决这个问题。）
class Solution:
def isIsomorphic(self, s: str, t: str) -> bool:
if not s or not t: return True
hashMap = {}
for i in range(len(s)):
if t[i] not in hashMap:
hashMap[t[i]] = s[i]
else:
if hashMap[t[i]] != s[i]:
return False
hashMap = {}
for i in range(len(s)):
if s[i] not in hashMap:
hashMap[s[i]] = t[i]
else:
if hashMap[s[i]] != t[i]:
return False
return True
4. 回文子字符串个数
LeetCode 647. Palindromic Substrings (Medium)
方法一：暴力循环时间复杂度为 三层循环。创建一个判断是否回文串的函数。从长度为1到整个字符串遍历数组，依次判断该串是否回文。超时！
方法二：时间复杂度为 ，两层循环，省去了单独判断是否回文串的一层循环。
从头遍历字符串中的每一个元素，从当前位置开始向左右延伸，每次延伸一个长度，如果延伸的同时两边符合回文串的性质，那么向最终结果中+1。循环的结束条件是不越界且当前状态是一个回文串。
# 方法一：
class Solution:
def countSubstrings(self, s: str) -> int:
total = len(s)
for i in range(2, len(s)+1):
left, right = 0, i-1
while right < len(s):
if self.judge(s[left:right+1]):
total += 1
left += 1
right += 1
else:
left += 1
right += 1
return total
def judge(self, s):
left, right = 0, len(s)-1
while left < right:
if s[left] == s[right]:
left += 1
right -= 1
continue
else:
return False
return True
# 方法二
class Solution:
def __init__(self):
self.cnt = 0
def countSubstrings(self, s: str) -> int:
for i in range(len(s)):
self.extend(s, i, i)
self.extend(s, i, i + 1)
return self.cnt
def extend(self, s, start, end):
while start >= 0 and end < len(s) and s[start] == s[end]:
start -= 1
end += 1
self.cnt += 1
5. 判断一个整数是否是回文数
LeetCode 9. Palindrom Number (Easy)
考虑两个数1221，和12321.前面一个数偶数位，后面一个数奇数位。我们只需要求解一半即可。使用最简单的while循环来判断。
class Solution:
def isPalindrome(self, x: int) -> bool:
if x == 0: return True
if x < 0 or x % 10 == 0: return False
half = 0
while x > half:
half = half * 10 + x % 10
x //= 10
return x == half or x == half // 10
6. 统计二进制字符串中连续1和连续0数量相同的子字符串个数
LeetCode 696. Count Binary Substrings (Easy)
本题可以将原来串中的序列进行分组统计到一个列表中。形如下面两种情况所示
s = "110001111000000", the groups = [2, 3, 4, 6]
s = "10101", the groups = [1, 1, 1, 1, 1]
方法一：使用groups数组统计不同字符的次数。
连续的1和0数量相同的子串，一定存在相邻的两个分组内。加入是这种情形s = "11000", groups = [2, 3],那么可以生成的串有1100, 10两种情况，可以发现，可以形成的数量取决于较小的那个值。两次循环，时间复杂度为
，空间复杂度为
。实现代码如下：
方法二：直接通过一次遍历同时记录相邻1和0的出现此处，并计算结果去最小值到res中去，时间复杂度是 ，空间复杂度为 。因为少了一次循环，比方法一的速度要快。
# 方法一
class Solution:
def countBinarySubstrings(self, s: str) -> int:
# s = "110001111000000", then groups = [2, 3, 4, 6]
# s = "10101", the groups = [1, 1, 1, 1, 1]
group, res = [1], 0
for i in range(1, len(s)):
if s[i] == s[i-1]:
group[-1] += 1
else:
group.append(1)
for i in range(1, len(group)):
res += min(group[i], group[i-1])
return res
# 方法二
class Solution(object):
def countBinarySubstrings(self, s):
ans, prev, cur = 0, 0, 1
for i in range(1, len(s)):
if s[i-1] != s[i]:
ans += min(prev, cur)
prev, cur = cur, 1
else:
cur += 1
return ans + min(prev, cur)
转载：https://blog.csdn.net/weixin_46391502/article/details/106561964