目标​:刷完灵神专题训练算法题单

阶段目标📌:【算法题单】滑动窗口与双指针

LeetCode题目:

  • 2953. 统计完全子字符串
  • 1016. 子串能表示从 1 到 N 数字的二进制串

其他:

今日总结
往期打卡


2953. 统计完全子字符串

跳转: 2953. 统计完全子字符串

学习: 题解

问题:

给你一个字符串 word 和一个整数 k

如果 word 的一个子字符串 s 满足以下条件,我们称它是 完全字符串:

  • s 中每个字符 恰好 出现 k 次。
  • 相邻字符在字母表中的顺序 至多 相差 2 。也就是说,s 中两个相邻字符 c1c2 ,它们在字母表中的位置相差 至多2

请你返回 word完全 子字符串的数目。

子字符串 指的是一个字符串中一段连续 非空 的字符序列。

思路:

从k长的窗口开始,2k,3k长依此遍历求字典值全是k的情况计数不难想
因为相邻差至多为2,所以遍历整个数组要维护窗口相邻差最值
用分组循环从边界切开分段求能简化计算同时降低复杂度

一共26个小写字母,所以哪怕长度大于26 * k也不需要再遍历
每个字符k次除了直接遍历一遍字典还可以维护字典中值为k的数量

复杂度:

  • 时间复杂度: O(26∗4∗n)O(26*4*n)O(264n)
  • 空间复杂度: O(26)O(26)O(26)

代码:

class Solution:def countCompleteSubstrings(self, word: str, k: int) -> int:def f(s:list) -> int:ans = 0for size in range(1,27):    # 26个字母,所以最多不会超过26,后面的都不用算j = size * kif j > len(s):breakcnt = Counter(s[:j])count = 0for i in cnt.values():if i == k:count += 1if count == size:   # 因为和是j,所以统计cnt里的k对上size即可ans += 1for i,ch in enumerate(s[j:]):if cnt[ch] == k:count -= 1cnt[ch] = cnt.get(ch,0) + 1if cnt[ch] == k:count += 1if cnt[s[i]] == k:count -= 1cnt[s[i]] -= 1if cnt[s[i]] == k:count += 1if count == size:ans += 1return ansi = ans = 0n = len(word)while i in range(n):    # 分组循环start = ii += 1while i < n and abs(ord(word[i])-ord(word[i - 1])) <= 2:i += 1ans += f(word[start:i])return ans

1016. 子串能表示从 1 到 N 数字的二进制串

跳转: 1016. 子串能表示从 1 到 N 数字的二进制串

学习: 题解

问题:

给定一个二进制字符串 s 和一个正整数 n,如果对于 [1, n] 范围内的每个整数,其二进制表示都是 s子字符串 ,就返回 true,否则返回 false

子字符串 是字符串中连续的字符序列。

思路:

对于去除前导0的二进制串,更长的串集合整体右移一位完全可以覆盖更短的串
于是可以用滑动窗口遍历最长的串集合
但由于n不一定是2的幂-1或-2,即最长的串集合一般不全,所以确保不漏,除了最长的次长的二进制串也要遍历

即以n的二进制长-1为k,在s上求 k 长和 k+1 长的滑动窗口

  • 区间 [2k,n][2^k,n][2k,n] 内的二进制数的长度均为 k+1k+1k+1,这有 n−2k+1n−2^k+1n2k+1 个,所以应满足 m≥k+1+(n−2k+1−1)=n−2k+k+1m≥k+1+(n−2^k+1−1)=n−2^k+k+1mk+1+(n2k+11)=n2k+k+1
  • 区间 [2k−1,2k−1][2^{k−1},2^k−1][2k1,2k1] 内的二进制数的长度均为 k,这有 2k−12^{k−1}2k1 个,所以应满足 m≥k+(2k−1−1)=2k−1+k−1m≥k+(2^{k−1}−1)=2^{k−1}+k−1mk+(2k11)=2k1+k1

复杂度:

  • 时间复杂度: O(m)O(m)O(m)
  • 空间复杂度: O(min(m,n))O(min(m,n))O(min(m,n))

代码:

