知识点： max，min
class Solution:
def computeArea(self, ax1: int, ay1: int, ax2: int, ay2: int, bx1: int, by1: int, bx2: int, by2: int) -> int:
a = (ax1 - ax2) * (ay1 - ay2)
b = (bx2 - bx1) * (by2 - by1)
w = min(ax2, bx2) - max(ax1, bx1)
h = min(ay2, by2) - max(ay1, by1)
c = max(w, 0) * max(h, 0)
return a + b - c
2、1957. 删除字符使字符串变好
知识点： 字符串（索引、切片、长度），len，!=，+=，in (not in) ，or 和 for。
教程：Python 1-09 字符串
class Solution:
def makeFancyString(self, s: str) -> str:
# n = len(s)
# if n < 3: return s
res = s[:2]
for c in s[2:]:
if c != res[-1] or c != res[-2]:
res += c
return res
3、1221. 分割平衡字符串
class Solution:
def balancedStringSplit(self, s: str) -> int:
res = d = 0
for ch in s:
d += (1 if ch == "R" else -1)
if d == 0: res += 1
return res
4、796. 旋转字符串
知识点： find，True，False，all，%
方法一：穷举法class Solution:
def rotateString(self, s: str, goal: str) -> bool:
m, n = len(s), len(goal)
if m != n: return False
if m == 0: return True
# if s == goal: return True
for i in range(n):
# if all(s[(i+j) % n] == goal[j] for j in range(n)):
# return True
s = s[1:] + s[0]
if s == goal: return True
return False
方法二：判断子串
先判断长度是否相同，不相同返回 False，其次拼接两个 s，则如果 goal 是由 s 旋转而成，则拼接后的 s 一定包含 goal。
class Solution:
def rotateString(self, s: str, goal: str) -> bool:
# if len(s) != len(goal): return False
# return goal in s * 2
# return len(s) == len(goal) and (s * 2).find(goal) != -1
return len(s) == len(goal) and goal in s * 2
5、1768. 交替合并字符串
方法一：
class Solution:
def mergeAlternately(self, word1: str, word2: str) -> str:
x, res = min(len(word1), len(word2)), ''
for i in range(x):
res += word1[i] + word2[i]
res += word1[x:] + word2[x:] # 处理剩余的部分
return res
方法二：队列，zip_longest
class Solution:
def mergeAlternately(self, word1: str, word2: str) -> str:
# a, b = deque(word1), deque(word2)
# res = ""
# while a and b:
# res += a.popleft()
# res += b.popleft()
# res += "".join(a) + "".join(b)
# return res
# from itertools import zip_longest
return "".join(sum(zip_longest(word1, word2, fillvalue=""), ()))
6、面试题 01.06. 字符串压缩
class Solution:
def compressString(self, S: str) -> str:
# n, res, i = len(S), '', 0
# while i < n:
# j = i
# while j < n and S[j] == S[i]:
# j += 1
# res += S[i] + str(j - i)
# i = j
if not S: return S
tmp, cnt, res = S[0], 0, ''
for c in S:
if c == tmp:
cnt += 1
else:
res += tmp + str(cnt)
tmp, cnt = c, 1
res += tmp + str(cnt)
return res if len(res) < len(S) else S
7、415. 字符串相加
知识点： divmod，//，%，str，int，if … else …
方法一：模拟设定 i，j 两指针分别指向 num1，num2 尾部，模拟人工加法；
计算进位： 计算 carry = tmp // 10，代表当前位相加是否产生进位；
添加当前位： 计算 tmp = n1 + n2 + carry，并将当前位 tmp % 10 添加至 res 头部；
索引溢出处理： 当指针 i 或 j 走过数字首部后，给 n1，n2 赋值为 0，相当于给 num1，num2 中长度较短的数字前面填 0，以便后续计算。
当遍历完 num1，num2 后跳出循环，并根据 carry 值决定是否在头部添加进位 1，最终返回 res 即可。
class Solution:
def addStrings(self, num1: str, num2: str) -> str:
res = ""
i, j, carry = len(num1) - 1, len(num2) - 1, 0
while i >= 0 or j >= 0:
n1 = int(num1[i]) if i >= 0 else 0
n2 = int(num2[j]) if j >= 0 else 0
tmp = n1 + n2 + carry
carry, rem = divmod(tmp, 10) # carry = tmp // 10 ;rem = tmp % 10
res = str(rem) + res
i, j = i - 1, j - 1 # i -= 1; j -= 1
return "1" + res if carry else res
# return str(int(num1) + int(num2))
434. 字符串中的单词数
方法一：split
class Solution:
def countSegments(self, s: str) -> int:
return len(s.split())
方法二：标记
class Solution:
def countSegments(self, s: str) -> int:
res = 0
flag = True
for c in s:
if c != ' ':
if flag:
res += 1
flag = False
else:
flag = True
return res
方法三：
class Solution:
def countSegments(self, s: str) -> int:
res = 0
for i, c in enumerate(s):
if (i == 0 or s[i-1] == ' ') and c != ' ':
res += 1
return res
1436. 旅行终点站
知识点： 列表 list，append。
教程：Python 1-14 列表
class Solution:
def destCity(self, paths: List[List[str]]) -> str:
start, end = [], []
for s, e in paths:
start.append(s)
end.append(e)
for x in end:
if x not in start:
return x
**知识点：**推导式，生成器，next。
教程：Python 推导式
class Solution:
def destCity(self, paths: List[List[str]]) -> str:
citiesA = {path[0] for path in paths}
return next(path[1] for path in paths if path[1] not in citiesA)
1. 两数之和
方法一：暴力解法
枚举数组中的每一个数 x，在 x 后面的元素中寻找 target - x。
知识点： 海象表达式 :=，双循环。
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(n:=len(nums)):
for j in range(i+1, n): # 从 i 后面找
if nums[i] + nums[j] == target:
return [i,j]
return []
方法二：
知识点： enumerate，index，异常处理 try … except … ，pass。
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i, element in enumerate(nums):
#if target-element in nums[i+1:]:
# return [i,nums.index(target-element,i+1)]
try:
j = nums.index(target-element,i+1)
return i, j
except:
pass
方法三：哈希表
知识点： 字典（dict）
教程：
- 哈希表 Hash table
- Python 中的可哈希对象与不可哈希对象
创建一个字典，对于每一个 x，首先查询哈希表中是否存在 target - x，如果存在，则返回结果，否则将 x 插入到哈希表中。
注意：方法一是对于 x，从后面找 target-x；方法二是先把 target-x 和它的下标放到字典中，然后对后面的 x 在字典中找 target-x。
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashtable = dict()
for i, right in enumerate(nums):
left = target - right
if left in hashtable:
return [hashtable[left], i]
hashtable[nums[i]] = i
return []
1544. 整理字符串
方法一：模拟
知识点： list，lower，append，pop，join，split，ord，chr。
教程：
从左到右扫描字符串 s 的每个字符。扫描过程中，维护当前整理好的字符串，记为 res。当扫描到字符 ch 时，有两种情况：
字符 ch 与字符串 res 的最后一个字符互为同一个字母的大小写：根据题意，两个字符都要在整理过程中被删除，因此要弹出 res 的最后一个字符；否则：两个字符都需要被保留，因此要将字符 ch 附加在字符串 res 的后面。
判断两个字母是否是互为大小写：
res[-1].lower() == ch.lower() and res[-1] != ch # 方法一
abs(ord(res[-1]) - ord(ch)) == 32: # 方法二：大小写字母 ASCII 值相差 32
ord(ch) ^ 32 == ord(res[-1]) # 方法三：运用异或判断是否互为大小写 ord('a') ^ 32 = ord('A'); ord('A') ^ 32 = ord('a');
ord() 函数是 chr() 函数（对于 8 位的 ASCII 字符串）的配对函数，它以一个字符串（Unicode 字符）作为参数，返回对应的 ASCII 数值，或者 Unicode 数值。
ord("中") # 20013
chr(20013) # '中'
class Solution:
def makeGood(self, s: str) -> str:
res = list()
for ch in s:
# if res and res[-1].lower() == ch.lower() and res[-1] != ch:
# if res and abs(ord(res[-1]) - ord(ch)) == 32: # 大小写字母 ASII 值相差 32
if res and ord(ch) ^ 32 == ord(res[-1]):
res.pop()
else:
res.append(ch)
return "".join(res)
