运用哈希表求解问题

62 阅读 0 评论 41 点赞

我是靠谱客的博主丰富过客，最近开发中收集的这篇文章主要介绍运用哈希表求解问题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

哈希表是根据键（key）而直接访问在内存存储位置的数据结构，也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。

力扣299.猜数字游戏

class Solution {
    public String getHint(String secret, String guess) {
        int[] ints1 = new int[10];
        int[] ints2 = new int[10];
        int n=secret.length();
        int Bulls=0,Cows=0;
        for(int i=0;i<n;i++){
            if(secret.charAt(i)==guess.charAt(i)){
                Bulls++;
            }
            else{
               ints1[secret.charAt(i)-'0']++;
               ints2[guess.charAt(i)-'0']++;
            }
            }
            for(int j=0;j<10;j++){
                Cows+=Math.min(ints1[j],ints2[j]);
            }
        
        StringBuffer buffer = new StringBuffer();
        buffer.append(Bulls);
        buffer.append('A');
        buffer.append(Cows);
        buffer.append('B');
        return buffer.toString();
        

    }
}

力扣645.错误的集合(原地修改）

用一个哈希表记录数组中的数字，用一个长度为n+1的新数组代替哈希表，将旧数组中的数字作为新数组的数字下标，之后遍历新数组数值为零的元素的数字下标即为复制错误的数字，新数组数值为二的元素的数字下标即为多复制的数字

class Solution {
    public int[] findErrorNums(int[] nums) {
         int n = nums.length;
        int[] hash = new int[n + 1];
        for (int i = 0; i < n; i++){
            hash[nums[i]]++;
        }
        int[] re=new int[2];
        for (int i = 0; i < n+1; i++) {
            if (hash[i]==0&&i!=0) {
              re[1]=i;
              }
              if (hash[i]==2) {
              re[0]=i;
              }

        }
           return re;
    }
}

力扣1.两数之和

创建一个哈希表，对于每一个X哈希表中是有否target-x，我首先的想法是把所有数据存入表中在进行查找，可是这样就要进行两次循环，时间和内存都有一定量的浪费

class Solution {
    public int[] twoSum(int[] nums, int target) {
         HashMap<Integer, Integer> hashMap = new HashMap<>();
        for(int i=0;i< nums.length;i++){
            hashMap.put(nums[i],i);
        }
        for(int i=0;i< nums.length;i++){
            if(hashMap.containsKey(target-nums[i])){
                int a=hashMap.get(target-nums[i]);
                if(a!=i){
                return new int[]{a,i };
                }
            }
        }
     return new int[0];   

    }
}

下面是力扣的官方题解

在一次循环中完成两个任务，如果添加的数字已经有满足的就不用再添加了，之所以后添加而不添先加是为了避免自身加自身等于目标值的情况

class Solution {
    public int[] twoSum(int[] nums, int target) {
       Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; ++i) {
            if (hashtable.containsKey(target - nums[i])) {
                return new int[]{hashtable.get(target - nums[i]), i};
            }
            hashtable.put(nums[i], i);
        }
        return new int[0];
     }
}

力扣167两数之和 II - 输入有序数组

与上述解法基本一致，但其实这个方法并没有利用这个题的有序性，时间和内存消耗比较严重

其他更优解在写二分和双指针时会补充上

class Solution {
    public int[] twoSum(int[] numbers, int target) {

       Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
        for (int i = 0; i < numbers.length; ++i) {
            if (hashtable.containsKey(target - numbers[i])) {
                return new int[]{hashtable.get(target - numbers[i])+1, i+1};
            }
            hashtable.put(numbers[i], i);
        }
        return new int[0];
     }
}

，448.找到所有数字中消失的数字(原地修改）

用一个哈希表记录数组中的数字，用一个长度为n+1的新数组代替哈希表，将旧数组中的数字作为新数组的数字下标，之后遍历新数组数值为零的元素的数字下标即为消失的数字

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
  int n = nums.length;
        int[] hash = new int[n + 1];
        for (int i = 0; i < n; i++){
            hash[nums[i]]++;
        }
        List list=new ArrayList();
        for (int i = 0; i < n+1; i++) {
            if (hash[i]==0&&i!=0) {
                list.add(i);
            }
        }
        return list;
    }
}