# class Solution:
#     def queryString(self, s: str, n: int) -> bool:
#         set_ = set()
#         s = list(map(int,s))
#         for i,num in enumerate(s):
#             if num == 0: continue
#             j = i + 1
#             while num <= n:
#                 set_.add(num)
#                 if j == len(s): break
#                 num = num << 1 | s[j]
#                 j += 1
#         return len(set_) == nclass Solution:def queryString(self, s: str, n: int) -> bool:if n == 1:return "1" in sm = len(s)k = n.bit_length() - 1if m < max(k + 1 + (n - (1 << k)), k + (1 << k - 1) - 1):return Falsedef check(k: int, lower: int, upper: int) -> bool:if lower > upper:return Trueif k == 1:return "1" in sseen = set()bits = list(map(int, s[k - 1 :]))num = int(s[: k - 1], 2)mask = (1 << k - 1) - 1# 滑动窗口只找k长的二进制值即可for i in bits:num = ((num & mask) << 1) + iif lower <= num <= upper:seen.add(num)return len(seen) == upper - lower + 1# return check(k + 1, 1 << k, n) and check(k, 1 << k - 1, (1 << k) - 1)# 可以进一步缩小范围,不必计算全部的2^{k-1}到2^k-1,因为会和2^k到n有重复# return check(k + 1, 1 << k, n) and check(k, (n >> 1) + 1, (1 << k) - 1)# 实测用 n//2 性能更优return check(k + 1, 1 << k, n) and check(k, n // 2 + 1, (1 << k) - 1)

总结

继续练习定长滑动窗口,学习了分组循环和python二进制操作

往期打卡

暑假算法日记第三天

暑假算法日记第二天

暑假算法日记第一天

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.pswp.cn/bicheng/88192.shtml
繁体地址,请注明出处:http://hk.pswp.cn/bicheng/88192.shtml
英文地址,请注明出处:http://en.pswp.cn/bicheng/88192.shtml

如若内容造成侵权/违法违规/事实不符,请联系英文站点网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Linux 常用命令大全(2025简明版)

&#x1f9ed; 一、文件和目录操作命令说明ls列出目录内容ls -l以列表形式显示&#xff08;含权限&#xff09;cd /path切换目录pwd显示当前路径mkdir dir创建目录mkdir -p dir/subdir递归创建目录rm file删除文件rm -r dir删除目录&#xff08;递归&#xff09;rm -rf dir强制…

React Ref 指南:原理、实现与实践

前言 React Ref&#xff08;引用&#xff09;是React中一个强大而重要的概念&#xff0c;它为我们提供了直接访问DOM元素或组件实例的能力。虽然React推崇声明式编程和数据驱动的理念&#xff0c;但在某些场景下&#xff0c;我们仍需要直接操作DOM或访问组件实例。本文将深入探…

4.权重衰减(weight decay)

