首页 > 其他分享 >LeeCode刷题记录——哈希表

LeeCode刷题记录——哈希表

时间:2023-03-20 20:12:45浏览次数:47  
标签:le temp maxlen LeeCode 哈希 指针 ri 刷题

根本没学过这个东西,被薄纱,直接躺板板了,抑郁的时候垂死病中惊坐起,赶紧上来记一下笔记。
题目:给定一个字符串 s ,请你找出其中不含有重复字符的最长子串的长度。
评论区和官方参考答案都看了一遍,最终我选择了这个版本的答案:(才,才不是因为它简单呢)

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int le = 0, ri = 1, maxlen = 0;//定义左指针,右指针,最大长度
        int strlen = s.size();//定义strlen为字符串的长度
        if(strlen <= 1) return strlen;//处理基准情况,当字符串长度为0或者1时直接不用比了
        unordered_map<char,int> ump;//这个就是哈希表了,一般的形式是unordered_map<key,value>可以通过key的值查找对应的value,储存时是没有顺序的

        ump.insert(make_pair(s[0], 0));//在已经建立好的哈希表中插入一组值,make_pair可以将两个数据合成一组数据,这里插入了s[0]作为key,插入0作为value
        while(ri < strlen){//当右指针小于表长时
            if( ump.count(s[ri]) != 0){//如果哈希表中有s[ri](用中文解释好复杂,这个应该看得懂吧),执行下面的语句,否则跳过
                int temp_le = ump[s[ri]] + 1;//定义变量temp_le,值为哈希表中s[ri]的下一个值
                for(int i = le; i < temp_le; i++){//遍历左指针直到i=temp_le
                    ump.erase(s[i]);
//删除哈希表中的s[i]对应的value,这已经是第三个没见过的函数了,麻了,正常用法有erase(pos,n)删除从pos开始的n个字符,
//erase(position)删除position处的字符,erase(first,last)删除从first到last之间的字符
                }
                le = temp_le;//把左指针赋值为temp_le(用while循环,左指针自增到temp_le后脱离循环可以吗)
            }
            ump.insert(make_pair(s[ri], ri));//在哈希表中插入一对值,key为s[ri],value为ri
            int temp_length = ri - le + 1;//定义变量temp_length,值为每一次循环时左指针和右指针的差值
            if(temp_length > maxlen)  maxlen = temp_length;//每一次循环时,差值大于maxlen,将maxlen赋值为差值
            ri++;//右指针自加
        }
        return maxlen;
    }
};

代码都解释完了,捋一下解题思路啊:原作者的思路和答案掺糅在一起,太长了,我这里说简单点,看不懂这里有链接:(官方有思路视频,但我没看,比较懒):https://leetcode.cn/problems/longest-substring-without-repeating-characters/solutions/227999/wu-zhong-fu-zi-fu-de-zui-chang-zi-chuan-by-leetc-2/
思路:首先遍历一遍字符串,把字符串的值和对应的位置都遍历进哈希表里,遍历的过程中如果遇到了相同的值,就把第一个左指针(temp_le)移到右指针前面一格的位置,然后把第一个指针(le)到第二个左指针间的元素全部删掉,在每一次循环结束的时候,比较当前左指针和右指针的差值与maxlen的大小,直到遍历结束,maxlen输出遍历其中差值最大的一次。
(虽然上一篇的博客的阅读量是大了点,但我毕竟还是个菜鸡,这种刷题笔记该记就得记)

标签:le,temp,maxlen,LeeCode,哈希,指针,ri,刷题
From: https://www.cnblogs.com/apeiriaDolce/p/17237538.html

相关文章

  • leetcode刷题--TypeError:object of type 'NoneType' has no len()/AttributeError: 'N
    错误:一.TypeError:objectoftype'NoneType'hasnolen()list=[]i=0j=0whilelen(list)<=len(nums1)+len(nums2):报错:TypeError:objectoftype'NoneType'ha......
  • 字符串哈希函数
    1、概念哈希之所以广泛存在,是因为它能在绝大多数情况下可以在O(1)的时间复杂度中完成元素的查找。它的核心是数组,如果输入是一个自然数,那么当然可以在常数时间内搜索到自......
  • DJBX33A哈希(Hash)算法
    1DJBX33A算法原理2DJBX33A算法典型实现2.1PHP(zend_string.h)2.2Apache(apr_hash.c)2.3BerkeleyDB(src\hash\hash_func.c)2.4Python(pyhash.c)3DJBX33A......
  • 刷题疑惑2
    1、整数除法:先转化为unsignedint;通过逆向乘法,使除数左移至不大于被除数的最左位,再相减;此时的商就是1左移对应的位数,继续循环判断左移,商用或逻辑相加,最终判断此值是否......
  • P4343 [SHOI2015]自动刷题机
    https://www.luogu.com.cn/problem/P4343 #include<iostream>usingnamespacestd;constintN=1e5+2;#defineintlonglongconstintinf=1e15;inta[N],n......
  • 【LeeCode】26. 删除有序数组中的重复项
    【题目描述】给你一个 升序排列 的数组 ​​nums​​​ ,请你​​ 原地​​ 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 ......
  • 算法刷题记录
    http://acm.hdu.edu.cn/showproblem.php?pid=1094#include<iostream>#include<vector>intmain(){usingnamespacestd;vector<int>vecrow;......
  • 【LeeCode】207. 课程表 -- todo
    【题目描述】你这个学期必须选修 ​​numCourses​​​ 门课程,记为 ​​0​​​ 到 ​​numCourses-1​​ 在选修某些课程之前需要一些先修课程。先修课程按数组 ......
  • 【链表】复习/刷题 记录
    leetcode203.RemoveLinkedListElements/***Definitionforsingly-linkedlist.*structListNode{*intval;*ListNode*next;*ListNode......
  • 【LeeCode】1122. 数组的相对排序
    【题目描述】给你两个数组,​​arr1​​​ 和 ​​arr2​​​,​​arr2​​​ 中的元素各不相同,​​arr2​​​ 中的每个元素都出现在 ​​arr1​​ 中。对 ​​arr1​......