一只小码农

每天进步一点点

哈希表easy篇总结

发表于 分类于 Valine：
本文字数： 7.7k 阅读时长 ≈ 7 分钟
对leetcode上哈希表easy篇的总结

##哈希表刷题总结

基本介绍

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

一个通俗的例子是，为了查找电话簿中某人的号码，可以创建一个按照人名首字母顺序排列的表（即建立人名 xx 到首字母 F(x)F(x) 的一个函数关系），在首字母为 WW 的表中查找 “王” 姓的电话号码，显然比直接查找就要快得多。这里使用人名作为关键字，“取首字母” 是这个例子中哈希函数的函数法则 F()F()，存放首字母的表对应哈希表。关键字和函数法则理论上可以任意确定。

哈希表是使用 O(1)O(1) 时间进行数据的插入删除和查找，但是哈希表不保证表中数据的有序性，这样在哈希表中查找最大数据或者最小数据的时间是 O(N)O(N) 实现。哈希表不支持需要元素间任何排序信息的操作，例如findMin、findMax或者打印输出排序号的整张表。

设计哈希映射

哈希表是一个在不同语言中都有的通用数据结构。例如，Python 中的 dict 和 Java 中的 Hashmap。哈希表的特性是可以根据给出的 key 快速访问 value。

设计哈希表有两个问题需要去解决： 1). 如何设计哈希方法？ 和 2).如何避免哈希碰撞？ 。

1). 如何设计哈希方法？：哈希方法会将键值映射到某块存储空间，一个好的哈希方法应该将不同的键值 均匀 地分布在存储空间中。

2). 如何避免哈希碰撞？：哈希方法要将大量的键值映射到一个有限的空间里,这样就有可能会将不同的键值映射到同一个存储空间，这种情况称为 ‘哈希碰撞’ 。哈希碰撞是不可避免的，但可以用策略来解决哈希碰撞。

1.有多少小于当前数字的数字

####一、暴力求解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int[] smallerNumbersThanCurrent(int[] nums) {
        //第一种方法1：暴力求解法，逐一遍历除当前元素之外的所有元素
        /**
        复杂度分析：
        空间复杂度为O(n)，需要存储新的答案数组
        时间复杂度为O(n^2)
        **/
        int length = nums.length;
        int newtime[] = new int[length];
        for(int i=0;i<length;i++){
            int time = 0;
            for(int h=0;h<length;h++){
                if(nums[i]>nums[h]){
                    time++;
                }
            }
            newtime[i] = time;
        }
        return newtime;
    }

}

二、计数排序

三、快速排序

四、排序与映射结合

2.第一个只出现一次的字符

3.1哈希表的遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public char firstUniqChar(String s) {
        HashMap<Character,Boolean> dic = new HashMap<>();
        char[] string = s.toCharArray();
        for(char c:string){
            dic.put(c,!dic.containsKey(c));
        }
        for(char c:string){
            if(dic.get(c))
                return c;
        }
        return ' ';
    } 
}
/**
复杂度分析：
时间复杂度：O(n)
空间复杂度：O(1)
**/

3.2有序hash表的遍历

哈希表是 去重 的，即哈希表中键值对数量 ≤ 字符串 s 的长度。因此，相比于方法一，方法二减少了第二轮遍历的循环次数。当字符串很长（重复字符很多）时，方法二则效率更高。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public char firstUniqChar(String s) {
        Map<Character,Boolean> dic = new LinkedHashMap<>();
        char[] string = s.toCharArray();
        for(char c:string){
            dic.put(c,!dic.containsKey(c));
        }
        for(Map.Entry<Character,Boolean> d : dic.entrySet()){
            if(d.getValue())
                return d.getKey();
        }
        return ' ';
    }
}

3.3补充知识：Java中的Character类

Character 类用于对单个字符进行操作。

Character 类在对象中包装一个基本类型 char 的值(类似于Integer与int的关系)

1
2
3
4
5
6
7
char ch = 'a';
 
// Unicode 字符表示形式
char uniChar = '\u039A'; 
 
