01.01、判定字符是否唯一
01.01、[简单] 判定字符是否唯一
1、题目描述
实现一个算法,确定一个字符串 s 的所有字符是否全都不同。
在这一题中,我们的任务是判断一个字符串 s 中的所有字符是否全都不同。我们将讨论两种不同的方法来解决这个问题,并详细解释每种方法的实现过程。
2、方法一:使用哈希表计数
2.1、思路解析
我们可以利用一个哈希表(数组)来记录字符串中每个字符的出现次数。具体步骤如下:
- 字符数判断:如果字符串的长度超过 26,那么肯定有重复字符,因为只有 26 个小写字母。
- 哈希表初始化:创建一个长度为 26 的数组
hash,用于记录每个字符的出现次数。 - 遍历字符串:对于字符串中的每个字符,将对应的哈希表位置加 1。
- 重复字符检测:在遍历过程中,如果某个字符的出现次数大于 1,直接返回
false。 - 返回结果:遍历结束后,如果没有发现重复字符,返回
true。
2.2、代码实现
class Solution {
public:bool isUnique(string astr) {// 如果字符串长度超过 26,必然有重复字符if (astr.size() > 26) {return false;}// 初始化一个哈希表,长度为 26,对应 26 个字母int hash[26] = {0};// 遍历字符串中的每个字符for (const auto& ch : astr) {// 将字符转换为相应的索引位置hash[ch - 'a']++;// 如果某个字符的计数大于 1,则返回 falseif (hash[ch - 'a'] > 1) {return false;}}// 如果没有发现重复字符,返回 truereturn true;}
};
2.3、代码详解
- 首先检查字符串长度。如果长度超过 26,立即返回
false,因为小写字母只有 26 个,无法保证全部字符唯一。 - 初始化一个长度为 26 的整型数组
hash,用于记录每个字母的出现次数。 - 使用范围循环遍历字符串中的每个字符。
- 计算当前字符在
hash数组中的索引,并将其对应的值加 1。如果某个字符的计数大于 1,表示该字符重复,立即返回false。 - 遍历结束后,如果没有重复字符,则返回
true。
3、方法二:使用位图优化
3.1、思路解析
第二种方法使用了位图(bit vector)来优化空间复杂度。这种方法的核心思想是使用一个整数的位来表示字符是否出现过。具体步骤如下:
- 字符数判断:与方法一相同,首先判断字符串长度是否超过 26。
- 位图初始化:使用一个整数
bitMap来表示字符出现情况,初始值为 0。 - 遍历字符串:对于字符串中的每个字符,检查
bitMap中相应的位置是否已经设置。 - 重复字符检测:如果
bitMap中相应的位置已经设置过,返回false。否则,将该位置设置为 1。 - 返回结果:遍历结束后,如果没有发现重复字符,返回
true。
3.2、代码实现
class Solution {
public:bool isUnique(string astr) {// 利用鸽巢原理来做的优化,如果字符串长度超过 26,必然有重复字符if (astr.size() > 26)return false;// 使用位图(bit vector)来记录字符出现情况int bitMap = 0;// 遍历字符串中的每个字符for (const auto& ch : astr) {int i = ch - 'a'; // 将字符转换为相应的位位置// 判断当前字符是否已经在 bitMap 中出现过if (((bitMap >> i) & 1) == 1)return false; // 如果已出现,返回 false// 将当前字符加入到 bitMap 中bitMap |= 1 << i;}// 如果没有发现重复字符,返回 truereturn true;}
};
3.3、代码详解
- 同样首先检查字符串长度。如果长度超过 26,直接返回
false。 - 初始化一个整型变量
bitMap,初始值为 0,用于记录字符的出现情况。 - 遍历字符串中的每个字符。计算当前字符在
bitMap中对应的位位置。 - 检查
bitMap中相应的位是否已经为 1。如果为 1,表示该字符已出现过,返回false。如果当前字符没有出现过,将对应的位设置为 1。 - 遍历结束后,如果没有重复字符,返回
true。
4、总结
这两种方法都可以有效地判断一个字符串中的字符是否全都不同。方法一使用了哈希表,代码直观易懂,而方法二使用了位图优化,节省了空间。如果字符串长度超过 26,直接返回 false,因为小写字母只有 26 个,因此这是一种基于鸽巢原理的优化。选择哪种方法取决于具体的需求和优化目标。
相关文章:
01.01、判定字符是否唯一
01.01、[简单] 判定字符是否唯一 1、题目描述 实现一个算法,确定一个字符串 s 的所有字符是否全都不同。 在这一题中,我们的任务是判断一个字符串 s 中的所有字符是否全都不同。我们将讨论两种不同的方法来解决这个问题,并详细解释每种方法…...
第五届“传智杯”全国大学生计算机大赛(练习赛)水题题解
目录 复读 题目描述 输入格式 输出格式 输入输出 说明/提示 源代码 时钟 题目描述 输入格式 输出格式 输入输出 说明/提示 源代码 平等的交易 题目描述 输入格式 输出格式 输入输出 说明/提示 源代码 清洁工 题目描述 输入格式 输出格式 输入输出…...
iOS 苹果开发者账号: 查看和添加设备UUID 及设备数量
参考链接:苹果开发者账号下添加新设备UUID - 简书 如果要添加新设备到 Profiles 证书里: 1.登录开发者中心 Sign In - Apple 2.找到证书设置: Certificate,Identifiers&Profiles > Profiles > 选择对应证书 edit &g…...
推进数字园区建设-成都国际数字影像产业园
在当今数字化浪潮的席卷下,数字园区建设已成为推动区域经济发展、提升产业竞争力的关键举措。成都国际数字影像产业园作为数字产业领域的重要项目,以其独特的发展模式和创新实践,在推进数字园区建设方面取得了显著成效,为数字产业…...
oracle linux8.10+ oracle 23ai安装
介质准备: 数据库23ai https://edelivery.oracle.com 上述网站下载基础版本,本次未使用。 本次是安装了带补丁的版本: Database Release Update 23.6.0.24.10 GoldImage表示带补丁用于直接安装的软件包 查找888.1对应Primary Note for …...
PH热榜 | 2024-12-25
1. Assistive24 标语:为残障人士提供的免费辅助技术 介绍:Assistive24 是一款免费的 Chrome 浏览器扩展程序,可以帮助患有注意力缺陷多动障碍 (ADHD)、阅读障碍 (dyslexia) 和低视力等障碍的用户更方便地浏览网页。它提供语音导航、自定义…...
OpenCV相机标定与3D重建(36)计算两幅图像之间基本矩阵(Fundamental Matrix)的函数findFundamentalMat()的使用
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 从两幅图像中的对应点计算基本矩阵。 cv::findFundamentalMat 是 OpenCV 中用于计算两幅图像之间基本矩阵(Fundamental Matrix&#…...
ZLG嵌入式笔记 | 电源设计避坑(上)
产品上量后,通常都会有降成需求。多年来,接触过不少产品降成案例,在电源上下刀过猛,引发了产品偶发性问题,带来了很不好的负面影响。本文将对这些案例进行总结,提供电源设计参考,确保产品降成不…...
.NET能做什么?全面解析.NET的应用领域
.NET 是由微软开发的一个开源、跨平台的开发框架。它不仅支持构建各种应用程序,还能运行在不同的操作系统上,包括 Windows、Linux 和 macOS。自从 .NET Core 的推出,.NET 成为了一个现代化的开发平台,能够满足企业和开发者日益多样…...
初始JavaEE篇 —— 网络原理---传输层协议:深入理解UDP/TCP
找往期文章包括但不限于本期文章中不懂的知识点: 个人主页:我要学编程程(ಥ_ಥ)-CSDN博客 所属专栏:JavaEE 目录 UDP协议 参数解析: 校验和的计算 TCP协议 参数解析: 确认应答机制 超时重传 连接管理 三次握…...
企业如何搭建安全的跨网文件安全交换管理系统
在数字化转型的浪潮中,企业对数据的安全性和流动性提出了前所未有的高要求。特别是在网络隔离的情况下,如何实现跨网的安全、高效的文件交换成为了众多企业迫切需要解决的问题。 这不仅是技术上的挑战,还涉及到企业内部管理流程的优化和安全策…...
2023 年 12 月青少年软编等考 C 语言四级真题解析
目录 T1. 移动路线T2. 公共子序列T3. 田忌赛马T4. 宠物小精灵之收服 T1. 移动路线 此题为 2021 年 12 月四级第一题原题,见 2021 年 12 月青少年软编等考 C 语言四级真题解析中的 T1。 T2. 公共子序列 此题为 2022 年 3 月四级第四题原题,见 2022 年 …...
GDPU Vue前端框架开发 期末赛道出勇士篇(更新ing)
记住,年底陪你跨年的不会仅是方便面跟你的闺蜜,还有孑的笔记。 选择题 1.下列选项用于设置Vue.js页面视图的元素是()。 A. Template B. script C. style D. title 2.下列选项中能够定义Vuejs根实例对象的元素是(&…...
老旧小区用电安全保护装置#限流式防火保护器参数介绍#
摘要 随着居民住宅区用电负荷的增加,用电安全问题日益突出,火灾隐患频繁发生。防火限流式保护器作为一种新型电气安全设备,能够有效预防因电气故障引发的火灾事故。本文介绍了防火限流式保护器的工作原理、技术特点及其在居民住宅区用电系统…...
7.C语言 宏(Macro) 宏定义,宏函数
目录 宏定义 宏函数 1.注释事项 2.注意事项 宏(Macro)用法 常量定义 简单函数实现 类型检查 条件编译 宏函数计算参数个数 宏定义进行类型转换 宏定义进行位操作 宏定义进行断言 总结 宏定义 #include "stdio.h" #include "string.h" #incl…...
4.系统学习-集成学习
集成学习 前言Bias and Variance过拟合(overfitting)与欠拟合(underfitting)集成学习为什么有效?Blending 模型集成Stakcing 模型集成Bagging模型集成Bagging 模型集成算法流程:Boosting模型集成作业 前言 …...
Max AI prompt2:
1,prompt1——总体概览 “请根据以下指导原则撰写文献解读,特别关注作者的研究思路和方法论: 1. 研究背景与目的: 概述文章研究的背景,明确研究的主要目的和研究问题。 2. 研究思路: 详细描述作者如何构建…...
[Unity Shader][图形渲染]【游戏开发】 Shader数学基础8 - 齐次坐标
在计算机图形学中,齐次坐标是一种方便计算和表示几何变换的方式。通过将三维空间中的 33矩阵扩展为 44的形式,可以统一表示平移、旋转、缩放等几何变换操作。在本篇文章中,我们将详细解析齐次坐标的定义及其在图形变换中的应用。 什么是齐次坐标? 齐次坐标的核心思想是通过…...
挑战一个月基本掌握C++(第十二天)了解命名空间,模板,预处理器
一 命名空间 假设这样一种情况,当一个班上有两个名叫 Zara 的学生时,为了明确区分它们,我们在使用名字之外,不得不使用一些额外的信息,比如他们的家庭住址,或者他们父母的名字等等。 同样的情况也出现在 …...
python实现根据搜索关键词爬取某宝商品信息
当程序打开淘宝登陆页面后,需要快速手动登录淘宝,如果服务报错,需要重新登录! pip安装库 pip install pyquery pip install selenium pip install openpyxl # 代码说明:代码功能: 基于ChromeDriver爬取tao…...
KubeSphere 容器平台高可用:环境搭建与可视化操作指南
Linux_k8s篇 欢迎来到Linux的世界,看笔记好好学多敲多打,每个人都是大神! 题目:KubeSphere 容器平台高可用:环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...
浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)
✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义(Task Definition&…...
conda相比python好处
Conda 作为 Python 的环境和包管理工具,相比原生 Python 生态(如 pip 虚拟环境)有许多独特优势,尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处: 一、一站式环境管理:…...
OpenLayers 可视化之热力图
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 热力图(Heatmap)又叫热点图,是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...
突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合
强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...
相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了: 这一篇我们开始讲: 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下: 一、场景操作步骤 操作步…...
【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力
引言: 在人工智能快速发展的浪潮中,快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型(LLM)。该模型代表着该领域的重大突破,通过独特方式融合思考与非思考…...
2021-03-15 iview一些问题
1.iview 在使用tree组件时,发现没有set类的方法,只有get,那么要改变tree值,只能遍历treeData,递归修改treeData的checked,发现无法更改,原因在于check模式下,子元素的勾选状态跟父节…...
Java面试专项一-准备篇
一、企业简历筛选规则 一般企业的简历筛选流程:首先由HR先筛选一部分简历后,在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如:Boss直聘(招聘方平台) 直接按照条件进行筛选 例如:…...