4.1 手动实现权重衰减 import torch from torch import nn from torch.utils.data import TensorDataset,DataLoader import matplotlib.pyplot as plt def synthetic_data(w,b,num_inputs):Xtorch.normal(0,1,size(num_inputs,w.shape[0]))yXwbytorch.normal(0,0.1,sizey.shap…

OpenCV开发-初始概念

第一章 OpenCV核心架构解析1.1 计算机视觉的基石OpenCV&#xff08;Open Source Computer Vision Library&#xff09;作为跨平台计算机视觉库&#xff0c;自1999年由Intel发起&#xff0c;已成为图像处理领域的标准工具。其核心价值体现在&#xff1a;跨平台性&#xff1a;支持…

LeetCode 930.和相同的二元子数组

给你一个二元数组 nums &#xff0c;和一个整数 goal &#xff0c;请你统计并返回有多少个和为 goal 的 非空 子数组。 子数组 是数组的一段连续部分。 示例 1&#xff1a; 输入&#xff1a;nums [1,0,1,0,1], goal 2 输出&#xff1a;4 解释&#xff1a; 有 4 个满足题目要求…

【论文解读】Referring Camouflaged Object Detection

论文信息 论文题目&#xff1a;Referring Camouflaged Object Detection 论文链接&#xff1a;https://arxiv.org/pdf/2306.07532 代码链接&#xff1a;https://github.com/zhangxuying1004/RefCOD 录用期刊&#xff1a;TPAMI 2025 论文单位&#xff1a;南开大学 ps&#xff1a…

Spring中过滤器和拦截器的区别及具体实现

在 Spring 框架中&#xff0c;过滤器&#xff08;Filter&#xff09; 和 拦截器&#xff08;Interceptor&#xff09; 都是用于处理 HTTP 请求的中间件&#xff0c;但它们在作用范围、实现方式和生命周期上有显著区别。以下是详细对比和实现方式&#xff1a;核心区别特性过滤器…

CANFD 数据记录仪在新能源汽车售后维修中的应用

一、前言随着新能源汽车市场如火如荼和新能源汽车电子系统的日益复杂&#xff0c;传统维修手段在面对复杂和偶发故障时往往捉襟见肘&#xff0c;CANFD 数据记录仪则凭借其独特优势&#xff0c;为售后维修带来新的解决方案。二、 详细介绍在新能源汽车领域&#xff0c;CANFD 数据…

某当CRM XlsFileUpload存在任意文件上传(CNVD-2025-10982)

免责声明 本文档所述漏洞详情及复现方法仅限用于合法授权的安全研究和学术教育用途。任何个人或组织不得利用本文内容从事未经许可的渗透测试、网络攻击或其他违法行为。使用者应确保其行为符合相关法律法规,并取得目标系统的明确授权。 前言: 我们建立了一个更多,更全的…

自然语言处理与实践

文章目录Lesson1&#xff1a;Introduction to NLP、NLP 基础与文本预处理1.教材2.自然语言处理概述(1)NLP 的定义、发展历程与应用场景(2)NLP 的主要任务&#xff1a;分词、词性标注、命名实体识别、句法分析等2.文本预处理3.文本表示方法&#xff1a;词向量表示/词表征Lesson2…

CSS揭秘:9.自适应的椭圆

前置知识&#xff1a;border-radius 用法前言 本篇目标是实现一个椭圆&#xff0c;半椭圆&#xff0c;四分之一椭圆。 一、圆形和椭圆 当我们想实现一个圆形时&#xff0c;通常只要指定 border-radius 为 width/height 的一半就可以了。 当我们指定的border-radius的值超过了 w…

善用关系网络:开源AI大模型、AI智能名片与S2B2C商城小程序赋能下的成功新路径

摘要&#xff1a;本文聚焦于关系在个人成功中的关键作用&#xff0c;指出关系即财富&#xff0c;善用关系、拓展人脉是成功的重要途径。在此基础上&#xff0c;引入开源AI大模型、AI智能名片以及S2B2C商城小程序等新兴技术工具&#xff0c;探讨它们如何助力个体在复杂的关系网络…

2025年渗透测试面试题总结-2025年HW(护网面试) 34(题目+回答)

安全领域各种资源&#xff0c;学习文档&#xff0c;以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具&#xff0c;欢迎关注。 目录 2025年HW(护网面试) 34 一、网站信息收集 核心步骤与工具 二、CDN绕过与真实IP获取 6大实战方法 三、常…

萤石全新上线企业AI对话智能体,开启IoT人机交互新体验

一、什么是萤石AI对话智能体&#xff1f;如何让设备听得到、听得懂&#xff1f;这次萤石发布的AI对话Agent&#xff0c;让设备能进行自然、流畅、真人感的AI对话智能体&#xff0c;帮助开发者打造符合业务场景的AI对话智能体能力&#xff0c;实现全双工、实时打断、可扩展、对话…

智绅科技:以科技为翼,构建养老安全守护网

随着我国老龄化进程加速&#xff0c;2025年60岁以上人口突破3.2亿&#xff0c;养老安全问题成为社会关注的焦点。智绅科技作为智慧养老领域的领军企业&#xff0c;以“科技赋能健康&#xff0c;智慧守护晚年”为核心理念&#xff0c;通过人工智能、物联网、大数据等技术融合&am…

矩阵系统源码部署实操指南:搭建全解析,支持OEM

矩阵系统源码部署指南矩阵系统是一种高效的数据处理框架&#xff0c;适用于大规模分布式计算。以下为详细部署步骤&#xff0c;包含OEM支持方案。环境准备确保服务器满足以下要求&#xff1a;操作系统&#xff1a;Linux&#xff08;推荐Ubuntu 18.04/CentOS 7&#xff09;硬件配…

基于python的个人财务记账系统

博主介绍&#xff1a;java高级开发&#xff0c;从事互联网行业多年&#xff0c;熟悉各种主流语言&#xff0c;精通java、python、php、爬虫、web开发&#xff0c;已经做了多年的毕业设计程序开发&#xff0c;开发过上千套毕业设计程序&#xff0c;没有什么华丽的语言&#xff0…

从 CODING 停服到极狐 GitLab “接棒”,软件研发工具市场风云再起

CODING DevOps 产品即将停服的消息&#xff0c;如同一颗重磅炸弹&#xff0c;在软件研发工具市场炸开了锅。从今年 9 月开始&#xff0c;CODING 将陆续下线其 DevOps 产品&#xff0c;直至 2028 年 9 月 30 日完全停服。这一变动让众多依赖 CODING 平台的企业和个人开发者陷入了…

#渗透测试#批量漏洞挖掘#HSC Mailinspector 任意文件读取漏洞(CVE-2024-34470)

免责声明 本教程仅为合法的教学目的而准备&#xff0c;严禁用于任何形式的违法犯罪活动及其他商业行为&#xff0c;在使用本教程前&#xff0c;您应确保该行为符合当地的法律法规&#xff0c;继续阅读即表示您需自行承担所有操作的后果&#xff0c;如有异议&#xff0c;请立即停…

深入解析C++驱动开发实战:优化高效稳定的驱动应用

深入解析C驱动开发实战&#xff1a;优化高效稳定的驱动应用 在现代计算机系统中&#xff0c;驱动程序&#xff08;Driver&#xff09;扮演着至关重要的角色&#xff0c;作为操作系统与硬件设备之间的桥梁&#xff0c;驱动程序负责管理和控制硬件资源&#xff0c;确保系统的稳定…