Search, insert and delete of hash table

Hello, everyone , I'm Xiao Sheng , This week I'll share some hash table algorithm exercises

Search, insert and delete hash table

217. There are duplicate elements

217. There are duplicate elements

Given an array of integers , Determine whether there are duplicate elements

If a value exists, it appears at least twice in the array , The function returns true . If every element in the array is different , Then return to false

Example 1:

 Input : [1,2,3,1]
 Output : true

Example 2:

 Input : [1,2,3,4]
 Output : false

Example 3:

 Input : [1,1,1,3,3,4,3,2,4,2]
 Output : true

class Solution {
    
    public boolean containsDuplicate(int[] nums) {
    
        Arrays.sort(nums);
        for(int i=0;i<nums.length-1;i++){
    
            if(nums[i]==nums[i+1]){
    
                return true;
            }
        }
        return false;
    }
}

349. Intersection of two arrays

349. Intersection of two arrays

Given two arrays , Write a function to calculate their intersection .

Example 1：

 Input ：nums1 = [1,2,2,1], nums2 = [2,2]
 Output ：[2]

Example 2：

 Input ：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
 Output ：[9,4]

explain ：

• Each element of the output must be unique .
• We can ignore the order of output results .

class Solution {
    
    public int[] intersection(int[] nums1, int[] nums2) {
    
        if(nums1.length*nums2.length == 0) return null;
        HashSet<Integer> sites   = new HashSet<>();
        int index = 0;
        int[] array = new int[nums1.length<nums2.length?nums1.length:nums2.length];
        for(int i=0;i<nums1.length;i++){
    
            for(int j=0;j<nums2.length;j++){
    
                if(nums1[i]==nums2[j] && sites.add(nums1[i])){
    
                    array[index] = nums1[i];
                    index++;
                }
            }
        }
        int[] array2 = new int[index];
        for(int i=0;i<index;i++){
    
            array2[i] = array[i];
        }
        return array2;  
    }
}

202. Happy number

202. Happy number

The difficulty is simple 730

Write an algorithm to judge a number n Is it a happy number .

「 Happy number 」 Defined as ：

• For a positive integer , Replace the number with the sum of the squares of the numbers in each of its positions .
• Then repeat the process until the number becomes 1, It could be Infinite loop But it doesn't change 1.
• If It can be 1, So this number is the happy number .

If n If it's happy, count it back true ; No , Then return to false .

Example 1：

 Input ：n = 19
 Output ：true
 explain ：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

Example 2：

 Input ：n = 2
 Output ：false

Tips ：

• 1 <= n <= 231 - 1

class Solution {
    
    public boolean isHappy(int n) {
    
        Set<Integer> set = new HashSet<>();
        while(n != 1){
     
            n = happyTurn(n);
            if(n == 1) return true;
            if(!set.add(n)) return false;
        }
        return true;
    }
    
    public int happyTurn(int n){
    
        int round,sum=0;    //  Remainder   Sum up 
        while(n > 0){
    
            round = n%10;
            n = n/10;
            sum += round*round;
        }
        return sum;
    }
}

290. Rules of words

290. Rules of words

The difficulty is simple 403

Give a rule pattern And a string str , Judge str Follow the same rule .

there follow Finger perfect match , for example , pattern Each letter and string in str There is a two-way connection between each non empty word in .

Example 1:

 Input : pattern = "abba", str = "dog cat cat dog"
 Output : true

Example 2:

 Input :pattern = "abba", str = "dog cat cat fish"
 Output : false

Example 3:

 Input : pattern = "aaaa", str = "dog cat cat dog"
 Output : false

Example 4:

 Input : pattern = "abba", str = "dog dog dog dog"
 Output : false

explain :
You can assume pattern Contains only lowercase letters , str Contains lowercase letters separated by a single space .

class Solution {
    
