[算法刷题笔记]哈希表(1)

╰+攻爆jí腚メ 2024-04-21 08:03 84阅读 0赞

> #### ✨哈希表刷题笔记 ####
> 
>  *  前言
>  *  找到字符串中第一个唯一字符
>  *  有效的字母异位词
>  *  NC312 字母异位词的长度
>  *  结束语
> 
>   
> ?个人主页: [不断前进的皮卡丘][Link 1]  
> ?博客描述: **梦想也许遥不可及，但重要的是追梦的过程，用博客记录自己的成长，记录自己一步一步向上攀登的印记**  
> **?网站推荐：千里之行，始于足下。每天坚持刷题，巩固所学知识，也为将来找工作，面试做好准备**\----- [刷题神器][Link 2]  
> ✔️ 对于哈希表相关知识不清楚的，大家可以看看这篇博客[哈希表细节狂魔][Link 3]  
> ![在这里插入图片描述][04f3be82e4c54e9390727ca29efede52.png_pic_center]

## 前言 ##

> 学习算法，还有一些知识的时候，有时候看书后以为自己懂了，结果做题就发现自己没什么思路，为此，博主决定坚持刷题，这里给大家推荐一个适合大家做题复习，准备面试的网站[点此进入][Link 2]，里面还有大量的面经，大家可以在面试之前去看看  
> ![在这里插入图片描述][15ff82da90f44be2a95cb48c93105248.png]  
> 我们可以看到里面根据不同知识层面分成对应的题库，算法也进行了对应的分类，十分的友好，接下来就开始今天的刷题之旅

## 找到字符串中第一个唯一字符 ##

![在这里插入图片描述][27f61849e1184138aab6ac34e7d45d6e.png]

class Solution {
        
        public int firstUniqChar(String s) {
        
            //用来存储每一个字母出现的次数
              int[] cnt=new int[26];
            for(int i=0;i<s.length();i++){
        
                int index=s.charAt(i)-'a';
                cnt[index]++;
            }
            //遍历数组
            for(int i=0;i<s.length();i++){
        
                //获得字符在计数数组中的下标
                 int index=s.charAt(i)-'a';
                 if(cnt[index]==1){
        
                     return i;
                 } 
            }
            return -1;
    
        }
    }

## 有效的字母异位词 ##

给定两个字符串s,t，我们需要判断s和t是不是字母异位词，其实就是说，字符串s和t出现的字符必须是相同的，并且出现的次数要一样。

class Solution {
        
       public boolean isAnagram(String s, String t) {
        
           if(s.length()!=t.length()) return false;
           //构造哈希表
         int[]arr=new int[26];
           for(int i=0;i<s.length();i++){
        
               //计算字符串s在哈希表中出现多少次
               arr[s.charAt(i)-'a']++;
           }
           //接下来，我们只需要把字符串t每个字符遍历
           //看它在哈希表中出现的次数是否和s相同就可以了 
           //如果对应下标的元素值为0，说明这个字符在字符串s中没出现过，但是在t出现过，返回false 
           //如果下标相同，但是出现次数不一样，也说明他们不是字母异位词
           for(int i=0;i<t.length();i++){
        
               if(arr[t.charAt(i)-'a']==0){
        
                   return false;
               }else{
        
                   arr[t.charAt(i)-'a']--;
               }
    
               
           }
           //最后我们只需要遍历哈希表，看看对应下标的元素值是否为0，就能知道二者字符出现的次数是否相同
           for(int i=0;i<arr.length;i++){
        
               if(arr[i]!=0){
        
                   return false;
               }
           }
           return true;
       }
    }

接下来，我们可以做几道相关的变形题目

## NC312 字母异位词的长度 ##

[字母异位词的长度][Link 4]  
![在这里插入图片描述][30c26c1198fc4e34b84e7d33a4f95abe.png]  
题目的意思是如果s,c是字母异位词，那么就返回他们的长度，如果不是，就返回-1，我们只需要根据前面一道题目的模板来进行修改

