当前位置: 首页 > news >正文

【leetcode78-81贪心算法、技巧96-100】

贪心算法【78-81】

121.买卖股票的最佳时机

在这里插入图片描述

class Solution:def maxProfit(self, prices: List[int]) -> int:dp=[[0,0] for _ in range(len(prices))]  #dp[i][0]第i天持有股票,dp[i][1]第i天不持有股票dp[0][0] = -prices[0]for i in range(1, len(prices)):dp[i][0] = max(dp[i-1][0], -prices[i])dp[i][1] = max(dp[i-1][1],dp[i-1][0]+prices[i])return dp[-1][1]

55.跳跃游戏

在这里插入图片描述

## for循环
class Solution:def canJump(self, nums: List[int]) -> bool:cover = 0if len(nums) == 1: return Truefor i in range(len(nums)):if i <= cover:cover = max(i + nums[i], cover)if cover >= len(nums) - 1: return Truereturn False

45.跳跃游戏

在这里插入图片描述

class Solution:def jump(self, nums) -> int:if len(nums)==1:  # 如果数组只有一个元素,不需要跳跃,步数为0return 0i = 0  # 当前位置count = 0  # 步数计数器cover = 0  # 当前能够覆盖的最远距离while i <= cover:  # 当前位置小于等于当前能够覆盖的最远距离时循环for i in range(i, cover+1):  # 遍历从当前位置到当前能够覆盖的最远距离之间的所有位置cover = max(nums[i]+i, cover)  # 更新当前能够覆盖的最远距离if cover >= len(nums)-1:  # 如果当前能够覆盖的最远距离达到或超过数组的最后一个位置,直接返回步数+1return count+1count += 1  # 每一轮遍历结束后,步数+1
'''动态规划
1. dp[i]: 到nums[i]的最小跳跃次数
2. j<= nums[i]; dp[i+j] = min(dp[i+j], dp[i]+1)
3.dp[0] = 0,其他初始化为最大值
'''
class Solution:def jump(self, nums: List[int]) -> int:dp = [float('inf')] * len(nums)dp[0] = 0for i in range(len(nums)):for j in range(nums[i]+1):if i+j < len(nums):dp[i+j] = min(dp[i+j], dp[i]+1)return dp[-1]

763.划分字母区间

在这里插入图片描述

在这里插入图片描述
题目要求:划分尽可能多的片段,每个字母最多出现在一个片段里面

可以分为如下两步:

  1. 统计每一个字符最后出现的位置
  2. 从头遍历字符,并更新字符的最远出现下标,如果找到字符最远出现位置下标和当前下标相等了,则找到了分割点
class Solution:def partitionLabels(self, s: str) -> List[int]:last_occurrence = {}  # 存储每个字符最后出现的位置for index, ch in enumerate(s):last_occurrence[ch] = iresult = []start = 0end = 0for index, ch in enumerate(s):end = max(end, last_occurrence[ch])  # 找到当前字符出现的最远位置if index == end:  # 如果当前位置是最远位置,表示可以分割出一个区间result.append(end - start + 1)start = index + 1return result

技巧【96-100】

136.只出现一次的数字

在这里插入图片描述

空间常数,位运算
在这里插入图片描述

class Solution:def singleNumber(self, nums: List[int]) -> List[int]:x = 0for num in nums:  # 1. 遍历 nums 执行异或运算x ^= num      return x         # 2. 返回出现一次的数字 x

169.多数元素

在这里插入图片描述

'''
======当发生 票数和 =0 时,剩余数组的众数一定不变 =====
如果vote为0,当前元素为临时众数
如果临时众数是全局众数,抵消的数字里面,一半是众数;没抵消的数组里面,众数肯定不变
如果临时众数不是全局众数,vito会变成0
'''
class Solution:def majorityElement(self, nums: List[int]) -> int:vote = 0for i in nums:if vote == 0:x = i   #众数是iif i == x:vote += 1else : vote -= 1return x

