Tag: Hash Map

Posted 2022-04-20Updated 2022-04-20LeetCode / Medium / 复习2 minutes read (About 243 words)

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

对于数组中每个数字，计算其前缀的和。
前缀[i]减去前缀[j]的差，等于[j]-[i]之间数字的和。（类似一种DP，数组可以用一个变量代替。）

因此，原题目等于寻找找前缀[i]-前缀[j] = k。
用哈希表储存已经遍历过的前缀和出现的次数。
每次遍历时先查看哈希表内是否有当前[前缀和-k]的键在。
如果有则加入到count中。
（哈希表中需要提前放入一个0键，值等于1，为了计算[前缀和-k]等于0的情况。）

class Solution {
    public int subarraySum(int[] nums, int k) {
        
        int[] sum = new int[nums.length + 1];
        HashMap<Integer, Integer> map = new HashMap();
        int count = 0;
        map.put(0, 1);
        
        for(int i = 1; i <= nums.length; i++){
            sum[i] = sum[i-1] + nums[i-1];
            count += map.getOrDefault(sum[i]-k, 0);
            map.put(sum[i], map.getOrDefault(sum[i], 0) + 1);
        }
        
        return count;
    }
}

Posted 2022-04-18Updated 2022-04-19LeetCode / Easy / 复习3 minutes read (About 431 words)

706. Design HashMap

Design a HashMap without using any built-in hash table libraries.

Implement the MyHashMap class:

MyHashMap() initializes the object with an empty map.
void put(int key, int value) inserts a (key, value) pair into the HashMap. If the key already exists in the map, update the corresponding value.
int get(int key) returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
void remove(key) removes the key and its corresponding value if the map contains the mapping for the key.

哈希表，先设置一个素数Prime作为map的尺寸。
（这里设置成素数是为了减少可能的碰撞。）
创建一个Pair类记录key和value。

map初始化时需要生成一个LinkedList数组。

hash方法计算哈希值。用key % Prime并返回。
put方法，根据key计算其哈希值h。如果列表中有则重新设置当前Pair的value。
get方法，根据哈希值h搜索并查找链表中的Pair，如果找到则返回Pair，否则返回-1。
remove方法，根据哈希值h搜索并remove链表中的Pair。

class MyHashMap {
    final int PRIME = 1009;
    List<Pair>[] map;
    public MyHashMap() {
        map = new LinkedList[PRIME];
        for(int i = 0; i < PRIME; i++){
            map[i] = new LinkedList<Pair>();
        }
    }
    
    public void put(int key, int value) {
        int h = hash(key);
        for(Pair p : map[h]){
            if(p.getKey() == key){
                p.setValue(value);
                return;
            }
        }
        Pair p = new Pair(key, value);
        map[h].add(p);
    }
    
    public int get(int key) {
        int h = hash(key);
        for(Pair p : map[h]){
            if(p.getKey() == key){
                return p.value;
            }
        }
        return -1;
    }
    
    public void remove(int key) {
        int h = hash(key);
        for(Pair p : map[h]){
            if(p.getKey() == key){
                map[h].remove(p);
                return;
            }
        }
    }
    
    private int hash(int key){
        return key % PRIME;
    }
}

class Pair {
    int key;
    int value;
    public Pair(int k, int v){
        key = k;
        value = v;
    }
    
    public int getKey(){
        return key;
    }
    public int getValue(){
        return value;
    }
    public void setValue(int v){
        value = v;
    }
}

/**
 * Your MyHashMap object will be instantiated and called as such:
 * MyHashMap obj = new MyHashMap();
 * obj.put(key,value);
 * int param_2 = obj.get(key);
 * obj.remove(key);
 */

Posted 2022-04-16Updated 2022-04-16LeetCode / Easy4 minutes read (About 526 words)

169. Majority Element

问题
Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Boyer-Moore投票算法
基本思想：
众数的值为+1，非众数的值为-1。其加和作为投票值。
遍历整个数组，由于众数数量大于非众数，因此最后结果一定为正数。

设置count记录票数，遍历数组。
当count为0时，则将当前的数组设为众数。当之后的数字与其相等，则count+1，反之则-1。
遍历完成后返回当前的众数。

根据以上规则，每次我们选择的众数，都是已遍历数组范围内出现最多次数的数值之一。
由于给定的数组的众数超过半数，因此遍历到最后的众数，一定是整个数组中出现最多次的数值。

