Tag: Hash Map

Posted 2022-08-26Updated 2022-08-26LeetCode / Medium / 复习3 minutes read (About 411 words)

Question

You are given an integer n. We reorder the digits in any order (including the original order) such that the leading digit is not zero.

Return true if and only if we can do this so that the resulting number is a power of two.

Solution

打表，将所有二的指数全部计算出来，并用数组统计各个数字出现的频率。
然后同样统计n中各个数字出现的频率。

如果两者中有频率完全相同的情况，则返回true，反之返回false。

Code

class Solution {
    public boolean reorderedPowerOf2(int n) {
        int[] reorders = new int[10];
        int m = 1, digits = 0;
        for(int i = n; i > 0; i/=10){
            reorders[i % 10]++;
            digits++;
        }
        
        int size = 0;
        List<Integer[]> powerOfTwo = new ArrayList<>();
        
        while(m > 0 && size <= digits){
            size = 0;
            Integer[] bin = new Integer[10];
            Arrays.fill(bin, 0);
            for(int i = m; i > 0; i/=10){
                size++;
                bin[i % 10]++;
            }
            if(size == digits) powerOfTwo.add(bin);
            m *= 2;
        }
        
        for(Integer[] bin : powerOfTwo) if(check(bin, reorders)) return true;
        return false;
    }
    
    private boolean check(Integer[] bin, int[] reorders){
        for(int i = 0; i < bin.length; i++) if(bin[i] != reorders[i]) return false;
        return true;        
    }
}

Solution 2

回溯，遍历计算可以组成的所有数字。
打表记录所有二的指数并记录在哈希表内，如果所有组成数字中有哈希表内的数字则返回true，反之返回false。

Code

class Solution {
    HashSet<Integer> visited, set, numbers;
    List<Integer> arr, res;
    public boolean reorderedPowerOf2(int n) {
        int m = 1;
        set = new HashSet<>();
        visited = new HashSet<>();
        numbers = new HashSet<>();
        res = new ArrayList<Integer>();
        while(m > 0){
            set.add(m);
            m *= 2;
        }
        
        arr = new ArrayList<>();
        
        while(n > 0){
            arr.add(n % 10);
            n /= 10;
        }
        
        for(int i = 0; i< arr.size(); i++){
            if(arr.get(i) == 0) continue;
            visited.add(i);
            reorder(arr.get(i));
            visited.remove(i);
        }
        
        
        for(int num : res) if(set.contains(num)) return true;
        return false;
    }
    
    private void reorder(int num){
        if(visited.size() == arr.size()){
            res.add(num);
            return;
        };
        
        if(numbers.contains(num)) return;
        numbers.add(num);

        for(int i = 0; i < arr.size(); i++){
            if(visited.contains(i)) continue;
            int next = num * 10 + arr.get(i);
            visited.add(i);
            reorder(next);
            visited.remove(i);
        }
    }
}

Posted 2022-08-21Updated 2022-08-21LeetCode / Medium / 复习3 minutes read (About 466 words)

659. Split Array into Consecutive Subsequences

Question

You are given an integer array nums that is sorted in non-decreasing order.

Determine if it is possible to split nums into one or more subsequences such that both of the following conditions are true:

Each subsequence is a consecutive increasing sequence (i.e. each integer is exactly one more than the previous integer).

All subsequences have a length of 3** or more**.

Return true* if you can split nums according to the above conditions, or false otherwise*.

A subsequence of an array is a new array that is formed from the original array by deleting some (can be none) of the elements without disturbing the relative positions of the remaining elements. (i.e., [1,3,5] is a subsequence of [1,2,3,4,5] while [1,3,2] is not).

Solution

用优先级队列储存每个可组成的列表。
优先级队列根据列表的长度排列。

用哈希表记录每个列表的尾数，和其对应的优先级队列。
遍历所有数字，如果存在当前数字num-1为尾数的队列，则获取长度最小的列表，并添加当前数字num在列表中。
然后将新的优先级队列放入哈希表中。

遍历整个哈希表中的数组，如果有数组的长度小于3，则返回false，否则返回true。

Code