// 字符数组
char[] charArray ={ 'a', 'b', 'c', 'd', 'e' };

然而，在实际开发过程中，我们经常会遇到需要使用对象，而不是内置数据类型的情况。为了解决这个问题，Java语言为内置数据类型char提供了包装类Character类。

Character类提供了一系列方法来操纵字符。你可以使用Character的构造方法创建一个Character类对象，例如：

在某些情况下，Java编译器会自动创建一个Character对象。

例如，将一个char类型的参数传递给需要一个Character类型参数的方法时，那么编译器会自动地将char类型参数转换为Character对象。 这种特征称为装箱，反过来称为拆箱。

1
2
3
4
5
6
// 原始字符 'a' 装箱到 Character 对象 ch 中
Character ch = 'a';
 
// 原始字符 'x' 用 test 方法装箱
// 返回拆箱的值到 'c'
char c = test('x');

image-20210202160601128

###3.只出现一次的字符

####3.1哈希表两次遍历

使用哈希表存储每个数字和该数字出现的次数。遍历数组即可得到每个数字出现的次数，并更新哈希表，最后遍历哈希表，得到只出现一次的数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int singleNumber(int[] nums) {
        //使用Hash表的第一次遍历
        HashMap<Integer,Boolean> dic = new HashMap<>();
        for(int i:nums){
            dic.put(i,!dic.containsKey(i));
        }

        for(int i:nums){
            if(dic.get(i))
                return i;   //不能返回nums[i],这里的增强for循环中的i代表的是nums[]中的某一个元素
        }
        return -1;   //当表示如不存在所求值时，，不能返回null,要返回-1.    
    }
}

3.2位运算

1
2
3
4
5
6
7
8
9
10
 
class Solution {
    public int singleNumber(int[] nums) {
        int single = 0;
        for (int num : nums) {
            single ^= num;
        }
        return single;
    }
}

3.3集合运算

使用集合存储数组中出现的所有数字，并计算数组中的元素之和。由于集合保证元素无重复，因此计算集合中的所有元素之和的两倍，即为每个元素出现两次的情况下的元素之和。由于数组中只有一个元素出现一次，其余元素都出现两次，因此用集合中的元素之和的两倍减去数组中的元素之和，剩下的数就是数组中只出现一次的数字。

3.4集合放入与删除

使用集合存储数字。遍历数组中的每个数字，如果集合中没有该数字，则将该数字加入集合，如果集合中已经有该数字，则将该数字从集合中删除，最后剩下的数字就是只出现一次的数字。

4.岛屿的周长

####方法一：迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int islandPerimeter(int[][] grid) {
        int land=0;
        int border=0;

        int j = grid.length;
        int k = grid[0].length;
        for(int i=0;i<j;i++){
            for(int h=0;h<k;h++){
                if(grid[i][h]==1){
                    land++;
                    if(i<grid.length-1&&grid[i+1][h]==1){
                    border++;
                    }
                     if(h<grid[0].length-1&&grid[i][h+1]==1){
                    border++;
                     }
                }
             }
        }
        return 4*land-2*border;
    }
}
/**
找规律，凡是两个陆地相接，必然在最后的周长计算里面损失两个边长值
**/

方法二：DFS深度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
从土地到土地，之间不会产生周长，但从土地迈入海洋，之间会产生 1 个周长，从土地迈出矩阵边界，也会产生 1 个周长。
**/
class Solution {

    public int dfsfunction(int i,int j,int[][]grid){
        if(i<0||i>=grid.length||j<0||j>=grid[0].length){
            return 1;   //当前正好要越界，周长值+1
        }
        if(grid[i][j]==0){
            return 1;  //说明从陆地来到了海上，周长值+1
        }
        if(grid[i][j]==2){
            return 0;   //DFS需要记录状态，避免重复访问
        }
        grid[i][j]=2; //到此，该节点已经访问完毕，状态变更
        
        //从当前模块开始，向上下左右进行遍历，其实有递归的思想，最后的结果随着递归的出栈，子问题的解自上而下的返回，最终得出大问题的解
        return dfsfunction(i-1,j,grid)+dfsfunction(i,j-1,grid)+dfsfunction(i+1,j,grid)+dfsfunction(i,j+1,grid);       
    }
    public int islandPerimeter(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(grid[i][j]==1){
                       return dfsfunction(i,j,grid); 
                }
            }
        }
        return 0;
    }
}

