leecode

news/2024/10/30 21:30:27/

leecode128,最长连续子序列,哈希表枚举,要注意技巧,判断num-1是否在哈希表中,可以降低时间复杂度。

class Solution:def longestConsecutive(self, nums: List[int]) -> int:nums_set = set(nums)long_path = 0for num in nums_set:if num-1 not in nums_set:current_num = numcurrent_path = 1while current_num + 1 in nums_set:current_num += 1current_path += 1long_path = max(long_path,current_path)return long_path

旋转数组

leecode33,搜索旋转数组,二分后两边子数组一个有序一个无序,在有序的那一边继续搜索。但是要考虑重复数字的存在。

class Solution:def search(self, nums,target: int) -> int:if len(nums) == 0:return -1if len(nums) == 1:if nums[0] == target:return 0else:return -1l = 0r = len(nums)while l < r:mid = (l+r)//2if nums[mid] == target:return midif nums[l] == nums[mid] and nums[r-1] == nums[mid]:l += 1r -= 1elif nums[l]<=nums[mid]:if nums[l]<=target<=nums[mid]:r = midelse:l = mid + 1else:if nums[mid]<=target<=nums[r-1]:l = mid + 1else:r = midreturn -1

leecode81,旋转数组,leecode38加强版,有重复数字,难以判断子数组哪个有序,所以碰到nums[l],nums[mid],nums[r-1]三数字相等时,l和r分别加减1

class Solution:def search(self, nums,target: int) -> int:if len(nums) == 0:return -1if len(nums) == 1:return nums[0] == targetl = 0r = len(nums)while l < r:mid = (l+r)//2if nums[mid] == target:return Trueif nums[l] == nums[mid] and nums[r-1] == nums[mid]:l += 1r -= 1elif nums[l]<=nums[mid]:if nums[l]<=target<=nums[mid]:r = midelse:l = mid + 1else:if nums[mid]<=target<=nums[r-1]:l = mid + 1else:r = midreturn False

leecode153,查找旋转数组的最小值,二分法。注意起始区间l = 0,r = len(nums)-1,当nums[mid]>nums[r]时,说明mid在左边子区间,那么不考虑左边区间;当nums[mid]<nums[r]时,说明mid在右边区间,那么不考虑右边区间;当nums[mid] == nums[r]的时候,如果有重复元素,则无法区分,此时只能让r -= 1。返回的索引要考虑实际问题,本题就是最小元素的索引,即右边区间的最左边的点。

class Solution:def findMin(self, nums):    l,r = 0,len(nums)-1while l < r:mid = (l+r)//2if nums[mid]>nums[r]:l = mid + 1elif nums[mid] < nums[r]:r = midelse:r -= 1return nums[l]#或者nums[r]if __name__ == "__main__":solution = Solution()nums = [3,4,5,1,2]ans = solution.findMin(nums)print(ans)

leecode154,寻找旋转数组的最小值,leecode153加强版本,包含重复元素,二分法。注意起始区间l = 0,r = len(nums)-1,当nums[mid]>nums[r]时,说明mid在左边子区间,那么不考虑左边区间;nums[mid]<nums[r]时,说明mid在右边区间,那么不考虑右边区间;当nums[mid] == nums[r]的时候,如果有重复元素,则无法区分,此时只能让r -= 1

class Solution:def findMin(self, nums):    l,r = 0,len(nums)while l < r:mid = (l+r)//2if nums[mid]>nums[r-1]:l = mid + 1elif nums[mid] < nums[r-1]:r = midelse:r -= 1return nums[l]#或者nums[r]

dfs

leecode695,岛屿的最大面积,dfs,要注意变量、边界条件和递归表达式三要素

class Solution:def dfs(self, grid, cur_i, cur_j) -> int:if cur_i < 0 or cur_j < 0 or cur_i>=len(grid) or cur_j>=len(grid[0]) or grid[cur_i][cur_j] != 1:return 0grid[cur_i][cur_j] = 0ans = 1for next_i,next_j in [0,1],[0,-1],[1,0],[-1,0]:di,dj = cur_i+next_i,cur_j+next_jans += self.dfs(grid,di,dj)return ansdef maxAreaOfIsland(self, grid: List[List[int]]) -> int:ans = 0for i in range(len(grid)):for j in range(len(grid[0])):ans = max(ans,self.dfs(grid,i,j))return ans

leecode200,岛屿数量,dfs,具体代码思路和leecode695岛屿最大面积很相似

