哈希表+字符串

这篇具有很好参考价值的文章主要介绍了哈希表+字符串。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一)知识回顾:

1)哈希表是什么?哈希表是存储数据的容器

2)哈希表有啥用?快速的查找某一个元素

3)什么时候使用哈希表?频繁的查找某一个数的时候,当我们快速查找某一个数的时候,不光要想到哈希表还需要想到二分查找,但是二分查找算法的局限性太强了,必须数组中有序或者是数组中出现二段性的时候才会使用到二分

4)如何让使用哈希表?

4.1)使用语言自带的容器

4.2)使用数组模拟简易哈希表hash<key,nums[index],一般适用于字符串中的字符,可以使用数组下标来模拟字符的ASCILL码值,使用数组值可以是字符的个数,字符的下标,一般可以创建一个100-200个数组即可,这样就会使代码变得非常简洁,因为避免创建容器,使用容器中方法等等

4.3)但数据范围小的时候:1-10^2~3~4~4~5,但是当出现负数不建议使用数组

二)常见算法题:

一)两数之和:

1. 两数之和 - 力扣(LeetCode)

解法1:暴力枚举O(N^2)

1)我们首先每一次先固定一个数left,然后从这个数(不包含array[left])后面找到right下标的数使得array[left]+array[right]==target

哈希表+字符串,散列表,数据结构

2)我们可以先固定最后一个数nums[right],然后从这个数前面的数进行寻找nums[left]+nums[right]==target

哈希表+字符串,散列表,数据结构

暴力解法慢的原因就是每当我们固定一个数nums[index]之后,需要在这个数前面寻找target-nums[index]的数,此时还是需要使用遍历的方式进行查找,而如果我们要是使用哈希表的话,就可以快速找到要检索的元素

解法2:哈希表hash<nums[i],下标>

当我们固定一个数right的时候,可以在哈希表中找到target-nums[right]的值,因为此时哈希表中存的都是nums[right]之前的数,这样就很好的规避了找到两个相同的数相加等于target,当没有找到的时候可以将nums[right]加入到哈希表中,right++,直到找到最终的结果即可

为什么之前的暴力策略不太好用呢?

之前使用的暴力策略是首先每一次先固定一个数left,然后从这个数(不包含array[left])后面找到right下标的数使得array[left]+array[right]==target,是需要将nums[left]后面的数(不包括nums[left])的数全部加入到哈希表中,如果是这样的话,是需要一开始将所有的数都加入到哈希表中,[2,4,5,8],target=8,此时再来进行模拟就可能找到两个4相加等于8,可能自己找到自己了,所以还是需要特殊的进行判断的

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer,Integer> result=new HashMap<>();
        for(int right=0;right<nums.length;right++){//先固定最后一个数
            if(result.containsKey(target-nums[right])){//再来枚举第一个数
                return new int[]{result.get(target-nums[right]),right};
            }else{
                result.put(nums[right],right);
            }
        }
        return null;
    }
}
二)判断是否互为字符重排:

面试题 01.02. 判定是否互为字符重排 - 力扣(LeetCode)

1)回溯:时间超时

class Solution {
    List<String> result=new ArrayList<>();
    boolean[] check;
    StringBuilder path=new StringBuilder();
    public void dfs(char[] array){
        if(path.length()==array.length) {
             result.add(path.toString());
             return;
        }
        for(int i=0;i<array.length;i++){
            if(check[i]==false){
                path.append(array[i]);
                check[i]=true;
                dfs(array);
                check[i]=false;
                path.deleteCharAt(path.length()-1);
            }
        }
    }
    public boolean CheckPermutation(String s1, String s2) {
         char[] array=s1.toCharArray();
         this.check=new boolean[array.length];
         dfs(array);
         return result.contains(s2);
    }
}

 2)使用官方提供的哈希表

哈希表+字符串,散列表,数据结构

3)使用数组模拟的哈希表来解决这道问题

哈希表+字符串,散列表,数据结构

