码龙的成长之路

0%

LeetCode系列之哈希表

发表于 更新于
本文字数： 7.3k 阅读时长 ≈ 7 分钟

记录哈希表类型的算法题，提供多思路多解法

[TOC]

1 数对和

image-20200728230433071

1
//暴力解法，超时，时间：O(n2) 空间:O(n)
2
public List<List<Integer>> pairSums(int[] nums, int target) {
3
        List<List<Integer>> res = new ArrayList<>();
4
        boolean[] visited = new boolean[nums.length];
5
        for(int i=0;i<nums.length-1;i++){
6
            for(int j=i+1;j<nums.length;j++){
7
                if(!visited[i]&&!visited[j]&&nums[i]+nums[j]==target){
8
                    List<Integer> tmp = new ArrayList<>();
9
                    tmp.add(nums[i]);
10
                    tmp.add(nums[j]);
11
                    res.add(tmp);
12
                    visited[i]=true;
13
                    visited[j] =true;
14
                }
15
            }
16
        }
17
        return res;
18
    }
1
//Hash表方法  时间:O(n) 空间:O(n)
2
public List<List<Integer>> pairSums(int[] nums, int target) {
3
    List<List<Integer>> res = new ArrayList<>();
4
    HashMap<Integer, Integer> map = new HashMap<>();//key :nums[i] value: 出现的次数
5
    for (int i = 0; i < nums.length; i++) {
6
        Integer count = map.get(target - nums[i]);
7
        if (count != null) {//包含且大于
8
            res.add(Arrays.asList(nums[i], target - nums[i]));
9
            if (count == 1)
10
                map.remove(target - nums[i]);
11
            else
12
                map.put(target - nums[i], count - 1);
13
        } else {
14
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
15
        }
16
    }
17
    return res;
18
}
1
//另外一种，双指针算法，需要对数组进行排序，时间：O(nlogn)
2
 public List<List<Integer>> pairSums(int[] nums, int target) {
3
        //对数组进行排序
4
        Arrays.sort(nums);
5
        List<List<Integer>> ans = new LinkedList<>();
6
        int left = 0, right = nums.length - 1;
7
        while (left < right) {
8
            int sum = nums[left] + nums[right];
9
            //如果两个的和小于目标值，那么left指针向右走一步继续寻找
10
            if (sum < target)
11
                ++left;
12
            //如果两个的和大于目标值，那么right指针向左走一步继续寻找
13
            else if (sum > target)
14
                --right;
15
            //如果刚好等于要找的target值，那么加入结果集中，并且left指针和right指针分别向右和向左走一步(因为一个数只能属于一个数对)
16
            else
17
                ans.add(Arrays.asList(nums[left++], nums[right--]));
18
        }
19
        return ans;
20
    }

2 最佳直线

image-20200729224154709

1
//暴力，利用直线两点公式 a*x+b*y+c=0 (x1,y1)与(x2,y2)计算出a=y1-y2,b=x2-x1,c=(x1 - x2) * y1 - (y1 - y2) * x1
2
//时间：O(n3) ,(x1,y1)——> i;(x2,y2)--> j ,
3
public int[] bestLine(int[][] points) {
4
        int[] res = new int[2];
5
        int max = 0;
6
        for (int i = 0; i < points.length; i++) {
7
            for (int j = i + 1; j < points.length; j++) {
8
                int count = 1;//统计直线上的点数
9
                for (int[] point : points) {
10
                    if (isLine(points[i], points[j], point)) {
11
                        count++;
12
                    }
13
                }
14
                if (count > max) {
15
                    res[0] = i;
16
                    res[1] = j;
17
                    max = count;
18
                } else if (max == count) {
19
                    if (res[0] == i && res[1] > j)
20
                        res[1] = j;
21
                }
22
23
            }
24
        }
25
        return res;
26
    }
27
    private boolean isLine(int[] p1, int[] p2, int[] p3) {
28
        int x1 = p1[0], y1 = p1[1], x2 = p2[0], y2 = p2[1];
29
        int a = y1 - y2, b = x2 - x1, c = (x1 - x2) * y1 - (y1 - y2) * x1;
30
        return a * p3[0] + b * p3[1] + c == 0;
31
    }
