The first question is : 781. Rabbits in the forest

LeetCode: 781. Rabbits in the forest

describe :
There are an unknown number of rabbits in the forest . Ask some of the rabbits “ How many rabbits are there with you （ Refers to the rabbit being asked ） Same color ?” , Collect the answers into an integer array answers in , among answers[i] It's No i The answer of the rabbit .

Here's your array answers , Return to the minimum number of rabbits in the forest .

Their thinking :

1. Here we use hash table to solve problems . value The value is , The number of rabbits corresponding to the color
2. Traversal array , Check whether the value exists in the hash table . If there is , You also need to judge the current value Is the value greater than 0.
   • for example [1,1,1] The situation of , Here you are 3 A reply 1, If they all have the same color , Then it can't be 1, Will be contradictory , therefore , Only two colors are the same , The rest 1 One is the same as the others .
3. If it exists in the hash table , And value Greater than 0, Then let value-1. Subtract one person .
4. If the hash table here does not exist , Directly record the results

Code implementation :

class Solution {
    
    public int numRabbits(int[] answers) {
    
        Map<Integer,Integer> map = new HashMap<>();
        int res = 0;
        for(int answer : answers) {
    
            if(map.containsKey(answer) && map.get(answer) > 0) {
    
                map.put(answer,map.get(answer) - 1);
            }else {
    
                res += answer + 1;
                map.put(answer,answer);
            }
        }
        return res;
    }
}

The second question is : 783. Binary search tree node minimum distance

LeetCode: 783. Binary search tree node minimum distance

describe :
Give you a binary search tree root node root , return Between any two different node values in the tree The minimum difference between .

The difference is a positive number , Its value is equal to the absolute value of the difference between the two values .

Their thinking :

1. Because it's a binary search tree . Middle order traversal is ordered .
2. Then calculate the difference for the ordered , You can get the minimum difference .
3. Use the root node to compare .

Code implementation :

class Solution {
    
    private TreeNode pre = null;
    private int res = Integer.MAX_VALUE;
    public int minDiffInBST(TreeNode root) {
    
        if(root == null) return 0;
        minDiffInBST(root.left);
        if(pre != null) {
    
            res = Math.min(res,root.val - pre.val);
        }
        pre = root;
        minDiffInBST(root.right);
        return res;
    }
}

Third question : 804. The only Morse code word

LeetCode: 804. The only Morse code word

describe :
The International Morse code defines a standard encoding method , Each letter corresponds to a string of dots and dashes , such as :

• 'a' Corresponding ".-" ,
• 'b' Corresponding "-..." ,
• 'c' Corresponding "-.-." , And so on .

For convenience , all 26 The Morse code list of English letters is as follows ：

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

Here's an array of strings words , Each word can be written as a combination of each letter corresponding to the Morse code .

• for example ,“cab” It can be written. “-.-…–…” ,( namely “-.-.” + “.-” + “-…” A combination of strings ). We call such a connection process Translation of words .

Yes words Translate all words in , Back to different Translation of words The number of .

Their thinking :

1. Here we define an array directly , Used to put the Morse code corresponding to each letter
2. Then traverse words, Get the string form of Morse password corresponding to each string .
3. Put in set in , see set Size

Code implementation :

class Solution {
    
    public int uniqueMorseRepresentations(String[] words) {
    
        String[] str = {
    ".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
        Set<String> set = new HashSet<>();
        for(String word : words) {
    
            StringBuilder sb = new StringBuilder();
            for(char ch : word.toCharArray()) {
    
                sb.append(str[ch-'a']);
            }
            set.add(sb.toString());
        }
        return set.size();
    }
}

Fourth question : 817. Linked list component

LeetCode: 817. Linked list component

describe :
Given the chain header node head, Each node on the linked list has a Unique integer value . Also give a list nums, This list is a subset of the integer values in the above list .

Returns a list of nums Number of components in , The definition of a component here is ： The value of the longest continuous node in a link list （ The value must be in the list nums in ） A collection of components .

Their thinking :

1. First of all, will Array nums All elements in Add to hash table
2. Go through the list again , If there are elements in the linked list , It means that this is a component , Record sequence .
3. If the traversal element does not exist in the hash table at this time , Then separate , Next time when traversal exists , You need to record again .
4. You can use one Boolean type to mark

Code implementation :

class Solution {
    
