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

【算法】位运算算法——判断字符是否唯一

题解:判断字符是否唯一(位运算算法)

目录

  • 1.题目
  • 2.题解
  • 3.位图参考代码
  • 4.细节
  • 5.总结

1.题目

题目链接:LINK
在这里插入图片描述

2.题解

题解有两种方法,
一是做一个哈希数组,去查重;
二是直接用一个变量每一位来对应表示是否有这个字母即可(位图算法)。

下面仅说位图算法:
在这里插入图片描述

3.位图参考代码

class Solution {
public:bool isUnique(string astr) {if(astr.length() > 26) return false;// 鸽巢原理int ret = 0;//32个比特位全是0for(auto& ch : astr){int n = ch - 'a';// 查重if(((ret >> n) & 1) == 1) return false;// 加入ret中ret = (ret | (1 << n));}return true;}
};

4.细节

鸽巢原理:
这里如果一个string的长度 > 26 且 都为小写字母的话,那么一定有重复的,所以可以不用判断直接返回false。

5.总结

用位图比哈希数组更加节约空间,直接把O(N)的空间复杂度降成了O(1)…


EOF

http://www.lryc.cn/news/356481.html

相关文章:

  • AAAI2024 基于扩散模型 多类别 工业异常检测 DiAD
  • JavaEE-Spring Controller(服务器控制以及Controller的实现和配置)
  • 页面导出PDF,非可视区域如何解决
  • Android UI:ViewTree: 监听
  • 【光伏干货】光伏无人机巡检步骤
  • 『大模型笔记』从头开始代码构建GPT!
  • idea的project structure下project [lauguage ]()level 没有java的sdk17选项如何导入
  • JavaScript数据类型与转换
  • 三十、openlayers官网示例解析Double click, Drag and Zoom——第二次点击鼠标拖拽缩放地图效果、取消地图双击放大事件
  • 前端基础入门三大核心之网络安全篇:TLS/SSL的魔法之旅
  • Flutter 中的 SnackBarAction 小部件:全面指南
  • Point-Nerf 理论笔记和理解
  • 深度学习中的梯度消失和梯度爆炸问题
  • Flink 通过 paimon 关联维表,内存降为原来的1/4
  • Python知识详解【1】~{正则表达式}
  • 装饰模式:鸡腿堡
  • 视图【mysql数据库】
  • opencv的findContours()函数
  • 多电压档hold扫尾
  • ABAP Json解析案例
  • QT学习(20):QStyle和自定义样式
  • 香橙派 AIpro 昇腾 Ascend C++ 分类模型适配
  • 2024吉林省电赛(达盛杯)
  • 【算法题】520 钻石争霸赛 2024 全解析
  • Yii 结合MPDF 给PDF文件添加多行水印
  • 你什么时候感觉学明白Java了?
  • 马斯克xAI融资60亿美元,宣布打造世界第一超算中心,10万张H100GPU
  • 贪心算法[1]
  • 卢文岩博士受邀参与中国科学院大学校友论坛 解码DPU核心价值
  • 2024年上半年软件设计师试题及答案(回忆版)