4)只使用一个哈希表来解决这道问题

哈希表+字符串,散列表,数据结构

三)存在重复元素

217. 存在重复元素 - 力扣(LeetCode)

哈希表:固定一个数right,看看right前面的数有没有出现过array[right],如果出现过直接返回,如果没有出现过就把这个数加入到哈希表中,和之前做两数之和的逻辑是一样的,就是先固定末尾的数找找前面有没有出现过这个数即可

class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashMap<Integer,Integer> result=new HashMap<>();
for(int right=0;right<nums.length;right++){//枚举后面的数,找找这个数在前面有没有出现过
            if(result.containsKey(nums[right])) return true;
            result.put(nums[right],right);
        }
    return false;//说明此时所有的元素都是不重复的
    }
}
四)存在重复元素(2)

219. 存在重复元素 II - 力扣(LeetCode)

这道题相比于上道题来说来说有一个需要注意的点,就是找到最近的一个重复元素,前面的元素就不需要进行考虑的,所以出现重复元素的时候,我们是可以大胆地把之前的元素覆盖掉的,一定不会影响我们的最终结果的

哈希表+字符串,散列表,数据结构

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashMap<Integer,Integer> result=new HashMap<>();
        for(int right=0;right<nums.length;right++){
            if(result.containsKey(nums[right])&&(Math.abs(right-result.get(nums[right]))<=k)){
                return true;
            }
            result.put(nums[right],right);//不用担心覆盖掉之前的元素
        }
     return false;
    }
}
五)字母异位词分组

49. 字母异位词分组 - 力扣(LeetCode)

判断两个单词是否互为异位词可以采用Arrays.sort(array)排序来进行实现,这个排序是根据ASCILL码来进行排序的,如果两个单词互为异位词,那么经过排序之后的字符序列一定是相等的

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> result=new ArrayList<>();
        HashMap<String,List<String>> hash=new HashMap<>();
        for(String str:strs){
             char[] array=str.toCharArray();
//1.先将字符数组进行排序,这样更方便地判断出两个字母是否互为异位词
             Arrays.sort(array);
             String key=new String(array);
//2.相同的异位词会被加入到同一个key的List<String>数组里面
             if(hash.containsKey(key)){
                 hash.get(key).add(str);
             }else{
                 List<String> list=new ArrayList<>();
                 list.add(str);
                 hash.put(key,list);
             }
        }
//3.遍历map返回最终结果
     for(Map.Entry<String,List<String>> entry:hash.entrySet()){
             result.add(entry.getValue());
     }
    return result;
    }
}
六)有序数组的平方

977. 有序数组的平方 - 力扣(LeetCode)

哈希表+字符串,散列表,数据结构

class Solution {
    public int[] sortedSquares(int[] nums) {
        int newArray[]=new int[nums.length];
        int left=0;
        int right=nums.length-1;
        int index=nums.length-1;
        while(left<=right){
            int leftData=nums[left]*nums[left];
            int rightData=nums[right]*nums[right];
            if(leftData<=rightData){
                  newArray[index]=rightData;
                  index--;
                  right--;
            }else{
                 newArray[index]=leftData;
                 index--;
                 left++;
            }
        }
    return newArray;
    }
}
七)两个数组的交集:

349. 两个数组的交集 - 力扣(LeetCode)

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        int result[]=new int[nums1.length+nums2.length];
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int Index1=0;
        int Index2=0;
        int resultIndex=0;
        int prev=-1;
        while(Index1<nums1.length&&Index2<nums2.length){
            if(nums1[Index1]==nums2[Index2]){
//防止计算到重复的元素
if(resultIndex==0||nums1[Index1]!=result[resultIndex-1]){
                    result[resultIndex]=nums1[Index1];
                    resultIndex++;
                }
                    Index1++;
                    Index2++;
            }else if(nums1[Index1]<nums2[Index2]){
                  Index1++;
            }else{
                Index2++;
            }
        }
    return Arrays.copyOfRange(result,0,resultIndex);
    }
}
八)最长公共前缀:

