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 collections
d = collections.defaultdict(int)
for i in nums:
d[i] += 1
if 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 = 0
for 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 + 1
res = max(res, cur_len)
hash_dict[num] = cur_len
hash_dict[num-left] = cur_len
hash_dict[num+right] = cur_len
print(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
# BFS
while 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 = tmp
return 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:
return
dic.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 = 0
dic = {}
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”
- 解题思路
整形数组转为字符串数组排序。
知识点:
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 1
elif str(x1) + str(x2) < str(x2) + str(x1):
return -1
else:
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_key
class Solution:
def largestNumber(self, nums: List[int]) -> str:
def cmp(x1, x2):
if str(x1) + str(x2) > str(x2) + str(x1):
return 1
elif str(x1) + str(x2) < str(x2) + str(x1):
return -1
else:
return 0
nums.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 = 0
if not m or not n:
return res
def dfs(i, j):
ans = 0
while 0<=i < m and 0<=j < n and grid[i][j] == 1:
grid[i][j] = 0
ans = 1 + dfs(i+1, j) + dfs(i-1, j) + dfs(i, j-1) + dfs(i, j+1)
return ans
for 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 head
slow, fast = head, head
while fast:
if slow.val != fast.val:
slow.next = fast
slow = slow.next
fast = fast.next
slow.next = None
return 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 = 0
for char in s + "+":
if char.isdigit():
num = num * 10 + int(char)
elif char != " ":
calculate[op](num)
op, num = char, 0
# print res
return 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 defaultdict
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
pred_dict = defaultdict(int)
pred_dict[0] = 1
predSum = 0
res = 0
for i in range(len(nums)):
predSum += nums[i]
r = predSum - k
res += 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 = next
class 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.next
current.next = current.next.next
current.next.next = temp
temp.next = temp1
current = current.next.next
return 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 = 0
right = 0
min_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 += 1
right += 1
return 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-1
while left <=right:
mid = left + (right-left)//2
if nums[left] <= nums[mid] and nums[mid] <= nums[right]:
return nums[left]
elif nums[mid] >= nums[left]:
left = mid + 1
elif nums[mid] <= nums[right]:
right = mid
class Solution:
def findMin(self, nums: List[int]) -> int:
n = len(nums)
left = 0
right = n - 1
if nums[left] < nums[right]: # not rorate
return nums[left]
while left < right:
mid = left + (right-left) // 2
if nums[mid] < nums[right]:
right = mid
else:
left = mid + 1
return nums[left]