Niuke topic - parity rearrangement of linked list, right view of output binary tree, bracket generation, first non repeating character in character stream

---

subject 1—— Parity rearrangement of linked list

Given a single chain table , Please set a function , Put the odd and even nodes of the linked list together , Output after rearrangement .
requirement ： Time complexity O(n), Spatial complexity O(n).

Example
Input ：{1,2,3,4,5,6}
Output ：{1,3,5,2,4,6}

Their thinking

You can use double pointers , A pointer is used to link odd nodes , A pointer is used to link even nodes . The specific methods are as follows ：

• First, deal with the case that the linked list is empty , Linked list is empty. , Then the header node is returned directly ;
• Use double pointer odd and even Traverse odd nodes and even nodes respectively , At the beginning of the ,odd Point to the first node ,even Point to the second node ;
• Traverse two nodes at a time , The cycle condition is even The pointer is not null and even.next Don't empty , Ergodic time , The next node of the odd pointer points to the next node of the even number , The next node of the even pointer points to the next node of the odd node ;
• Connect the even node after the last odd node , Then return to the head .

Code implementation

import java.util.*;
/* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */
public class Solution {
    
    public ListNode oddEvenList (ListNode head) {
    
        if(head == null)
            return head;
        ListNode even = head.next;
        ListNode evenHead = even;
        ListNode odd = head;
        while(even != null && even.next != null){
    
            // Odd digits connect the last of even digits 
            odd.next = even.next;
            // The odd pointer moves back to point to the next 
            odd = odd.next;
            // Even bits connect the next of odd numbers 
            even.next = odd.next;
            // The even bit pointer moves back to point to the next 
            even = even.next;
        }
        odd.next = evenHead;
        return head;
    }
}

subject 2—— Output the right view of the binary tree

Please traverse according to the preamble of the binary tree , Middle order traversal recovery binary tree , And print out the right view of the binary tree .
requirement ： Spatial complexity O(n), Time complexity O(n).

Example
Input ：[1,2,4,5,3], [4,2,5,1,3]
Output ：[1,3,5]

Their thinking

First, check the size of the two traversal sequences , If it is 0, Then the empty tree will not be printed . Using recursive algorithm to construct binary tree , Then the constructed tree is traversed by depth first search , During traversal ( First, traverse the root node , Then put its left node and right node on the stack respectively , According to the stack first in then out principle , Every time, the rightmost node is accessed first ), We can use the stack to save the access node and depth , And add the rightmost node value of each layer to the hash table according to the depth .
The time complexity is O(n^2), The space complexity is O(n).

In the above method, we must find the root node of the middle order traversal every time , To solve this problem , We can use the hash table to directly map the middle order elements and subscripts , You can visit directly later .
When building a tree recursively , To ensure correct access to array subscripts , We will introduce the sequence of each recursive access , The subscripts of the post order and its left and right nodes are taken as parameters .
At the same time, you can also use hierarchy traversal to find the rightmost node of each layer , The method of traversing the tree hierarchically is as follows ： Build queue , Join the root node into the team , Use one size Variable , Record the current queue size every time you enter the first layer , wait until size by 0 When , It's the rightmost node , Record the elements of this node .
The time complexity is O(n), The space complexity is O(n).

Code implementation

import java.util.*;
public class Solution {
    
    // Construct a binary tree 
    public TreeNode buildTree(int[] xianxu,int[] zhongxu){
    
        if(xianxu.length == 0 || zhongxu.length == 0)
            return null;
        TreeNode root = new TreeNode(xianxu[0]);
        for(int i=0;i<zhongxu.length;i++){
    
            if(zhongxu[i] == xianxu[0]){
    
                root.left = buildTree(Arrays.copyOfRange(xianxu,1,i+1),Arrays.copyOfRange(zhongxu,0,i));
                root.right = buildTree(Arrays.copyOfRange(xianxu,i+1,xianxu.length),Arrays.copyOfRange(zhongxu,i+1,zhongxu.length));
            }
        }
        return root;
    }
    public ArrayList<Integer> rightSlideView(TreeNode root){
    
        Map<Integer,Integer> mp = new HashMap<Integer,Integer>();
        int max_depth = -1;
        // Maintain deep access nodes 
        Stack<TreeNode> nodes = new Stack<TreeNode>();
        // Maintain the depth of depth traversal 
        Stack<Integer> depths = new Stack<Integer>();
        nodes.push(root);
        depths.push(0);
        // Start traversing 
        while(!nodes.isEmpty()){
    
            TreeNode node = nodes.pop();
            int depth = depths.pop();
            if(node != null){
    
                max_depth = Math.max(max_depth,depth);
                if(mp.get(depth) == null)
                    mp.put(depth,node.val); // The value of the rightmost node is added to the hash table 
                nodes.push(node.left);
                nodes.push(node.right);
                depths.push(depth+1);
                depths.push(depth+1);
            }
        }
        ArrayList<Integer> res = new ArrayList<Integer>();
        for(int i=0;i<=max_depth;i++){
    
            res.add(mp.get(i));
        }
        return res;
    }
    public int[] solve (int[] xianxu, int[] zhongxu) {
    
        if(xianxu.length == 0)
            return new int[0];
        TreeNode root = buildTree(xianxu,zhongxu);
        ArrayList<Integer> temp = rightSlideView(root);
        int[] res = new int[temp.size()];
        for(int i=0;i<temp.size();i++){
    
            res[i] = temp.get(i);
        }
        return res;
    }
}