14. 最长公共前缀 - 力扣(LeetCode)

时间复杂度:需要遍历所有的字符串

解法1:两两字符串依次进行比较,从而求出最长公共前缀,现在的问题就转化成了,给定两个字符串,如何求出最长公共前缀?

可以定义一个指针index,从一个字符串从头到尾依次进行扫描,当两个字符串对应的字符相同的时候,直接使用结果字符串拼接上这个字符,然后index++,直到移动到两个字符串不相同或者是某一个位置两个字符串中有一个字符串已经越界了

哈希表+字符串,散列表,数据结构

class Solution {
    public String findCommonPrefixString(String str1,String str2){
           int index=0;
           while(index<str1.length()&&index<str2.length()){
               if(str1.charAt(index)==str2.charAt(index)){
                   index++;
               }else{
                   break;
               }
           }
        //要么index这个下标越界了,要么对应的两个字符不相等了,循环退出
        return str1.substring(0,index);
    }
    public String longestCommonPrefix(String[] strs) {
        //解法1:两两进行比较
        String ret=strs[0];
        for(int i=1;i<strs.length;i++){
            ret=findCommonPrefixString(strs[i],ret);
        }
    return ret;
    }
}

解法2:统一进行比较

1)当index从前向后进行遍历的时候,如果发现某一个字符串已经越界了,那么最长公共前缀就是ret;

2)第二种情况就是index在进行向后遍历的过程中发现,当前各个字符串的某一些字符是不相等的,此时应该停止计数,那么最长公共前缀就是ret;

哈希表+字符串,散列表,数据结构

class Solution {
    public String longestCommonPrefix(String[] strs) {
        int index=0;
        for(index=0;index<strs[0].length();index++){
            char ch=strs[0].charAt(index);
            for(String s:strs){
                if(index==s.length()||s.charAt(index)!=ch){
//如果出现了有一个字符串下标越界访问或者是有一个字符串对应字符不相等直接返回
                     return strs[0].substring(0,index);
                }
            }
        }
        //只要是循环能够全部运行完,说明所有的字符串都是相同的
    return strs[0];
    }
}
九)最长回文子串

5. 最长回文子串 - 力扣(LeetCode)

解法1:暴力破解:

本题求的是最长回文子串,那么只是需要枚举所有的子字符串,依次进行判断所有的子串是否回文,可以每一次固定起始位置和终止位置进行判断即可,枚举所有的子串时间复杂度是O(N^2),再进行判断每一个子串是否回文那么时间复杂度就是O(N^3)

解法2:中心扩展算法

中心扩展算法是以index为中心,向两边扩展,看看能扩展到什么程度,因为回文串的特性就是选取一个字符为中心或者是选取两个字符为中心,左边的字符和右边的字符是完全对称的

哈希表+字符串,散列表,数据结构
1)选取index为中心,left和right都指向index,

right指针向左移动,right指针向右移动,如果发现nums[right]!=nums[left]或者是其中有一个指针越界了,那么最终回文串就是

nums[left-1,right-1],但是上面枚举的情况是以index为中心,奇数回文串的情况

2)选取index和index+1为中心,left指向index,right指针指向index+1,

right指针向左移动,right指针向右移动,如果发现nums[right]!=nums[left]或者是其中有一个指针越界了,那么最终回文串就是

nums[left-1,right-1],但是上面枚举的情况是以index为中心,偶数回文串的情况

3)总结:首先固定一个中心点的下标,然后从中心点开始向两边进行扩展,还需要注意奇数长度和偶数长度都是需要进行考虑的