官方题解1:迭代—-利用算子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};

    public int islandPerimeter(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] == 1) {
                    int cnt = 0;
                    for (int k = 0; k < 4; ++k) {
                        int tx = i + dx[k];
                        int ty = j + dy[k];
                        if (tx < 0 || tx >= n || ty < 0 || ty >= m || grid[tx][ty] == 0) {
                            cnt += 1;
                        }
                    }
                    ans += cnt;
                }
            }
        }
        return ans;
    }
}

####官方题解2:DFS—-利用算子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    constexpr static int dx[4] = {0, 1, 0, -1};
    constexpr static int dy[4] = {1, 0, -1, 0};
public:
    int dfs(int x, int y, vector<vector<int>> &grid, int n, int m) {
        if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == 0) {
            return 1;
        }
        if (grid[x][y] == 2) {
            return 0;
        }
        grid[x][y] = 2;
        int res = 0;
        for (int i = 0; i < 4; ++i) {
            int tx = x + dx[i];
            int ty = y + dy[i];
            res += dfs(tx, ty, grid, n, m);
        }
        return res;
    }
    int islandPerimeter(vector<vector<int>> &grid) {
        int n = grid.size(), m = grid[0].size();
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] == 1) {
                    ans += dfs(i, j, grid, n, m);
                }
            }
        }
        return ans;
    }
};

这个题放在散列表题目下，个人觉得是因为可以使用散列表去记录方格的访问状态

key用来放方格点，value用true或者false来代表方格是否被访问过。

5.岛屿的数量

###6.岛屿的最大面积

7.查找常用字符

总体来说，还是hash表的思路，重点在于用一个数组创建索引，用另外一个数组更新值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//遍历、计数、更新
/**
用数组实现一个哈希表，以字符为数组下标索引：字符-'a'=索引---即：0-'a',2-'b',3-'c',25-'z'.
用freq数组存储当前遍历字符串中各字符的数量,在遍历完成后，
以各字符数量的最小值更新minfreq数组，遍历完成后即可得到公共字符的数量集合hash，
将minfreq数组中的非0值还原成字符串加入到列表中，即可得到答案。
**/

class Solution {
    public List<String> commonChars(String[] A) {
        int[] minfreq = new int[26];   //建立minfreq[c]来存储各字符串中c出现的最小次数
        Arrays.fill(minfreq,Integer.MAX_VALUE);//将指定的int值分配给指定的int数组的每个元素，即此时minfreq中的每个元素值均为Integer.MAX_VALUE。

        for(String word:A){
            int[] freq = new int[26];
            int length = word.length();
            for(int i=0;i<length;i++){
                char ch =word.charAt(i);
                ++freq[ch-'a'];             //ch-'a'创建索引
            }

            for(int i=0;i<26;i++){
                minfreq[i] = Math.min(minfreq[i],freq[i]);
            }
        }

        List<String> ans = new ArrayList<String>();
        for(int i=0;i<26;i++){
            for(int j=0;j<minfreq[i];j++){
                ans.add(String.valueOf((char)(i+'a')));  //i+'a'是在将还原minfreq中的字符还原成字符串
            }
        }
        return ans;

    }
}

8.唯一元素的和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int sumOfUnique(int[] nums) {
        HashMap<Integer,Boolean> dic = new HashMap<Integer,Boolean>();
        int length = nums.length;
        for(int i:nums){
            dic.put(i,!dic.containsKey(i));
        }
        int sum=0;
        for(int i:nums){
            if(dic.get(i)){
                sum+=i;
            }
        }
        return sum;
    }
}
//字符串调用length，调用的是方法，因而要加()；数组调用length，调用的是属性，不需要加()。
谢谢你的支持哦，继续加油.