核心就是对拼消耗。
玩一个诸侯争霸的游戏，假设你方人口超过总人口一半以上，并且能保证每个人口出去干仗都能一对一同归于尽。最后还有人活下来的国家就是胜利。

那就大混战呗，最差所有人都联合起来对付你（对应你每次选择作为计数器的数都是众数），或者其他国家也会相互攻击（会选择其他数作为计数器的数），但是只要你们不要内斗，最后肯定你赢。

最后能剩下的必定是自己人。

class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        int major = 0;
        
        for(int num : nums){
            if(count == 0){
                major = num;
            }
            if(major == num){
                count++;
            }
            else{
                count--;
            }
        }
        return major;
    }
}

遍历数组，并将各个数值出现的次数记录在哈希表中。
当出现的次数大于数组的一半，则该数值是众数。

class Solution {
    public int majorityElement(int[] nums) {
        HashMap<Integer,Integer> map = new HashMap();
        for(int num : nums){
            map.put(num, map.getOrDefault(num,0)+1);
            if(map.get(num) > nums.length/2){
                return num;
            }
        }
        return -1;
    }
}

Posted 2022-04-16Updated 2022-04-16LeetCode / Easya minute read (About 197 words)

653. Two Sum IV - Input is a BST

问题
Given the root of a Binary Search Tree and a target number k, return true if there exist two elements in the BST such that their sum is equal to the given target.

DFS搜索，每次递归时检查HashSet中是否有当前节点的值。如没有则将目标值减去当前节点的值加入HashSet。如有则返回true。
递归左侧节点和右侧节点，并返回二者的或运算。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    HashSet<Integer> set;
    public boolean findTarget(TreeNode root, int k) {
        set = new HashSet();
        return dfs(root,k);
    }
    
    private boolean dfs(TreeNode root, int k){
        if(root == null){
            return false;
        }
        if(set.contains(root.val)){
            return true;
        }
        set.add(k - root.val);

        return dfs(root.left,k) || dfs(root.right,k);
    }
}

Posted 2022-04-07Updated 2022-04-06LeetCode / Medium2 minutes read (About 239 words)

36. Valid Sudoku

问题
Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

Each row must contain the digits 1-9 without repetition.

Each column must contain the digits 1-9 without repetition.

Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Note:

A Sudoku board (partially filled) could be valid but is not necessarily solvable.

Only the filled cells need to be validated according to the mentioned rules.

遍历并创建三组不同的哈希表，每个表内包含一组哈希集合。
如果访问的元素已在哈希集合内，则返回false

class Solution {
    public boolean isValidSudoku(char[][] board) {
        HashMap<Integer,HashSet<Character>> rowMap = new HashMap<Integer,HashSet<Character>>();
        HashMap<Integer,HashSet<Character>> colMap = new HashMap<Integer,HashSet<Character>>();
        HashMap<Integer,HashSet<Character>> blockMap = new HashMap<Integer,HashSet<Character>>();

        for (int i = 0; i < board[0].length; i++ ){
            for (int j = 0; j < board.length; j++ ){
                char curChar = board[i][j];
                if (curChar == '.'){
                    continue;
                }
                if (!rowMap.containsKey(i)){
                    rowMap.put(i, new HashSet<Character>());
                }
                if (!colMap.containsKey(j)){
                    colMap.put(j, new HashSet<Character>());
                }
                if (!blockMap.containsKey(j/3*3+i/3)){
                    blockMap.put(j/3*3+i/3, new HashSet<Character>());
                }
                HashSet<Character> curRow = rowMap.get(i);
                HashSet<Character> curCol = colMap.get(j);
                HashSet<Character> curBlock = blockMap.get(j/3*3+i/3);
                
                if ( !curRow.contains(curChar) && !curCol.contains(curChar) && !curBlock.contains(curChar) ){
                    curRow.add(curChar);
                    curCol.add(curChar);
                    curBlock.add(curChar);
                }
                else{
                    return false;
                }   
            }
        }
        return true;
    }
}

Posted 2022-04-07Updated 2022-04-20LeetCode / Medium / 复习2 minutes read (About 264 words)

923. 3Sum With Multiplicity

Given an integer array arr, and an integer target, return the number of tuples i, j, k such that i < j < k and arr[i] + arr[j] + arr[k] == target.

As the answer can be very large, return it modulo 109 + 7.

首先遍历元素，根据元素的值和出现次数建立哈希表。
然后再哈希表中选择三个元素，如果和等于target，则计算三个元素出现次数的乘积。
最后除以重复计算的次数。
由于数值较大，因此中途计算应该采用长整型long。