class Solution {
    public boolean isPossible(int[] nums) {
        HashMap<Integer, PriorityQueue<List<Integer>>> map = new HashMap<>();
        
        for(int num : nums){
            PriorityQueue<List<Integer>> last = map.getOrDefault(num - 1, null);
            PriorityQueue<List<Integer>> curr = map.getOrDefault(num, new PriorityQueue<List<Integer>>((a,b) -> a.size() - b.size()));

            if(last == null || last.size() == 0){
                List<Integer> arr = new ArrayList<>();
                arr.add(num);
                curr.add(arr);
                map.put(num, curr);
            }
            else{
                List<Integer> arr = last.poll();
                arr.add(num);
                curr.add(arr);
                map.put(num, curr);
            }
        }                   
                                      
        for(int last : map.keySet()){
            for(List<Integer> arr : map.get(last)){
                if(arr.size() < 3) return false;
            }
        }
        return true;
        
    }
}

Solution 2

不需要保存整个列表，只需要保存对应末尾数字的列表长度即可。

Code

class Solution {
    public boolean isPossible(int[] nums) {
        HashMap<Integer, PriorityQueue<Integer>> map = new HashMap<>();
        
        for(int num : nums){
            PriorityQueue<Integer> last = map.getOrDefault(num - 1, null);
            PriorityQueue<Integer> curr = map.getOrDefault(num, new PriorityQueue<Integer>());

            if(last == null || last.size() == 0){
                curr.add(1);
                map.put(num, curr);
            }
            else{
                int min = last.poll();
                curr.add(min+1);
                map.put(num, curr);
            }
        }                   
                                      
        for(int last : map.keySet()){
            for(int len : map.get(last)){
                if(len < 3) return false;
            }
        }
        return true;

    }
}

Posted 2022-08-08Updated 2022-08-08LeetCode / Medium / 复习3 minutes read (About 474 words)

823. Binary Trees With Factors

Question

Given an array of unique integers, arr, where each integer arr[i] is strictly greater than 1.

We make a binary tree using these integers, and each number may be used for any number of times. Each non-leaf node’s value should be equal to the product of the values of its children.

Return the number of binary trees we can make. The answer may be too large so return the answer modulo 109 + 7.

Solution

根据题意，二叉树的根是两个子节点的乘积，因此一个根节点可组成的二叉树总数，相当于其左子节点可组成的二叉树总数，乘以其右子节点可组成的二叉树总数。

因此我们可以先将数组arr排序，用dp[]数组记录以从小到大的数字作为根节点可组成的最大二叉树总数。

由于每个根节点至少可以和自身组成一个节点，因此将dp[]数组初始化为1。

动态规划

从小到大遍历dp[]数组。
在遍历时，从遍历数值i的左侧选取当前位置的子节点。（根据题意子节点一定小于根节点）
当当前位置arr[i]可以整除arr[left]时，则有可能存在另一个子节点。此时根据哈希表中获得对应的另一个子节点right。如果right存在，则dp[i]更新为dp[i]+dp[left]*dp[right]的值。

最后将dp[]数组中记录的所有数字加和并返回。

Code

class Solution {
    public int numFactoredBinaryTrees(int[] arr) {
        final int MOD = (int) Math.pow(10, 9) + 7;
        Arrays.sort(arr);   //from minium to maxium
        HashMap<Integer, Integer> map = new HashMap<>();
        
        for(int i = 0; i < arr.length; i++){
            map.put(arr[i], i);
        }
        
        long[] dp = new long[arr.length];
        Arrays.fill(dp, 1);
        
        for(int i = 0; i < arr.length; i++){
            for(int left = 0; left < i; left++){
                if(arr[i] % arr[left] == 0){   //make sure divisible
                    int k = arr[i] / arr[left];
                    if(map.containsKey(k)){
                        int right = map.get(k);
                        dp[i] = (dp[i] + dp[left] * dp[right]) % MOD; 
                    }
                }
            }
        }
        
        int res = 0;
        
        for(long num : dp){
            res += num;
            res %= MOD;
        }
        
        return (int) res;
    }
}

Posted 2022-08-06Updated 2022-08-06LeetCode / Hard2 minutes read (About 291 words)

1220. Count Vowels Permutation

Question

Given an integer n, your task is to count how many strings of length n can be formed under the following rules:

Each character is a lower case vowel ('a', 'e', 'i', 'o', 'u')

