热题系列章节5

169. 多数元素

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1:
输入: [3,2,3]
输出: 3

示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2

题目要求返回出现次数大于⌊ n/2 ⌋ 的元素，这里需要向下取整，并使用Counter()统计数组中元素及其出现的次数，最后遍历统计字典中元素的值，找到值大于⌊ n/2 ⌋ 的键返回即可。

class Solution:def majorityElement(self, nums: List[int]) -> int:import collectionsd = collections.defaultdict(int)for i in nums:d[i] += 1if d[i] > len(nums) // 2:return i 

128. 最长连续序列

用哈希表存储每个端点值对应连续区间的长度
若数已经在哈希表中: 跳过不做处理
若是新数则加入：
取出其左右相邻数已有的连续区间长度 left 和 right
计算当前数的区间长度：cur_length = left + right + 1
根据cur_length 更新最大长度 max_length的值
更新区间两端点的长度值
3
2:2 (1, 2)
4:3 (4, 5,6)
2 + 1 + 3 = 6

class Solution:def longestConsecutive(self, nums: List[int]) -> int:hash_dict = dict()res = 0for num in nums:if num not in hash_dict:left = hash_dict.get(num-1, 0)right = hash_dict.get(num + 1, 0)cur_len = left + right + 1res = max(res, cur_len)hash_dict[num] = cur_lenhash_dict[num-left] = cur_lenhash_dict[num+right] = cur_lenprint(hash_dict)return res

662. 二叉树最大宽度

给你一棵二叉树的根节点 root ，返回树的 最大宽度 。

树的 最大宽度 是所有层中最大的 宽度 。

每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。

题目数据保证答案将会在 32 位 带符号整数范围内。

示例 1：

输入：root = [1,3,2,5,3,null,9]
输出：4
解释：最大宽度出现在树的第 3 层，宽度为 4 (5,3,null,9) 。
示例 2：

输入：root = [1,3,2,5,null,null,9,6,null,7]
输出：7
解释：最大宽度出现在树的第 4 层，宽度为 7 (6,null,null,null,null,null,7) 。
示例 3：

输入：root = [1,3,2,5]
输出：2
解释：最大宽度出现在树的第 2 层，宽度为 2 (3,2) 。
提示：

树中节点的数目范围是 [1, 3000]
-100 <= Node.val <= 100

# 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
class Solution:def widthOfBinaryTree(self, root: TreeNode) -> int:if not root:return 0# 分别是坐标和节点queue = [(0, root)]res = 1# BFSwhile queue:# 首末元素的坐标差就是最大宽度res = max(res, queue[-1][0] - queue[0][0] + 1)tmp = []for i, q in queue:if q.left:tmp.append((i * 2, q.left))if q.right:tmp.append((i * 2 + 1, q.right))queue = tmpreturn res

# 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
class Solution:def widthOfBinaryTree(self, root: TreeNode) -> int:# dfs更新最大宽度，用字典记录每层的左侧节点pos，递归时传递当前遍历到的root的pos# 时间复杂度O(N)；空间复杂度O(N)def dfs(root, pos=0, level=0):if not root:returndic.setdefault(level, pos)self.max_width = max(self.max_width, pos - dic[level] + 1)dfs(root.left, pos*2, level+1)dfs(root.right, pos*2+1, level+1)self.max_width = 0dic = {}dfs(root)return self.max_width

179. 最大数

. 题目描述
给定一组非负整数 nums，重新排列它们每位数字的顺序使之组成一个最大的整数。

注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。

示例 1：

输入：nums = [10,2]
输出：“210”
示例 2：

输入：nums = [3,30,34,5,9]
输出：“9534330”
示例 3：

输入：nums = [1]
输出：“1”
示例 4：

输入：nums = [10]
输出：“10”

2. 解题思路
   整形数组转为字符串数组排序。

知识点：
1.sorted(iterable, cmp=None, key=None, reverse=False)：此语法针对Python2，在Python3中，cmp参数被移除，需要在key的地方传入functools.cmp_to_key函数。根据sorted的机制，cmp传入之后，会根据传入的自定义函数排序，类似于冒泡排序。自定义函数需要指定x1 < x2时，返回-1，x1 > x2时，返回1，x1 == x2时，返回0，最后根据规则返回升序结果。例如，传入的自定义函数如下：def cmp(x1, x2):if str(x1) + str(x2) > str(x2) + str(x1):return 1elif str(x1) + str(x2) < str(x2) + str(x1):return -1else:return 0
将两数以字符串形式拼接比较大小，最后将以升序形式返回拼接结果最大的列表，将列表中每个数连起来就是结果。排序做的相当于两两比较str(x1) + str(x2)和str(x2) + str(x1)的关系，将小的放前面，大的放后面。2.functools.cmp_to_key（callable）：将比较函数转化为关键字函数。callable是函数名。传入的函数接受2个参数，比较这2个参数，例如：x，y， 当x > y时返回1；小于时返回-1；否则返回0。

from functools import cmp_to_keyclass Solution:def largestNumber(self, nums: List[int]) -> str:def cmp(x1, x2):if str(x1) + str(x2) > str(x2) + str(x1):return 1elif str(x1) + str(x2) < str(x2) + str(x1):return -1else:return 0nums.sort(key=cmp_to_key(cmp), reverse=True)return str(int(''.join(map(str, nums))))

695. 岛屿的最大面积

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
输出：6
解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。
示例 2：

