LeetCode 刷题 第七天

1.特殊最长序列 II

给定字符串列表 strs ，返回其中 最长的特殊序列 。如果最长特殊序列不存在，返回 -1 。

特殊序列 定义如下：该序列为某字符串 独有的子序列（即不能是其他字符串的子序列）。 

s 的 子序列可以通过删去字符串 s 中的某些字符实现。 

 示例 1： 


输入: strs = ["aba","cdc","eae"]
输出: 3


 示例 2: 


输入: strs = ["aaa","aaa","aa"]
输出: -1

分析：

双层遍历。

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. 从上到下打印二叉树

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

分析：

层次遍历，借助队列实现。

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. 从上至下打印二叉树 II

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

例如:
给定二叉树: [3,9,20,null,null,15,7],

返回其层次遍历结果：

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

分析：

与上一题一样，只是多了一个要记录当前层数。

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. 从上至下打印二叉树 III

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

例如:
给定二叉树: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回其层次遍历结果：

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

分析：

与前一天类似，只不过是在偶数层是正序的层次遍历，在奇数层是倒序的层次遍历，这时需要借助双端队列来实现。

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); // 偶数层 -> 队列头部
                else tmp.addFirst(node.val); // 奇数层 -> 队列尾部
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            res.add(tmp);
        }
        return res;
    }
}

5. 二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

分析：

采用递归分治的思想。

递推工作：

1. 划分左右子树： 遍历后序遍历的 [i, j]区间元素，寻找 第一个大于根节点的节点，索引记为 m。此时，可划分出左子树区间 [i,m-1]、右子树区间 [m, j - 1]、根节点索引 j 。
2. 判断是否为二叉搜索树：
   1. 左子树区间 [i, m - 1]内的所有节点都应 << postorder[j] 。而第 1.划分左右子树步骤已经保证左子树区间的正确性，因此只需要判断右子树区间即可。
   2. 右子树区间 [m, j-1]内的所有节点都应 >> postorder[j]。实现方式为遍历，当遇到 postorder[j]≤postorder[j] 的节点则跳出；则可通过 p = j判断是否为二叉搜索树。

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);
    }
}