热题系列章节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 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. 解题思路
    整形数组转为字符串数组排序。
知识点:
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]

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/695837.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

shell编程(三)—— 运算符

和其他编程语言一样&#xff0c;bash也有多种类型的运算符&#xff0c;本篇对bash的相关运算符做简单介绍。 一、运算符 1.1 算术运算符 常见的算术运算符&#xff0c;如加&#xff08;&#xff09;、减&#xff08;-&#xff09;、乘&#xff08;*&#xff09;、除&#xf…

简单介绍一下vim

简单介绍一下vim 一、vim是什么&#xff1f;二、vim的优点三、vi/vim的使用命令模式输入模式底线命令模式 四、vi/vim 按键说明&#xff08;一&#xff09;命令模式可用的光标移动、复制粘贴、搜索替换等移动光标的方法:搜索替换的方法删除、复制与贴上的方法 &#xff08;二&a…

嵌入式Linux系统编程 — 3.5 utime、utimes、futimens、utimensat函数修改文件时间属性

目录 1 文件的时间属性简介 2 utime()函数 2.1 utime()函数简介 2.2 示例程序 3 utimes()函数 3.1 utimes()函数简介 3.2 示例程序 4 futimens()函数 4.1 futimens()函数简介 4.2 示例程序 5 utimensat()函数 5.1 utimensat()函数简介 5.2 示例程序 1 文件的时间…

如何从SD存储卡恢复已删除的图像

SD卡概述 在日常工作和学习中&#xff0c;SD卡经常被用作许多设备上的存储设备&#xff0c;例如数码相机&#xff0c;手机&#xff0c;摄像机&#xff0c;行车记录仪以及监控设备&#xff0c;用于为我们存储图像&#xff0c;视频&#xff0c;文档&#xff0c;音频和其他数据。…

html5实现个人网站源码

文章目录 1.设计来源1.1 网站首页页面1.2 个人工具页面1.3 个人日志页面1.4 个人相册页面1.5 给我留言页面 2.效果和源码2.1 动态效果2.2 目录结构 源码下载 作者&#xff1a;xcLeigh 文章地址&#xff1a;https://blog.csdn.net/weixin_43151418/article/details/139564407 ht…

12. Django 第三方功能应用

12. 第三方功能应用 因为Django具有很强的可扩展性, 所以延伸了第三方功能应用. 通过本章的学习, 读者能够在网站开发过程中快速实现API接口开发, 验证码生成与使用, 站内搜索引擎, 第三方网站实现用户注册, 异步任务和定时任务, 即时通信等功能.12.1 Django Rest Framework框…

【YOLOv5进阶】——修改网络结构(以C2f模块为例)

一、站在巨人的肩膀上 这里我们借鉴YOLOv8源码&#xff1a; 上期说到&#xff0c;对于网络模块定义详情在common.py这个文件&#xff0c;如Conv、CrossConv、C3f等。本期要修改的需要参考YOLOv8里的C2f模块&#xff0c;它定义在YOLOv8的module文件夹的block.py文件里&#xf…

js调试过程中修改变量值

1.在想要变更的地方添加断点 2.添加监视表达式 3.执行网页代码&#xff0c;当执行到断点处则会停止 4.点击执行下一步&#xff0c;则会执行监视表达式

新材料正不断推动模具3D打印行业发展

随着工业4.0的浪潮席卷全球&#xff0c;模具制造行业也迎来了技术革新的新纪元。3D打印技术以其独特的制造优势&#xff0c;正逐渐在模具制造领域崭露头角。然而&#xff0c;要实现模具3D打印技术的广泛应用&#xff0c;高性能的打印材料是不可或缺的关键因素。 材料是模具3D打…

一、Socket创建和连接

C网络编程&#xff08;asio&#xff09; 文章目录 C网络编程&#xff08;asio&#xff09;1、Asio概述2、网络编程基本流程2、创建socket3、创建监听socket4、绑定accpet监听套接字5、连接指定的端点6、服务器接收连接 点击查看代码 1、Asio概述 ​ Asio起源于Boost库&#xf…

超详解——python条件和循环——小白篇