1
//Hash表，还是利用公式：ax+by+c=0
2
//对于给定的a,b,c，可以唯一确定一条直线，且a,b,c三者的最大公约数为1，否则为重复直线，如4x+2y+1=0与8*x+4y+2=0属于同一条直线
3
//基本思路：points[i][0]作为x1,points[i][1]作为y1,points[j][0]:x2,points[j][1]:y2
4
//1 利用公式计算a,b,c的值:a=y1-y2,b=x2-x1,c=a * x2 + b * y2
5
//2 计算a,b,c的最大公约数
6
//3 让a,b,c依次除以最大公约数，直到3者不可约
7
//4 以a,b,c作为key, 出现的点数作为value,，每次固定(x1,y1),遍历其他点，找出最大重复点数
8
class PointValue {
9
    int value;//重复点
10
    int x;//横坐标
11
    int y;//纵坐标
12
13
    PointValue(int value, int x, int y) {
14
        this.value = value;
15
        this.x = x;
16
        this.y = y;
17
    }
18
}
19
public int[] bestLine(int[][] points) {
20
    	int[] res = {Integer.MAX_VALUE, Integer.MAX_VALUE};
21
        int max = 0;
22
        for (int i = 0; i < points.length; i++) {
23
            HashMap<String, PointValue> map = new HashMap<>();
24
            int x1 = points[i][0], y1 = points[i][1];
25
            for (int j = i + 1; j < points.length; j++) {
26
                int x2 = points[j][0], y2 = points[j][1];
27
                int a = y1 - y2, b = x2 - x1;
28
                int c = a * x2 + b * y2;
29
                int gcd_num = gcd(gcd(a, b), c);
30
                a /= gcd_num;
31
                b /= gcd_num;
32
                c /= gcd_num;
33
                String key = a + "," + b + "," + c;
34
                if (map.containsKey(key)) {
35
                    //原有的直线，保留较小的i,j
36
                    PointValue pointValue = new PointValue(map.get(key).value + 1, Math.min(map.get(key).x, i), Math.min(map.get(key).y, j));
37
                    map.put(key, pointValue);
38
39
                } else {
40
                    //新增的直线
41
                    PointValue value = new PointValue(1, i, j);
42
                    map.put(key, map.getOrDefault(key, value));
43
                }
44
                if (max < map.get(key).value) {
45
                    //找到最长直线，更新res
46
                    res[0] = map.get(key).x;
47
                    res[1] = map.get(key).y;
48
                    max = map.get(key).value;
49
                } else if (max == map.get(key).value) {
50
                    if (res[0] == i && res[1] > j)
51
                        //若i相等，res[1]取较小者
52
                        res[1] = j;
53
                }
54
            }// end for j
55
        }
56
    	return res;
57
    }
58
    private static int gcd(int a, int b) {
59
        if (b == 0)
60
            return a;
61
        return gcd(b, a % b);
62
    }

3 有效的数独

image-20200803225300395

1
public boolean isValidSudoku(char[][] board) {
2
        char space = '.';
3
        int row = board.length, col = board[0].length;
4
        HashMap<Integer, Set<Object>> boxMap = new HashMap<>();
5
    	//保证 3*3唯一性,key为当前点所在的区域,value:区域set,保证插入不重复
6
        /** box = i/3*3+j/3;
7
        *	  0 1 2
8
        *	  3 4 5
9
        *	  6 7 8
10
        **/
11
        for (int i = 0; i < row; i++) {
12
            Set<Object> rowSet = new HashSet<>();
13
            Set<Object> colSet = new HashSet<>();
14
            for (int j = 0; j < col; j++) {
15
                if (board[i][j] != space && !rowSet.add(board[i][j]))//保证当前行唯一
16
                    return false;
17
                if (board[j][i] != space && !colSet.add(board[j][i]))//保证当前列唯一
18
                    return false;
19
                int box = i / 3 * 3 + j / 3;//计算当前节点所在区域的位置
20
                if (board[i][j] != space) {
21
                    if (boxMap.containsKey(box)) {
22
                        Set<Object> boxSet = boxMap.get(box);
23
                        if (!boxSet.add(board[i][j]))//3*3宫内重复,返回false
24
                            return false;
25
                    } else {
26
                        Set<Object> boxSet = new HashSet<>();
27
                        boxSet.add(board[i][j]);
28
                        boxMap.put(box, boxSet);
29
                    }
30
                }
31
            }
32
        }
33
        return true;
34
    }

