current position:Home>[introduction to 100 day algorithm - three questions a day - Day8] isomorphic string, duplicate elements, flip binary tree

[introduction to 100 day algorithm - three questions a day - Day8] isomorphic string, duplicate elements, flip binary tree

2021-08-25 22:36:04 nezha

Hello everyone , I'm Nezha , A person who loves coding Java The engineer , In line with “ More haste, less speed. , If you want to reach, you need to be quick ” The attitude of learning , Growing up on the road of no return , Growth , Just take time to polish your eyes , When I was young, I valued , When you are old, you look like a feather , When I was young, I despised , When you are old, you look like Mount Tai , The road to growth , Is also gradually put down obsession , The journey of inner peace .

Maybe , We never know where we can go , Meet who , What kind of person will you become in the end , But remember , Someone who can climb high , Never someone else's shoulder , It's the one who stays up all night , The road of life has just started , When you are tired, don't be confused , Look back , You are no longer that young and frivolous boy .

   Dalian Friendship Plaza


Algorithms are the foundation of advanced architects , The foundation is not solid , The earth trembled and the mountains swayed ,2021-8-14 Start to brush questions , The goal is 100 God ,300 Avenue LeetCode Algorithm problem , Sharing is the best way to learn , come on. , Hi up .

1、LeetCode 205. Isomorphic Strings

subject

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 .

Xiaobian vegetable solution

public static boolean isIsomorphic(String s, String t) {
    Map<String, String> map = new HashMap<>();
    for (int i = 0; i < s.length(); i++) {
        // The first string is the current character 
        String sc = String.valueOf(s.charAt(i));
        // The second string is the current character 
        String tc = String.valueOf(t.charAt(i));
        // If the first one map Include this character , Judge whether the current position value of the second string is equal to map Of value, Unequal return false
        if (map.containsKey(sc)){
            if(!map.get(sc).equals(tc)){
                return false;
            }
        }else{// If not 
            // There should not be a value of tc Of key
            if(map.containsValue(tc)){
                return false;
            }
            // Put in map
            map.put(sc, tc);
        }
    }
    return true;
}

The boss points out the country

public static boolean isIsomorphic(String s, String t) {
    Map<Character, Character> map1 = new HashMap<Character, Character>();
    Map<Character, Character> map2 = new HashMap<Character, Character>();
    for (int i = 0; i < s.length(); i++) {
        // The first string is the current character 
        char sc = s.charAt(i);
        // The second string is the current character 
        char tc = t.charAt(i);
        // If map1 contain , Then the value must be equal to tc,,,,, If map2 Contains this value , Then this value must be equal to sc,, Otherwise, the report will be wrong 
        if (map1.containsKey(sc) && map1.get(sc)!=tc || map2.containsKey(tc) && map2.get(tc)!=sc){
            return false;
        }
        map1.put(sc,tc);
        map2.put(tc,sc);
    }
    return true;
}

The only drawback is Character The problem of ,,, Keep in mind that , Keep in mind that .

2、LeetCode 217. There are duplicate elements

subject

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 .

Xiaobian vegetable solution  

public boolean containsDuplicate(int[] nums) {
   List<Integer> list = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) {
        if(list.contains(nums[i])){
            return true;
        }
        list.add(nums[i]);
    }
    return false;
}

Prompt out of time limit !

The boss points out the country

public static boolean containsDuplicate(int[] nums) {
    Set<Integer> set = new HashSet<Integer>();
    for (int n : nums) {
        if (!set.add(n)) {
            return true;
        }
    }
    return false;
}

Set Inefficient retrieval of elements , Efficient delete and insert ;List High efficiency in finding elements , Inserting and deleting elements is inefficient .

Use contains Method to query whether the element exists HashSet than ArrayList Much faster .

3、LeetCode 226. Flip binary tree

subject

Turn over a binary tree .

Xiaobian vegetable solution

public TreeNode invertTree(TreeNode root) {
    if(root == null){
        return null;
    }
    TreeNode left = invertTree(root.left);
    TreeNode right = invertTree(root.right);
    root.left = right;
    root.right  = left;
    return root;
}

Recommended reading

【100 Introduction to sky algorithm - Three questions a day - Day1】 Middle order traversal of binary trees 、 Sum of two numbers 、 Integer inversion

【100 Introduction to sky algorithm - Three questions a day - Day2】 Two points search 、 First wrong version 、 Search insert location

【100 Introduction to sky algorithm - Three questions a day - Day3】 Palindrome number 、 Roman numerals to numbers 、 Maximum common prefix

【100 Introduction to sky algorithm - Three questions a day - Day4】 Valid parenthesis 、 Remove duplicate items from an ordered array 、 Realization strStr

【100 Introduction to sky algorithm - Three questions a day - Day5】 Length of last word 、 Same tree 、 The best time to buy and sell stocks

【100 Introduction to sky algorithm - Three questions a day - Day6】 Symmetric binary tree 、 The maximum depth of a binary tree 、 Convert an ordered array to a binary search tree

【100 Introduction to sky algorithm - Three questions a day - Day7】 Verify the palindrome string 、 A number that appears only once 、 Most elements

copyright notice
author[nezha],Please bring the original link to reprint, thank you.
https://en.qdmana.com/2021/08/20210825223601298o.html

Random recommended