class Solution {
    public int threeSumMulti(int[] arr, int target) {
        //enumberate every element and put them into the map
        HashMap<Integer, Long> map = new HashMap<Integer, Long>();
        long count = 0;
        
        for ( int num : arr ){
            if (!map.containsKey(num)){
                map.put(num, (long)1);
            }
            else{
                map.put(num, map.get(num)+1);
            }
        }
        
        //traverse whole elements and select three numbers
        
        for ( int a : map.keySet() ){
            long totalA = map.get(a);
            for (int b : map.keySet()){
                long totalB = map.get(b);
                if ( a == b ){
                    if (totalB < 2){
                        continue;
                    }
                    totalB = totalB - 1;
                }

                int c = target - a - b;
                if ( map.containsKey(c) ){
                    long totalC = map.get(c);
                    long total = 0;
                    if ( a == b && b == c ){
                        total = totalA * totalB * ( totalC - 2 ) ;
                    }
                    else if ( b == c || a == c ){
                        total = totalA * totalB * ( totalC - 1 ) ;
                    }
                    else{
                        total = totalA * totalB * totalC;
                    }
                    if ( total > 0 ){
                        count += total;
                    }

                }
            }
        }
        count/=6;
        int ans = (int) (count % 1000000007);
            
        return ans;
    }
}

Posted 2022-04-06Updated 2022-08-16LeetCode / Easy2 minutes read (About 240 words)

387. First Unique Character in a String

Problems

Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.

Solution

遍历，数组统计记录出现次数。
如果数组未记录过，则将其index添加进列表中保存。

遍历列表，如果数组统计结果为1，则返回对应的index。
否则返回-1。

Code 1

class Solution {
    public int firstUniqChar(String s) {
        List<Integer> arr = new ArrayList<>();
        int[] bin = new int[26];
        
        for(int i = 0; i < s.length(); i++){
            if(bin[s.charAt(i) - 'a'] == 0) arr.add(i);
            bin[s.charAt(i) - 'a']++;
        }
        
        for(int i = 0; i < arr.size(); i++){
            if(bin[s.charAt(arr.get(i)) - 'a'] == 1) return arr.get(i);  
        }
        
        return -1;
    }
}

Solution

遍历，建立哈希表，记录出现次数。
再次遍历，如果出现次数为1，则返回下标。

Code 2

class Solution {
    public int firstUniqChar(String s) {
        HashMap<Character,Integer> map = new HashMap<Character,Integer>();
        for ( int i = 0; i < s.length(); i++ ){
            char curChar = s.charAt(i);
            if ( !map.containsKey(curChar) ){
                map.put(curChar, 1);
            }
            else{
                map.put(curChar, map.get(curChar)+1);
            }
        }
        
        for ( int i = 0; i < s.length(); i++ ){
            char curChar = s.charAt(i);
            if ( map.get(curChar) == 1 ){
                return i;
            }
        }
        return -1;
    }
}

Posted 2022-04-04Updated 2022-04-10LeetCode / Easya minute read (About 179 words)

350. Intersection of Two Arrays II

问题描述
Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.

遍历一个数组，将所有元素添加到哈希表中。
遍历第二个数组，如果在哈希表中则添加到数组中。

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        ArrayList<Integer> arr = new ArrayList<Integer>();
        int count = 0;

        for ( int i = 0 ; i < nums1.length ; i++ ){
            if (!map.containsKey(nums1[i])){
                map.put(nums1[i],1);
            }
            else{
                map.put(nums1[i],map.get(nums1[i])+1);
            }
            
        }

        for ( int i = 0 ; i < nums2.length ; i++ ){
            if (map.containsKey(nums2[i])){
                if (map.get(nums2[i]) > 0){
                    count++;
                    arr.add(nums2[i]);
                    map.put(nums2[i],map.get(nums2[i])-1);
                }
            }
        }
        int[] ans = new int[count]; 
        
        for (int i = 0 ; i < arr.size() ; i++){
            ans[i] = arr.get(i);
        }
        return ans;
    }
}

Posted 2022-04-03Updated 2022-05-02LeetCode / Easya minute read (About 136 words)

1. Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

采用哈希表储存遍历过的数值及下标，查表如果有键则返回其下标及当前下标。

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

Problems

Solution

Code 1

Solution

Code 2

Recents

Archives

Links