# 计算两个数之和 # @param s string字符串 表示第一个整数 # @param t string字符串 表示第二个整数 # @return string字符串 # classSolution: defsolve(self , s: str, t: str) -> str: # write code here res = "" i, j, carry = len(s) - 1, len(t) - 1, 0 while i >= 0or j >= 0: n1 = int(s[i]) if i >= 0else0 n2 = int(t[j]) if j >= 0else0 tmp = n1 + n2 + carry carry = tmp // 10 res = str(tmp % 10) + res i, j = i - 1, j - 1 return"1" + res if carry else res
2、「NC3」「链表中环的入口结点」:中等
# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None classSolution: defEntryNodeOfLoop(self, pHead): # write code here slow = self.hasCycle(pHead) if slow == None: returnNone fast = pHead while fast != slow: fast = fast.next slow = slow.next return slow
defhasCycle(self, head): if head == None: returnNone fast = head slow = head while fast != Noneand fast.next != None: fast = fast.next.next slow = slow.next if fast == slow: return slow returnNone
3、「NC4」「判断链表中是否有环」:简单
# class ListNode: # def __init__(self, x): # self.val = x # self.next = None
# # # @param head ListNode类 # @return bool布尔型 # classSolution: defhasCycle(self , head: ListNode) -> bool: ifnot head: returnFalse slow = head fast = head while fast != Noneand fast.next != None: fast = fast.next.next slow = slow.next if fast == slow: returnTrue returnFalse
4、「NC6」「二叉树中的最大路径和」:困难
这道题的Python答案在牛客网无法通过,在力扣网能通过:
https:///problems/jC7MId/
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right classSolution: def__init__(self): self.maxSum = float("-inf")
classSolution: defPrint(self , pRoot: TreeNode) -> List[List[int]]: # write code here head = pRoot res = [] ifnot head: return res temp = queue.Queue() temp.put(head) flag = True whilenot temp.empty(): row = [] flag = not flag n = temp.qsize() for i in range(n): p = temp.get() row.append(p.val) if p.left: temp.put(p.left) if p.right: temp.put(p.right) if flag: row = row[::-1] res.append(row) return res
classSolution: deflevelOrder(self , root: TreeNode) -> List[List[int]]: # write code here res = [] ifnot root: return res q = queue.Queue() q.put(root) cur = None whilenot q.empty(): row = [] n = q.qsize() for i in range(n): cur = q.get() row.append(cur.val) if cur.left: q.put(cur.left) if cur.right: q.put(cur.right) res.append(row) return res
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param A string字符串 # @return int整型 # classSolution: deffunc(self, s: str, begin: int, end: int) -> int: while begin >= 0and end < len(s) and s[begin] == s[end]: begin -= 1 end += 1 return end - begin - 1
defgetLongestPalindrome(self , A: str) -> int: # write code here maxlen = 1 for i in range(len(A) - 1): maxlen = max(maxlen, max(self.func(A, i, i), self.func(A, i, i + 1))) return maxlen
11、「NC18」「顺时针旋转矩阵」:中等
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param mat int整型二维数组 # @param n int整型 # @return int整型二维数组 # classSolution: defrotateMatrix(self , mat: List[List[int]], n: int) -> List[List[int]]: # write code here for i in range(n): for j in range(i): mat[i][j], mat[j][i] = mat[j][i], mat[i][j] for i in range(n): mat[i].reverse() return mat
12、「NC19」「连续子数组的最大和」:简单
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param array int整型一维数组 # @return int整型 # classSolution: defFindGreatestSumOfSubArray(self , array: List[int]) -> int: # write code here dp = [0for i in range(len(array))] dp[0] = array[0] maxsum = dp[0] for i in range(1, len(array)): dp[i] = max(dp[i - 1] + array[i], array[i]) maxsum = max(maxsum, dp[i]) return maxsum
13、「NC22」「合并两个有序的数组」:简单
# # # @param A int整型一维数组 # @param B int整型一维数组 # @return void # classSolution: defmerge(self , A, m, B, n): # write code here i = m - 1 j = n - 1 p = m + n - 1 while i >= 0and j >= 0: if A[i] > B[j]: A[p] = A[i] p -= 1 i -= 1 else: A[p] = B[j] p -= 1 j -= 1 while j >= 0: A[p] = B[j] p -= 1 j -= 1
14、「NC24」「删除有序链表中重复的元素-II」:中等
跟简单的区别:要求重复元素全部删除
# class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param head ListNode类 # @return ListNode类 # classSolution: defdeleteDuplicates(self , head: ListNode) -> ListNode: # write code here ifnot head: returnNone res = ListNode(0) res.next = head cur = res while cur.next and cur.next.next: if cur.next.val == cur.next.next.val: temp = cur.next.val while cur.next != Noneand cur.next.val == temp: cur.next = cur.next.next else: cur = cur.next return res.next
15、「NC25」「删除有序链表中重复的元素-I」:简单
跟中等的区别:要求重复元素保留一个
# class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param head ListNode类 # @return ListNode类 # classSolution: defdeleteDuplicates(self, head: ListNode) -> ListNode: # write code here ifnot head: returnNone cur = head while cur and cur.next: if cur.val == cur.next.val: cur.next = cur.next.next else: cur = cur.next return head
16、「NC26」「括号生成」:中等
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param n int整型 # @return string字符串一维数组 # classSolution: defrecursion(self, left: int, right: int, temp: str, res: List[str], n: int): if left == n and right == n: res.append(temp) return if left < n: self.recursion(left + 1, right, temp + "(", res, n) if right < n and left > right: self.recursion(left, right + 1, temp + ")", res, n)
defgenerateParenthesis(self , n: int) -> List[str]: # write code here res = list() temp = str() self.recursion(0, 0, temp, res, n) return res
defdfs(dummy, tmp): res.append(tmp[:]) for i in range(dummy, len(S)): tmp.append(S[i]) dfs(i + 1, tmp) tmp.pop()
dfs(0, []) return res
18、「NC28」「最小覆盖子串」:困难
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param S string字符串 # @param T string字符串 # @return string字符串 # classSolution: defminWindow(self, S: str, T: str) -> str: # write code here cnt = len(S) + 1 hash = dict() for i in range(len(T)): if T[i] in hash: hash[T[i]] -= 1 else: hash[T[i]] = -1 slow = 0 fast = 0 left = -1 right = -1 while fast < len(S): c = S[fast] if c in hash: hash[c] += 1 while Solution.check(self, hash): if cnt > fast - slow + 1: cnt = fast - slow + 1 left = slow right = fast c = S[slow] if c in hash: hash[c] -= 1 slow += 1 fast += 1 if left == -1: return"" return S[left : right + 1]
defcheck(self, hash): for key, value in hash.items(): if value < 0: returnFalse returnTrue
19、「NC30」「缺失的第一个正整数」:中等
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param nums int整型一维数组 # @return int整型 # classSolution: defminNumberDisappeared(self , nums: List[int]) -> int: # write code here n = len(nums) mp = dict() for i in range(n): if nums[i] in mp: mp[nums[i]] += 1 else: mp[nums[i]] = 1 res = 1 while res in mp: res += 1 return res
20、「NC31」「第一个只出现一次的字符」:简单
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param str string字符串 # @return int整型 # classSolution: defFirstNotRepeatingChar(self , str: str) -> int: # write code here mp = dict() for i in str: if i in mp: mp[i] += 1 else: mp[i] = 1 for i in range(len(str)): if mp[str[i]] == 1: return i return-1
21、「NC33」「合并两个排序的链表」:简单
# class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param pHead1 ListNode类 # @param pHead2 ListNode类 # @return ListNode类 # classSolution: defMerge(self , pHead1: ListNode, pHead2: ListNode) -> ListNode: # write code here if pHead1 == None: return pHead2 if pHead2 == None: return pHead1 head = ListNode(0) cur = head while pHead1 and pHead2: if pHead1.val <= pHead2.val: cur.next = pHead1 pHead1 = pHead1.next else: cur.next = pHead2 pHead2 = pHead2.next cur = cur.next if pHead1: cur.next = pHead1 else: cur.next = pHead2 return head.next
22、「NC35」 **编辑距离(二)**:困难
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # min edit cost # @param str1 string字符串 the string # @param str2 string字符串 the string # @param ic int整型 insert cost # @param dc int整型 delete cost # @param rc int整型 replace cost # @return int整型 # classSolution: defminEditCost(self, str1: str, str2: str, ic: int, dc: int, rc: int) -> int: # write code here dp = [[0for _ in range(len(str2) + 1)] for _ in range(len(str1) + 1)] for i in range(1, len(str2) + 1): dp[0][i] = dp[0][i - 1] + ic for i in range(1, len(str1) + 1): dp[i][0] = dp[i - 1][0] + dc
for i in range(1, len(str1) + 1): for j in range(1, len(str2) + 1): if str1[i - 1] == str2[j - 1]: dp[i][j] = dp[i - 1][j - 1] else: dp[i][j] = min(dp[i - 1][j - 1] + rc, dp[i][j - 1] + ic, dp[i - 1][j] + dc) return dp[-1][-1]
23、「NC36」「在两个长度相等的排序数组中找到上中位数」:中等
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # find median in two sorted array # @param arr1 int整型一维数组 the array1 # @param arr2 int整型一维数组 the array2 # @return int整型 # classSolution: deffindMedianinTwoSortedAray(self , arr1: List[int], arr2: List[int]) -> int: # write code here p1, p2 = 0, 0 ans = 0 for i in range(len(arr1)): if arr1[p1] <= arr2[p2]: ans = arr1[p1] p1 += 1 else: ans = arr2[p2] p2 += 1 return ans
24、「NC37」「合并区间」:中等
from functools import cmp_to_key
# class Interval: # def __init__(self, a=0, b=0): # self.start = a # self.end = b # # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param intervals Interval类一维数组 # @return Interval类一维数组 # classSolution: defmerge(self, intervals: List[Interval]) -> List[Interval]: # write code here res = list() if len(intervals) == 0: return res intervals.sort(key=cmp_to_key(lambda a, b: a.start - b.start)) res.append(intervals[0]) for i in range(len(intervals)): if intervals[i].start <= res[-1].end: res[-1].end = max(res[-1].end, intervals[i].end) else: res.append(intervals[i]) return res
25、「NC40」 **链表相加(二)**:中等
# class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param head1 ListNode类 # @param head2 ListNode类 # @return ListNode类 # classSolution: # 反转链表 defreverseList(self, pHead: ListNode): if pHead == None: returnNone cur = pHead pre = None while cur: # 断开链表,要记录后续一个 temp = cur.next # 当前的next指向前一个 cur.next = pre # 前一个更新为当前 pre = cur # 当前更新为刚刚记录的后一个 cur = temp return pre
defbacktracking(self, num, target, cur, begin, arr, result): """ num: 入参数组列表 target:目标值 cur:当前值 begin:开始指针 arr:临时存储数组 result:满足条件的组合 """ if cur >= target: if cur == target: result.append(list(arr)) return result for i in range(begin, len(num)): if i > begin and num[i] == num[i - 1]: # 去重 continue # 减枝 arr.append(num[i]) self.backtracking(num, target, cur + num[i], i + 1, arr, result) arr.pop(-1) return result
31、「NC49」「最长的括号子串」:困难
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param s string字符串 # @return int整型 # classSolution: deflongestValidParentheses(self, s: str) -> int: res = 0 # 记录上一次连续括号结束的位置 start = -1 st = [] for i in range(len(s)): # 左括号入栈 if s[i] == "(": st.append(i) # 右括号 else: # 如果右括号时栈为空,不合法,设置为结束位置 if len(st) == 0: start = i else: # 弹出左括号 st.pop() # 栈中还有左括号,说明右括号不够,减去栈顶位置就是长度 if len(st) != 0: res = max(res, i - st[-1]) # 栈中没有括号,说明左右括号行号,减去上一次结束的位置就是长度 else: res = max(res, i - start) return res
32、「NC50」「链表中的节点每k个一组翻转」:中等
# class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param head ListNode类 # @param k int整型 # @return ListNode类 # classSolution: defreverseKGroup(self, head: ListNode, k: int) -> ListNode: # 找到每次翻转的尾部 tail = head # 遍历k次到尾部 for i in range(0, k): # 如果不足k到了链表尾,直接返回,不翻转 if tail == None: return head tail = tail.next # 翻转时需要的前序和当前节点 pre = None cur = head # 在到达当前段尾节点前 while cur != tail: # 翻转 temp = cur.next cur.next = pre pre = cur cur = temp # 当前尾指向下一段要翻转的链表 head.next = self.reverseKGroup(tail, k) return pre
# class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param head ListNode类 # @param n int整型 # @return ListNode类 # classSolution: defremoveNthFromEnd(self, head: ListNode, n: int) -> ListNode: # 添加表头 res = ListNode(-1) res.next = head # 当前节点 cur = head # 前序节点 pre = res fast = head # 快指针先行n步 while n: fast = fast.next n = n - 1 # 快慢指针同步,快指针到达末尾,慢指针就到了倒数第n个位置 while fast: fast = fast.next pre = cur cur = cur.next # 删除该位置的节点 pre.next = cur.next # 返回去掉头 return res.next
36、「NC54」「三数之和」:中等
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param num int整型一维数组 # @return int整型二维数组 # classSolution: defthreeSum(self, num: List[int]) -> List[List[int]]: res = list(list()) n = len(num) # 不够三元组 if n < 3: return res # 排序 num.sort() for i in range(n - 2): if i != 0and num[i] == num[i - 1]: continue # 后续的收尾双指针 left = i + 1 right = n - 1 # 设置当前数的负值为目标 target = -num[i] while left < right: # 双指针指向的二值相加为目标,则可以与num[i]组成0 if num[left] + num[right] == target: res.append([num[i], num[left], num[right]]) while left + 1 < right and num[left] == num[left + 1]: # 去重 left += 1 while right - 1 > left and num[right] == num[right - 1]: # 去重 right -= 1 # 双指针向中间收缩 left += 1 right -= 1 # 双指针指向的二值相加大于目标,右指针向左 elif num[left] + num[right] > target: right -= 1 # 双指针指向的二值相加小于目标,左指针向右 else: left += 1 return res
37、「NC55」「最长公共前缀」:简单
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param strs string字符串一维数组 # @return string字符串 # classSolution: deflongestCommonPrefix(self, strs: List[str]) -> str: n = len(strs) # 空字符串数组 if n == 0: return"" # 遍历第一个字符串的长度 for i in range(len(strs[0])): temp = strs[0][i] # 遍历后续的字符串 for j in range(1, n): # 比较每个字符串该位置是否和第一个相同 if i == len(strs[j]) or strs[j][i] != temp: # 不相同则结束 return strs[0][0:i] # 后续字符串有整个字一个字符串的前缀 return strs[0]
38、「NC57」「反转数字」:简单
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param x int整型 # @return int整型 # classSolution: defreverse(self, x): # write code here x = str(x) if x[0] == "-": a = int("-" + x[1:][::-1]) else: a = int(x[::-1]) return a if-2**31 < a < 2**31-1else0
l, r = dfs(x.left), dfs(x.right) # 使用左右子树的信息得到当前节点的信息 mx = max(x.val, r.mx) mi = min(x.val, l.mi) height = max(l.height, r.height) + 1 is_bst = l.is_bst and r.is_bst and l.mx < x.val < r.mi is_full = l.is_full and r.is_full and l.height == r.height is_cbt = ( is_full or l.is_full and r.is_full and l.height - 1 == r.height or l.is_full and r.is_cbt and l.height == r.height or l.is_cbt and r.is_full and l.height - 1 == r.height )
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param numbers int整型一维数组 # @param target int整型 # @return int整型一维数组 # classSolution: deftwoSum(self, numbers: List[int], target: int) -> List[int]: res = [] # 创建哈希表,两元组分别表示值、下标 hash = dict() # 在哈希表中查找target-numbers[i] for i in range(len(numbers)): temp = target - numbers[i] # 若是没找到,将此信息计入哈希表 if temp notin hash: hash[numbers[i]] = i else: # 哈希表中记录的是之前的数字,所以该索引比当前小 res.append(hash[temp] + 1) res.append(i + 1) break return res
41、「NC62」「判断是不是平衡二叉树」:简单
# class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None # # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param pRoot TreeNode类 # @return bool布尔型 # classSolution: # 计算该子树深度函数 defdeep(self, root: TreeNode): ifnot root: return0 # 递归算左右子树的深度 left = self.deep(root.left) right = self.deep(root.right) # 子树最大深度加上自己 return left + 1if left > right else right + 1
defIsBalanced_Solution(self, pRoot: TreeNode) -> bool: # 空树为平衡二叉树 ifnot pRoot: returnTrue left = self.deep(pRoot.left) right = self.deep(pRoot.right) # 左子树深度减去右子树相差绝对值大于1 if left - right > 1or left - right < -1: returnFalse # 同时,左右子树还必须是平衡的 return self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution( pRoot.right )
42、「NC63」「扑克牌顺子」:简单
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param numbers int整型一维数组 # @return bool布尔型 # classSolution: defIsContinuous(self, numbers: List[int]) -> bool: hash = dict() # 设置顺子上下界 max = 0 min = 13 # 遍历牌 for i in range(len(numbers)): if numbers[i] > 0: # 顺子不能重复 if numbers[i] in hash: returnFalse else: # 将新牌加入哈希表 hash[numbers[i]] = i # 更新上下界 if numbers[i] >= max: max = numbers[i] if numbers[i] <= min: min = numbers[i] # 如果两张牌大于等于5,剩下三张牌无论如何也补不齐 if (max - min) >= 5: returnFalse else: returnTrue
43、「NC65」「斐波那契数列」:简单
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param n int整型 # @return int整型 # classSolution: defFibonacci(self, n): # write code here # 斐波拉契数的边界条件: F(0)=0 和 F(1)=1 if n < 2: return n else: a, b = 0, 1 for i in range(n - 1): a, b = b, a + b # 状态转移方程,每次滚动更新数组
return b
44、「NC66」「两个链表的第一个公共结点」:简单
# class ListNode: # def __init__(self, x): # self.val = x # self.next = None
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param number int整型 # @return int整型 # classSolution: defjumpFloor(self, number: int) -> int: # 从0开始,第0项是1,第一项是1 if number <= 1: return1 res = 0 a = 1 b = 1 # 初始化的时候把a=1,b=1 for i in range(2, number + 1): # 第三项开始是前两项的和,然后保留最新的两项,更新数据相加 res = a + b a = b b = res return res
46、「NC70」「单链表的排序」:中等
# class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param head ListNode类 the head node # @return ListNode类 # classSolution: # 合并两段有序链表 defmerge(self, pHead1: ListNode, pHead2: ListNode): # 一个已经为空了,直接返回另一个 if pHead1 == None: return pHead2 if pHead2 == None: return pHead1 # 加一个表头 head = ListNode(0) cur = head # 两个链表都要不为空 while pHead1 and pHead2: # 取较小值的节点 if pHead1.val <= pHead2.val: cur.next = pHead1 # 只移动取值的指针 pHead1 = pHead1.next else: cur.next = pHead2 # 只移动取值的指针 pHead2 = pHead2.next # 指针后移 cur = cur.next # 哪个链表还有剩,直接连在后面 if pHead1: cur.next = pHead1 else: cur.next = pHead2 # 返回值去掉表头 return head.next
defsortInList(self, head): # 链表为空或者只有一个元素,直接就是有序的 if head == Noneor head.next == None: return head left = head mid = head.next right = head.next.next # 右边的指针到达末尾时,中间的指针指向该段链表的中间 while right and right.next: left = left.next mid = mid.next right = right.next.next # 左边指针指向左段的左右一个节点,从这里断开 left.next = None # 分成两段排序,合并排好序的两段 return self.merge(self.sortInList(head), self.sortInList(mid))
defpop(self): # 将第一个栈中内容弹出放入第二个栈中 while self.stack1: self.stack2.append(self.stack1.pop()) # 第二个栈栈顶就是最先进来的元素,即队首 res = self.stack2.pop() # 再将第二个栈的元素放回第一个栈 while self.stack2: self.stack1.append(self.stack2.pop()) return res
51、「NC78」「反转链表」:简单
# class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param head ListNode类 # @return ListNode类 # classSolution: # 返回ListNode defReverseList(self, pHead): # write code here pre = None head = pHead while head: temp = head.next head.next = pre pre = head head = temp return pre
52、「NC82」「滑动窗口的最大值」:困难
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param num int整型一维数组 # @param size int整型 # @return int整型一维数组 # classSolution: defmaxInWindows(self, num: List[int], size: int) -> List[int]: res = [] # 窗口大于数组长度的时候,返回空 if size <= len(num) and size != 0: from collections import deque
# 双向队列 dq = deque() # 先遍历一个窗口 for i in range(size): # 去掉比自己先进队列的小于自己的值 while len(dq) != 0and num[dq[-1]] < num[i]: dq.pop() dq.append(i) # 遍历后续数组元素 for i in range(size, len(num)): res.append(num[dq[0]]) while len(dq) != 0and dq[0] < (i - size + 1): # 弹出窗口移走后的值 dq.popleft() # 加入新的值前,去掉比自己先进队列的小于自己的值 while len(dq) != 0and num[dq[-1]] < num[i]: dq.pop() dq.append(i) res.append(num[dq[0]]) return res
53、「NC86」「矩阵元素查找」:中等
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param mat int整型二维数组 # @param n int整型 # @param m int整型 # @param x int整型 # @return int整型一维数组 # classSolution: deffindElement(self, mat: List[List[int]], n: int, m: int, x: int) -> List[int]: # write code here i = n - 1 j = 0 while i >= 0and j < m: if mat[i][j] == x: return [i, j] elif x < mat[i][j]: i -= 1 elif x > mat[i][j]: j += 1
54、「NC89」「字符串变形」:简单
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param s string字符串 # @param n int整型 # @return string字符串 # classSolution: deftrans(self, s: str, n: int) -> str: if n == 0: return s res = "" for i in range(n): # 大小写转换 if s[i] <= "Z"and s[i] >= "A": res += chr(ord(s[i]) - ord("A") + ord("a")) elif s[i] >= "a"and s[i] <= "z": res += chr(ord(s[i]) - ord("a") + ord("A")) else: # 空格直接复制 res += s[i] # 单词反序 res = list(res.split(" "))[::-1] print(res) return" ".join(res)
# 获取最长公共子序列 defans(self, i: int, j: int, b: List[List[int]]): res = "" # 递归终止条件 if i == 0or j == 0: return res # 根据方向,往前递归,然后添加本级字符 if b[i][j] == 1: res = res + self.ans(i - 1, j - 1, b) res = res + self.x[i - 1] elif b[i][j] == 2: res = res + self.ans(i - 1, j, b) elif b[i][j] == 3: res = res + self.ans(i, j - 1, b) return res
defLCS(self, s1: str, s2: str) -> str: # 特殊情况 if s1 isNoneor s2 isNone: return"-1" len1 = len(s1) len2 = len(s2) self.x = s1 self.y = s2 # dp[i][j]表示第一个字符串到第i位,第二个字符串到第j位为止的最长公共子序列长度 dp = [[0] * (len2 + 1) for i in range(len1 + 1)] # 动态规划数组相加的方向 b = [[0] * (len2 + 1) for i in range(len1 + 1)] # 遍历两个字符串每个位置求的最长长度 for i in range(1, len1 + 1): for j in range(1, len2 + 1): # 遇到两个字符相等 if s1[i - 1] == s2[j - 1]: # 考虑由二者都向前一位 dp[i][j] = dp[i - 1][j - 1] + 1 # 来自于左上方 b[i][j] = 1 # 遇到的两个字符不同 # 左边的选择更大,即第一个字符串后退一位 elif dp[i - 1][j] > dp[i][j - 1]: dp[i][j] = dp[i - 1][j] # 来自于左方 b[i][j] = 2 # 右边的选择更大,即第二个字符串后退一位 else: dp[i][j] = dp[i][j - 1] # 来自于上方 b[i][j] = 3 # 获取答案字符串 res = self.ans(len1, len2, b) # 检查答案是否位空 if res isNoneor res == "": return"-1" else: return res
defget(self, key: int) -> int: # write code here if key in self.lru_cache: self.lru_cache.move_to_end(key) return self.lru_cache.get(key, -1)
defset(self, key: int, value: int) -> None: # write code here if key in self.lru_cache: del self.lru_cache[key] self.lru_cache[key] = value if len(self.lru_cache) > self.size: self.lru_cache.popitem(last=False)
58、「NC94」「设计LFU缓存结构」:困难
这道题放弃吧,绝对不会考。
59、「NC95」「数组中的最长连续子序列」:困难
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # max increasing subsequence # @param arr int整型一维数组 the array # @return int整型 # classSolution: defMLS(self, arr: List[int]) -> int: # write code here nums = set(arr) res = 0 for i in nums: if i - 1notin nums: j = i + 1 while j in nums: j += 1 res = max(res, j - i) return res
60、「NC96」「判断一个链表是否为回文结构」:简单
# class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param head ListNode类 the head # @return bool布尔型 # classSolution: defisPail(self, head: ListNode) -> bool: nums = [] # 将链表元素取出一次放入数组 while head: nums.append(head.val) head = head.next temp = nums.copy() # 准备一个数组承接翻转之后的数组 temp.reverse() for i in range(len(nums)): # 正向遍历与反向遍历相同 if nums[i] != temp[i]: returnFalse returnTrue
classSolution: defsolve(self, nums): # write code here # 将整型的数字转化为字符串 s = nums for i in range(len(nums)): s[i] = str(s[i]) for i in range(len(nums)): for j in range(len(nums) - i - 1): a = nums[j] b = nums[j + 1] if int("".join([b, a])) > int("".join([a, b])): s[j], s[j + 1] = s[j + 1], s[j] if s[0] == "0": return"0" return"".join(s)
68、「NC113」「验证IP地址」:中等
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # 验证IP地址 # @param IP string字符串 一个IP地址字符串 # @return string字符串 # classSolution: defisIPv4(self, IP: str): s = IP.split(".") # IPv4必定为4组 if len(s) != 4: returnFalse for i in range(len(s)): # 不可缺省,有一个分割为零,说明两个点相连 if len(s[i]) == 0: returnFalse # 比较数字位数及不为零时不能有前缀零 if len(s[i]) < 0or len(s[i]) > 3or (s[i][0] == "0"and len(s[i]) != 1): returnFalse # 遍历每个分割字符串,必须为数字 for j in range(len(s[i])): if s[i][j] < "0"or s[i][j] > "9": returnFalse # 转化为数字比较,0-255之间 num = int(s[i]) if num < 0or num > 255: returnFalse returnTrue
defisIPv6(self, IP: str): s = IP.split(":") # IPv6必定为8组 if len(s) != 8: returnFalse for i in range(len(s)): # 每个分割不能缺省,不能超过4位 if len(s[i]) == 0or len(s[i]) > 4: returnFalse for j in range(len(s[i])): # 不能出现a-fA-F以外的大小写字符 ifnot ( s[i][j].isdigit() or s[i][j] >= "a" and s[i][j] <= "f" or s[i][j] >= "A" and s[i][j] <= "F" ): returnFalse returnTrue
defsolve(self, IP: str) -> str: if len(IP) == 0: return"Neither" if Solution.isIPv4(self, IP): return"IPv4" elif Solution.isIPv6(self, IP): return"IPv6" return"Neither"
69、「NC116」「把数字翻译成字符串」:中等
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # 解码 # @param nums string字符串 数字串 # @return int整型 # classSolution: defsolve(self, nums: str) -> int: # 排除0 if nums == "0": return0 # 排除只有一种可能的10 和 20 if nums == "10"or nums == "20": return1 # 当0的前面不是1或2时,无法译码,0种 for i in range(1, len(nums)): if nums[i] == "0": if nums[i - 1] != "1"and nums[i - 1] != "2": return0 # 辅助数组初始化为1 dp = [1for i in range(len(nums) + 1)] for i in range(2, len(nums) + 1): # 在11-19,21-26之间的情况 if (nums[i - 2] == "1"and nums[i - 1] != "0") or ( nums[i - 2] == "2"and nums[i - 1] > "0"and nums[i - 1] < "7" ): dp[i] = dp[i - 1] + dp[i - 2] else: dp[i] = dp[i - 1] return dp[len(nums)]
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param input int整型一维数组 # @param k int整型 # @return int整型一维数组 # classSolution: defGetLeastNumbers_Solution(self, input: List[int], k: int) -> List[int]: res = [] if len(input) >= k and k != 0: import heapq
# 小根堆,每次输入要乘-1 pq = [] for i in range(k): # 构建一个k个大小的堆 heapq.heappush(pq, (-1 * input[i])) for i in range(k, len(input)): # 较小元素入堆 if (-1 * pq[0]) > input[i]: heapq.heapreplace(pq, (-1 * input[i])) # 堆中元素取出入数组 for i in range(k): res.append(-1 * pq[0]) heapq.heappop(pq) return res