Day 7 of leetcode question brushing

1. Special longest sequence II

 Given string list  strs , Return to it   The longest special sequence  . If the longest special sequence does not exist , return  -1 .

 Special sequence   The definition is as follows ： The sequence is a string   Unique subsequence （ That is, it cannot be a subsequence of another string ）. 

s  Of   Subsequences can be made by deleting strings  s  Implementation of some characters in . 

  Example  1： 


 Input : strs = ["aba","cdc","eae"]
 Output : 3


  Example  2: 


 Input : strs = ["aaa","aaa","aa"]
 Output : -1

analysis ：

Double traversal .

class Solution {
    public int findLUSlength(String[] strs) {
        int res = -1;
        boolean flag;
        for (int i = 0; i < strs.length; i++) {
            flag = false;
            for (int j = 0; j < strs.length; j++) {
                if (i == j) continue;
                if ((isSub(strs[i], strs[j]))){
                    flag = true;
                }
            }
            if (!flag){
                if (res < strs[i].length()){
                    res = strs[i].length();
                }
            }

        }
        return res;

    }

    public boolean isSub(String a, String b){
        int i=0, j=0;
        while (i < a.length() && j < b.length()){
            if (b.charAt(j) != a.charAt(i)){
                ++j;
            }else {
                ++i;
                ++j;
            }
        }
        return i>=a.length();
    }
}

2. Print binary tree from top to bottom

Print out each node of the binary tree from top to bottom , Nodes of the same layer are printed from left to right .

analysis ：

Level traversal , Implementation with queues .

class Solution {
    public int[] levelOrder(TreeNode root) {
        if(root == null) return new int[0];
        Queue<TreeNode> queue = new LinkedList<>(){
   { add(root); }};
        ArrayList<Integer> ans = new ArrayList<>();
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            ans.add(node.val);
            if(node.left != null) queue.add(node.left);
            if(node.right != null) queue.add(node.right);
        }
        int[] res = new int[ans.size()];
        for(int i = 0; i < ans.size(); i++)
            res[i] = ans.get(i);
        return res;
    }
}

3. Print a binary tree from top to bottom II

Print binary tree from top to bottom , Nodes of the same layer are printed from left to right , Print each layer to a line .

for example :
Given binary tree : [3,9,20,null,null,15,7],

Return its hierarchical traversal result ：

[
  [3],
  [9,20],
  [15,7]
]

analysis ：

Same as the previous question , Just one more layer to record the current number .

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null){
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            List<Integer> list = new ArrayList<>();
            for (int i = queue.size();i>0;i--) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left!=null) queue.add(node.left);
                if (node.right!=null) queue.add(node.right);
            }
            res.add(list);
        }
        return res;

    }
}

4.  Print a binary tree from top to bottom III

Please implement a function to print binary trees in zigzag order , The first line is printed from left to right , The second layer prints from right to left , The third line is printed from left to right , Other lines and so on .

for example :
Given binary tree : [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

Return its hierarchical traversal result ：

[
  [3],
  [20,9],
  [15,7]
]

analysis ：

Similar to the previous day , It's just traversal at the even level that is positive order , The odd layer is traversed in reverse order , At this time, we need to use double ended queue to realize .

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if(root != null) queue.add(root);
        while(!queue.isEmpty()) {
            LinkedList<Integer> tmp = new LinkedList<>();
            for(int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                if(res.size() % 2 == 0) tmp.addLast(node.val); //  Even layers  ->  Queue header 
                else tmp.addFirst(node.val); //  Odd number layer  ->  Queue tail 
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            res.add(tmp);
        }
        return res;
    }
}

5. The post order traversal sequence of binary search tree

Enter an array of integers , Determine whether the array is the result of the subsequent traversal of a binary search tree . If so, return  true, Otherwise return to  false. Suppose that any two numbers of the input array are different from each other .

analysis ：

Adopt the idea of recursive divide and conquer .

Recursive work ：

1. Divide the left and right subtrees ： Ergodic sequence ergodic [i, j] Interval elements , seek The first node larger than the root node , The index is marked as m. here , The left subtree interval can be divided [i,m-1]、 Right subtree interval [m, j - 1]、 Root node index j .
2. Determine whether it is a binary search tree ：
   1. Left subtree interval [i, m - 1] All nodes in the should << postorder[j] . And the first 1. The steps of dividing the left and right subtrees have ensured the correctness of the left subtree interval , Therefore, we only need to judge the interval of the right subtree .
   2. Right subtree interval [m, j-1] All nodes in the should >> postorder[j]. The implementation method is traversal , When you meet postorder[j]≤postorder[j] The node will jump out ; You can go through p = j Determine whether it is a binary search tree .

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return recur(postorder, 0, postorder.length - 1);
    }
    boolean recur(int[] postorder, int i, int j) {
        if(i >= j) return true;
        int p = i;
        while(postorder[p] < postorder[j]) p++;
        int m = p;
        while(postorder[p] > postorder[j]) p++;
        return p == j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1);
    }
}