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

力扣天天练--week3-LeetCode75

topic75-9-t443:压缩字符串

题目描述:

给你一个字符数组 chars ,请使用下述算法压缩:

从一个空字符串 s 开始。对于 chars 中的每组 连续重复字符 :

如果这一组长度为 1 ,则将字符追加到 s 中。
否则,需要向 s 追加字符,后跟这一组的长度。
压缩后得到的字符串 s 不应该直接返回 ,需要转储到字符数组 chars 中。需要注意的是,如果组长度为 10 或 10 以上,则在 chars 数组中会被拆分为多个字符。

请在 修改完输入数组后 ,返回该数组的新长度。

你必须设计并实现一个只使用常量额外空间的算法来解决此问题。

示例:

 思路:

  1. 定义一个辅助函数 reverse,用于反转字符列表中指定位置之间的字符。
  2. 定义变量 n,表示字符列表的长度。
  3. 定义变量 write 和 left,表示压缩后的字符列表和当前字符的左边界。
  4. 遍历字符列表,用 read 指针指向当前字符。
  5. 如果 read 指针指向字符列表的最后一个元素,或者当前字符与下一个字符不同,执行以下操作:
    • 将当前字符写入压缩后的字符列表。
    • 计算相同字符的数量,即 read - left + 1
    • 如果相同字符的数量大于 1,则将该数字转换为字符串,并写入压缩后的字符列表中。
    • 调用 reverse 函数,将数字字符串反转,使其顺序正确。
    • 将 left 指针移动到下一个字符的位置。
    • 将 write 指针移动到下一个位置,以准备写入下一个字符或数字。
  6. 返回 write,表示压缩后的字符列表的长度。

 

class Solution:def compress(self, chars: List[str]) -> int:# 定义一个辅助函数 reverse,用于反转字符列表中指定位置之间的字符def reverse(left: int, right: int) -> None:while left < right:chars[left], chars[right] = chars[right], chars[left]left += 1right -= 1n = len(chars)write = left = 0 # write 表示压缩后的字符列表中当前位置,left 表示当前字符的左边界for read in range(n): # 遍历字符列表,用 read 指针指向当前字符if read == n - 1 or chars[read] != chars[read + 1]: # 如果当前字符是最后一个字符或者与下一个字符不同chars[write] = chars[read] # 将当前字符写入压缩后的字符列表write += 1 # 将 write 指针向右移动一位num = read - left + 1 # 计算相同字符的数量if num > 1: # 如果相同字符的数量大于 1anchor = write # 将 anchor 指针指向 write 指针当前位置,用于记录数字字符串的起始位置while num > 0: # 将数字转换为字符串,并写入压缩后的字符列表中chars[write] = str(num % 10)write += 1num //= 10reverse(anchor, write - 1) # 将数字字符串反转,使其顺序正确left = read + 1 # 将 left 指针移动到下一个字符的位置,用于记录下一段相同的字符的左边界return write # 返回 write,表示压缩后的字符列表的长度

topic75-10-t283:移动零

题目描述:

给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

请注意 ,必须在不复制数组的情况下原地对数组进行操作。

示例:

 思路:

  1. 定义变量 i 和 j,分别表示当前遍历到的元素和当前非零元素的位置。
  2. 遍历列表 nums,使用指针 i 指向当前遍历到的元素。
  3. 如果 i 指向的元素不为 0,将其移到列表的非零元素区域,并将指针 j 向右移动一位,以便下一次将非零元素移到该位置。
  4. 遍历结束后,将列表中剩余的元素全部赋值为 0,以将它们移到列表的末尾。
