本文主要是介绍Week1-3 LeetCode（共20道题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1. 两数之和 （简单）
class Solution(object):def twoSum(self, nums, target):""":type nums: List[int]:type target: int:rtype: List[int]"""# 创字典记录：在就返回target-num的下标和i 不在就把i加入字典hashtable = dict()for i, num in enumerate(nums):if target - num in hashtable:return [hashtable[target - num], i]hashtable[nums[i]] = ireturn []
225. 用队列实现栈 （简单）
class MyStack(object):def __init__(self):self.queue1 = []self.queue2 = []def push(self, x):""":type x: int:rtype: None"""# 空的队进新元素，然后把不空的队列的元素放到刚刚添加新元素的队if not self.queue1:self.queue1.append(x)while self.queue2:self.queue1.append(self.queue2.pop(0))else:self.queue2.append(x)while self.queue1:self.queue2.append(self.queue1.pop(0))def pop(self):""":rtype: int"""if self.queue1:return self.queue1.pop(0)elif self.queue2:return self.queue2.pop(0)else:return Nonedef top(self):""":rtype: int"""if self.queue1:return self.queue1[0]elif self.queue2:return self.queue2[0]else:return Nonedef empty(self):""":rtype: bool"""return not(self.queue1) and not(self.queue2)# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()
232.用栈实现队列 （简单）
class MyQueue(object):def __init__(self):self.stack1 = []self.stack2 = []def push(self, x):self.stack1.append(x)def pop(self):if not self.stack2:while self.stack1:self.stack2.append(self.stack1.pop())return self.stack2.pop()def peek(self):if not self.stack2:while self.stack1:self.stack2.append(self.stack1.pop())return self.stack2[-1]def empty(self):return not self.stack1 and not self.stack2
2917. 找出数组中的 K-or 值 （简单）
class Solution(object):def findKOr(self, nums, k):""":type nums: List[int]:type k: int:rtype: int"""# 枚举数组nums中元素nums[j]ans = 0for i in range(31):cnt = sum(1 for num in nums if ((num >> i) & 1) > 0)if cnt >= k:ans |= 1 << i # 将ans的第i位设置为1 （将二进制数1左移i位，然后与ans执行按位或操作）return ans
2129.将标题首字母大写 （简单）
class Solution(object):def capitalizeTitle(self, title):""":type title: str:rtype: str"""res = []for word in title.split():if len(word) <= 2:res.append(word.lower())else:res.append(word[0].upper() + word[1:].lower())return ' '.join(res)
2864.最大二进制奇数 （简单）
class Solution(object):def maximumOddBinaryNumber(self, s):""":type s: str:rtype: str"""cnt = s.count('1')return '1' * (cnt - 1) + '0' * (len(s) - cnt) + '1'
2.两数相加 （中等）
# 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 addTwoNumbers(self, l1, l2):""":type l1: ListNode:type l2: ListNode:rtype: ListNode"""carry = 0head = ListNode()current = headwhile l1 or l2 or carry:x = l1.val if l1 else 0y = l2.val if l2 else 0current_sum = x + y + carrycarry = current_sum // 10current_digit = current_sum % 10current.next = ListNode(current_digit)current = current.nextif l1:l1 = l1.nextif l2:l2 = l2.nextreturn head.next
3.无重复字符的最长子串 （中等）
class Solution(object):def lengthOfLongestSubstring(self, s):""":type s: str:rtype: int"""charIndex = {} # 存储字符及其最后出现的位置left = 0 max_length = 0for i in range(len(s)):if s[i] in charIndex and charIndex[s[i]] >= left:left = charIndex[s[i]] + 1 # 更新窗口的起始位置charIndex[s[i]] = i # 更新字符的最后出现位置current_length = i - left + 1 # 计算当前窗口的长度max_length = max(max_length, current_length)return max_length
6. Z 字形变换 （中等）
class Solution(object):def convert(self, s, numRows):""":type s: str:type numRows: int:rtype: str"""if numRows < 2:return sres = ["" for _ in range(numRows)] # 创建了一个包含 numRows 个空字符串的列表i, flag = 0, -1for c in s:res[i] += cif i == 0 or i == numRows - 1:flag = -flagi += flagreturn "".join(res)
7. 整数反转（中等）
class Solution(object):def reverse(self, x):""":type x: int:rtype: int"""rev = 0Min, Max = -2**31, 2**31 - 1 # 重点：需要判断反转后的数字是否超过 32 位有符号整数的范围while x != 0:if rev < Min // 10 + 1 or rev > Max // 10:return 0digit = x % 10if x < 0 and digit > 0:digit -= 10x = (x - digit) // 10rev = rev * 10 + digitreturn rev
1976.到达目的地的方案数 （中等）
class Solution(object):def countPaths(self, n, roads):""":type n: int:type roads: List[List[int]]:rtype: int"""mod = 10 ** 9 + 7graph = {i : [] for i in range(n)}for road in roads:u, v, time = roadgraph[u].append((v, time))graph[v].append((u, time))dist = [float('inf')] * nways = [0] * ndist[0] = 0ways[0] = 1heap = [(0, 0)] #(time, node)while heap:curr_time, curr_node = heapq.heappop(heap)if curr_time > dist[curr_node]:continuefor neighbor, time in graph[curr_node]:if dist[curr_node] + time < dist[neighbor]:dist[neighbor] = dist[curr_node] + timeways[neighbor] = ways[curr_node]heapq.heappush(heap, (dist[neighbor], neighbor))elif dist[curr_node] + time == dist[neighbor]:ways[neighbor] = (ways[neighbor] + ways[curr_node]) % modreturn ways[-1]
2575.找出字符串的可整除数组 （中等）
class Solution(object):def divisibilityArray(self, word, m):""":type word: str:type m: int:rtype: List[int]"""cur = 0res = []for c in word:cur = (cur * 10 + int(c)) % mres.append(1 if cur == 0 else 0)return res
2576. 求出最多标记下标 （中等）
class Solution(object):def maxNumOfMarkedIndices(self, nums):""":type nums: List[int]:rtype: int"""# 思路：# 假设存在k对匹配# 那么 nums[i] 一定要匹配 nums[n - k + i]# 如果对于所有的 0 <= i <k 都有 2 * nums[i] <= nums[n - k + i]# 那么可以匹配k对nums.sort()left, right = 0, len(nums) // 2 + 1 # 开区间while left + 1 < right:k = (left + right) // 2if all(nums[i] * 2 <= nums[i - k] for i in range(k)):left = kelse:right = kreturn left * 2
2834. 找出美丽数组的最小和 （中等）
class Solution(object):def minimumPossibleSum(self, n, target):""":type n: int:type target: int:rtype: int"""# 使用贪心算法# 为使得数组之和最小，按照1, 2, 3...的顺序考虑# 添加了 x 之后， 就不能添加target - x# 最大可以添加到 target / 2 # 如果个数不够，继续从target, target + 1, target + 2, ... 依次添加# 两种情况# 1. n <= target / 2 # 最小数组和为 (1+n) * n / 2# 2. n > target / 2 等差数列 求和# 最小数组和为 (1 + target / 2) * target / 2 / 2 + (target + (target + (n - target / 2) - 1)) * (n - target) / 2mod = 10 ** 9 + 7m = target // 2if n <= m :return ((1 + n) * n // 2) % modreturn ((1 + m) * m // 2 + (n - m) * (target + (target + (n - m) - 1)) // 2 ) % mod
1261. 在受污染的二叉树中查找元素 (中等)
class FindElements(object):def __init__(self, root):""":type root: TreeNode"""root.val = 0self.values = set()def dfs(node):if not node:return self.values.add(node.val)if node.left:node.left.val = 2 * node.val + 1dfs(node.left)if node.right:node.right.val = 2 * node.val + 2dfs(node.right)dfs(root)def find(self, target):""":type target: int:rtype: bool"""return target in self.values
2789.合并后数组中的最大元素 （中等）
class Solution(object):def maxArrayValue(self, nums):""":type nums: List[int]:rtype: int"""for i in range(len(nums) - 2, -1, -1):if nums[i] <= nums[i + 1]:nums[i] += nums[i + 1]return nums[0]
5. 最长回文子串 （中等）
class Solution(object):def expandAroundCenter(self, s, left, right):while left >= 0 and right < len(s) and s[left] == s[right]:left -= 1right += 1return left + 1, right -1def longestPalindrome(self, s):""":type s: str:rtype: str"""start, end = 0, 0for i in range(len(s)):left1, right1 = self.expandAroundCenter(s, i, i)left2, right2 = self.expandAroundCenter(s, i, i + 1)if right1 - left1 > end - start:start, end = left1, right1if right2 - left2 > end - start:start, end = left2, right2return s[start: end + 1]
4.寻找两个正序数组的中位数 （困难）
class Solution(object):def findMedianSortedArrays(self, nums1, nums2):""":type nums1: List[int]:type nums2: List[int]:rtype: float"""nums = nums1 + nums2nums.sort()mid = len(nums) // 2if len(nums) % 2 == 0:return (nums[mid] + nums[mid - 1]) / 2.0else:return (nums[mid])
2312. 卖木头块 （困难）
class Solution:def sellingWood(self, m, n, prices):h_ps = sorted(list(set([i[0] for i in prices])))w_ps = sorted(list(set([i[1] for i in prices])))dps = [[None] * (n+1) for _ in range(m+1)]hw2p = dict()for h, w, p in prices:hw2p[(h, w)] = pdef func(h, w):if dps[h][w] is None:if h == 0 or w == 0:dps[h][w] = 0else:if (h, w) in hw2p:max_ps = hw2p[(h, w)]else:max_ps = 0for ht in h_ps:if ht >= h:breakelse:ps = func(h - ht, w) + func(ht, w)if ps > max_ps:max_ps = psfor wt in w_ps:if wt >= w:breakelse:ps = func(h, w - wt) + func(h, wt)if ps > max_ps:max_ps = psdps[h][w] = max_psreturn dps[h][w]return func(m, n)
2386.返回数组的第k大和 （困难）
class Solution(object):def kSum(self, nums, k):""":type nums: List[int]:type k: int:rtype: int"""n = len(nums)total = 0for i in range(n):if nums[i] >= 0:total += nums[i]else:nums[i] = -nums[i]nums.sort()ret = 0pq = [(nums[0], 0)]for j in range(2, k + 1):t, i = heappop(pq)ret = tif i == n - 1:continueheappush(pq, (t + nums[i + 1], i + 1))heappush(pq, (t - nums[i] + nums[i + 1], i + 1))return total - ret
这篇关于Week1-3 LeetCode（共20道题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
