2259. Remove Digit From Number to Maximize Result
Posted Updated LeetCode / Easya minute read (About 184 words)

2259. Remove Digit From Number to Maximize Result

Question

You are given a string number representing a positive integer and a character digit.

Return the resulting string after removing exactly one occurrence of digit from number such that the value of the resulting string in decimal form is maximized. The test cases are generated such that digit occurs at least once in number.

Read more
649. Dota2 Senate
Posted Updated LeetCode / Medium3 minutes read (About 483 words)

649. Dota2 Senate

Question

In the world of Dota2, there are two parties: the Radiant and the Dire.

The Dota2 senate consists of senators coming from two parties. Now the Senate wants to decide on a change in the Dota2 game. The voting for this change is a round-based procedure. In each round, each senator can exercise one of the two rights:

  • Ban one senator’s right: A senator can make another senator lose all his rights in this and all the following rounds.
  • Announce the victory: If this senator found the senators who still have rights to vote are all from the same party, he can announce the victory and decide on the change in the game.

Given a string senate representing each senator’s party belonging. The character 'R' and 'D' represent the Radiant party and the Dire party. Then if there are n senators, the size of the given string will be n.

The round-based procedure starts from the first senator to the last senator in the given order. This procedure will last until the end of voting. All the senators who have lost their rights will be skipped during the procedure.

Suppose every senator is smart enough and will play the best strategy for his own party. Predict which party will finally announce the victory and change the Dota2 game. The output should be "Radiant" or "Dire".

Read more
Posted Updated LeetCode / Medium2 minutes read (About 359 words)

609. Find Duplicate File in System

Question

Given a list paths of directory info, including the directory path, and all the files with contents in this directory, return all the duplicate files in the file system in terms of their paths. You may return the answer in any order.

A group of duplicate files consists of at least two files that have the same content.

A single directory info string in the input list has the following format:

  • "root/d1/d2/.../dm f1.txt(f1_content) f2.txt(f2_content) ... fn.txt(fn_content)"

It means there are n files (f1.txt, f2.txt ... fn.txt) with content (f1_content, f2_content ... fn_content) respectively in the directory “root/d1/d2/.../dm". Note that n >= 1 and m >= 0. If m = 0, it means the directory is just the root directory.

The output is a list of groups of duplicate file paths. For each group, it contains all the file paths of the files that have the same content. A file path is a string that has the following format:

  • "directory_path/file_name.txt"

Solution

使用StringBuffer对字符串进行处理。
采用HashMap建立内容和对应列表的映射。

遍历处理字符串，并添加到map中。
最后遍历map，如果对应的列表size大于1，则加入结果。

Code

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
37
38
39
40
class Solution {
    public List<List<String>> findDuplicate(String[] paths) {
        List<List<String>> res = new ArrayList<>();
        HashMap<String, List<String>> map = new HashMap<>();
        
        for(String path : paths){
            StringBuffer folder = new StringBuffer();
            
            int i = 0;
            while(path.charAt(i) != ' '){
                folder.append(path.charAt(i));
                i++;
            }
            while(i < path.length()){
                while(path.charAt(i) == ' ') i++;
                StringBuffer filename = new StringBuffer();
                while(i < path.length() && path.charAt(i) != '('){
                    filename.append(path.charAt(i));
                    i++;
                }

                StringBuffer content = new StringBuffer();
                while(i < path.length() && path.charAt(i) != ')'){
                    content.append(path.charAt(i));
                    i++;
                }
                i++;
                List<String> arr = map.getOrDefault(content.toString(), new ArrayList<String>());
                arr.add(folder.toString() + '/' + filename);
                map.put(content.toString(), arr);
            }
        }
        
        for(String content : map.keySet()){
            if(map.get(content).size() > 1) res.add(map.get(content));
        }
        
        return res;
    }
}
869. Reordered Power of 2
Posted Updated LeetCode / Medium / 复习3 minutes read (About 411 words)

869. Reordered Power of 2

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

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
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

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
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);
        }
    }
}
383. Ransom Note
Posted Updated LeetCode / Easya minute read (About 125 words)

383. Ransom Note

Question

Given two strings ransomNote and magazine, return true* if ransomNote can be constructed by using the letters from magazine and false otherwise*.

Each letter in magazine can only be used once in ransomNote.

Solution

数组统计，统计magazine内的字符。
遍历ransomNote，如果对字符数组位置为0则返回false。
每次遍历减少数组统计结果。

