0X00 leetcode 刷题 5 道
0X01 每道题的小小总结
面试题 10.01. Sorted Merge LCCI
热身题,一个简单的合并两个 array 的问题,一开始被 inplace 限制住了,,,,没想到可以先创建一个然后再复制....太傻了
class Solution:
def merge(self, A: List[int], m: int, B: List[int], n: int) -> None:
"""
Do not return anything, modify A in-place instead.
"""
if len(A) == 0 or len(B) == 0: return
# 好吧 被 inplace 这个东西限制住了
# 其实这个题目不难
# 最后想象边界情况
pa, pb = 0, 0
m, n = len(A) - len(B), len(B)
temp = [0] * (m+n)
count = 0
while pa < m or pb < n:
if pb == n:
temp[count] = A[pa]
pa += 1
elif pa == m:
temp[count] = B[pb]
pb += 1
elif A[pa] <= B[pb]:
temp[count] = A[pa]
pa += 1
else:
temp[count] = B[pb]
pb += 1
count += 1
A[:] = temp
时间空间复杂度:
O(N)/O(N)
425. Word Squares
dfs + trie 树优化 这是一个很重要的考点,必须记住
这道题还有个坑,坑在边界条件,其实我注意到了,但是后面忘了...
就是长度为 1 的情况
class Solution:
def find(self, prefix, cur, node):
if len(prefix) != 0:
if prefix[0] not in node: return
self.find(prefix[1:], cur, node[prefix[0]])
else:
if '#' in node:
cur.append(node['#'])
for k, v in node.items():
if k == '#': continue
self.find("", cur, v)
def wordSquares(self, words: List[str]) -> List[List[str]]:
if len(words) == 0: return None
# 建立 trie
self.trie = {}
for w in words:
p = self.trie
for c in w:
p = p.setdefault(c, {})
p['#'] = w
# print(self.trie)
def dfs(cur, prefix):
condidates = []
self.find(prefix, condidates, self.trie)
# print("condidates ", condidates)
prefixIdx = len(prefix) + 1
for c in condidates:
cur.append(c)
# print("caonima ", cur)
if len(cur) == m:
ans.append(cur[:])
else:
prefix = ""
for w in cur:
prefix += w[prefixIdx]
# print("prefix ", prefix)
dfs(cur, prefix)
cur.pop()
m = len(words[0])
ans = []
if m == 1:
return words
for w in words:
dfs([w], w[1])
return ans
421. Maximum XOR of Two Numbers in an Array
这个题目感觉挺难的,也并没有 trie 去做,具体用了两个性质
- 贪心
- a ^ b = c => b ^ c = a => a ^ c = b
思路我说一下:
- 我们假设一个最大值,看这个最大值能不能存在
利用贪心的思想,我就依次检查最高位能不能为 1 比如第一次(假设只有 4 位)
1000
我要看其他的数字能不能 ^ 出 1000 不需要两两 ^ .只需要
将所有数字 mask (只保留第 1 位)以后放入一个 set 里面
c = 1000 ^ a
如果 c 也在这个 set 里面那么,就能构成反之不行,
具体操作看代码:
class Solution:
def findMaximumXOR(self, nums: List[int]) -> int:
# 这个题目有点难度
# 首先复习两个位运算
# | 用来给某些位添加
# & 用来保留某些位其他置 0 用作 mask
res, mask = 0, 0
for i in range(31, -1, -1):
mask |= 1 << i
s = set()
for n in nums:
s.add(n & mask)
# 计算当前最大值
temp = res | (1 << i)
for t in s:
if t ^ temp in s:
res = temp
break
return res
时间空间复杂度:
O(32N)/O(1)
5. Longest Palindromic Substring
动态规划,「区间型动态规划」转移方程 见代码注释
class Solution:
def longestPalindrome(self, s: str) -> str:
# 区间型动态规划
# 长度是关键
# f(x, y) 的意思是 s[x:y+1] 是不是回文
# f(x, y) = f(x+1, y-1) and s[x] = s[y]
if s == "": return s
m = n = len(s)
dp = [[False] * n for _ in range(m)]
# init
# len1
for i in range(m):
dp[i][i] = True
ans = 1
idx1, idx2 = 0, 0
# len2
for i in range(m-1):
dp[i][i+1] = s[i] == s[i+1]
if dp[i][i+1]:
idx1, idx2 = i, i+1
ans = 2
for l in range(3, m+1):
for x in range(m - l + 1):
y = x + l - 1
dp[x][y] = dp[x+1][y-1] and s[x] == s[y]
if dp[x][y] and l > ans:
idx1, idx2 = x, y
ans = l
return s[idx1:idx2+1]
O()/O(
)
336. Palindrome Pairs
这个题目我感觉也非常难
重点还是理解大神代码里面的骚操作:
class Solution:
def palindromePairs(self, words: List[str]) -> List[List[int]]:
# 回文必想空字符
rev = {}
# 本身就是回文
palIdx = []
for idx, w in enumerate(words):
t = w[::-1]
rev[t] = idx
if t == w: palIdx.append(idx)
res = []
for idx, w in enumerate(words):
# 判断是不是空字符串
if w:
# 这里不需要 + 1 因为 0
for i in range(len(w)):
left, right = w[:i], w[i:]
# 判断是不是左边的
if left in rev and right[::-1] == right and rev[left] != idx:
res.append([idx, rev[left]])
# 同理
if right in rev and left == left[::-1] and rev[right] != idx:
res.append([rev[right], idx])
else:
# 空字符串的其中一部分已经在之前考虑过了
# 只需要 考虑 ("", 回文)
for loc in palIdx:
if loc == idx: continue
res.append([idx, loc])
return res
复杂度应该是 O() / O(n)
网友评论