import java.util.*;
    
    
    public class Solution {
        
       /**
        * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
        *
        * 
        * @param s string字符串 
        * @param c string字符串 
        * @return int整型
        */
       public int isCongruent (String s, String c) {
        
           // write code here
            if(s.length()!=c.length()) return -1;
          //构造哈希表
         int[]arr=new int[26];
          for(int i=0;i<s.length();i++){
        
              //计算字符串s在哈希表中出现多少次
              arr[s.charAt(i)-'a']++;
          }
          //接下来，我们只需要把字符串t每个字符遍历
          //看它在哈希表中出现的次数是否和s相同就可以了 
          //如果对应下标的元素值为0，说明这个字符在字符串s中没出现过，但是在t出现过，返回false 
          //如果下标相同，但是出现次数不一样，也说明他们不是字母异位词
          for(int i=0;i<c.length();i++){
        
              if(arr[c.charAt(i)-'a']==0){
        
                  return -1;
              }else{
        
                  arr[c.charAt(i)-'a']--;
              }
    
              
          }
          //最后我们只需要遍历哈希表，看看对应下标的元素值是否为0，就能知道二者字符出现的次数是否相同
          for(int i=0;i<arr.length;i++){
        
              if(arr[i]!=0){
        
                  return -1;
              }
          }
          return s.length();
       }
    }

## 结束语 ##

> 希望大家可  
> 以自己动手练习一下，算法光看是不行的，必须亲自动手敲代码，有时候你会发现自己有思路，但是又写不出来，这就是缺乏练习的原因。大家平时在做题的时候，可以多思考，多总结。  
> 刚开始的时候，我们可能遇到一种新的题型，完全没有思路的时候，其实可以先去看看别人的思路，还有题解，把它理解下来，然后把代码敲出来(不要复制粘贴,我们根据自己的理解敲出代码这样才有效果，如果中途卡住了，也可以再回过头去看看)  
> 另外，为了检测一下我们是否真正的掌握，我们可以去做几道相似的题目巩固一下，顺便检验一下自己的成果。  
> [点此跳转去练习][Link 2]![在这里插入图片描述][5e96aa56fa7445e49d327faa99883c79.png]  
> 这里面有对应的题目，比如链表，二叉树等等，我们可以找到自己想要练习的题目，根据标签就可以进行筛选了，非常的方便。  
> 算法不是看会的，而是在做题中学会的，这是我的个人看法，刚开始由浅入深，不要太追求效率，先把自己的思路写出来，然后逐渐培养思维，然后在有一定的积累以后，我们再来追求效率，再来追求一题多解。算法贵在坚持，不可能一朝一夕就成为大牛。  
> 如果有的小伙伴急着找工作的话，如果时间比较紧张，那么，我们可以先把一些面试高频的题目给做了，像这里面就列举出来了面试必刷题目。  
> [一起坚持下去，冲冲冲][Link 2]![在这里插入图片描述][c25b6a6f7b15469da28ef58e5b87d303.png]

[Link 1]: https://blog.csdn.net/qq_52797170?spm=1010.2135.3001.5343
[Link 2]: https://www.nowcoder.com/link/pc_csdncpt_pkq_sf
[Link 3]: https://blog.csdn.net/DarkAndGrey/article/details/123141969
[04f3be82e4c54e9390727ca29efede52.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/f7fb694b8fdb4b64a2e6540a8944a22c.png
[15ff82da90f44be2a95cb48c93105248.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/978b7694235746e0a5825e6fe2a41b5e.png
[27f61849e1184138aab6ac34e7d45d6e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/9a6fc242cddf41e6adc9ff4afffb5d61.png
[Link 4]: https://www.nowcoder.com/practice/59426f49136349b0901cc1b70447bf4b?tpId=196&tqId=40268&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=/exam/oj?page=1&pageSize=50&search=%25E5%25AD%2597%25E6%25AF%258D&tab=%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587&topicId=196&difficulty=undefined&judgeStatus=undefined&tags=585&title=%E5%AD%97%E6%AF%8D
[30c26c1198fc4e34b84e7d33a4f95abe.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/899bfe0b30914721bcebd799ee58ee61.png
[5e96aa56fa7445e49d327faa99883c79.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/ceee1b87c27143ad9802ea8e497dbc1b.png
[c25b6a6f7b15469da28ef58e5b87d303.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/08d452fb8001496a9a202aa8f8dd3160.png