最后返回true。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        char[] bin = new char[26];
        
        for(char c : magazine.toCharArray()) bin[c-'a']++;
        for(char c : ransomNote.toCharArray()){
            if(bin[c-'a'] == 0) return false;
            bin[c-'a']--;
        }
        
        return true;
    }
}
804. Unique Morse Code Words
Posted Updated LeetCode / Easya minute read (About 149 words)

804. Unique Morse Code Words

Question

International Morse Code defines a standard encoding where each letter is mapped to a series of dots and dashes, as follows:

  • 'a' maps to ".-",
  • 'b' maps to "-...",
  • 'c' maps to "-.-.", and so on.

For convenience, the full table for the 26 letters of the English alphabet is given below:

[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]

Given an array of strings words where each word can be written as a concatenation of the Morse code of each letter.

  • For example, "cab" can be written as "-.-..--...", which is the concatenation of "-.-.", ".-", and "-...". We will call such a concatenation the transformation of a word.

Return the number of different transformations among all words we have.

Solution

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int uniqueMorseRepresentations(String[] words) {
        String[] alphabet = new String[]{".-","-...","-.-.","-..",".","..-.","--.",
                                         "....","..",".---","-.-",".-..","--","-.",
                                         "---",".--.","--.-",".-.","...","-","..-",
                                         "...-",".--","-..-","-.--","--.."};
        HashSet<String> set = new HashSet<>();
        
        for(String word : words){
            StringBuffer sb = new StringBuffer();
            for(char c : word.toCharArray()){
                sb.append(alphabet[c - 'a']);
            }
            set.add(sb.toString());
        }
        
        return set.size();
    }
}
13. Roman to Integer
Posted Updated LeetCode / Easy2 minutes read (About 342 words)

13. Roman to Integer

Question

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

  • I can be placed before V (5) and X (10) to make 4 and 9.
  • X can be placed before L (50) and C (100) to make 40 and 90.
  • C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer.

Solution

倒叙遍历，记录几个mark以标注是否出现对应的字母。

初始res为0，根据字符加减数值。
如果出现则将mark设置为真。
如果mark为真，且上一个字符出现对应需要减去的罗马字符，则改加为减。

最后返回res值。

Code

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
37
38
39
40
41
class Solution {
    public int romanToInt(String s) {
        int res = 0;
        boolean markX = false, markC = false, markM = false;
        
        for(int i = s.length()-1; i >= 0; i--){
            char c = s.charAt(i);
            if(c == 'I'){
                if(markX) res -= 1;
                else res += 1;
            }
            else if(c == 'V'){
                markX = true;
                res += 5;
            }
            else if(c == 'X'){
                markX = true;
                if(markC) res -= 10;
                else res += 10;
            }
            else if(c == 'L'){
                markC = true;
                res += 50;
            }
            else if(c == 'C'){
                markC = true;
                if(markM) res -= 100;
                else res += 100;
            }
            else if(c == 'D'){
                markM = true;
                res += 500;
            }
            else if(c == 'M'){
                markM = true;
                res += 1000;
            }
        }
        return res;
    }
}
890. Find and Replace Pattern
Posted Updated LeetCode / 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

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
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;
    }
}
1647. Make Character Frequencies Unique
Posted Updated LeetCode / Medium2 minutes read (About 227 words)

1647. Make Character Frequencies Unique

Question

A string s is called good if there are no two different characters in s that have the same frequency.

Given a string s, return* the minimum number of characters you need to delete to make s good.*

The frequency of a character in a string is the number of times it appears in the string. For example, in the string "aab", the frequency of 'a' is 2, while the frequency of 'b' is 1.

Solution

数组统计+哈希表
用数组统计记录每个字符出现的数量。
count记录需要减少的字符数量。

遍历统计数组，如果哈希表中已经记录，则将数组统计减少，直到归零。
每减少一次则为count加一。
如果哈希表中未记录，则将当前数字添加到哈希表中。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int minDeletions(String s) {
        int count = 0;
        HashSet<Integer> set = new HashSet<>();
        int[] bin = new int[26];
        for(char c : s.toCharArray()){
            bin[c - 'a']++;
        }
        
        for(int i = 0; i < 26; i++){
            while(bin[i] !=0 && set.contains(bin[i])){
                bin[i]--;
                count++;
            }
            set.add(bin[i]);
        }
        return count;
    }
}
1689. Partitioning Into Deci-Binary Numbers
Posted Updated LeetCode / Mediuma few seconds read (About 100 words)

1689. Partitioning Into Deci-Binary Numbers

Question

