Li Kou brushing questions - hash table

 

  Preface

Hello, friends , I'm your classmate Xiao Wang

Today's topic of force deduction —— Hashtable

Hope to bring you useful knowledge

What I think Xiao Wang wrote is good Please use your hands give the thumbs-up Collection   Comment on

Xiao Wang's home page ： Xiao Wang

Xiao Wang's gitee： Xiao Wang

Xiao Wang's github： Xiao Wang

Catalog

442 Title Description ：

  Their thinking ：

Code attached ：

2283 Title Description ：

Their thinking ：

Code attached : 

884 Title Description ：

Their thinking ：

  Code details ：

2068 Title Description :

 

Their thinking ：

Code attached ：

---

442 Title Description ：

Give you a length of n Array of integers for nums , among nums All integers of are in the range [1, n] Inside , And each integer appears once or two . Please find out all that appear two The integer of , And Array form return .

You must design and implement a time complexity of O(n) And only the algorithm of constant extra space is used to solve this problem .

Example 1：

Input ：nums = [4,3,2,7,8,2,3,1]
Output ：[2,3]
Example 2：

Input ：nums = [1,1,2]
Output ：[1]
Example 3：

Input ：nums = [1]
Output ：[]
 

  Their thinking ：

According to the title requirements Use extra space to solve

We open up an array with equal space size  

• Go through the array
• If there is a repeating element add To list in
• Finally, it will be returned as an array  

Code attached ：

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer>list =new ArrayList<>();
        int arr[]=new int [nums.length];
        for(int i=0;i<nums.length;i++){
            if(nums[i]==arr[nums[i]-1]){
                list.add(nums[i]);
            }else{
                arr[nums[i]-1]=nums[i];
            }
        }
        return list;

        }

    }

 

 

2283 Title Description ：

Give you a length of n Array of integers for nums , among nums All integers of are in the range [1, n] Inside , And each integer appears once or two . Please find out all that appear two The integer of , And return as an array .

You must design and implement a time complexity of O(n) And only the algorithm of constant extra space is used to solve this problem .

Example 1：

Input ：nums = [4,3,2,7,8,2,3,1]
Output ：[2,3]
Example 2：

Input ：nums = [1,1,2]
Output ：[1]
Example 3：

Input ：nums = [1]
Output ：[]

Their thinking ：

This problem is directly related to the statistics frequency that will do

Traverse the number of occurrences of statistics

If the subscript i Content in num In the num[i] Time So return true Instead, return to false

Code attached : 

class Solution {
    public boolean digitCount(String num) {
        int len=num.length();
        int []map=new int [10];
        for(int i=0;i<len;i++){
            // The number of occurrences of Statistics 
            map[num.charAt(i)-'0']++;
        }
        for(int i=0;i<len;i++){
            if(map[i]!=num.charAt(i)-'0') return false;
        }
            return true;
    
        

    }
}

 

 

884 Title Description ：

The sentence A string of words separated by a space . Every word It's only made up of lowercase letters .

If a word happens to appear once in one of the sentences , In another sentence There was no , So the word is Unusual .

• Here are two for you The sentence s1 and Unordered list s2 , Back to all Uncommon words A list of . To return to the words in the list, you can press In any order organization .

Example 1：

Input ：s1 = "this apple is sweet", s2 = "this apple is sour"
Output ：["sweet","sour"]
Example 2：

Input ：s1 = "apple apple", s2 = "banana"
Output ：["banana"]

Their thinking ：

• Create a string array to splice two strings  
• use Hashtable The map counts the number of occurrences of each string
• Iterate over the hash table Set all values to 1 Key placement for

• If the number of occurrences is 1  It is the only uncommon string mentioned in the title

  Code details ：

class Solution {
    public String[] uncommonFromSentences(String s1, String s2) {
        // Create a string array to concatenate the two strings 
        String []AB=(s1+" "+s2).split(" ");
        // Count the number of occurrences of each string 
        Map<String,Integer>map=new HashMap<>();
        for(int i=0;i<AB.length;i++){
            map.put(AB[i],map.getOrDefault(AB[i],0)+1);
        }
        // If the number of occurrences is 1  It is the only uncommon string mentioned in the title 
        List<String>list=new ArrayList<>();
        for(String key:map.keySet()){
            if(map.get(key)==1){
                list.add(key);
            }
        }
        String []res=new String[list.size()];
        return list.toArray(res);
    }
}

2068 Title Description :

 

If two strings word1  and word2  In the from 'a'  To 'z'  The difference in the frequency of each letter is No more than  3 , So we call these two strings  word1 and  word2 Almost equal  .

Here you are. Both lengths are  n  String  word1 and  word2 , If  word1  and  word2  Almost equal  , Please return  true , Otherwise return to  false .

A letter x  Appearance frequency   It refers to the number of times it appears in the string .

Example 1：

Input ：word1 = "aaaa", word2 = "bccb"
Output ：false
explain ： character string "aaaa" There is 4 individual 'a' , however "bccb" There is 0 individual 'a' .
The difference between the two is 4 , Greater than upper limit 3 .
Example 2：

Input ：word1 = "abcdeef", word2 = "abaaacc"
Output ：true
explain ：word1 and word2 The difference in the frequency of each letter in the is at most 3 ：
- 'a' stay word1 In the 1 Time , stay word2 In the 4 Time , The difference is 3 .
- 'b' stay word1 In the 1 Time , stay word2 In the 1 Time , The difference is 0 .
- 'c' stay word1 In the 1 Time , stay word2 In the 2 Time , The difference is 1 .
- 'd' stay word1 In the 1 Time , stay word2 In the 0 Time , The difference is 1 .
- 'e' stay word1 In the 2 Time , stay word2 In the 0 Time , The difference is 2 .
- 'f' stay word1 In the 1 Time , stay word2 In the 0 Time , The difference is 1 .
Example 3：

Input ：word1 = "cccddabba", word2 = "babababab"
Output ：true
explain ：word1 and word2 The difference in the frequency of each letter in the is at most 3 ：
- 'a' stay word1 In the 2 Time , stay word2 In the 4 Time , The difference is 2 .
- 'b' stay word1 In the 2 Time , stay word2 In the 5 Time , The difference is 3 .
- 'c' stay word1 In the 3 Time , stay word2 In the 0 Time , The difference is 3 .
- 'd' stay word1 In the 2 Time , stay word2 In the 0 Time , The difference is 2 .

Their thinking ：

•   Create a 26 An array of size spaces To store 'a'-'z' The number of letters
• Traverse word1 and word2 Two strings
• The first string appears ++, The second one is --
• Finally, judge if the absolute value exceeds 3 Just go back to false Come back anyway true！

Code attached ：

class Solution {
    public boolean checkAlmostEquivalent(String word1, String word2) {
      int res[]=new int[26]; // Statistical characters 'a' To character 'z' Number of occurrences 
      for(char c1:word1.toCharArray()){
          res[c1-'a']++;
      }
      for(char c2:word2.toCharArray()){
          res[c2-'a']--;
      }
    // for(int i=0;i<word1.length();i++){
    //     res[word1.charAt(i)-'a']++;
    // }
    //    for(int i=0;i<word2.length();i++){
    //     res[word2.charAt(i)-'a']--;
    // }
      for(int i=0;i<26;i++){
          if(Math.abs(res[i])>3){
              return false;
          }
      }

        return true;
    }
}

 

 

Catalog

subject	difficulty
442. Duplicate data in array	****
2283. Determine whether the number count of a number is equal to the value of the digit	****
2068. Check that the two strings are almost equal	****
884. Unusual words in two sentences	****