哈希表+字符串_字符串哈希表

一)知识回顾:

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,咱们进行遍历这个字符串，开辟一个数组，数组的下标是对应字符的码值，对应的数组的值是他们对应的这个字符在字符串中出现的次数:

 
 
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 ' ';
    }
}