33/224-226
224-226
https://github.com/qwen233/224-226/blob/master/226/README.md
226. Palindrome Permutation
给一个字符串，检查是否可以通过重排列的方式使其成为回文串
1. 使用一个哈希表来存储每个字符的出现次数
2. 遍历哈希表，如果出现次数为奇数且不为1，则无法重排
3. 最后返回哈希表中的元素个数是否为奇数，因为奇数个回文串必须有一个字符出现奇数次
```
class Solution:
def canPermutePalindrome(self, s: str) -> bool:
# 1. 使用一个哈希表来存储每个字符的出现次数
hash_table = dict()
for char in s:
if char in hash_table:
hash_table[char] += 1
else:
hash_table[char] = 1
# 2. 遍历哈希表，如果出现次数为奇数且不为1，则无法重排
for key, value in hash_table.items():
if value % 2 != 0 and value != 1:
return False
# 3. 最后返回哈希表中的元素个数是否为奇数，因为奇数个回文串必须有一个字符出现奇数次
return len(hash_table) % 2 == 0
```
225. Implement Stack using Queues
给定两个队列，实现一个栈的接口
```
class MyStack:
def __init__(self):
"""
Initialize your data structure here.
"""
self.queue1 = deque()
self.queue2 = deque()
def push(self, x: int) -> None:
"""
Push element x onto stack.
"""
self.queue1.append(x)
def pop(self) -> int:
"""
Removes the element on top of the stack.
"""
if not self.queue1:
return None
while len(self.queue1) > 1:
self.queue2.append(self.queue1.popleft())
res = self.queue1.popleft()
self.queue1, self.queue2 = self.queue2, self.queue1
return res
def top(self) -> int:
"""
Get the top element.
"""
if not self.queue1:
return None
while len(self.queue1) > 1:
self.queue2.append(self.queue1.popleft())
res = self.queue1.popleft()
self.queue2.append(res)
self.queue1, self.queue2 = self.queue2, self.queue1
return res
def empty(self) -> bool:
"""
Returns whether the stack is empty.
"""
return not bool(self.queue1)
```
224. Basic Calculator
实现一个简单的计算器
1. 使用栈来存储中间结果
2. 遇到负号，将其压入栈中
3. 遇到运算符，判断是否为空，如果不为空，则弹出栈中的运算符进行计算，并将结果压入栈中，最后将当前运算符压入栈中
4. 遇到数字，将其直接压入栈中
5. 最后返回栈中的值
```
class Solution:
def calculate(self, s: str) -> int:
s = s.replace(' ', '')
stack = []
sign = 1
res = 0
for char in s:
if char.isdigit():
res = res * 10 + ord(char) - ord('0')
elif char == '+':
stack.append(res * sign)
res = 0
sign = 1
elif char == '-':
stack.append(res * sign)
res = 0
sign = -1
elif char == '(':
res = 0
sign = 1
stack.append('(')
elif char == ')':
while stack[-1] != '(':
stack.append(stack.pop() * sign)
stack.pop()
stack.append(res * sign)
res = 0
sign = 1
while stack:
stack.append(stack.pop() * sign)
return sum(stack)
```
223. Rectangle Area
计算两个矩形的重叠部分面积
1. 计算两个矩形的重叠部分，可以通过求两个矩形的边界最小值和最大值
2. 重叠部分的面积可以通过求两个矩形的重叠部分的宽度和高度来得到
```
class Solution:
def computeArea(self, A: int, B: int, C: int, D: int, E: int, F: int, G: int, H: int) -> int:
# 1. 计算两个矩形的重叠部分，可以通过求两个矩形的边界最小值和最大值
left = max(A, E)
right = min(C, G)
top = min(D, H)
bottom = max(B, F)
# 2. 重叠部分的面积可以通过求两个矩形的重叠部分的宽度和高度来得到
if left < right and top > bottom:
return (right - left) * (top - bottom)
else:
return (C - A) * (D - B) + (G - E) * (H - F)
```
222. Rectangle Area
计算两个矩