Each vowel 'a' may only be followed by an 'e'.

Each vowel 'e' may only be followed by an 'a' or an 'i'.

Each vowel 'i' may not be followed by another 'i'.

Each vowel 'o' may only be followed by an 'i' or a 'u'.

Each vowel 'u' may only be followed by an 'a'.

Since the answer may be too large, return it modulo 10^9 + 7.

Solution

DFS搜索，记忆化剪枝。
每次根据上一个字母last来从哈希表里选择下一个可选字母进行遍历，并计算总的可组成数sum。

Code

class Solution {
    final int MOD = (int) Math.pow(10, 9) + 7;
    int[][] memo;
    HashMap<Character, Character[]> map;
    public int countVowelPermutation(int n) {
        if(n == 1) return 5;
        map = new HashMap<>();
        memo = new int[26][n+1];
        Character[] vowels = {'a', 'e', 'i', 'o', 'u'}, 
        a = {'e'}, e = {'a','i'}, i = {'a','e','o','u'}, o = {'i', 'u'}, u = {'a'};
        map.put('a', a);
        map.put('e', e);
        map.put('i', i);
        map.put('o', o);
        map.put('u', u);
        
        int ans = 0;
        
        for(char vowel : vowels){
            ans += count(vowel, n-1);
            ans %= MOD;
        }
        return ans;
    }
    
    private int count(char last, int n){
        if(memo[last-'a'][n] != 0) return memo[last-'a'][n];
        if(n == 1){
            memo[last-'a'][n] = map.get(last).length;
            return memo[last-'a'][n];
        }
        
        int sum = 0;
        for(char next : map.get(last)){
            sum += count(next, n-1);
            sum %= MOD;
        }
        memo[last-'a'][n] = sum;
        return sum;
    }
}

Posted 2022-07-29Updated 2022-08-03LeetCode / Medium2 minutes read (About 323 words)

890. Find and Replace Pattern

Question

Given a list of strings words and a string pattern, return a list of words[i] that match pattern. You may return the answer in any order.

A word matches the pattern if there exists a permutation of letters p so that after replacing every letter x in the pattern with p(x), we get the desired word.

Recall that a permutation of letters is a bijection from letters to letters: every letter maps to another letter, and no two letters map to the same letter.

Solution

遍历words，对pattern和words中的字符建立映射。
used[]数组记录访问状况。

如未建立映射关系，且word中的字符已建立映射，则不在结果中添加当前字符串。
如未建立映射，则建立新的word与pattern的映射关系。
如果当前已经建立映射，但是当前字符违反了映射关系，则不在结果中添加当前字符串。

Code

class Solution {
    public List<String> findAndReplacePattern(String[] words, String pattern) {
        List<String> ret = new ArrayList<>();
        for(String word : words){
            HashMap<Character, Character> map = new HashMap<>();    //map characters from pattern and words
            boolean isSamePattern = true;
            int[] used = new int[26];
            
            for(int i = 0; i < word.length(); i++){
                char pc = pattern.charAt(i), wc = word.charAt(i);
                if( !map.containsKey(pc) ){
                    if(used[wc-'a'] == 0){  //add new map if there is no map between characters and the character in word is not used
                        map.put( pc, wc );
                        used[wc-'a']++;
                    }
                    else{
                        isSamePattern = false;
                        break;
                    }
                }
                else if( map.get(pc) != wc ){   //drop the word if not follow the pattern
                    isSamePattern = false;
                    break;
                }
            }
            if(isSamePattern) ret.add(word);
        }
        return ret;
    }
}

Posted 2022-05-31Updated 2022-05-31LeetCode / Medium3 minutes read (About 396 words)

1461. Check If a String Contains All Binary Codes

Question

Given a binary string s and an integer k, return true if every binary code of length k is a substring of s. Otherwise, return false.

Solution

位运算+哈希表，用整数num记录二进制编码并加入哈希表中。
首先将字符串内的前k位二进制码转换为整数。并将其数值添加到哈希表内。

滑动窗口遍历，维持num为k长度内二进制码所对应的整数，并在遍历时将num加入哈希集合。
如果哈希集合的size达到k长度对应的可组合数，则返回true，否则返回false。

位运算与掩码