import java.util.*;
public class Solution {
    
    public Map<Integer, Integer> index;
    //l1,r1 They are the subscripts of the leftmost node of the preamble , The subscript of the rightmost node of the preamble 
    //l2,r2 They are the subscripts of the leftmost node in the middle order , Coordinates of the rightmost node in the middle order 
    public TreeNode buildTree(int[] xianxu, int l1, int r1, int[] zhongxu, int l2, int r2){
    
        if(l1 > r1 || l2 > r2)
            return null;
        // The first node in preorder traversal is the root node 
        int xianxu_root = l1;
        // Locate the root node in the middle order traversal 
        int zhongxu_root = index.get(xianxu[xianxu_root]);
        TreeNode root = new TreeNode(xianxu[xianxu_root]);
        // Get the number of nodes in the left subtree 
        int leftsize = zhongxu_root - l2;
        root.left = buildTree(xianxu, l1 + 1, l1 + leftsize, zhongxu, l2, zhongxu_root - 1);
        root.right = buildTree(xianxu, l1 + leftsize + 1, r1, zhongxu, zhongxu_root + 1, r2);
        return root;
    }
    // Level traversal 
    public ArrayList<Integer> rightSideView(TreeNode root) {
    
        ArrayList<Integer> res = new ArrayList<Integer>();
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.offer(root);
        while(!q.isEmpty()){
    
            // The size in the queue is the node tree of this layer 
            int size = q.size(); 
            while(size-- != 0){
    
                TreeNode temp = q.poll();             
                if(temp.left != null) 
                    q.offer(temp.left);
                if(temp.right != null) 
                    q.offer(temp.right);
                // Rightmost element 
                if(size == 0) 
                    res.add(temp.val);
            }
        }
        return res;
    }
    
    public int[] solve (int[] xianxu, int[] zhongxu) {
    
        index = new HashMap<Integer, Integer>();
        // Blank nodes 
        if(xianxu.length == 0) 
            return new int[0];
        // Mark the position of the middle order node in the front order with a hash table 
        for(int i = 0; i < xianxu.length; i++) 
            index.put(zhongxu[i], i);
        // Build up trees 
        TreeNode root = buildTree(xianxu, 0, xianxu.length - 1, zhongxu, 0, zhongxu.length - 1);
        // Get right view output 
        ArrayList<Integer> temp = rightSideView(root);
        // Convert to array 
        int[] res = new int[temp.size()]; 
        for(int i = 0; i < temp.size(); i++)
            res[i] = temp.get(i);
        return res;
    }
}

subject 3—— Bracket generation

give n Parenthesis , Please write a function to generate all the data generated by n A legal combination of parentheses .
for example , Given n=3, The solution set is ：
“((()))”, “(()())”, “(())()”, “()()()”, “()(())”
requirement ： Spatial complexity O(n), Time complexity O(2^n).

Their thinking

One is the violent solution , Generate all possible sequences of parentheses , Then judge whether it is legal , But the time complexity is high .
In order to reduce the time complexity , We can reduce the number of parentheses in enumeration , If you want to generate a legal string , In the process of enumerating string sequences , There are only two choices , Or add the left parenthesis , Or add the right parenthesis , The premise of adding left parentheses is that the number of left parentheses is less than n, The premise of adding right parentheses is that the number of right parentheses is less than the number of left parentheses , Until the length of the string equals 2n, Then save the legal string .

Code implementation

import java.util.*;
public class Solution {
    
    public void backtrack(String str,int open,int close,int n,List<String> result){
    
        if(str.length() == n<<1){
    
            result.add(str);
            return;
        }
        if(open<n){
    
            backtrack(str+"(",open+1,close,n,result);
        }
        if(close<open){
    
            backtrack(str+")",open,close+1,n,result);
        }
    }
    public ArrayList<String> generateParenthesis (int n) {
    
        ArrayList<String> result = new ArrayList<>();
        backtrack("",0,0,n,result);
        return result;
    }
}

subject 4—— The first character in a character stream that does not repeat

Please implement a function to find the first character in the character stream that only appears once , For example, when only the first two characters are read from the character stream "go" when , The first character that appears only once is "g", Before reading from the character stream 6 Characters "google" when , The first character that appears only once is "l".
If there is no character in the current character stream that appears once , return # character .
requirement ： Spatial complexity O(n), Time complexity O(n).

Example
Input ：“google”
Output ：“ggg#ll”

Their thinking

Use a hash table to record the number of occurrences of characters , Then traverse the array of characters , The number of occurrences found in the hash table is 1 First character of .
You can also replace the string array with a queue , Constantly check the team leader elements , The number of occurrences found is 1 The first element of the team .

import java.util.*;
public class Solution {
    
    public ArrayList<Character> arr = new ArrayList<Character>();
    public HashMap<Character,Integer> map = new HashMap<Character,Integer>();
    //Insert one char from stringstream
    public void Insert(char ch)
    {
    
        arr.add(ch);// Insert characters 
        if(!map.containsKey(ch)){
    
            map.put(ch,1);
        }else{
    
            map.put(ch,map.get(ch)+1);
        }
    }
  //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
    
        for(int i=0;i<arr.size();i++){
    
            if(map.get(arr.get(i)) == 1)
                return arr.get(i);
        }
        return '#';
    }
}