class Solution:def dfs(self, grid, cur_i, cur_j) -> int:if cur_i < 0 or cur_j < 0 or cur_i == len(grid) or cur_j == len(grid[0]) or grid[cur_i][cur_j] != "1":returngrid[cur_i][cur_j] = "0"for di, dj in [[0, 1], [0, -1], [1, 0], [-1, 0]]:next_i, next_j = cur_i + di, cur_j + djself.dfs(grid, next_i, next_j)def numIslands(self, grid: List[List[str]]) -> int:ans = 0for i in range(len(grid)):for j in range(len(grid[0])):if grid[i][j] == "1":ans += 1self.dfs(grid,i,j)return ans

leecode 463,岛屿的周长,遍历判断即可

class Solution:def islandPerimeter(self, grid: List[List[int]]) -> int:ans = 0for i in range(len(grid)):for j in range(len(grid[0])):tmp = 4if grid[i][j] == 1:for next_i,next_j in [1,0],[-1,0],[0,1],[0,-1]:di,dj = i + next_i,j+ next_jif 0<=di<len(grid) and 0<=dj<len(grid[0]) and grid[di][dj] == 1:tmp -= 1ans += tmpreturn ans

反转链表

offer24、leecode206反转链表,双指针的迭代写法+递归写法,注意递归写法中值传递和结束过程。递归写法是不断递归修改节点的next,实质是从尾部节点开始修改。

# Definition for singly-linked list.
class ListNode:def __init__(self, x):self.val = xself.next = Noneclass Solution:def reverseList(self, head: ListNode) -> ListNode:if head == None:return headpre = Nonewhile head != None:tmp = head.nexthead.next = prepre = headhead = tmpreturn preclass Solution:def reverseList(self, head: ListNode) -> ListNode:def dfs(head,pre):if head == None:return preres = dfs(head.next,head)head.next = prereturn respre = None   return dfs(head,pre)def print_node(node):while node != None:print(node.val)node = node.next
if __name__ == "__main__":head = ListNode(1)head.next = ListNode(2)head.next.next = ListNode(3)solution = Solution()ans = solution.reverseList(head)print_node(ans)# [1,2,3,4,5]

leecode92,反转链表2,反转链表的加强版本,反转部分链表,要处理好left=1的边界条件

# Definition for singly-linked list.
class Solution:def reverseBetween(self, head, left: int, right: int):if head ==None or head.next ==None:return headi = 1pre = Nonestart = headwhile i < left:pre = startstart = start.nexti += 1j = icur_pre = Nonecur = start# 反转while j <= right:tmp = cur.nextcur.next = cur_precur_pre = curcur = tmpj += 1# 接起来,要考虑从链表开始就反转的情况,这个时候表头变了if pre !=None:pre.next = cur_prestart.next = curif pre == None:head = cur_prereturn head

打家劫舍

leecode198,打家劫舍,优化空间的动态规划

class Solution:def rob(self, nums):if len(nums) == 0:return 0if len(nums) == 1:return nums[0]dp_0 = nums[0]dp_1 = max(nums[0],nums[1])for i in range(2,len(nums)):tmp = dp_0dp_0 = dp_1dp_1 = max(nums[i]+tmp,dp_1)return dp_1

leecode213,打家劫舍,环形数组,对两个子数组进行动态规划,取结果最大的值

class Solution:def robrange(self,nums):dp_0 = nums[0]dp_1 = max(nums[0],nums[1])for i in range(2,len(nums)):tmp = dp_0dp_0 = dp_1dp_1 = max(nums[i]+tmp,dp_1)return dp_1def rob(self, nums):if len(nums) == 0:return 0if len(nums) == 1:return nums[0]if len(nums) == 2:return max(nums[0],nums[1])return max(self.robrange(nums[:len(nums)-1]),self.robrange(nums[1:]))

leecode337,打家劫舍,树形dp,注意模版

# 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 rob(self, root: Optional[TreeNode]) -> int:def dfs(root):if root == None:return 0,0l_rob,l_not_rob = dfs(root.left)r_rob,r_not_rob = dfs(root.right)rob = l_not_rob + r_not_rob + root.valnot_rob = max(l_rob,l_not_rob) + max(r_rob,r_not_rob)return rob,not_robreturn max(dfs(root))

最大化最小值/最小化最大值

leecode2569,打家劫舍,最小化最大值,二分法+dp

