首页 > 其他分享 >代码随想录一刷day7 哈希表day1

代码随想录一刷day7 哈希表day1

时间:2024-11-07 14:44:54浏览次数:3  
标签:map set 哈希 day7 随想录 数组 day1 key 异位

遇到了要快速判断一个元素是否出现集合里的时候,就要考虑哈希法。

但是哈希法也是牺牲了空间换取了时间,因为我们要使用额外的数组,set或者是map来存放数据,才能实现快速的查找。

常见三种实现哈希表的数据结构:数组 set集合 map映射

下面是set map的

红黑树是一种平衡二叉搜索树,所以key值是有序的,但key不可以修改,改动key值会导致整棵树的错乱,所以只能删除和增加。

 要使用集合来解决哈希问题的时候,优先使用unordered_set,因为它的查询和增删效率是最优的,如果需要集合是有序的,那么就用set,如果要求不仅有序还要有重复数据的话,那么就用multiset。

虽然std::set和std::multiset 的底层实现基于红黑树而非哈希表,它们通过红黑树来索引和存储数据。不过给我们的使用方式,还是哈希法的使用方式,即依靠键(key)来访问值(value)。所以使用这些数据结构来解决映射问题的方法,我们依然称之为哈希法。

题:

242.有效的字母异位词

思路:注意不要看到字符串处理有畏难心理

很简单,创建一个26个字符的数组,遍历s,对应字符-‘a' ++,反过来遍历t, --,如果有非零的则返回false;

 

49.字母异位词分组

 思路1:可以用排序来进行,存储用unordered——map

思路2:计数

用int数组记录每个出现多少,然后输出如 2a3b等字符串来作为key值,再通过key值匹配,有点麻烦

 

438.找到字符串中所有字母异位词

思路:滑动窗口

首先将slen<plen的进行返回

然后对正常的进行处理

1.计数

2.减去头一个,加上后一个

3.每一次操作完都进行比较,如果正确则加入ans

 

标签:map,set,哈希,day7,随想录,数组,day1,key,异位
From: https://www.cnblogs.com/wzzz-blogs/p/18523765

相关文章

  • NOIP2024集训Day71 贪心
    NOIP2024集训Day71贪心B.[CCO2015]饥饿的狐狸显然的,要求出最大美味值,应该先交错吃温度最大的和最小的饼干。所以我们给所有饼干按照温度排序,交替选择左右端点吃,如果喝水能够达到更大那就先喝水再吃,反正水管够。分两种情况,即左右端点谁先开始,再取个\(\operatorname{max}\)。......
  • 条件分支语句(day10)
    首先是上一篇的评论习题://第一题哦~第一题/*从键盘输入小明的期末成绩单:当成绩为100时,奖励一辆BWMx5,当成绩[80-99]时,奖励一台iPhone14Promax1TB,当成绩[60-79]时,奖励一本参考书,当成绩为其他时,奖励一个大耳巴子。*/varscore=......
  • 代码随想录第七天|哈希表part02--454.四数相加II、383. 赎金信、15. 三数之和、18. 四
    资源引用:leetcode题目:454.四数相加Ⅱ(454.四数相加II-力扣(LeetCode))383.赎金信(383.赎金信-力扣(LeetCode))15.三数之和(15.三数之和-力扣(LeetCode))18.四数之和(18.四数之和-力扣(LeetCode))例行碎碎念:今天也追赶上了一些进度,虽然生病感冒,但今天很好的坚持了从早到晚......
  • LOJ6119 「2017 山东二轮集训 Day7」国王
    题意给定一颗树,每个点有权值\(1\)和\(-1\),称一条路径是好的当且仅当路径上所有点的权值和为\(0\)。求连续编号区间\([l,r]\)使得两个点都在\([l,r]\)的好路径比两个点都不在\([l,r]\)的好路径数严格多的方案数。\(n\le10^5\)。Sol两个端点都在区间内不好做,......
  • 代码随想录算法训练营第十八天|leetcode530.二叉搜索树的最小绝对差、leetcode501.二
    1leetcode530.二叉搜索树的最小绝对差题目链接:530.二叉搜索树的最小绝对差-力扣(LeetCode)文章链接:代码随想录视频链接:你对二叉搜索树了解的还不够!|LeetCode:98.验证二叉搜索树_哔哩哔哩_bilibili思路:定义一个极大值作为结果,然后在中序遍历过程中进行比较出结果1.1自己的......
  • LOJ6118 「2017 山东二轮集训 Day7」鬼牌
    题意有\(n\)个球,\(m\)种颜色,\(i\)种颜色有\(a_i\)个球。每次随机选择两个球\(x\),\(y\)。使两个球的颜色都变为\(y\)的颜色。问最终只有一个颜色的球的期望步数。\(n\le10^9,m\le10^5\)。Sol显然的,考虑先枚举最终颜色,我们只关心当前有多少个最终颜色的球。......
  • 代码随想录打卡Day14
    1.力扣226:翻转二叉树题目描述:给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点。示例1:输入:root=[4,2,7,1,3,6,9]输出:[4,7,2,9,6,3,1]示例2:输入:root=[2,1,3]输出:[2,3,1]示例3:输入:root=[]输出:[]解答代码:/***Definitionforabin......
  • 代码随想录打卡Day18
    1.二叉搜索树的最小绝对差:题目描述给你一个二叉搜索树的根节点 root ,返回 树中任意两不同节点值之间的最小差值 。差值是一个正数,其数值等于两值之差的绝对值。示例1:输入:root=[4,2,6,1,3]输出:1代码:/***Definitionforabinarytreenode.*structTree......
  • 代码随想录打卡Day17
    1.力扣954:最大二叉树:题目描述:给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:创建一个根节点,其值为 nums 中的最大值。递归地在最大值 左边 的 子数组前缀上 构建左子树。递归地在最大值 右边 的 子数组后缀上 构建右......
  • 代码随想录打卡Day16
    1.力扣531:找树左下角的值。题目描述:给定一个二叉树的 根节点 root,请找出该二叉树的 最底层 最左边 节点的值。假设二叉树中至少有一个节点。示例1:输入:root=[2,1,3]输出:1示例2:输入:[1,2,3,4,null,5,6,null,null,7]输出:7解答代码:/***Defi......