A decimal number is called deci-binary if each of its digits is either 0 or 1 without any leading zeros. For example, 101 and 1100 are deci-binary, while 112 and 3001 are not.

Given a string n that represents a positive decimal integer, return the minimum number of positive deci-binary numbers needed so that they sum up to n.

Solution

遍历所有字符，返回字符串中的最大整数。

Code

1
2
3
4
5
6
7
8
9
class Solution {
    public int minPartitions(String n) {
        char max = '0';
        for(char s : n.toCharArray()){
            if(s > max) max = s;
        }
        return max - '0';
    }
}
Posted Updated LeetCode / Easya minute read (About 119 words)

2315. Count Asterisks

Question

You are given a string s, where every two consecutive vertical bars '|' are grouped into a pair. In other words, the 1st and 2nd '|' make a pair, the 3rd and 4th '|' make a pair, and so forth.

Return *the number of '*' in s, excluding the '*' between each pair of *'|'.

Note that each '|' will belong to exactly one pair.

Solution

统计“|”字符出现的数量，如果数量为偶数时，则计算出现的“*”符号。

Code

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int countAsterisks(String s) {
        int num = 0, count = 0;
        for(char c : s.toCharArray()){
            if(c == '|') num++;
            else if((num & 1) == 0 && c == '*') count++;
        }
        return count;
    }
}
771. Jewels and Stones
Posted Updated LeetCode / Easya minute read (About 142 words)

771. Jewels and Stones

Question

You’re given strings jewels representing the types of stones that are jewels, and stones representing the stones you have. Each character in stones is a type of stone you have. You want to know how many of the stones you have are also jewels.

Letters are case sensitive, so "a" is considered a different type of stone from "A".

Solution

数组统计，先遍历宝石，记录宝石的位置。
然后遍历石头，如果对应的位置已被记录则计数加一。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int numJewelsInStones(String jewels, String stones) {
        int ret = 0;
        int[] bin = new int[58];
        for(char c : jewels.toCharArray()){
            bin[c-'A']++;
        }
        
        for(char c : stones.toCharArray()){
            if(bin[c-'A'] != 0) ret++;
        }
        return ret;
    }
}
1108. Defanging an IP Address
Posted Updated LeetCode / Easya few seconds read (About 72 words)

1108. Defanging an IP Address

Question

Given a valid (IPv4) IP address, return a defanged version of that IP address.

A defanged IP address replaces every period "." with "[.]".

Solution

迭代每个字符，用StringBuffer类来组成新的字符串。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public String defangIPaddr(String address) {
        StringBuffer sb = new StringBuffer();
        for(char c : address.toCharArray()){
            if(c == '.'){
                sb.append("[.]");
            }
            else{
                sb.append(c);
            }
        }
        return sb.toString();
    }
}
820. Short Encoding of Words
Posted Updated LeetCode / Medium4 minutes read (About 596 words)

820. Short Encoding of Words

Question

A valid encoding of an array of words is any reference string s and array of indices indices such that:

  • words.length == indices.length
  • The reference string s ends with the '#' character.
  • For each index indices[i], the substring of s starting from indices[i] and up to (but not including) the next '#' character is equal to words[i].

Given an array of words, return the length of the shortest reference string s possible of any valid encoding of words.

Solution 1

LeetCode这几天的每日一题时不让我学会字典树势不罢休啊……

字典树，参数isLeaf记录每个TireNode节点是否为叶子节点。
将单词倒序组建字典树，并维护isLeaf的属性。

计算从根节点到达每个叶子节点的长度再加一的和即可。

Code

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
37
38
39
40
41
42
43
class Solution {
    class TrieNode{
        TrieNode[] next = new TrieNode[26];
        boolean isLeaf;
    }
    TrieNode root;
    int count;
    
    public int minimumLengthEncoding(String[] words) {        
        count = 0;
        root = new TrieNode();
        
        for(String word : words){
            add(word);
        }
        countLeaves(root, 0);
        return count;
    }
    
    private void add(String word){
        TrieNode curr = root;
        for(int i = word.length()-1; i >= 0; i--){
            int index = word.charAt(i) - 'a';
            if(curr.next[index] == null){
                curr.isLeaf = false;
                curr.next[index] = new TrieNode();
                curr.next[index].isLeaf = true;
            }
            curr = curr.next[index];
        }
    }
    
    private void countLeaves(TrieNode root, int length){
        if(root.isLeaf){
            count += length + 1;
        } 
        else{
            for(int i = 0; i < 26; i++){
                if(root.next[i] != null) countLeaves(root.next[i], length+1);
            }
        }
    }
}