class Solution:def minCapability(self, nums: List[int], k: int) -> int:n = len(nums)if n == 1: return nums[0]left, right = 1, 1e9+1# 求最小最大值,所以将初始最大值设置为极大的正数,方便求最小最大值ans = right while left < right:mid = (left + right) // 2   # 窃取能力mid# mid = (left + right) >> 1# dp[i],表示前 i 个(i从0算起)房间中可窃取金额不超过窃取能力mid的最大房间数dp = [0] * n# base case:第1个房屋dp[0],如果房屋金额<=窃取能力mid,选择窃取;# 第2个房屋dp[1],如果1、2间房屋其中一个满足条件,则可偷盗房间数为1,否则为0if nums[0] <= mid: dp[0] = 1dp[1] = 1 if min(nums[0], nums[1]) <= mid else 0for i in range(2, n):# 此房屋的金额nums[i]大于窃取能力mid,无法窃取,只能顺延dp[i-1]保证尽量大if nums[i] > mid:dp[i] = dp[i - 1]# 此房屋可以窃取, 可选择窃取(dp[i-2]+1)和不窃取(dp[i-1])的最优值else:dp[i] = max(dp[i - 1], dp[i - 2] + 1)# 只要窃取的房屋数量>=k即可成功,保存答案,继续寻找更小的符合条件的窃取能力if dp[n - 1] >= k:ans = midright = midelse:left = mid + 1return int(right)

http://www.ppmy.cn/news/104076.html

相关文章

有这个证书,网络安全工程师找工作不用愁

想要成为网络安全工程师&#xff0c;满足企业的用人要求。最基本的&#xff0c;你需要熟悉TCP/IP协议&#xff0c;熟悉sql注入原理和手工检测、熟悉内存缓冲区溢出原理和防范措施、熟悉信息存储和传输安全、熟悉数据包结构、熟悉Ddos攻击类型和原理。并且有一定的ddos攻防经验&…

给一个有序数组生成平衡搜索二叉树(java)

给一个有序数组生成平衡搜索二叉树 给一个有序数组生成平衡搜索二叉树递归生成二叉树专题 给一个有序数组生成平衡搜索二叉树 给定一个有序的数组,用这个数组生成一个平衡搜索二叉树. 这个题还是很简单的,知道什么时平衡搜索二叉树就行了, 左边值小于头节点值,头节点值小于右边…

Linux部署jumpserver堡垒机及问题汇总

部署过程相对复杂&#xff01;请耐心浏览&#xff01; 目录 一、jumpserver堡垒机简介 1.1 为什么需要使用堡垒机? 1.2 堡垒机主要功能 二、准备工作 2.1 关闭防火墙以及SElinux 1.2 时间同步 1.3 更改主机名 1.4 yum源备份及准备 1.5 安装初始工具 1.6 修改系统字…

对于后端Linux的入门知识

为什么使用Linux 文章来自https://librehunt.org/&#xff0c;在这个网站里&#xff0c;你可以根据它提供的选项&#xff0c;最终选出适合你的Linux版本 It’s safe and private. No tracking. No company watching over you, no “big brother is watching you” nonsense. Ju…

jmeter接口工具使用详解之基础介绍

目录 一、优点 二、安装及下载 三、基础构成 jmeter是一款优秀的开源性能测试工具&#xff0c; 一、优点 1、开源工具&#xff0c;可扩展性非常好 2、高可扩展性&#xff0c;用户可自定义调试相关模块代码 3、精心简单的GUI设计&#xff0c;小巧灵活 4、完全的可移植性…

App 软件开发《单选2》试卷及答案解析(订正)

App 软件开发《单选2》试卷及答案解析&#xff08;订正&#xff09; 注&#xff1a;本文章部分答案及解析来自 ChatGPT 的回答&#xff0c;正确性请自行甄辨。&#xff08;这玩意儿经常一本正经的胡说八道&#xff09; 文章目录 App 软件开发《单选2》试卷及答案解析&#xff0…

ASRT语音识别系统的部署以及模型的使用(运用篇)

ASRT语音识别系统的部署以及模型的使用(运用篇) 前言 ASRT是一个中文语音识别系统&#xff0c;由AI柠檬博主开源在GitHub上。 GitHub地址&#xff1a;ASRT_SpeechRecognition 国内Gitee镜像地址&#xff1a;ASRT_SpeechRecognition 文档地址&#xff1a;ASRT语音识别工具文…

iPad Pro “买后生产力” - 在iPad上远程连接服务器编程写代码【公网远程】

文章目录 前言视频教程1. 本地环境配置2. 内网穿透2.1 安装cpolar内网穿透(支持一键自动安装脚本)2.2 创建HTTP隧道 3. 测试远程访问4. 配置固定二级子域名4.1 保留二级子域名4.2 配置二级子域名 5. 测试使用固定二级子域名远程访问6. iPad通过软件远程vscode6.1 创建TCP隧道 7…