输入：grid = [[0,0,0,0,0,0,0,0]]
输出：0

class Solution:def maxAreaOfIsland(self, grid: List[List[int]]) -> int:m, n = len(grid), len(grid[0])res = 0if not m or not n:return resdef dfs(i, j):ans = 0while 0<=i < m and 0<=j < n and grid[i][j] == 1:grid[i][j] = 0ans = 1 + dfs(i+1, j) + dfs(i-1, j) + dfs(i, j-1) + dfs(i, j+1)    return ansfor i in range(m):for j in range(n):if grid[i][j] == 1:res = max(res, dfs(i, j))return res

83. 删除排序链表中的重复元素

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:if not head or not head.next:return headslow, fast = head, headwhile fast:if slow.val != fast.val:slow.next = fastslow = slow.nextfast = fast.nextslow.next = Nonereturn head

227. 基本计算器 II

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

整数除法仅保留整数部分。

你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。

注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

示例 1：
输入：s = “3+2*2”
输出：7

示例 2：
输入：s = " 3/2 "
输出：1

示例 3：
输入：s = " 3+5 / 2 "
输出：5

提示：
1 <= s.length <= 3 * 105
s 由整数和算符 (‘+’, ‘-’, ‘*’, ‘/’) 组成，中间由一些空格隔开
s 表示一个 有效表达式
表达式中的所有整数都是非负整数，且在范围 [0, 231 - 1] 内
题目数据保证答案是一个 32-bit 整数

关键在于怎么处理乘法和除法，如果是乘法或者除法，我们需要用前面的数和当前的数做运算。
因此此处可以用栈来记录前面的数字，用一个符号变量记录前一个符号，当遍历到一个新数字时，判断一下前面的符号是什么，
如果是乘除，就和前面的数字运算，如果是+，就向栈中push这个数字，如果是-，就push这个数字的负数。
遍历到结尾，把最后一个数字入栈，此时栈中存放的都是要进行加法运算的数字。

import operator
class Solution(object):def calculate(self, s):""":type s: str:rtype: int"""res = []calculate = {"+": lambda x: res.append(x),"-": lambda x: res.append(-x),"*": lambda x: res.append(x * res.pop()),"/": lambda x: res.append(int(operator.truediv(res.pop(), x)))}op = "+"num = 0for char in s + "+":if char.isdigit():num = num * 10 + int(char)elif char != " ":calculate[op](num)op, num = char, 0# print resreturn sum(res)

152. 乘积最大子数组

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

示例 1:

输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:

输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

class Solution:def maxProduct(self, nums: List[int]) -> int:res = pre_min = pre_max = nums[0]for i in range(1, len(nums)):tmp1 = pre_min*nums[i]tmp2 = pre_max*nums[i]pre_max = max(nums[i], tmp1, tmp2)pre_min = min(nums[i], tmp1, tmp2)res = max(pre_max, res)return res

560. 和为K的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

示例 1：
输入：nums = [1,1,1], k = 2
输出：2

示例 2：
输入：nums = [1,2,3], k = 3
输出：2

提示：

1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107

前缀和+哈希
在遍历的过程中构建前缀和
使用字典记录每个前缀和的出现次数
把presum[i]-presum[j] == k  ->找sumi - k 是否存在
用哈希存已有的前缀和结果+次数，

from collections import defaultdictclass Solution:def subarraySum(self, nums: List[int], k: int) -> int:pred_dict = defaultdict(int)pred_dict[0] = 1predSum = 0res = 0for i in range(len(nums)):predSum += nums[i]r = predSum - kres += pred_dict[r]pred_dict[predSum] = pred_dict[predSum]  + 1 return res 

24. 两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = nextclass Solution:def swapPairs(self, head: ListNode) -> ListNode:dummy_head = ListNode(next=head)current = dummy_head# 必须有cur的下一个和下下个才能交换，否则说明已经交换结束了while current.next and current.next.next:temp = current.next # 防止节点修改temp1 = current.next.next.nextcurrent.next = current.next.nextcurrent.next.next = temptemp.next = temp1current = current.next.nextreturn dummy_head.next

209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例：
输入：s = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

提示：
1 <= target <= 10^9
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^5

class Solution:def minSubArrayLen(self, s: int, nums: List[int]) -> int:l = len(nums)left = 0right = 0min_len = float('inf')cur_sum = 0 #当前的累加值while right < l:cur_sum += nums[right]while cur_sum >= s: # 当前累加值大于目标值min_len = min(min_len, right - left + 1)cur_sum -= nums[left]left += 1right += 1return min_len if min_len != float('inf') else 0

153. 寻找旋转排序数组中的最小值

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

示例 2：
输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 3 次得到输入数组。

示例 3：
输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。

class Solution:def findMin(self, nums: List[int]) -> int:n = len(nums)left, right = 0, n-1while left <=right:mid = left + (right-left)//2if nums[left] <= nums[mid] and nums[mid] <= nums[right]:return nums[left]elif nums[mid] >= nums[left]:left = mid + 1elif nums[mid] <= nums[right]:right = mid

class Solution:def findMin(self, nums: List[int]) -> int:n = len(nums)left = 0right = n - 1if nums[left] < nums[right]:  # not roratereturn nums[left]while left < right:mid = left + (right-left) // 2if nums[mid] < nums[right]:right = midelse:left = mid + 1return nums[left]