75.颜色分类

在这里插入图片描述

在这里插入图片描述三路快排:nums[0…zero] = 0 ;nums[zero+1…i-1] = 1 ;nums[two…n-1] = 2
在这里插入图片描述在这里插入图片描述
'''
nums[0…zero] = 0 ;
nums[zero+1…i-1] = 1 ;
nums[two…n-1] = 2
'''
class Solution:def sortColors(self, nums: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""i, zero, two = 0,-1, len(nums)while i < two:if nums[i] == 1:i += 1elif nums[i] == 2:two -= 1nums[i], nums[two] = nums[two], nums[i]else:zero += 1nums[i], nums[zero] = nums[zero], nums[i]  #nums[zero]=1i += 1

31.下一个排列

在这里插入图片描述

在这里插入图片描述

class Solution:def nextPermutation(self, nums: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""length = len(nums)for i in range(length-2,-1,-1):if nums[i] >= nums[i+1]:continue  #剪枝for j in range(length-1,i,-1):if nums[j] > nums[i]:nums[j], nums[i] = nums[i], nums[j]self.reverse(nums, i+1, length-1)returnself.reverse(nums, 0, length-1)  #代表是,降序排列#翻转nums[left...... right]def reverse(self, nums, left, right):while left < right:nums[left], nums[right] = nums[right], nums[left]left += 1right -= 1

287.寻找重复数

在这里插入图片描述

环形链表在这里插入图片描述

class Solution:def findDuplicate(self, nums: List[int]) -> int:def next(i):return nums[i]slow = fast = 0while True:slow = next(slow)fast = next(next(fast))if slow == fast:breakslow = 0while slow != fast:slow = next(slow)fast = next(fast)return slow  #入环的地方

哈希表

class Solution:def findDuplicate(self, nums: List[int]) -> int:hmap = set()for num in nums:if num in hmap: return numelse:hmap.add(num)return -1

相关文章:

【leetcode78-81贪心算法、技巧96-100】

贪心算法【78-81】 121.买卖股票的最佳时机 class Solution:def maxProfit(self, prices: List[int]) -> int:dp[[0,0] for _ in range(len(prices))] #dp[i][0]第i天持有股票&#xff0c;dp[i][1]第i天不持有股票dp[0][0] -prices[0]for i in range(1, len(prices)):dp[…...

IEC62056标准体系简介-4.IEC62056-53 COSEM应用层

为在通信介质中传输COSEM对象模型&#xff0c;IEC62056参照OSI参考模型&#xff0c;制定了简化的三层通信模型&#xff0c;包括应用层、数据链路层&#xff08;或中间协议层&#xff09;和物理层&#xff0c;如图6所示。COSEM应用层完成对COSEM对象的属性和方法的访问&#xff…...

嵌入式应用开发之代码整洁之道

前言&#xff1a;本系列教程旨在如何将自己的代码写的整洁&#xff0c;同时也希望小伙伴们懂如何把代码写脏&#xff0c;以备不时之需&#xff0c;同时本系列参考 正点原子 &#xff0c; C代码整洁之道&#xff0c;编写可读的代码艺术。 #好的代码的特点 好的代码应该都有着几…...

iwconfig iwpriv学习之路

iwconfig和iwpriv是两个常用的wifi调试工具&#xff0c;最近需要使用这两个工具完成某款wifi芯片的定频测试&#xff0c;俗话说好记性不如烂笔头&#xff0c;于是再此记录下iwconfig和iwpriv的使用方式。 -----再牛逼的梦想&#xff0c;也抵不住傻逼般的坚持&#xff01; ----2…...

【Docker-compose】搭建php 环境

文章目录 Docker-compose容器编排1. 是什么2. 能干嘛3. 去哪下4. Compose 核心概念5. 实战 &#xff1a;linux 配置dns 服务器&#xff0c;搭建lemp环境&#xff08;Nginx MySQL (MariaDB) PHP &#xff09;要求6. 配置dns解析配置 lemp Docker-compose容器编排 1. 是什么 …...

【记录】LaTex|LaTex 代码片段 Listings 添加带圆圈数字标号的箭头(又名 LaTex Tikz 库画箭头的简要介绍)

文章目录 前言注意事项1 Tikz 的调用方法&#xff1a;newcommand2 标号圆圈数字的添加方式&#xff1a;\large{\textcircled{\small{1}}}\normalsize3 快速掌握 Tikz 箭头写法&#xff1a;插入点相对位移标号node3.1 第一张图&#xff1a;插入点相对位移3.2 第二张图&#xff1…...

《框架封装 · Redis 事件监听》

&#x1f4e2; 大家好&#xff0c;我是 【战神刘玉栋】&#xff0c;有10多年的研发经验&#xff0c;致力于前后端技术栈的知识沉淀和传播。 &#x1f497; &#x1f33b; CSDN入驻不久&#xff0c;希望大家多多支持&#xff0c;后续会继续提升文章质量&#xff0c;绝不滥竽充数…...

小白学webgl合集-Three.js加载器

THREE.TextureLoader: 用途: 加载单个图像文件并将其作为纹理应用到材质上。示例: const loader new THREE.DataTextureLoader(); loader.load(path/to/data.bin, function (texture) {const material new THREE.MeshBasicMaterial({ map: texture });const geometry new TH…...

【算法】字符串的排列

难度&#xff1a;中等 给你两个字符串 s1 和 s2 &#xff0c;写一个函数来判断 s2 是否包含 s1 的排列。如果是&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 换句话说&#xff0c;s1 的排列之一是 s2 的 子串 。 示例 1&#xff1a; 输入&#xff1a;…...

5-3.损失函数

文章最前&#xff1a; 我是Octopus&#xff0c;这个名字来源于我的中文名–章鱼&#xff1b;我热爱编程、热爱算法、热爱开源。所有源码在我的个人github &#xff1b;这博客是记录我学习的点点滴滴&#xff0c;如果您对 Python、Java、AI、算法有兴趣&#xff0c;可以关注我的…...

SCSA第四天

ASPF FTP --- 文件传输协议 Tftp --- 简单文件传输协议 FTP协议相较于Tftp协议 ---- 1&#xff0c;需要进行认证 2&#xff0c;拥有一套完整的命令集 用户认证 防火墙管理员认证 ---- 校验登录者身份合法性 用户认证 --- 上网行为管理中的一环 上网用户认证 --- 三层认证…...

品牌策划必读:9本改变游戏规则的营销经典

作为深耕品牌十余年的策划人&#xff0c;这些年自学啃下的书不计其数。 这里特意挑选了几本知名度不高但是却非常有用的“遗珠”优质品牌策划书籍分享出来。 如果你是一位初步了解品牌的人&#xff0c;这些书籍既包含了品牌理论基础&#xff0c;也有实用的实践指导。 这些书…...

泛型

背景 优点 类型绝对安全避免强制类型转换 泛型类 定义 使用 举例 泛型类 // 泛型类 T就是类型参数 public class Generic<T>{// key这个成员变量的类型为T,T的类型由外部指定private T t;public void set(T t){this.t t;}public T get(){return t;} }使用 // 创建一个泛…...

react动态渲染列表与函数式组件

1.如何使用jsx语法动态渲染列表呢&#xff0c;下边我用一个例子来切实总结一下 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scal…...

小程序内容管理系统设计

设计一个小程序内容管理系统&#xff08;CMS&#xff09;时&#xff0c;需要考虑以下几个关键方面来确保其功能完善、用户友好且高效&#xff1a; 1. 需求分析 目标用户&#xff1a;明确你的目标用户群体&#xff0c;比如企业、媒体、个人博主等&#xff0c;这将决定系统的功…...

HDFS 块重构和RedundancyMonitor详解

文章目录 1. 前言2 故障块的重构(Reconstruct)2.1 故障块的状态定义和各个状态的统计信息2.2 故障文件块的查找收集2.5.2.1 misReplica的检测2.5.2.2 延迟队列(postponedMisreplicatedBlocks)的构造和实现postponedMisreplicatedBlocks中Block的添加postponedMisreplicatedBloc…...

Power BI DAX常用函数使用场景和代码示例

Power BI函数表达式对于没有接触过的朋友可能会有些迷茫&#xff0c;花一点时间了解一下原理在学习一些常用的DAX函数&#xff0c;就可以解决工作中绝大部分问题&#xff0c;函数使用都是共同的。 以下是一些最常用的DAX函数&#xff0c;如聚合&#xff0c;计数&#xff0c;日期…...

机器学习与深度学习:区别与联系(含工作站硬件推荐)

一、机器学习与深度学习区别 机器学习&#xff08;ML&#xff1a;Machine Learning&#xff09;与深度学习&#xff08;DL&#xff1a;Deep Learning&#xff09;是人工智能&#xff08;AI&#xff09;领域内两个重要但不同的技术。它们在定义、数据依赖性以及硬件依赖性等方面…...

大模型/NLP/算法面试题总结5——Transformer和Rnn的区别

Transformer 和 RNN&#xff08;循环神经网络&#xff09;是两种常见的深度学习模型&#xff0c;广泛用于自然语言处理&#xff08;NLP&#xff09;任务。 它们在结构、训练方式以及处理数据的能力等方面有显著的区别。以下是它们的主要区别&#xff1a; 架构 RNN&#xff0…...

【RHCE】转发服务器实验

1.在本地主机上操作 2.在客户端操作设置主机的IP地址为dns 3.测试,客户机是否能ping通...

Android Wi-Fi 连接失败日志分析

1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分&#xff1a; 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析&#xff1a; CTR…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

Cursor实现用excel数据填充word模版的方法

cursor主页&#xff1a;https://www.cursor.com/ 任务目标&#xff1a;把excel格式的数据里的单元格&#xff0c;按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例&#xff0c;…...

css实现圆环展示百分比,根据值动态展示所占比例

代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序

一、开发准备 ​​环境搭建​​&#xff1a; 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 ​​项目创建​​&#xff1a; File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...

Redis数据倾斜问题解决

Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中&#xff0c;部分节点存储的数据量或访问量远高于其他节点&#xff0c;导致这些节点负载过高&#xff0c;影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...

给网站添加live2d看板娘

给网站添加live2d看板娘 参考文献&#xff1a; stevenjoezhang/live2d-widget: 把萌萌哒的看板娘抱回家 (ノ≧∇≦)ノ | Live2D widget for web platformEikanya/Live2d-model: Live2d model collectionzenghongtu/live2d-model-assets 前言 网站环境如下&#xff0c;文章也主…...

永磁同步电机无速度算法--基于卡尔曼滤波器的滑模观测器

一、原理介绍 传统滑模观测器采用如下结构&#xff1a; 传统SMO中LPF会带来相位延迟和幅值衰减&#xff0c;并且需要额外的相位补偿。 采用扩展卡尔曼滤波器代替常用低通滤波器(LPF)&#xff0c;可以去除高次谐波&#xff0c;并且不用相位补偿就可以获得一个误差较小的转子位…...

消防一体化安全管控平台:构建消防“一张图”和APP统一管理

在城市的某个角落&#xff0c;一场突如其来的火灾打破了平静。熊熊烈火迅速蔓延&#xff0c;滚滚浓烟弥漫开来&#xff0c;周围群众的生命财产安全受到严重威胁。就在这千钧一发之际&#xff0c;消防救援队伍迅速行动&#xff0c;而豪越科技消防一体化安全管控平台构建的消防“…...