202. Happy Number
class Solution:
def isHappy(self, n: int) -> bool:
char2int = {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4,
'5': 5, '6': 6, '7': 7, '8': 8, '9': 9}
cache = set()
while True:
cache.add(n)
product = 0
for i in str(n):
i = char2int[i]
product += (i * i)
n = product
if n == 1:
return True
if n in cache:
return False
203. Remove Linked List Elements
class Solution:
def removeElements(self, head: ListNode, val: int) -> ListNode:
dummy=ListNode(next=head)
curr=dummy
while curr.next:
if curr.next.val==val:
curr.next=curr.next.next
else:
curr=curr.next
return dummy.next
204. Count Primes
！！！思路：
- 如果判断 i 为 prime，那么
i*i::i都是合数 - 如果 i 为合数，那么
i*i::i也是合数，但其实不用i排除，之前就排除掉了
class Solution:
def countPrimes(self, n: int) -> int:
if n < 2:
return 0
is_prime = [True] * n
is_prime[0] = is_prime[1] = False
for i in range(2, int(n ** 0.5) + 1):
if is_prime[i]:
is_prime[i * i:n:i] = [False] * ((n - 1 - i * i) // i + 1)
return sum(is_prime)
205. Isomorphic Strings
class Solution:
def isIsomorphic(self, s: str, t: str) -> bool:
if len(s)!=len(t):
return False
cache=dict()
for idx in range(len(s)):
if s[idx] in cache:
if cache[s[idx]]==t[idx]:
continue
else:
return False
else:
cache[s[idx]]=t[idx]
# 上面保证了不会一对多，还要排除多对一
val=cache.values()
if len(val)!=len(set(val)):
return False
return True
209. Minimum Size Subarray Sum
思路
- 求 cumsum
- 类似 2-sum 的方法求 2-minus（beat 5%）
- 性能优化：right 从上一次的right 开始遍历即可
class Solution:
def minSubArrayLen(self, target: int, nums) -> int:
# cumsum
for idx in range(1, len(nums)):
nums[idx] = nums[idx] + nums[idx - 1]
nums = [0] + nums
res = []
right=0
for left in range(len(nums)):
target_tmp = nums[left] + target
for right in range(right, len(nums)):
if nums[right] >= target_tmp:
res.append(right - left)
break
return min(res) if res else 0
213. House Robber II
House Robber 跑两次，一次掐头，一次去位。
class Solution:
def rob(self, nums) -> int:
if len(nums)<=2:
return max(nums)
def rob1(nums):
cache = dict()
def dfs(idx):
if idx in cache:
return cache[idx]
if idx == len(nums) - 1 or idx == len(nums) - 2:
res = nums[idx]
else:
res = nums[idx] + max(dfs(i) for i in range(idx + 2, len(nums)))
cache[idx] = res
return res
return max(dfs(i) for i in range(len(nums)))
return max(rob1(nums[1:]), rob1(nums[:-1]))
215. Kth Largest Element in an Array
作弊1:
nums.sort(reverse=True)
nums[k]
作弊2
return heapq.nlargest(n=k, iterable=nums)[-1]
216. Combination Sum III
思路：dfs
- f(k,n,i) 定义为k个数组合，加和为n，从i出发（不含i）
- 回溯法
class Solution:
def combinationSum3(self, k: int, n: int):
cache = dict()
def dfs(k, n, i):
if (k, n, i) in cache:
return cache[(k, n, i)]
if k == 0 and n == 0:
return [[]]
if k == 0 and n != 0:
return []
if n < 0:
return []
if i > 9:
return []
if n == i and k == 1:
return [[i]]
# 回溯法：用i与不用i
return [[i] + item for item in dfs(k - 1, n - i, i + 1)] + dfs(k, n, i + 1)
return dfs(k, n, 1)
217. Contains Duplicate
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
cache=set()
for num in nums:
if num in cache:
return True
cache.add(num)
return False
220. Contains Duplicate III
??? beat 5%，不是很好，下一遍再过一遍
algo1 超时：nums = [2147483647, -1, 2147483647]，k = 1，t = 2147483647
algo2 用滑动窗口
class Solution:
def containsNearbyAlmostDuplicate(self, nums, k: int, t: int) -> bool:
def algo1():
all_nums = set(nums)
cache = dict()
for idx, num in enumerate(nums):
if num in cache:
if idx - cache[num] <= k:
return True
for j in range(num - t, num + t + 1):
if j in all_nums:
cache[j] = idx
return False
def algo2():
for idx, num in enumerate(nums):
left, right = num - t, num + t
for j in range(idx + 1, min(idx + k + 1, len(nums))):
if left <= nums[j] <= right:
print(left, right, nums[j], idx)
return True
return False
if t <= 100:
return algo1()
else:
return algo2()
219. Contains Duplicate II
简单
class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
cache=dict()
for idx,num in enumerate(nums):
if num in cache:
if idx-cache[num]<=k:
return True
cache[num]=idx
return False
221. Maximal Square
思路（抄的）
f(i,j)表示右下角为(i,j)的正方形大小- （如果
matrix[i][j]=='1'）对应的正方形大小为：f(i-1,j), f(i,j-1), f(i-1,j-1)中最小的一个+1
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
h,w=len(matrix),len(matrix[0])
cache=dict()
def dfs(i,j):
if not (0<=i<h and 0<=j<w):
return 0
if (i,j) in cache:
return cache[(i,j)]
if matrix[i][j]=='0':
return 0
res=min(dfs(i-1,j),dfs(i,j-1),dfs(i-1,j-1))+1
cache[(i,j)]=res
return res
res=0
for i in range(h):
for j in range(w):
res=max(res,dfs(i,j))
return res*res
222. Count Complete Tree Nodes
二叉树遍历，套公式即可
# dfs解法
class Solution:
def countNodes(self, root: TreeNode) -> int:
if not root:
return 0
res=[0]
def dfs(node):
res[0]+=1
if node.left:
dfs(node.left)
if node.right:
dfs(node.right)
dfs(root)
return res[0]
# bfs解法
class Solution:
def countNodes(self, root: TreeNode) -> int:
if not root:
return 0
res=0
queue=[root]
while queue:
new_queue=list()
for node in queue:
res+=1
if node.left:
new_queue.append(node.left)
if node.right:
new_queue.append(node.right)
queue=new_queue
return res
223. Rectangle Area
思路（看题解）如何计算重叠区域：先计算x轴的重叠区间，再计算y轴的重叠区间
class Solution:
def computeArea(self, ax1: int, ay1: int, ax2: int, ay2: int, bx1: int, by1: int, bx2: int, by2: int) -> int:
def get_1_dim_overlap(a1, a2, b1, b2):
tmp = [(a1, 1), (a2, 1), (b1, 0), (b2, 0)]
tmp.sort()
if tmp[0][1] == tmp[1][1]:
return 0
else:
return tmp[2][0] - tmp[1][0]
def get_rect_area(x1,x2,y1,y2):
return abs((x2-x1)*(y2-y1))
overlap=get_1_dim_overlap(ax1,ax2,bx1,bx2)*get_1_dim_overlap(ay1,ay2,by1,by2)
return get_rect_area(ax1,ax2,ay1,ay2)+get_rect_area(bx1,bx2,by1,by2)-abs(overlap)
227. Basic Calculator II
eval(s.replace('/','//'))
228. Summary Ranges
class Solution:
def summaryRanges(self, nums: List[int]) -> List[str]:
idx =0
res=[]
while idx<len(nums):
res.append(str(nums[idx]))
last=False
while idx<len(nums)-1 and nums[idx+1]-nums[idx]==1:
idx+=1
last=True
if last:
res[-1]+=('->'+str(nums[idx]))
idx+=1
return res
229. Majority Element II
简单
len_num=len(nums)/3
counter=collections.Counter(nums)
return [key for key,val in counter.items() if val>len_num]
232. Implement Queue using Stacks
typedef struct {
int *a;
int *b;
int size_a;
int size_b;
} MyQueue;
MyQueue *myQueueCreate() {
MyQueue *obj = malloc(sizeof(MyQueue));
obj->a = malloc(100 * sizeof(int));
obj->b = malloc(100 * sizeof(int));
obj->size_a = 0;
obj->size_b = 0;
return obj;
}
void myQueuePush(MyQueue *obj, int x) {
obj->a[obj->size_a] = x;
obj->size_a += 1;
}
void repack(MyQueue *obj) {
for (int i = obj->size_a - 1; i >= 0; i--) {
obj->b[obj->size_a - i - 1] = obj->a[i];
}
obj->size_b = obj->size_a;
obj->size_a = 0;
}
int myQueuePop(MyQueue *obj) {
if (obj->size_b == 0) {
repack(obj);
}
obj->size_b -= 1;
return obj->b[obj->size_b];
}
int myQueuePeek(MyQueue *obj) {
if (obj->size_b == 0) {
repack(obj);
}
return obj->b[obj->size_b - 1];
}
bool myQueueEmpty(MyQueue *obj) {
return obj->size_a == 0 && obj->size_b == 0;
}
void myQueueFree(MyQueue *obj) {
free(obj->a);
free(obj->b);
free(obj);
}
234. Palindrome Linked List
2个方法：
- 链表遍历。转为list之后就好判断了。
- 快慢指针找中点。半部分做链表反转。
题解：https://leetcode.cn/problems/palindrome-linked-list/solution/cji-bai-90-by-guofei9987-t0d9/
258. Add Digits
class Solution:
def addDigits(self, num: int) -> int:
def sum1(num):
res = 0
while num:
num, tmp = divmod(num, 10)
res += tmp
return res
while num>=10:
num=sum1(num)
return num
289. Game of Life
class Solution:
def gameOfLife(self, board) -> None:
h, w = len(board), len(board[0])
new_board = [[None] * w for i in range(h)]
def get_neighbor_sum(row, col):
res = 0
for diff_i in (-1, 0, 1):
for diff_j in (-1, 0, 1):
if diff_i == diff_j == 0:
continue
if 0 <= row + diff_i < h and 0 <= col + diff_j < w:
res += board[row + diff_i][col + diff_j]
return res
for row in range(h):
for col in range(w):
neighbor_sum = get_neighbor_sum(row, col)
if board[row][col] == 1:
if 2 <= neighbor_sum <= 3:
new_board[row][col] = 1
else:
new_board[row][col] = 0
else:
if neighbor_sum == 3:
new_board[row][col] = 1
else:
new_board[row][col] = 0
for row in range(h):
for col in range(w):
board[row][col] = new_board[row][col]