    public int numComponents(ListNode head, int[] nums) {
    
        Set<Integer> set = new HashSet<>();
        for(int num : nums) {
    
            set.add(num);
        }
        int count = 0;
        ListNode cur = head;
        boolean flg = false;
        while(cur != null) {
    
            if(set.contains(cur.val)) {
    
                if(!flg) count++;
                flg = true;
                set.remove(cur.val);
            }else{
    
                flg = false;
            }
            cur = cur.next;
        }
        return count;
    }
}

Fifth question : 2074. Invert the nodes of the even length group

LeetCode: 2074. Invert the nodes of the even length group

describe :
Give you a list of the head node head .

Nodes in the list According to the order Divided into several Non empty Group , The lengths of these non empty groups form a sequence of natural numbers （1, 2, 3, 4, …）. A group of length Is the number of nodes allocated in the group . let me put it another way ：

• node 1 Assigned to the first group
• node 2 and 3 Assigned to the second group
• node 4、5 and 6 Assigned to the third group , And so on

Be careful , The length of the last group may be less than or equal to 1 + The length of the penultimate group .

reverse Every even numbers Nodes in the length group , And return the head node of the modified linked list head .

Their thinking :

1. Here, when traversing the linked list , You can use one n=1 To record , Every time n++, This is also grouping 1 , 2 ,3 ,4 …
2. Pay attention here , Maybe you grouped 2 individual But the length of the linked list is not enough , So when traversing, you should also pay attention to the real packet length .
3. If the true length is even It's about to reverse .
4. Reverse to record the inverted head node , Tail node , And then link .

Code implementation :

class Solution {
    
    public ListNode reverseEvenLengthGroups(ListNode head) {
    
        ListNode cur = head;
        ListNode pre = null;
        int n = 1;
        while(cur != null) {
    
            int k = 0;
            ListNode tmp = pre;
            while(k < n && cur!= null) {
    
                pre = cur;
                cur = cur.next;
                k++;
            }
            
            if(k % 2 == 0) {
    
                ListNode tmpNext = tmp.next;
                pre = reverse(tmp.next,pre);
                tmp.next = pre;
                tmpNext.next = cur;
                pre = tmpNext;
            }
            n++;
        }
        return head;
    }
    public ListNode reverse(ListNode cur, ListNode pre) {
    
        ListNode ret = null;
        while(cur != pre) {
    
            ListNode curNext = cur.next;
            cur.next = ret;
            ret = cur;
            cur = curNext;
        }
        pre.next = ret;
        return pre;
    }
}

Sixth question : 2130. The largest twins in the linked list are

LeetCode: 2130. The largest twins in the linked list are

describe :
In a size of n And n by even numbers In the linked list , about 0 <= i <= (n / 2) - 1 Of i , The first i Nodes （ Subscript from 0 Start ） The twin node of is (n-1-i) Nodes .

• For example ,n = 4 Then the node 0 Is the node 3 Twin nodes of , node 1 Is the node 2 Twin nodes of . This is the length of n = 4 All twin nodes in the linked list .

Twin sum It is defined as the sum of the values of a node and its twin nodes .

Give you the head node of a linked list with an even length head , Please return to the linked list The largest twins and .

Their thinking :

1. Here you can traverse in turn .
2. First, get the intermediate node . Here we use the fast and slow pointer method .
3. Then reverse the second half .
4. Let a node point to the head node of the left half , A node points to the head node of the right half .
5. Then traverse relatively , Find the maximum value of the added value of two nodes ,

Code implementation :

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */
class Solution {
    
    public int pairSum(ListNode head) {
    
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
    
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode cur = slow;
        ListNode ret = null;
        while(cur != null) {
    
            ListNode curNext = cur.next;
            cur.next = ret;
            ret = cur;
            cur = curNext;
        }
        int max = 0;
        while(head != null && ret != null) {
    
            max = Math.max(max,head.val + ret.val);
            head = head.next;
            ret = ret.next;
        }
        return max;
    }
}