为了维护整数num，首先将其二进制编码向左移动一位。
然后与mask进行按位与运算，屏蔽掉多余的位数。

mask的值为k长度对应的可组合数-1。

Code

class Solution {
    public boolean hasAllCodes(String s, int k) {
        if(s.length() < k) return false;    //字符串长度不足则返回false
        char[] bin = s.toCharArray();
        int n = s.length(), m = (int) Math.pow(2, k);
        HashSet<Integer> set = new HashSet<>(); //哈希表记录访问过的数字
        
        int num = Integer.parseInt(s.substring(0,k), 2);    //字符串以二进制转换为整数
        int mask = m-1; //掩码等于寻找长度-1
        set.add(num);
        
        for(int i = k; i < s.length(); i++){  //位运算，维护窗口内整数的值
            num <<= 1;  //位运算左移一位
            num &= mask;    //出界的位置被掩码遮盖
            if(bin[i] == '1') num++;
            set.add(num);
            if(set.size() == m) return true;    //如果哈希表长度等于2^k，则已经遍历了所有组合，返回true
        }
        return false;
    }
}

Posted 2022-05-06Updated 2022-05-07LeetCode / Hard / 复习3 minutes read (About 423 words)

149. Max Points on a Line

Question

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.

Solution

首先选取一个点，然后创建哈希表。记录这个点与其他点的斜率关系与出现次数。记录一个出现次数最多的max值，如果当前次数大于max则更新max。

注意计算斜率时对y == 0和 x == 0时要返回无穷大和0，否则会有精度问题。
最后返回max + 1。

可以优化的地方是，当max大于总点数的一半，或者max大于剩余的点时，因为已经找到了最大的max值，可以直接返回答案。

Code

class Solution {
    public int maxPoints(int[][] points) {
        int n = points.length;
        if(n == 1) return 1;
        else if(n == 2) return 2;
        int max = 0;
        
        for(int i = 0; i < points.length; i++){
            if(max > points.length / 2) break;
            if(max > points.length - i) break;
            HashMap<Double, Integer> map = new HashMap<>();
            
            for(int j = i+1; j < points.length; j++){
                double k = getSlope(points[i], points[j]);
                int count = map.getOrDefault(k, 0) + 1;
                max = Math.max(max, count);
                map.put(k, count);
            }
        }
        return max + 1 ;
        
    }
    
    private double getSlope(int[] p1, int[] p2){
        double x1 = p1[0], y1 = p1[1], x2 = p2[0], y2 = p2[1];
        if(y1-y2 == 0) return Double.MAX_VALUE;
        if(x1-x2 == 0) return 0;
        double k = (x1 - x2) / (y1 - y2);
        return k;
    }
}

叉乘计算可以判断两个向量是否重合。
由于叉乘乘积（$|a||b|sinθ$）的模等于两个向量组成的平行四边形的面积，因此当两者乘积为0时，则两个向量重合。

点乘乘积得到的是向量在另一个向量上的投影的乘积，$|a||b|cosθ$

Posted 2022-05-05Updated 2022-05-04LeetCode / Mediuma minute read (About 203 words)

451. Sort Characters By Frequency

Question

Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string.

Return the sorted string. If there are multiple answers, return any of them.

Solution

哈希表记录字符出现的频率。然后将其添加到优先队列中。
最后根据优先级队列的顺序，加入每个字符对应的哈希表中记录的字符数。
理论上也可以用数组记录频率，但是问题中字符较复杂故未采用。

Code

class Solution {
    public String frequencySort(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        PriorityQueue<Character> pq = new PriorityQueue<>((a,b) -> map.get(b) - map.get(a));
        StringBuffer sb = new StringBuffer();
        for(char c : s.toCharArray()){
            map.put(c, map.getOrDefault(c, 0)+1);
        }
        for(char c : map.keySet()){
            pq.add(c);
        }
        while(!pq.isEmpty()){
            char c = pq.poll();
            for(int i = 0; i < map.get(c); i++){
                sb.append(c);
            }
        }
        return sb.toString();
    }
}

Posted 2022-05-04Updated 2022-05-04LeetCode / Medium2 minutes read (About 358 words)

1679. Max Number of K-Sum Pairs

Question

You are given an integer array nums and an integer k.