class Solution {
    int startIndex=0;
    int maxLen=0;
    public void isPalindrome(char[] array,int left,int right){
    while(left>=0&&right<array.length){
        if(array[left]==array[right]){
            if(maxLen<right-left+1){
                maxLen=right-left+1;
                startIndex=left;             
             }
                    left--;
                    right++;
              }else{
                  break;
              }
          }
}
    public String longestPalindrome(String s) {
        char[] array=s.toCharArray();
        for(int i=0;i<array.length;i++){
            isPalindrome(array,i,i);
            isPalindrome(array,i,i+1);
        }
        System.out.println(startIndex);
    return s.substring(startIndex,startIndex+maxLen);
    }
}
十)二进制求和

67. 二进制求和 - 力扣(LeetCode)

本质上就是一个不断在进行模拟的过程,本为和等于sum=((array1[aindex]+array2[bindex])+carry)%2,进为等于sm/2,这样的就可以巧妙的计算出从低位向高位求和

class Solution {
    public String addBinary(String a, String b) {
        int carry=0;
        int sum=0;
        char[] array1=a.toCharArray();
        char[] array2=b.toCharArray();
        int aindex=array1.length-1;
        int bindex=array2.length-1;
        StringBuilder result=new StringBuilder();
    while(aindex>=0||bindex>=0){
        sum=aindex>=0?Integer.parseInt(array1[aindex]+""):0;
        sum+=bindex>=0?Integer.parseInt(array2[bindex]+""):0;
        sum+=carry;
        carry=sum/2;
        sum=sum%2;
        result.append(sum);
        aindex--;
        bindex--;
       }
        if(carry!=0) result.append(carry);
        return result.reverse().toString();
    }
}
十一)字符串相乘

43. 字符串相乘 - 力扣(LeetCode)

解法1:模拟小学的列竖式运算

1)首先先拿第二个字符串的每一个字符转化成数字之后和第一个字符串的每一个字符进行相乘得到一个结果,这个结果就是一个普通的字符串,画图理解;

2)定义一个结果数组,依次和每一个第一步进行相乘的结果相加,最终返回的就是我们想要的结果

3)细节问题:

哈希表+字符串,散列表,数据结构

哈希表+字符串,散列表,数据结构

1)但是它们不能够直接进行相加,因此我们需要注意高位相乘的时候要注意补0

2)处理前导0

2)注意计算结果的顺序

哈希表+字符串,散列表,数据结构

哈希表+字符串,散列表,数据结构

class Solution {
    public String addString(String str1,String str2){
        StringBuilder result=new StringBuilder();
        char[] array1=str1.toCharArray();
        char[] array2=str2.toCharArray();
        int tail1=array1.length-1;
        int tail2=array2.length-1;
        int carry=0;
        while(tail1>=0||tail2>=0){
              int sum=0;
            sum+=tail1>=0?array1[tail1]-'0':0;
            sum+=tail2>=0?array2[tail2]-'0':0;
            sum+=carry;
            result.append(sum%10);
            carry=sum/10;
            tail1--;
            tail2--;
        }
        if(carry!=0) result.append(carry);
        result.reverse();
        return result.toString();
    }
    public String multiply(String num1, String num2) {
         if(num1.equals("0")||num2.equals("0")){
            return "0";
     } 
        //1.先将字符串2进行逆序操作
        num2=new StringBuilder(num2).reverse().toString();
        String result=new String();
        char[] array1=num1.toCharArray();
        char[] array2=num2.toCharArray();
        //2.将字符串2的每一个数字和字符串1的每一个数字进行相乘
        for(int index=0;index<array2.length;index++){
            //1.先进行拼接前导0
                int data2=array2[index]-'0';
                String prefix="";
                for(int i=0;i<index;i++){
                    prefix+="0";
                }
            //2.再进行字符串相乘
                int sum=0;
                int carry=0;
                StringBuilder current=new StringBuilder();
                for(int i=array1.length-1;i>=0;i--){
                    int data1=array1[i]-'0';
                    sum=(data1*data2+carry)%10;
                    carry=(data1*data2+carry)/10;
                    current.append(sum);
                }
                if(carry!=0) current.append(carry);
        prefix=current.reverse().toString()+prefix.toString();
            //3.最后进行两个字符串的相加
                result=addString(prefix,result);
        }
    return result;
    }
}
解法2:针对解法1做一下优化,无进位相乘然后再相加,最后处理进位