Solution 2

排序，将数组words根据单词倒序排序。
倒序构成字典树，如果展开新的字典树分支（创建新的TrieNode节点）则将count加入根节点到新节点的距离。

Code

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
    class TrieNode{
        TrieNode[] next = new TrieNode[26];
        boolean end;
    }
    TrieNode root;
    int count;
    
    public int minimumLengthEncoding(String[] words) {
        Arrays.sort(words, new Comparator<String>(){
            public int compare(String a, String b){
                int i = a.length()-1, j = b.length()-1;
                while(i >= 0 && j >= 0){
                    int index = a.charAt(i) - b.charAt(j);
                    if(index == 0){
                        i--;
                        j--;
                    }
                    else{
                        return index;
                    }
                }
                return j - i;
            }
        });
        
        count = 0;
        root = new TrieNode();
        
        for(String word : words){
            add(word);
        }
        
        return count;
    }
    
    private void add(String word){
        TrieNode curr = root;
        int length = 1;
        boolean newTrieNode = false;
        for(int i = word.length()-1; i >= 0; i--){
            int index = word.charAt(i) - 'a';
            if(curr.next[index] == null){
                curr.next[index] = new TrieNode();
                newTrieNode = true;
            }
            curr = curr.next[index];
            length++;
        }
        curr.end = true;
        if(newTrieNode) count += length;
    }
}

Solution 3

倒序重组字符串并记录到reversedWords[]数组，然后根据字典顺序排序。
如果数组的上一个字符串不是下一个字符串的前缀，则加入上一个字符串的长度加一。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {    
    public int minimumLengthEncoding(String[] words) {
        String[] reversedWords = new String[words.length];
        int count = 0, index = 0;
        for(String word : words){
            reversedWords[index] = new StringBuffer(word).reverse().toString();
            index++;
        }
        
        Arrays.sort(reversedWords);
        for(int i = 0; i < words.length-1; i++){
            if(!reversedWords[i+1].startsWith(reversedWords[i])) count += reversedWords[i].length()+1;
        }
        count += reversedWords[words.length-1].length()+1;
        return count;
    }
}
1268. Search Suggestions System
Posted Updated LeetCode / Medium / 复习2 minutes read (About 366 words)

1268. Search Suggestions System

Question

You are given an array of strings products and a string searchWord.

Design a system that suggests at most three product names from products after each character of searchWord is typed. Suggested products should have common prefix with searchWord. If there are more than three products with a common prefix return the three lexicographically minimums products.

Return a list of lists of the suggested products after each character of searchWord is typed.

Solution

字典树+优先级队列。
在TrieNode节点中保存PriorityQueue，以记录该节点下的三个单词。
注意PriorityQueue中的String需要按倒序排列，以保证维护时可以直接poll掉字符顺序较后的单词。

add()方法

创建并添加TrieNode节点，同时在移动当前节点位置时，需要维护PriorityQueue，当长度大于3时，则挤出字典顺序排列较后的单词。

search()方法

在查找前缀时，将每个TrieNode节点上的PriorityQueue倒序加入List。

Code

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
37
38
39
40
41
42
43
44
45
46
47
class Solution {
    class TrieNode{
        boolean end;
        TrieNode[] children = new TrieNode[26];
        PriorityQueue<String> q = new PriorityQueue<>((a, b) -> b.compareTo(a));
    }
    
    TrieNode root;
    
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        List<List<String>> ret = new ArrayList<>();
        root = new TrieNode();
        for(String word : products){
            add(word);
        }
        return search(searchWord);
    }
    
    private void add(String word){
        TrieNode curr = root;
        for(char c : word.toCharArray()){
            int i = c - 'a';
            if(curr.children[i] == null) curr.children[i] = new TrieNode();
            curr = curr.children[i];
            curr.q.add(word);
            if(curr.q.size() > 3) curr.q.poll();
        }
        curr.end = true;
    }
    
    private List<List<String>> search(String prefix){
        List<List<String>> ret = new ArrayList<>();
        TrieNode curr = root;
        for(char c : prefix.toCharArray()){
            int i = c - 'a';
            if(curr.children[i] == null) curr.children[i] = new TrieNode();
            curr = curr.children[i];
            List<String> temp = new ArrayList<>();
            while(!curr.q.isEmpty()){
                temp.add(curr.q.poll());
            }
            Collections.reverse(temp);
            ret.add(temp);
        }
        return ret;
    }
}
Follow

Recents

Archives

Links

×