In one operation, you can pick two numbers from the array whose sum equals k and remove them from the array.

Return the maximum number of operations you can perform on the array.

Solution

两种思路，第一种，哈希表统计总数，然后逐个排除。
每次从数组中取一个数，先查询寻找的target是否在哈希表内。
如果表内存在target，则将target的计数减一，对数加一。

如果target不在表内，则将当前的数字加入表内。
最后返回结果。时间复杂度为O(n)。

Code

class Solution {
    public int maxOperations(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int count = 0;
        for(int num : nums){
            int target = k - num;
            if(map.containsKey(target) && map.get(target) > 0){
                map.put(target, map.get(target)-1);
                count++;
            }
            else{
                map.put(num, map.getOrDefault(num, 0)+1);
            }
        }
        return count;
    }
}

Solution 2

第二种思路，先排序。
然后双指针放在首尾。
当两者的和等于目标值时增加计数器，并移动两个指针。
当两者的和大于目标值时，右侧指针左移。
当两者的和小于目标值时，左侧指针右移。
最后返回结果。由于有排序存在，因此时间复杂度为O(nlogn) + O(n)。

Code

class Solution {
    public int maxOperations(int[] nums, int k) {
        Arrays.sort(nums);
        int left = 0, right = nums.length-1, count = 0;

        while(left < right){
            if(nums[left] + nums[right] == k){
                count++;
                left++;
                right--;
            }
            else if(nums[left] + nums[right] > k){
                right--;
            }
            else{
                left++;
            }
        }
        return count;
    }
}

Posted 2022-04-27Updated 2022-06-25LeetCode / Medium / 复习2 minutes read (About 353 words)

1202. Smallest String With Swaps

You are given a string s, and an array of pairs of indices in the string pairs where pairs[i] = [a, b] indicates 2 indices(0-indexed) of the string.

You can swap the characters at any pair of indices in the given pairs any number of times.

Return the lexicographically smallest string that s can be changed to after using the swaps.

并查集，注意要使用路径压缩否则会超时。
先将所有配对联通。然后创建一个数组group记录每个字符串位置的分组情况。
根据分组，借助优先队列保存字符串。
通过哈希表创建group和PriorityQueue的映射。
按当前位置的分组情况和优先队列的顺序来添加字符串。
最后返回字符串。

class Solution {
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        StringBuffer sb = new StringBuffer();
        UnionFind uf = new UnionFind(s.length());
        
        for(List<Integer> pair : pairs){
            uf.union(pair.get(0), pair.get(1));    
        }
        
        int[] group = new int[s.length()];
        for(int i = 0; i < s.length(); i++){
            group[i] = uf.find(i);
        }
        
        HashMap<Integer, PriorityQueue<Character>> map = new HashMap<>();
        
        for(int i = 0; i < s.length(); i++){
            PriorityQueue<Character> bin = map.getOrDefault(group[i], new PriorityQueue<Character>());
            bin.add(s.charAt(i));
            map.put(group[i], bin);
        }
        for(int i = 0; i < s.length(); i++){
            sb.append(map.get(group[i]).poll());
        }
        return sb.toString();
    }
    
    class UnionFind {
        int[] parent;
        int[] count;
        public UnionFind(int n){
            parent = new int[n];
            count = new int[n];
            for(int i = 0; i < n; i++){
                parent[i] = i;
                count[i] = 1;
            }
        } 
        
        private int find(int id){
            if(parent[id] == id) return id;
            parent[id] = find(parent[id]);
            return parent[id];
        }
        
        private boolean union(int id1, int id2){
            int p1 = find(id1);
            int p2 = find(id2);
            if(p1 == p2) return false;
            if(count[p1] > count[p2]) parent[p2] = p1;
            else parent[p1] = p2;
            return true;
        }
    }
}

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

187. Repeated DNA Sequences

The DNA sequence is composed of a series of nucleotides abbreviated as ‘A’, ‘C’, ‘G’, and ‘T’.

For example, “ACGAATTCCG” is a DNA sequence.
When studying DNA, it is useful to identify repeated sequences within the DNA.

Given a string s that represents a DNA sequence, return all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule. You may return the answer in any order.