哈希表+字符串,散列表,数据结构

哈希表+字符串,散列表,数据结构

class Solution {
    public String addString(int[] nums){
        StringBuilder result=new StringBuilder();
        int sum=0;
        int carry=0;
        for(int i=0;i<nums.length;i++){
            sum=(carry+nums[i])%10;
            carry=(carry+nums[i])/10;
            result.append(sum);  
        }
        if(carry!=0) result.append(carry);
      return result.reverse().toString();
    }
    public String multiply(String ss1, String ss2) {
        if(ss1.equals("0")||ss2.equals("0")) return "0";
        ss1=new StringBuilder(ss1).reverse().toString();
        ss2=new StringBuilder(ss2).reverse().toString();
        char[] s1=ss1.toCharArray();
        char[] s2=ss2.toCharArray();
        int[] result=new int[s1.length+s2.length-1];
        for(int i=0;i<s1.length;i++){
            for(int j=0;j<s2.length;j++){
                result[i+j]=result[i+j]+((s1[i]-'0')*(s2[j]-'0'));
            }
        }
    String ret=addString(result);
    return ret;
    }
}

 在字符串 s 中找出第一个只出现一次的字符

 public char firstUniqChar(String s) {
        if(s==null||s.equals(""))
        {
            return ' ';
        }
        HashMap<Character,Integer> map=new HashMap<>();
        for(int i=0;i<s.length();i++){
            if(!map.containsKey(s.charAt(i))){
                map.put(s.charAt(i),1);
            }else{
                int count=map.get(s.charAt(i));
                count++;
                map.put(s.charAt(i),count);
            }
        }
       for(int j=0;j<s.length();j++){
           char ch=s.charAt(j);
           if(map.get(ch)==1)
           {
               return ch;
           }
       }  
       return ' ';
    }
   
}

上面的这个题还有一种思路:

假设我们现在给定的字符串是:bacdcd,咱们进行遍历这个字符串,开辟一个数组,数组的下标是对应字符的码值,对应的数组的值是他们对应的这个字符在字符串中出现的次数:

哈希表+字符串,散列表,数据结构文章来源地址https://www.toymoban.com/news/detail-683859.html



class Solution {
    public char firstUniqChar(String s) {
        if(s==null||s.equals(""))
        {
            return ' ';
        }
        char ch=' ';
        int[] array=new int[26];
        for(int i=0;i<s.length();i++){
             ch=s.charAt(i);
            array[ch-97]++;
        }
        for(int j=0;j<s.length();j++){
            ch=s.charAt(j);
            if(array[ch-97]==1){
               return ch;
            }
        }
        return ' ';
    }
}