    public boolean wordPattern(String pattern, String s) {
    
        HashMap<String,Character> StrChar = new HashMap<>();
        HashMap<Character,String> CharStr = new HashMap<>();
        int n = s.length(),m=pattern.length(),sIndex=0,patternIndex=0;
        while(--m >=0){
    
            char ch = pattern.charAt(patternIndex++);
            String str = "";
            if(sIndex>=n) break;
            for(int i=sIndex;i<n && s.charAt(i)!=' ';i++){
    
                str += s.charAt(i)+"";
                sIndex++;
            }
            sIndex+=1;
            if(StrChar.containsKey(str)&&StrChar.get(str)!=ch){
    
                return false;
            }
            if(CharStr.containsKey(ch)&&!CharStr.get(ch).equals(str)){
    
                return false;
            }
            StrChar.put(str,ch);
            CharStr.put(ch,str);
        }
        return m<0&&sIndex>=n;
    }
}

205. Isomorphic Strings

205. Isomorphic Strings

The difficulty is simple 405

Given two strings s and *t*, Judge whether they are isomorphic .

If s The characters in can be replaced according to some mapping relationship *t* , So these two strings are isomorphic .

Every character that appears should be mapped to another character , Without changing the order of characters . Different characters cannot be mapped to the same character , The same character can only be mapped to the same character , Characters can be mapped to themselves .

Example 1:

 Input ：s = "egg", t = "add"
 Output ：true

Example 2：

 Input ：s = "foo", t = "bar"
 Output ：false

Example 3：

 Input ：s = "paper", t = "title"
 Output ：true

Tips ：

• It can be assumed s and *t* Same length .

class Solution {
    
    public boolean isIsomorphic(String s, String t) {
    
        HashMap<Character,Character> chst = new HashMap<>();  
        HashMap<Character,Character> chts = new HashMap<>();  
        int m=s.length(),n=t.length(),nIndex=0,mIndex=0;
        char chs,cht;
        if(m!=n) return false;
        for(int i=0;i<m;i++){
    
            chs = s.charAt(i);
            cht = t.charAt(i);
            if(chst.containsKey(chs)&&chst.get(chs)!=cht){
    
                return false;
            }
            if(chts.containsKey(cht)&&chts.get(cht)!=chs){
    
                return false;
            }
            chst.put(chs,cht);
            chts.put(cht,chs);
        }
        return true;
    }
}

633. Sum of squares （ Non hash table ）

633. Sum of squares

Given a nonnegative integer c , You have to decide if there are two integers a and b, bring a2 + b2 = c .

Example 1：

 Input ：c = 5
 Output ：true
 explain ：1 * 1 + 2 * 2 = 5

Example 2：

 Input ：c = 3
 Output ：false

Example 3：

 Input ：c = 4
 Output ：true

Example 4：

 Input ：c = 2
 Output ：true

Example 5：

 Input ：c = 1
 Output ：true

Tips ：

• 0 <= c <= 231 - 1

Method 1 ： Use sqrt function

Their thinking ：

1. Find the maximum square by square n
2. Put the maximum square n As a conditional decreasing cycle
3. Until you find another subtracted square, it returns true
4. If the number is not found until the end of the cycle, it returns false

class Solution {
    
    public boolean judgeSquareSum(int c) {
    
        int n = (int)Math.sqrt(c)+1;  // +1  Just to offset  n--
        while(n-- > 0)
            if(Math.sqrt(c-n*n) == (int)Math.sqrt(c-n*n))
                return true;
        return false;
    }
}

Method 2 ： Double pointer

• If a^2 + b^2 =c, We found a solution to the problem , return true
• If a^2 + b^2 <c, At this time, we need to a The value of the add 1, Continue to find
• If a^2 + b^2 >c, At this time, we need to b The value of the reduction 1, Continue to find

Have you ever thought about the possibility of missing

	0	1	2	3	4
0	0	1	4	9	16
1	1	2	5	10	17
2	4	5	8	13	20
3	9	10	13	18	25
4	16	17	20	25	32

class Solution {
    
    public boolean judgeSquareSum(int c) {
    
        long left = 0;
        long right = (long) Math.sqrt(c);
        while (left <= right) {
    
            long sum = left * left + right * right;
            if (sum == c) {
    
                return true;
            } else if (sum > c) {
    
                right--;
            } else {
    
                left++;
            }
        }
        return false;
    }
}