目录 1. 缩进和悬挂else 2. 条件表达式 3. 和循环搭配的else 4. 可调用对象 总结&#xff1a; 1. 缩进和悬挂else 在Python中&#xff0c;代码块是通过缩进来表示的。条件判断和循环结构的代码块需要正确缩进。悬挂else指的是else子句和相应的if或循环在同一级别的缩进。 …

AVL树 ---(C++)

本篇讲全面的讲解 AVL 树的插入&#xff0c;旋转以及验证 AVL 树的性能&#xff08;本篇未实现删除代码&#xff09;。至于为什么会有 AVL 树&#xff0c;这是因为简单的二叉搜索树并不能直接的保证搜索的效率&#xff0c;因为当我们在二叉搜索树中插入一段有序的序列的时候&am…

STC90C51驱动LCD1602、LCD12864、OLED

主控芯片&#xff08;STC90C516RDPG5151028&#xff09;介绍 ROM64K,RAM1280字节&#xff0c;40Pin&#xff0c;3个定时器&#xff0c;1个串口&#xff0c;8个中断源&#xff08;分别是&#xff1a;外部中断0(INTO)、外部中断 1(INT1)、外部中断 2(INT2)、外部中断 3(INT3)、定…

【微信小程序开发(从零到一)】——个人中心页面的实战项目(二)

&#x1f468;‍&#x1f4bb;个人主页&#xff1a;开发者-曼亿点 &#x1f468;‍&#x1f4bb; hallo 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍&#x1f4bb; 本文由 曼亿点 原创 &#x1f468;‍&#x1f4bb; 收录于专栏&#xff1a…

「动态规划」如何计算能获得多少点数?

740. 删除并获得点数https://leetcode.cn/problems/delete-and-earn/description/ 给你一个整数数组nums&#xff0c;你可以对它进行一些操作。每次操作中&#xff0c;选择任意一个nums[i]&#xff0c;删除它并获得nums[i]的点数。之后&#xff0c;你必须删除所有等于nums[i] …

【网络安全的神秘世界】web应用程序安全与风险

&#x1f31d;博客主页&#xff1a;泥菩萨 &#x1f496;专栏&#xff1a;Linux探索之旅 | 网络安全的神秘世界 | 专接本 第一章&#xff1a;web应用程序安全与风险 web攻击基础知识 1、什么是web应用攻击 web攻击的本质&#xff0c;就是通过http协议篡改应用程序&#xff0…

虚拟机ping不通主机,但是主机可以ping通虚拟机

我在Windows10系统安装了虚拟机&#xff0c;设置的主机与虚拟机的连接方式是桥接&#xff0c;安装好后&#xff0c;发现虚拟机ping不通主机&#xff0c;但是主机可以ping通虚拟机。 我的操作是&#xff1a;关闭防火墙&#xff0c;发现虚拟机可以ping通主机了。说明是Windows10…

python后端结合uniapp与uview组件tabs,实现自定义导航按钮与小标签颜色控制

实现效果&#xff08;红框内&#xff09;&#xff1a; 后端api如下&#xff1a; task_api.route(/user/task/states_list, methods[POST, GET]) visitor_token_required def task_states(user):name_list [待接单, 设计中, 交付中, 已完成, 全部]data []color [#F04864, …

CPP初级:模板的运用!

目录 一.泛型编程 二.函数模板 1.函数模板概念 2.函数模板格式 3.函数模板的原理 三.函数模板的实例化 1.隐式实例化 2.显式实例化 3.模板参数的匹配原则 四.类模板 1.类模板的定义格式 2.类模板的实例化 一.泛型编程 泛型编程&#xff1a;编写与类型无关的通用代码…

express入门01服务器搭建以及get和post请求的监听

微搭提供了后端API的能力&#xff0c;但是不同的版本收费差别巨大&#xff0c;因为使用的门槛限制了中小企业使用低代码平台。那可不可以既要又要呢&#xff1f;答案是肯定的&#xff0c;那其实掌握一定的后端框架&#xff0c;借助我们在低代码中已经熟练掌握的技能其实是比较容…