class Solution:def moveZeroes(self, nums: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""i = 0 # 定义指针 i,表示当前遍历到的元素j = 0 # 定义指针 j,表示当前非零元素的位置# 遍历列表 numswhile i < len(nums):# 如果当前元素不为 0,将其移到列表的非零元素区域if nums[i] != 0:nums[j] = nums[i]j += 1 # 将指针 j 向右移动一位,以便下一次将非零元素移到该位置i += 1 # 将指针 i 向右移动一位,遍历下一个元素# 将列表中剩余的元素全部赋值为 0,以将它们移到列表的末尾while j < len(nums):nums[j] = 0j += 1# 算法结束,返回 None

topic75-11-t392:判断子序列

题目描述:

给定字符串 s 和 t ,判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace"是"abcde"的一个子序列,而"aec"不是)。

示例:

 思路:

  1. 定义两个指针 first 和 second,分别指向 t 和 s 的开头。
  2. 计算字符串 t 和 s 的长度 lengtht 和 lengths,如果 s 的长度为 0,则直接返回 True。
  3. 使用 while 循环遍历字符串 t,直到 first 指针到达 t 的末尾。
  4. 如果 s[second] 和 t[first] 相等,则将 first 和 second 指针分别向右移动一位,继续进行比较。
  5. 如果 s[second] 和 t[first] 不相等,则将 first 指针向右移动一位,继续进行比较。
  6. 如果 second 指针到达了 s 的末尾,说明 s 是 t 的子序列,返回 True。
  7. 如果 first 指针到达了 t 的末尾,说明已经遍历完了整个字符串 t,但是没有找到 s,返回 False。

 

class Solution:def isSubsequence(self, s: str, t: str) -> bool:first, second = 0, 0 # 初始化双指针lengtht, lengths = len(t), len(s)if lengths == 0: # 如果 s 的长度为 0,则直接返回 Truereturn Truewhile first < lengtht: # 使用 while 循环遍历字符串 tif s[second] == t[first]: # 如果 s[second] 和 t[first] 相等,则将指针分别向右移动一位,继续进行比较first += 1second += 1elif s[second] != t[first]: # 如果 s[second] 和 t[first] 不相等,则将 first 指针向右移动一位,继续进行比较first += 1if second == lengths: # 如果 second 指针到达 s 的末尾,说明 s 是 t 的子序列,返回 Truereturn Truereturn False # 如果 first 指针到达 t 的末尾,说明已经遍历完了整个字符串 t,但是没有找到 s,返回 False

topic75-13-t1679:K和数对的最大数目

题目描述:

给你一个整数数组 nums 和一个整数 k 。

每一步操作中,你需要从数组中选出和为 k 的两个整数,并将它们移出数组。

返回你可以对数组执行的最大操作数。

示例:

 思路1:先对数组排序,然后左右指针逼近,统计其中符合条件的个数,最后返回count。时间复杂度O(nlogn)

class Solution:def maxOperations(self, nums: List[int], k: int) -> int:# 思路:先排序,再左右指针逼近count = 0 # 用来存储结果length = len(nums)nums.sort() # 对 nums 排序left, right = 0, length - 1 # 定义左右指针,分别指向 nums 的开头和结尾while left < right: # 使用 while 循环遍历 numsif nums[left] + nums[right] == k: # 如果 nums[left] + nums[right] == k,说明找到了一对元素的和等于 kcount += 1 # 将 count 值加 1left += 1 # 将 left 指针向右移动一位right -= 1 # 将 right 指针向左移动一位elif nums[left] + nums[right] > k: # 如果 nums[left] + nums[right] > k,说明当前两个元素的和太大,将 right 指针向左移动一位right -= 1else: # 如果 nums[left] + nums[right] < k,说明当前两个元素的和太小,将 left 指针向右移动一位left += 1return count # 返回 count 的值

思路2:时间复杂度O(n)

  1. 使用 Python 的 Counter 类对列表 nums 进行统计,得到一个字典 tmp,其中键为列表中的元素,值为该元素在列表中出现的次数。
  2. 初始化变量 ans,用于存储结果,将其初始化为 0。
  3. 遍历字典 tmp,对于每个键值对 (num, count),根据其值的大小和键的值与 k 的关系,计算符合条件的数对数量,并将其加入 ans 中。
  4. 算法结束,返回结果。

 

from collections import Counterclass Solution:def maxOperations(self, nums: List[int], k: int) -> int:tmp = Counter(nums) # 使用 Counter 统计 nums 中每个元素出现的次数ans = 0 # 初始化变量 ans,用于存储结果for num in tmp: # 遍历 Counter 对象 tmpif num * 2 < k: # 如果 num * 2 < k,则说明可以找到与 num 相加等于 k 的数ans += min(tmp[num], tmp.get(k-num, 0)) # 将 num 和 k - num 中较小值的出现次数加入 ans 中elif num * 2 == k: # 如果 num * 2 == k,则说明 num 和 k - num 相等ans += tmp[num] // 2 # 将 num 的出现次数的一半加入 ans 中else: # 如果 num * 2 > k,则说明再往后的数都比 k - num 大,不可能找到符合条件的数对breakreturn ans # 返回结果 ans

相关文章:

力扣天天练--week3-LeetCode75

topic75-9-t443:压缩字符串 题目描述&#xff1a; 给你一个字符数组 chars &#xff0c;请使用下述算法压缩&#xff1a; 从一个空字符串 s 开始。对于 chars 中的每组 连续重复字符 &#xff1a; 如果这一组长度为 1 &#xff0c;则将字符追加到 s 中。 否则&#xff0c;需…...

5.2 方法的定义和调用

5.2 方法的定义和调用 Java的方法类似于其他语言的函数&#xff0c;是一段用来完成特定功能的代码片段&#xff0c;一般情况下&#xff0c;定义一个方法包含以下语法&#xff1a; 一、方法的定义 方法包含一个方法头和一个方法体 修饰符 返回值类型 方法名 &#xff08;参数类…...

Linux基础以及常用命令

目录 1 Linux简介1.1 不同应用领域的主流操作系统1.2 Linux系统版本1.3 Linux安装1.3.1 安装VMWare1.3.2 安装CentOS镜像1.3.3 网卡设置1.3.4 安装SSH连接工具1.3.5 Linux和Windows目录结构对比 2 Linux常用命令2.0 常用命令&#xff08;ls&#xff0c;pwd&#xff0c;cd&#…...

echarts 折线图上只显示某一个点值

<template> <div> <!-- 数据来源 --> <div class"echarts" ref"echartsRef"></div> </div> </template> <script setup langts name"reconciled"> import { ref } from "vue"; im…...

1、传统锁回顾(Jvm本地锁,MySQL悲观锁、乐观锁)

目录 1.1 从减库存聊起1.2 环境准备1.3 简单实现减库存1.4 演示超卖现象1.5 jvm锁1.6 三种情况导致Jvm本地锁失效1、多例模式下&#xff0c;Jvm本地锁失效2、Spring的事务导致Jvm本地锁失效3、集群部署导致Jvm本地锁失效 1.7 mysql锁演示1.7.1、一个sql1.7.2、悲观锁1.7.3、乐观…...

【Java||牛客】DFS应用迷宫问题

step by step. 题目&#xff1a; 描述 定义一个二维数组 N*M &#xff0c;如 5 5 数组下所示&#xff1a; int maze[5][5] { 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, }; 它表示一个迷宫&#xff0c;其中的1表示墙壁&#xff0c;0表示可…...

【vue】Vue中class样式的动态绑定

简介&#xff1a;Vue中class样式的绑定 1、字符串写法 使用场景&#xff1a;样式的类型不确定 写法&#xff1a; <div :class"xd_bg">测试账号</div> 手动触发样式改变 注意&#xff1a;字符串使用的是vue实例data中已有的属性 2、对象写法 使…...

机器学习深度学习——随机梯度下降算法(及其优化)

在我们没有办法得到解析解的时候&#xff0c;我们可以用过梯度下降来进行优化&#xff0c;这种方法几乎可以所有深度学习模型。 关于优化的东西&#xff0c;我自己曾经研究过智能排班算法和优化&#xff0c;所以关于如何找局部最小值&#xff0c;以及如何跳出局部最小值的一些基…...

【MTK平台】【wpa_supplicant】关于wpa_supplicant_8/src/p2p/p2p.c文件的介绍

本文主要介绍external/wpa_supplicant_8/src/p2p/p2p.c文件 先看下p2p_find 这个方法 P2P_find 主要用于 P2P&#xff08;点对点&#xff09;网络中查找其他对等方的功能。另外可以看到设置P2P模块的状态为 P2P_SEARCH int p2p_find(struct p2p_data *p2p, unsigned int tim…...

华为数通HCIP-流量过滤与转发路径控制

流量控制 分类&#xff1a;流量过滤、流量转发路径控制&#xff1b; 特点&#xff1a;1、作用于数据层面/转发层面&#xff1b; 2、不会影响路由表&#xff0c;针对转发流量生效&#xff1b; 实现步骤&#xff1a; 1、通过流量匹配工具匹配流量&#xff08;ACL…...

SpringBoot中定时任务开启多线程避免多任务堵塞

场景 SpringBoot中定时任务与异步定时任务的实现&#xff1a; SpringBoot中定时任务与异步定时任务的实现_霸道流氓气质的博客-CSDN博客 使用SpringBoot原生方式实现定时任务&#xff0c;已经开启多线程支持&#xff0c;以上是方式之一。 除此之外还可通过如下方式。 为什…...

回归预测 | MATLAB实现SO-CNN-BiLSTM蛇群算法优化卷积双向长短期记忆神经网络多输入单输出回归预测

回归预测 | MATLAB实现SO-CNN-BiLSTM蛇群算法优化卷积双向长短期记忆神经网络多输入单输出回归预测 目录 回归预测 | MATLAB实现SO-CNN-BiLSTM蛇群算法优化卷积双向长短期记忆神经网络多输入单输出回归预测预测效果基本介绍模型描述程序设计参考资料 预测效果 基本介绍 Matlab实…...

入侵检测——IDS概述、签名技术

1. 什么是IDS&#xff1f; IDS&#xff08;intrusion detection system&#xff09;入侵检测系统&#xff0c;是一种对网络传输进行即时监视&#xff0c;在发现可疑传输时发出警报或者采取主动反应措施的网络安全设备。它会对系统的运行状态进行监视&#xff0c;发现各种攻击企…...

golang 标准库json Marshal 序列化与反序列化

标准库代码 func Marshal(v any) ([]byte, error) {e : newEncodeState()defer encodeStatePool.Put(e)err : e.marshal(v, encOpts{escapeHTML: true})if err ! nil {return nil, err}buf : append([]byte(nil), e.Bytes()...)return buf, nil }func Unmarshal(data []byte, …...

【【51单片机AD/DA的分析】】

51单片机AD/DA的分析 看似单片机实验&#xff0c;其实是要学好数电 模数转换 与 数模转换 运算放大器 DA的转换就是利用运算放大器实现的 输出电压v0-(D7~D0)/256 x (VrefxRfb)/R D7~D0 就是我们控制的按键看输入多少 然后再划分256份 Vref是我们设置的一个基准电压 PWM 这种…...

在docker中安装使用达梦数据库

关于在docker中安装达梦数据库&#xff0c;达梦官方网站其实是有提供安装使用方法的&#xff0c;但可能还是有朋友不会&#xff0c;这里将在原文基础上简单扩充下。 注意&#xff1a;docker容器中&#xff0c;数据库安装后没有创建服务的脚本&#xff0c;只有bin、bin2、conf、…...

Leetcode-每日一题【剑指 Offer II 010. 和为 k 的子数组】

题目 给定一个整数数组和一个整数 k &#xff0c;请找到该数组中和为 k 的连续子数组的个数。 示例 1&#xff1a; 输入:nums [1,1,1], k 2输出: 2解释: 此题 [1,1] 与 [1,1] 为两种不同的情况 示例 2&#xff1a; 输入:nums [1,2,3], k 3输出: 2 提示: 1 < nums.leng…...

【JavaScript】使用Promise来处理异步调用,方法传入参数为接口,并回调接口的方法

例如我们在下面这个方法传入一个接口&#xff0c;并将方法的执行过程用传入的接口进行回调 connect() {wx.connectSocket({url: this.url,success: () > {console.log(WebSocket 连接创建成功);},fail: (err) > {console.error(WebSocket 连接创建失败, err);}});wx.onS…...

grid map学习笔记1之Ubuntu18.04+ROS-melodic编译安装grid_map栅格地图及示例运行

文章目录 0 引言1 安装依赖和编译1.1 安装依赖1.2 下载编译 2 运行示例2.1 simple_demo2.2 tutorial_demo2.3 iterators_demo2.4 image_to_gridmap_demo2.5 grid_map_to_image_demo2.6 opencv_demo2.7 resolution_change_demo2.8 filters_demo2.9 interpolation_demo 0 引言 苏…...

postgres wal2json插件jsonb字段数据丢失问题解决

使用pgwal2jsondebezium进行数据同步时&#xff0c;发现偶尔会有jsonb字段数据丢失的问题 进行测试时发现&#xff1a; 1、发生数据丢失的jsonb字段长度都比较大(超过toast阈值&#xff0c;使用toast表存储) 2、针对发生jsonb字段丢失的数据&#xff0c;jsonb字段本身未发生修…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

在四层代理中还原真实客户端ngx_stream_realip_module

一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡&#xff08;如 HAProxy、AWS NLB、阿里 SLB&#xff09;发起上游连接时&#xff0c;将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后&#xff0c;ngx_stream_realip_module 从中提取原始信息…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

佰力博科技与您探讨热释电测量的几种方法

热释电的测量主要涉及热释电系数的测定&#xff0c;这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中&#xff0c;积分电荷法最为常用&#xff0c;其原理是通过测量在电容器上积累的热释电电荷&#xff0c;从而确定热释电系数…...

协议转换利器,profinet转ethercat网关的两大派系,各有千秋

随着工业以太网的发展&#xff0c;其高效、便捷、协议开放、易于冗余等诸多优点&#xff0c;被越来越多的工业现场所采用。西门子SIMATIC S7-1200/1500系列PLC集成有Profinet接口&#xff0c;具有实时性、开放性&#xff0c;使用TCP/IP和IT标准&#xff0c;符合基于工业以太网的…...

API网关Kong的鉴权与限流:高并发场景下的核心实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 引言 在微服务架构中&#xff0c;API网关承担着流量调度、安全防护和协议转换的核心职责。作为云原生时代的代表性网关&#xff0c;Kong凭借其插件化架构…...

高防服务器价格高原因分析

高防服务器的价格较高&#xff0c;主要是由于其特殊的防御机制、硬件配置、运营维护等多方面的综合成本。以下从技术、资源和服务三个维度详细解析高防服务器昂贵的原因&#xff1a; 一、硬件与技术投入 大带宽需求 DDoS攻击通过占用大量带宽资源瘫痪目标服务器&#xff0c;因此…...