哈希表 + 滑动窗口 + 位操作。
将四个字符映射到四个二进制字符上。这样字符串就可以用20bit表示。
这样就可以用一个整数来表示这四个字符。
然后采用哈希表记录出现次数。

class Solution {
    static final int L = 10;
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> ret = new ArrayList<String>();
        if(s.length() < L) return ret;
        HashMap<Integer, Integer> map = new HashMap<>();
        int left = 0;
        int right = 10;
        
        int[] bin = new int[26];
        bin['A'-'A'] = 0;
        bin['T'-'A'] = 1;
        bin['C'-'A'] = 2;
        bin['G'-'A'] = 3;
        
        int x = 0;
        for(int i = 0; i < L-1; i++){
            x = (x << 2) | bin[s.charAt(i)-'A'];
        }
        
        for(int i = 0; i <= s.length() - L; i++){
            x = ((x << 2) | bin[s.charAt(i + L -1)-'A']) & ((1 << L * 2) - 1);
            map.put(x, map.getOrDefault(x, 0)+1);
            if(map.get(x) == 2) ret.add(s.substring(i, i+L)); 
        }
        return ret;
    }
}

遍历将字字符串加入哈希表并记录出现次数，然后返回出现次数大于1的字符串。
注意在循环时就可以直接添加结果到列表，这样可以减少操作。

class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> ret = new ArrayList<String>();
        HashMap<String, Integer> map = new HashMap<>();
        int left = 0;
        int right = 10;
        
        while(right <= s.length()){
            String sub = s.substring(left, right);
            map.put(sub, map.getOrDefault(sub, 0)+1);
            if(map.get(sub) == 2) ret.add(sub); 
            left++;
            right++;
        }
        return ret;
    }
}

Posted 2022-04-24Updated 2022-04-24LeetCode / Medium / 复习3 minutes read (About 436 words)

1396. Design Underground System

An underground railway system is keeping track of customer travel times between different stations. They are using this data to calculate the average time it takes to travel from one station to another.

Implement the UndergroundSystem class:

void checkIn(int id, string stationName, int t)

A customer with a card ID equal to id, checks in at the station stationName at time t.

A customer can only be checked into one place at a time.

void checkOut(int id, string stationName, int t)

A customer with a card ID equal to id, checks out from the station stationName at time t.

double getAverageTime(string startStation, string endStation)

Returns the average time it takes to travel from startStation to endStation.

The average time is computed from all the previous traveling times from startStation to endStation that happened directly, meaning a check in at startStation followed by a check out from endStation.

The time it takes to travel from startStation to endStation may be different from the time it takes to travel from endStation to startStation.

There will be at least one customer that has traveled from startStation to endStation before getAverageTime is called.
You may assume all calls to the checkIn and checkOut methods are consistent. If a customer checks in at time t1 then checks out at time t2, then t1 < t2. All events happen in chronological order.

两个哈希表，第一个暂存id。第二个用来储存“站点——站点”和路线中的总用时，路线中的总人数。
最后返回总用时除以总人数。
（一开始采用的算法没有考虑id重复进站，和id出站进站不同的情况。）

class UndergroundSystem {
    HashMap<Integer, Pair<String, Integer>> inMap;
    HashMap<String, int[]> outMap;
    public UndergroundSystem() {
        inMap = new HashMap<Integer, Pair<String, Integer>>();
        outMap = new HashMap<String, int[]>();
    }
    
    public void checkIn(int id, String stationName, int t) {
        Pair<String, Integer> data = new Pair(stationName, t);
        inMap.put(id, data);
    }
    
    public void checkOut(int id, String stationName, int t) {
        Pair<String, Integer> data = inMap.get(id);
        String route = data.getKey() + "-" + stationName;
  
        int[] routeData = outMap.getOrDefault(route, new int[2]);
        routeData[0] += t - data.getValue();
        routeData[1]++;
    
        outMap.put(route, routeData);
    }
    
    public double getAverageTime(String startStation, String endStation) {
        String route = startStation + "-" + endStation;
        return outMap.get(route)[0] / (double) outMap.get(route)[1];
    }
}

/**
 * Your UndergroundSystem object will be instantiated and called as such:
 * UndergroundSystem obj = new UndergroundSystem();
 * obj.checkIn(id,stationName,t);
 * obj.checkOut(id,stationName,t);
 * double param_3 = obj.getAverageTime(startStation,endStation);
 */

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