4 字母异位词分组

image-20200804220601410

1
 //1 字符串排序，kv存储  时间：O(NKlogK) K为字符串的最大长度  空间:O(NK)
2
public List<List<String>> groupAnagrams(String[] strs) {
3
    HashMap<String, List<String>>  map = new HashMap<>();
4
    for(String str:strs){
5
        char[] chars = str.toCharArray();
6
        Arrays.sort(chars);
7
        String key = String.valueOf(chars);//排序后相同的key放在一起
8
        map.put(key,map.getOrDefault(key,new ArrayList<>()));
9
        map.get(key).add(str);
10
    }
11
    return new ArrayList(map.values());
12
}
13
14
//2 官方题解，利用字母出现的次数计数作为key  时间：O(NK) 空间:O(NK)
15
public List<List<String>> groupAnagrams(String[] strs) {
16
    HashMap<String, List<String>> map = new HashMap<>();
17
    for (String str : strs) {
18
        int[] count = new int[26];
19
        for (char c : str.toCharArray()) {
20
            count[c - 'a']++;
21
        }
22
        StringBuilder sb = new StringBuilder();
23
        /**
24
        * 如: aba,baa,aab
25
        * key: .2.1.0.0.0.0,,,
26
        **/
27
        for (int i : count) {
28
            sb.append(".");
29
            sb.append(i);
30
        }
31
        String key = sb.toString();
32
        map.put(key, map.getOrDefault(key, new ArrayList<>()));
33
        map.get(key).add(str);
34
    }
35
    return new ArrayList(map.values());
36
}

5 复制带随机指针的链表

1
/**深拷贝：B为A的拷贝，A变化不影响B的变化，即在内存中访问的不同的地址，即使参数相同，但内存地址不同
2
*思路：map映射新的Node
3
*时间：O(n),空间：O(n)
4
**/
5
public Node copyRandomList(Node head) {
6
    if (head == null)
7
        return head;
8
    HashMap<Node, Node> map = new HashMap<>();
9
    Node cur = head;
10
    while (cur != null) {
11
        //先new出单个新节点
12
        map.put(cur, new Node(cur.val));
13
        cur = cur.next;
14
    }
15
    cur = head;
16
    while (cur != null) {
17
        //再在map中获取新的next节点和random节点
18
        map.get(cur).random = map.get(cur.random);
19
        map.get(cur).next = map.get(cur.next);
20
        cur = cur.next;
21
    }
22
    return map.get(head);
23
}
1
//思路二：遍历链表，代替map映射关系，每个节点后clone一个新节点
2
//ABC,AA'BB'CC',取出A'B'C'
3
//时间：O(N),空间：O(1)
4
public Node copyRandomList(Node head) {
5
    if(head==null)
6
        return null;
7
    //clone新节点 next
8
    Node  cur =head;
9
    while(cur!=null){
10
        Node tmp = cur.next;
11
        cur.next = new Node(cur.val);
12
        cur.next.next = tmp;
13
        cur =tmp;
14
    }
15
    //将新clone的节点赋值random
16
    cur =head;
17
    while(cur!=null){
18
        if(cur.random!=null)
19
            cur.next.random = cur.random.next;
20
        cur=cur.next.next;
21
    }
22
    //将新节点抽出来
23
    cur = head;
24
    Node ans = cur.next;
25
    Node res =ans;
26
    while(res.next!=null){
27
        Node tmp = res.next;
28
        cur.next = tmp;
29
        res.next = tmp.next;
30
        cur =tmp;
31
        res = tmp.next;
32
    }
33
    cur.next =null;
34
    return ans;
35
}
-------------未完待续-------------