LeetCode 第二十九天

1. 完全二叉树插入器

完全二叉树 是每一层（除最后一层外）都是完全填充（即，节点数达到最大）的，并且所有的节点都尽可能地集中在左侧。

设计一种算法，将一个新节点插入到一个完整的二叉树中，并在插入后保持其完整。

实现 CBTInserter 类:

• CBTInserter(TreeNode root) 使用头节点为 root 的给定树初始化该数据结构；
• CBTInserter.insert(int v) 向树中插入一个值为 Node.val == val的新节点TreeNode。使树保持完全二叉树的状态，并返回插入节点 TreeNode 的父节点的值；
• CBTInserter.get_root() 将返回树的头节点。

分析：

使用一个List才存储树的节点。当调用CBTInserter(TreeNode root)时，按照层序遍历的顺序把各个节点add到List中；调用CBTInserter.insert(int v) 时遍历List，找到插入节点的位置：如果当前节点root的左子树为空则root.left = node，如果右子树为空则root.right = node；调用CBTInserter.get_root()直接返回List(0)。

class CBTInserter {
    
    List<TreeNode> list = new ArrayList<>();
    int idx = 0;

    public CBTInserter(TreeNode root) {
    
        list.add(root);
        int cur = 0;
        while (cur < list.size()){
    
            TreeNode node = list.get(cur);
            if (node.left != null) list.add(node.left);
            if (node.right != null) list.add(node.right);
            cur++;
        }
    }

    public int insert(int val) {
    
        TreeNode node = new TreeNode(val);
        while (list.get(idx).left != null && list.get(idx).right != null) idx++;
        TreeNode n = list.get(idx);
        if (n.left == null) n.left = node;
        else if (n.right == null) n.right = node;
        list.add(node);
        return n.val;

    }

    public TreeNode get_root() {
    
        return list.get(0);

    }
}

2. 分数加减运算

给定一个表示分数加减运算的字符串 expression ，你需要返回一个字符串形式的计算结果。

这个结果应该是不可约分的分数，即最简分数。 如果最终结果是一个整数，例如 2，你需要将它转换成分数形式，其分母为 1。所以在上述例子中, 2 应该被转换为 2/1。

分析：

模拟整个的计算过程。记录分子和分母并不断地更新他们直到最后。初始化分子fz=0， 分母fm=1; 定义一个sign来记录正负号，遍历得到fz1和fm1，更新fz，fm：signfz=fzfm1+fmfz1 fm=fmfm1，得到新的fz和fm之后计算它们的最大公约数g对分数进行约分：fz=fz/g，fm=fm/g。

class Solution {
    
    public String fractionAddition(String expression) {
    
        long fz = 0, fm = 1;
        int i = 0;
        while (i < expression.length()) {
    
            int sign = 1;
            long fz1 = 0;
            if (expression.charAt(i) == '-' || expression.charAt(i) == '+'){
    
                sign = expression.charAt(i) == '-' ? -1 : 1;
                i++;
            }
            while (i < expression.length() && Character.isDigit(expression.charAt(i))) {
    
                fz1 = fz1 * 10 + expression.charAt(i) - '0';
                i++;
            }
            fz1 = sign * fz1;
            i++;
            long fm1 = 0;
            while (i < expression.length() && Character.isDigit(expression.charAt(i))) {
    
                fm1 = fm1 * 10 + expression.charAt(i) - '0';
                i++;
            }
            fz = fz * fm1 + fm * fz1;
            fm *= fm1;
        }
        if (fz == 0){
    
            return "0/1";
        }
        long g = gcd(Math.abs(fz), fm);
        return Long.toString(fz/g) + "/" + Long.toString(fm/g);


        }


    public long gcd(long a, long b) {
    
        long remainder = a % b;
        while (remainder != 0) {
    
            a = b;
            b = remainder;
            remainder = a % b;
        }
        return b;
    }

}

3. 字符串中的变位词

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。换句话说，第一个字符串的排列之一是第二个字符串的子串 。

分析：

使用滑动窗口。设s1的长度为n，s2的长度为m，只有m>=n，题目才有意义。因为是要判断s2中是否有s1的排列之一，那么长度一定是n，故滑动窗口的大小设置为n。定义两个数组count1，count2来记录s1中字母出现的次数和s2中当前滑动窗口内字母出现的次数，当count1与count2相等时返回true。

class Solution {
    
    public boolean checkInclusion(String s1, String s2) {
    
        int n = s1.length(), m = s2.length();
        if (n > m) return false;
        int[] count1 = new int[26];
        int[] count2 = new int[26];
        for (int i = 0; i < n; i++) {
    
            count1[s1.charAt(i) - 'a']++;
            count2[s2.charAt(i) - 'a']++;
        }
        if (Arrays.equals(count1, count2)) return true;
        for (int i = n; i < m; i++) {
    
            count2[s2.charAt(i) - 'a']++;
            count2[s2.charAt(i-n) - 'a']--;
            if (Arrays.equals(count1, count2)){
    
                return true;
            }
        }
        return false;
    }
}