Day 5 of leetcode question brushing

1.  Given the root node of a binary tree root , Please find the maximum value of each layer in the binary tree .

analysis ：

Use dfs. Define a List Store the maximum value of each layer , At the same time define a curHeight Record the maximum height at this time .List[curHeight] What is stored is the maximum value of this height .

    public List<Integer> largestValues(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        dfs(res, root, 0);
        return res;
    }
    public void dfs(List<Integer>res, TreeNode root, int height){
        if (height == res.size()){
            res.add(root.val);
        }else {
            res.set(height, Math.max(res.get(height), root.val));
        }

        if (root.right!=null){
            dfs(res, root.right,height+1);
        }
        if (root.left!=null){
            dfs(res,root.left,height+1);
        }

    }

2.  Please implement a function to determine whether a string represents a value （ Including integers and decimals ）.

 The number （ According to the order ） It can be divided into the following parts ：
 Several spaces 
 A decimal or integer 
（ Optional ） One 'e' or 'E', Followed by an integer /     Several spaces 
 decimal （ According to the order ） It can be divided into the following parts ：
（ Optional ） A symbolic character （'+'  or  '-'）

 One of the following formats ：
 At least one digit , Followed by a dot  '.'
 At least one digit , Followed by a dot  '.' , Followed by at least one number 
 One point  '.' , Followed by at least one number 

 Integers （ According to the order ） It can be divided into the following parts ：
（ Optional ） A symbolic character （'+'  or  '-'）
 At least one digit 

analysis ：

Can't , Look at the answer of the boss . This problem uses finite state automata . According to the character type and the characteristics of legal values , Define the state first , Then draw the state transition diagram .

In the order of strings from left to right , Define the following 9 States .

1. Starting space
2. The sign before the power sign
3. The number before the decimal point
4. decimal point 、 The number after the decimal point
5. When there is a space before the decimal point , decimal point 、 The number after the decimal point
6. Power sign
7. The sign after the power sign
8. The number after the power sign
9. Space at the end

among 2,3,7,8 It is a legal end state .

  Algorithm flow ：

1. First define the state transition table states,states[i] Use a hash table to store , Key value pair  (key, value) meaning ： If input  key , From the state  i  Transition to state  value . The state is initialized to p=0.
2. Traverse s Every character in c：
   • Using the characters t To record c The state of ：
     • c When it is a plus or minus sign , t='s';
     • c Is the number ,t='d';
     • c When it is a decimal point or a space ,t=c;
     • c When it is a power sign , t='e';
     • otherwise ,t='?', Represents an illegal character that does not belong to the judgment range , Then return directly to  false 
   • Termination conditions ： If the character type  t  Not in hash table  states[p] in , Description cannot be transferred to the next state , So go straight back  false.
   • State shift ： state p Transfer to state[p][t]
3. After jumping out of the loop , If the status belongs to 2,3,7,8 Then return to true.

    public boolean isNumber(String s) {
        Map[] states = {
                new HashMap<>() {
   { put(' ', 0); put('s', 1); put('d', 2); put('.', 4); }}, // 0.
                new HashMap<>() {
   { put('d', 2); put('.', 4); }},                           // 1.
                new HashMap<>() {
   { put('d', 2); put('.', 3); put('e', 5); put(' ', 8); }}, // 2.
                new HashMap<>() {
   { put('d', 3); put('e', 5); put(' ', 8); }},              // 3.
                new HashMap<>() {
   { put('d', 3); }},                                        // 4.
                new HashMap<>() {
   { put('s', 6); put('d', 7); }},                           // 5.
                new HashMap<>() {
   { put('d', 7); }},                                        // 6.
                new HashMap<>() {
   { put('d', 7); put(' ', 8); }},                           // 7.
                new HashMap<>() {
   { put(' ', 8); }}                                         // 8.
        };
        int p = 0;
        char t;
        for(char c : s.toCharArray()) {
            if(c >= '0' && c <= '9') t = 'd';
            else if(c == '+' || c == '-') t = 's';
            else if(c == 'e' || c == 'E') t = 'e';
            else if(c == '.' || c == ' ') t = c;
            else t = '?';
            if(!states[p].containsKey(t)) return false;
            p = (int)states[p].get(t);
        }
        return p == 2 || p == 3 || p == 7 || p == 8;
    }

3. Enter an array of integers , Implement a function to adjust the order of the Numbers in the array , Make all odd numbers in the first half of the array , All even numbers are in the second half of the array .

analysis ：

Relatively simple , Use double pointers to traverse from both ends of the array .

public int[] exchange(int[] nums) {
        if (nums.length < 2) return nums;
        int i =0, j = nums.length-1;
        while(i<j){
            while(i<j && nums[i]%2 != 0) ++i;
            while(i<j && nums[j]%2 == 0) --j;
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;

        }
        return nums;
    }

4.  Enter a linked list , Output the last number in the list k Nodes . In order to conform to the habits of most people , From 1 Start counting , That is, the tail node of the list is the last 1 Nodes .

analysis ：

Or double pointer problem , Keep the distance between the two pointers (K-1), When the first pointer traverses the last node, returning the second pointer is the penultimate k Nodes .

    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode node = head;
        for (int i = 0; i < k-1; i++) {
            node = node.next;
        }
        if (node == null) return null;
        while(node.next != null){
            head = head.next;
            node = node.next;
        }
        return head;

    }

5.  Define a function , Enter the head node of a linked list , Invert the linked list and output the head node of the inverted linked list .

analysis ：

Define two pointers pre and head, A record of the current node , A node that records the previous node of the current node , Then repair the current node next, And put pre and head Move back a bit .

    public ListNode reverseList(ListNode head) {
        if (head == null){
            return null;
        }
        ListNode pre = null;
        while (head.next != null){
            ListNode node = head;
            head = head.next;
            node.next = pre;
            pre = node;

        }
        head.next = pre;
        return head;
    }

6.  Enter two ascending ordered linked lists , Merge these two linked lists and make the nodes in the new linked list still be sorted incrementally

analysis ：

Define a header node , Then traverse the two linked lists respectively and compare val Size , Keep inserting new nodes behind the head node , Finally, we need to return the header node next.

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode cur = head;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = l1 !=null? l1 : l2;
        return head.next;

    }

7.  Input two binary trees A and B, Judge B Is it right? A Substructure of .( A convention empty tree is not a substructure of any tree )

analysis ：

Using recursive methods . If at present A Of val be equal to B Of val Then compare their subtrees , When B by null It means B All middle nodes are compared , return true. If at present A Of val It's not equal to B Of val, I'm going to A The nodes in the left and right subtrees of are related to B Of root Compare .

    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null){
            return false;
        }
        return recur(A,B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }

    public boolean recur(TreeNode A, TreeNode B){
        if (B == null) return true;
        if (A == null || A.val != B.val) return false;
        return recur(A.left, B.left) && recur(A.right, B.right);
    }