[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;
}
}
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) {
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;
}``````

【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