1600.王位继承顺序 (中等)
关键思路:
多叉树的前序遍历。
class ThroneInheritance(object):
def __init__(self, kingName):
"""
:type kingName: str
"""
self.king = kingName
self.dead = set() # 记录死亡人员
self.edges = defaultdict(list) # defaultdict(list) 中,如果访问的键不存在,则会自动创建一个空列表作为默认值
def birth(self, parentName, childName):
"""
:type parentName: str
:type childName: str
:rtype: None
"""
self.edges[parentName].append(childName)
def death(self, name):
"""
:type name: str
:rtype: None
"""
self.dead.add(name)
def getInheritanceOrder(self):
"""
:rtype: List[str]
"""
ans = list()
def preorder(name):
if name not in self.dead:
ans.append(name)
if name in self.edges:
for childName in self.edges[name]:
preorder(childName)
preorder(self.king)
return ans
# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()
11. 盛最多水的容器 (中等)
关键思路:
面积取决于两个支柱之间更矮的那个,因此,哪一个更矮就移动哪一个。
class Solution(object):
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
n = len(height)
MaxArea = 0
i = 0
j = n - 1
while i < j:
h = min(height[i], height[j])
area = h * (j - i)
MaxArea = max(area, MaxArea)
if height[i] < height[j]:
i += 1
else:
j -= 1
return MaxArea
12. 整数转罗马数字 (中等)
关键思路:
- 罗马数字的规则是:对于罗马数字从左到右的每一位,选择尽可能大的符号值
- 把所有可能出现的数值情况编成一个字典(共13种)
class Solution(object):
VALUE_SYMBOLS = [
(1000, "M"),
(900, "CM"),
(500, "D"),
(400, "CD"),
(100, "C"),
(90, "XC"),
(50, "L"),
(40, "XL"),
(10, "X"),
(9, "IX"),
(5, "V"),
(4, "IV"),
(1, "I"),
]
def intToRoman(self, num):
"""
:type num: int
:rtype: str
"""
roman = list()
for value, symbol in Solution.VALUE_SYMBOLS:
while num >= value:
num -= value
roman.append(symbol)
if num == 0:
break
return "".join(roman)
13. 罗马数字转整数 (简单)
关键思路:
默认为加,如果当前值小于下一个值,那就减。
class Solution(object):
SYMBOL_VALUES = {
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000,
}
def romanToInt(self, s):
"""
:type s: str
:rtype: int
"""
ans = 0
n = len(s)
for i, ch in enumerate(s):
value = Solution.SYMBOL_VALUES[ch]
if i < n - 1 and value < Solution.SYMBOL_VALUES[s[i + 1]]:
ans -= value
else:
ans += value
return ans
14. 最长公共前缀 (简单)
关键思路:
逐列对比
class Solution(object):
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
if not strs:
return ""
length, count = len(strs[0]), len(strs)
for i in range(length):
c = strs[0][i]
if any(i == len(strs[j]) or strs[j][i] != c for j in range(1, count)):
return strs[0][:i]
return strs[0]
2009. 使数组连续的最少操作数 (困难)
关键思路:
把题目转换为:最多能保留多少个数字。
使用滑动窗口, 窗口的大小为nums.length - 1
, 让nums[i]
依次作为滑动窗口的端点,看最多能框多少个不同的值,对于不同的值,可以想到集合set()
。
class Solution(object):
def minOperations(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
a = sorted(set(nums)) # 去重排序
ans = left = 0
for i, x in enumerate(a): # x 是修改后的连续数字的最大值 滑动窗口的区间是[x - n + 1, x]
while a[left] < x - n + 1: # 对不在区间内的计数
left += 1
ans = max(ans, i - left + 1) # 可以框进的整数数量
return n - ans
15.三数之和 (中等)
关键思路:
将原列表按从小到大排序后进行枚举,分为三个指针来指向i, j, k
,进行多次遍历求解。
每次遍历中, 如果每个指针指向的值和上一个指向的值相等,就遍历下一个,第一个指针从左往右遍历,第三个指针从右往左遍历,第二个指针在第一个指针的右边向右遍历,如果遇上了从右向左的指针,就停止遍历。
在下一次的遍历中,第三个指针重新回到最右,再次移动。
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
n = len(nums)
nums.sort()
ans = list()
for i in range(n):
if i > 0 and nums[i] == nums[i - 1]:
continue
k = n - 1
target = -nums[i]
for j in range(i + 1, n):
if j > i + 1 and nums[j] == nums[j - 1]:
continue
while j < k and nums[j] + nums[k] > target:
k -= 1
if j == k:
break
if nums[j] + nums[k] == target:
ans.append([nums[i], nums[j], nums[k]])
return ans
16. 最接近的三数之和 (中等)
关键思路:
固定一个指针,移动两个指针,大致思路与上一题相似。
class Solution(object):
def threeSumClosest(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
nums = sorted(nums)
n = len(nums)
result = nums[0] + nums[1] + nums[2]
mindiff = abs(target - result)
for i in range(n -2):
left = i + 1
right = n - 1
while left < right:
ans = nums[i] + nums[left] + nums[right]
if abs(target - ans) < mindiff:
result = ans
mindiff = abs(target - ans)
if ans > target:
right -= 1
elif ans == target:
return result
else:
left += 1
return result
17. 电话号码的字符组合 (中等)
关键思路:
看到组合就要想到回溯。
class Solution(object):
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
if not digits:
return []
phone = {'2':['a','b','c'],
'3':['d','e','f'],
'4':['g','h','i'],
'5':['j','k','l'],
'6':['m','n','o'],
'7':['p','q','r','s'],
'8':['t','u','v'],
'9':['w','x','y','z']}
def backtrack(conbination, nextdigit):
if len(nextdigit) == 0:
res.append(conbination)
else:
for letter in phone[nextdigit[0]]:
backtrack(conbination + letter, nextdigit[1:])
res = []
backtrack('', digits)
return res
18. 四数之和 (中等)
关键思路:
类似15、16题。
class Solution(object):
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
n = len(nums)
nums.sort()
ans = []
if n < 4 :
return []
for i in range(n - 3):
if i > 0 and nums[i] == nums[i - 1]:
continue
if nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target:
break
if nums[i] + nums[n - 1] + nums[n - 2] + nums[n - 3] < target:
continue
for j in range(i + 1, n - 2):
if j > i + 1 and nums[j] == nums[j - 1]:
continue
if nums[i] + nums[j + 1] + nums[j + 2] + nums[j] > target:
break
if nums[i] + nums[j] + nums[n - 1] + nums[n - 2] < target:
continue
left, right = j + 1, n - 1
while left < right:
total = nums[i] + nums[j] + nums[left] + nums[right]
if total == target:
ans.append([nums[i], nums[j], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]:
left += 1
left += 1
while left <right and nums[right] == nums[right - 1]:
right -= 1
right -= 1
elif total < target:
left += 1
else:
right -= 1
return ans
19. 删除链表的倒数第 N 个结点 (中等)
关键思路:
使用两个指针一起移动,其中一个先走n + 1
步,遍历到最后, 另一个直接到达倒数第n
个结点的前面一个。
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
"""
dummy = ListNode(0)
dummy.next = head
p = dummy
q = dummy
# 将 p 指针向前移动 n+1 步
for i in range(n + 1):
if p is None:
return head # 链表长度不足 n+1,无法删除节点
p = p.next
# 同时移动 p 和 q 指针,直到 p 指向链表末尾
while p is not None:
p = p.next
q = q.next
# 删除倒数第 n 个节点
q.next = q.next.next
return dummy.next
20. 有效的括号(简单)
关键思路:
使用栈
class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
# 括号匹配思路:使用栈
stack = []
mapping = {')':'(', ']' : '[', '}':'{'}
for char in s:
if char in mapping:
el = stack.pop() if stack else ''
if mapping[char] != el:
return False
else:
stack.append(char)
return not stack
1702. 修改后的最大二进制字符串 (中等)
关键思路:
规则1
的意思是前面的0
可以变成1
,推广则是我们可以将一连串的0
变成只有最后一位是0
、其他全是1
;
规则2
的意思是可以把后面的0
推到前面来,推广则是我们可以将任意一个0
往前推、推到所有的1
前面去。
因此:
观察到结果的规律在于0
的个数,如果没有0
, 直接返回。
如果有0
,变化后的数字最多只会有1
个0
,结果中 0
的位置取决于字符串第一个 0
的位置,之后每多一个 0
便可以向后移动一位。
class Solution(object):
def maximumBinaryString(self, binary):
"""
:type binary: str
:rtype: str
"""
n = len(binary)
i = binary.find("0")
if i < 0:
return binary
zeros = binary.count('0')
s = ['1'] * n
s[i + zeros - 1] = '0'
return ''.join(s)
1766. 互质数 (困难)
关键思路:
使用深度优先遍历,根节点到任意节点的搜索路径就是该节点的祖先节点的集合,故搜索路径上最近的与其互质的就是答案。
class Solution:
def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:
n = len(nums)
# 初始化
gcds = [[] for _ in range(51)]
tmp = [[] for _ in range(51)]
ans = [-1] * n
dep = [-1] * n
g = [[] for _ in range(n)]
def dfs(x: int, depth: int):
dep[x] = depth
for val in gcds[nums[x]]:
if not tmp[val]:
continue
las = tmp[val][-1]
if ans[x] == -1 or dep[las] > dep[ans[x]]:
ans[x] = las
tmp[nums[x]].append(x)
for val in g[x]:
if dep[val] == -1: # 被访问过的点dep不为-1
dfs(val, depth + 1)
tmp[nums[x]].pop()
for i in range(1, 51):
for j in range(1, 51):
if math.gcd(i, j) == 1:
gcds[i].append(j)
for x, y in edges:
g[x].append(y)
g[y].append(x)
dfs(0, 1)
return ans