49. Group Anagrams

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

利用JAVA中字符串会固定内存地址。（因此在进行字符串操作时是生成了新的对象。）
遍历每个单词，记录26个字母出现的次数，并映射到字符数组上。
将字符数组转换成字符串，生成一个新的字符串。

将字符串作为key放入map中，value储存原有单词。（字符串的内存地址固定，因此同样的字符串可以被搜索到。）

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> ret = new ArrayList<>();
        HashMap<String, List<String>> map = new HashMap<>();
        
        for(String word : strs){
            char[] alphabet = new char[26];
            for(int j = 0; j < word.length(); j++){
                alphabet[word.charAt(j)-'a']++;
            }
            String s = new String(alphabet);
            List<String> str = map.getOrDefault(s, new ArrayList<String>());
            str.add(word);
            map.put(s, str);
        }
        for(String key : map.keySet()){
            ret.add(map.get(key));
        }
        return ret;   
    }
}

Posted 2022-04-23Updated 2022-04-22LeetCode / Medium2 minutes read (About 252 words)

535. Encode and Decode TinyURL

Note: This is a companion problem to the System Design problem: Design TinyURL.
TinyURL is a URL shortening service where you enter a URL such as https://leetcode.com/problems/design-tinyurl and it returns a short URL such as http://tinyurl.com/4e9iAk. Design a class to encode a URL and decode a tiny URL.

There is no restriction on how your encode/decode algorithm should work. You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL.

Implement the Solution class:

Solution() Initializes the object of the system.

String encode(String longUrl) Returns a tiny URL for the given longUrl.

String decode(String shortUrl) Returns the original long URL for the given shortUrl. It is guaranteed that the given shortUrl was encoded by the same object.

计算传入连接的哈希值。将其作为key放入map中。
解码时将url转换为key，取出map中的value。

public class Codec {
    HashMap<Integer, String> map = new HashMap<>();
    
    // Encodes a URL to a shortened URL.
    public String encode(String longUrl) {
        int key = longUrl.hashCode();
        map.put(key, longUrl);
        return Integer.toString(key);
    }

    // Decodes a shortened URL to its original URL.
    public String decode(String shortUrl) {
        return map.get(Integer.parseInt(shortUrl));
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.decode(codec.encode(url));

Posted 2022-04-21Updated 2022-04-21LeetCode / Easy / 复习2 minutes read (About 299 words)

290. Word Pattern

Given a pattern and a string s, find if s follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in s.

先将s分割成数组。
如果words的长度和pattern的长度不同则返回false。
用长度为26的数组储存pattern的字符。
同时遍历words和pattern，将pattern的字符换算成数字作为index，将words[i]填入数组。
如果数组中已经有word存在，则检查新的word和数组内的word是否相等。
如果不相等，则返回false。

最后遍历数组，比对各个字符中对应的word是否相等，如果有相等的，则返回false。由于数组长度固定，因此这个操作的时间复杂度是O(1)。

class Solution {
    public boolean wordPattern(String pattern, String s) {
        String[] words = s.split(" ");
        String[] alphabet = new String[26];
        
        if(words.length != pattern.length()){
            return false;
        }
        
        for(int i = 0; i < pattern.length(); i++){
            
            if( alphabet[pattern.charAt(i) - 'a'] != null){
                if(!alphabet[pattern.charAt(i) - 'a'].equals(words[i])){
                    return false;
                }
            }
            else{
                alphabet[pattern.charAt(i) - 'a']  = words[i];
            }
        }
        
        for(int i = 0; i < alphabet.length; i++){
            for(int j = i+1; j < alphabet.length; j++){
                if(alphabet[i] == null || alphabet[j] == null){
                    continue;
                }
                if(alphabet[i].equals(alphabet[j])){
                    return false;
                }
            }
        }
        
        return true;
    }
}

Question

Solution

Code

Solution 2

Code

Question

Solution

Code

Solution 2

Code

Question

Solution

动态规划

Code

Question

Solution

Code

Question

Solution

Code

Question

Solution

位运算与掩码

Code

Question

Solution

Code

Question

Solution

Code

Question

Solution

Code

Solution 2

Code

Recents

Archives

Links