到了这里,关于哈希表+字符串的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构与算法--字符串(单选题)

    1、令s=\\\"abcabaa\\\",则它的特征向量next函数值和优化特征向量nextval函数值为(下标从0开始): A.next={0,1,1,1,2,3,2},nextval={0,1,1,0,1,2,1} B.next={-1,0,0,-1,0,2,1},nextval={-1,0,0,0,1,2,1} C.next={-1,0,0,0,1,2,1},nextval={-1,0,0,-1,0,2,1} D.next={-1,0,0,0,1,2,1},nextval={-1,0,0,0,1,2,1} C 规定next[1]=0 s[2]前,“a”,next[2]=重合

    2024年02月07日
    浏览(46)
  • 【数据结构】数组和字符串(十四):字符串匹配1:朴素的模式匹配算法(StringMatching)

      字符串(String)是由零个或多个字符(char)顺序排列组成的有限序列,简称为串。例如 “good morning”就是由12个字符构成的一个字符串。一般把字符串记作: S = ′ ′ a 0 a 1 … a n − 1 ′ ′ S=\\\'\\\'a_{0} a_{1}…a_{n-1}\\\'\\\' S = ′′ a 0 ​ a 1 ​ … a n − 1 ′′ ​   其中S是串名,引号中

    2024年02月05日
    浏览(72)
  • 数据结构(C语言):两个字符串比较大小

    在写这篇文章之前,作者想先和大家分享一个小故事。如果你不想看这个小故事的话,可以直接跳到第二点哦。 为了锻炼自己的编码能力,平时作业和实验题的代码我都是不看书、不看老师的PPT,按照自己的思路一行一行敲出来的。同时也不太理解那些照着书敲代码的同学。

    2024年02月03日
    浏览(44)
  • Redis数据结构与对象-字符串对象SDS

    Redis没有使用C的字符串,而是自己构建了简单动态字符串(Simple Dynamic String),简称SDS。通过这种字符串格式能够对redis字符串操作进行提速。下面介绍原理。 sds数据格式如下: 比如,一个sds 中存的是 “Redis” ,那么buf 中是一个char型的数组,存5个字符R, e,d,i,s len =5;free

    2023年04月16日
    浏览(46)
  • 数据结构与算法之字符串: Leetcode 557. 反转字符串中的单词 III (Typescript版)

    翻转字符串中的单词 III https://leetcode.cn/problems/reverse-words-in-a-string-iii/ 描述 给定一个字符串 s ,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初始顺序。 示例 1: 示例 2: 提示: 1 = s.length = 5 * 1 0 4 10^4 1 0 4 s 包含可打印的 ASCII 字符。 s 不包含任何开头或

    2024年02月01日
    浏览(74)
  • MATLAB 之 常用内部函数,运算,字符串和结构数据与单元数据

    内部函数是由 MATLAB 系统根据一般用户的需要编制并提供给用户使用的一组程序,也被称为系统函数或库函数。 MATLAB 提供了许多数学函数,函数的自变量规定为矩阵变量,运算法则是将函数逐项作用于矩阵的元素上,因而运算的结果是一个与自变量具有相同维数和大小的矩阵

    2024年02月04日
    浏览(51)
  • 【零基础学Rust | 基础系列 | 数据结构】元组,数组,向量,字符串,结构体

    在Rust编程语言中,数据结构是组织和存储数据的一种方式,它们使得数据可以高效地被访问和操作。本章将详细介绍元组,数组,向量,字符串,和结构体这几种基本的数据结构。 元组是Rust编程语言中的一种复合数据类型,它可以包含多个值,这些值可以是不同类型。元组

    2024年02月11日
    浏览(57)
  • 数据结构(Java实现)-字符串常量池与通配符

    字符串常量池 在Java程序中,类似于:1, 2, 3,3.14,“hello”等字面类型的常量经常频繁使用,为了使程序的运行速度更快、更节省内存,Java为8种基本数据类型和String类都提供了常量池。 “池” 是编程中的一种常见的, 重要的提升效率的方式, 我们会在未来的学习中遇到各

    2024年02月10日
    浏览(50)
  • 【JavaScript数据结构与算法】字符串类(计算二进制子串)

    个人简介 👀 个人主页: 前端杂货铺 🙋‍♂️ 学习方向: 主攻前端方向,也会涉及到服务端(Node.js) 📃 个人状态: 在校大学生一枚,已拿多个前端 offer(秋招) 🚀 未来打算: 为中国的工业软件事业效力 n 年 🥇 推荐学习:🍍前端面试宝典 🍉Vue2 🍋Vue3 🍓Vue2/3项目

    2024年02月05日
    浏览(42)
  • 【字典树/trie树】实现高效插入和查询字符串的数据结构

    本文是https://www.acwing.com/problem/content/description/837/的总结,有兴趣可以做做 字典树的实现依赖于树结构,有两种操作,1是插入字符串,2是查找字符串。使用idx维护最新的结点下标。如下图,假设我们维护一个   可以看到,我们维护了一个树形结构储存了左边的字符串,但是

    2024年02月03日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包