Week6-LeetCode

本文主要是介绍Week6-LeetCode，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1600.王位继承顺序 (中等)

关键思路：
多叉树的前序遍历。

class ThroneInheritance(object):def __init__(self, kingName):""":type kingName: str"""self.king = kingNameself.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 = 0i = 0j = n - 1while i < j:h = min(height[i], height[j])area = h * (j - i)MaxArea = max(area, MaxArea)if height[i] < height[j]:i += 1else:j -= 1return MaxArea         

12. 整数转罗马数字 (中等)

关键思路：

1. 罗马数字的规则是：对于罗马数字从左到右的每一位，选择尽可能大的符号值
2. 把所有可能出现的数值情况编成一个字典（共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 -= valueroman.append(symbol)if num == 0:breakreturn "".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 = 0n = 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 -= valueelse:ans += valuereturn 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 = 0for i, x in enumerate(a):  # x 是修改后的连续数字的最大值  滑动窗口的区间是[x - n + 1, x]while a[left] < x - n + 1:  # 对不在区间内的计数left += 1ans = 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]:continuek = n - 1target = -nums[i]for j in range(i + 1, n):if j > i + 1 and nums[j] == nums[j - 1]:continuewhile j < k  and nums[j] + nums[k] > target:k -= 1if j == k:breakif 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 + 1right = n - 1while left < right:ans = nums[i] + nums[left] + nums[right]if abs(target - ans) < mindiff:result = ansmindiff = abs(target - ans)if ans > target:right -= 1elif ans == target:return resultelse:left += 1return 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]:continueif nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target:breakif nums[i] + nums[n - 1] + nums[n - 2] + nums[n - 3] < target:continuefor j in range(i + 1, n - 2):if j > i + 1 and nums[j] == nums[j - 1]:continueif nums[i] + nums[j + 1] + nums[j + 2] + nums[j] > target:breakif nums[i] + nums[j] + nums[n - 1] + nums[n - 2] < target:continueleft, right = j + 1, n - 1while 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 += 1left += 1while left <right and nums[right] == nums[right - 1]:right -= 1right -= 1elif total < target:left += 1else:right -= 1return 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 = headp = dummyq = 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.nextq = 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 Falseelse: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 binaryzeros = binary.count('0')s = ['1'] * ns[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] * ndep = [-1] * n g = [[] for _ in range(n)]def dfs(x: int, depth: int):dep[x] = depthfor val in gcds[nums[x]]:if not tmp[val]:continuelas = tmp[val][-1]if ans[x] == -1 or dep[las] > dep[ans[x]]:ans[x] = lastmp[nums[x]].append(x)for val in g[x]:if dep[val] == -1: # 被访问过的点dep不为-1dfs(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

这篇关于Week6-LeetCode的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---