Count of Smaller Number before itself [TODO]

Segment Tree Query II [TODO]

这个写法好像是错的！
第一遍写的时候一直报null pointer exception
问题是这个query的区间有可能是超越tree的区间的
只要还有Overlap就合法
但是不能保证正好满足边界
所以对于base case来说只要 root.start == root.end 就应该返回
/**
 * Definition of SegmentTreeNode:
 * public class SegmentTreeNode {
 *     public int start, end, count;
 *     public SegmentTreeNode left, right;
 *     public SegmentTreeNode(int start, int end, int count) {
 *         this.start = start;
 *         this.end = end;
 *         this.count = count;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     *@param root, start, end: The root of segment tree and
     *                         an segment / interval
     *@return: The count number in the interval [start, end]
     */
    public int query(SegmentTreeNode root, int start, int end) {
        // write your code here
        if (root == null || start > end || start > root.end || end < root.start) return 0;
        if (start == root.start && end == root.end || root.start == root.end) return root.count;
        int mid = (root.start + root.end) / 2;
        if (end <= mid) return query(root.left, start, end);
        else if (start > mid) return query(root.right, start, end);
        else {
            return query(root.left, start, mid) + query(root.right, mid + 1, end);
        }
    }
}

114. Flatten Binary Tree to Linked List

五刷 07/2022

Version #1 Recursive

这次写的比较简洁

一个bug就是node.left要设为null

Time O(N)

Space O(N) worst case

Runtime: 1 ms, faster than 78.58% of Java online submissions for Flatten Binary Tree to Linked List.

Memory Usage: 42.3 MB, less than 71.23% of Java online submissions for Flatten Binary Tree to Linked List.

class Solution {

    public void flatten(TreeNode root) {

        flattenHelper(root);

    }

    

    // Returns the last node after flatten

    private TreeNode flattenHelper(TreeNode node) {

        if (node == null) {

            return null;

        }

        if (node.left == null && node.right == null) {

            return node;

        }

        TreeNode left = flattenHelper(node.left);

        TreeNode right = flattenHelper(node.right);

        if (left != null) {

            left.right = node.right;

            node.right = node.left;

            node.left = null;

        }

        return right == null ? left : right;

    }

}

四刷 05/2022

Version #1 Recursive

这里代码有冗余的

因为如果leftLast是Null 的话，当前node.right已经是右子树的root了不需要再更改了，所以只需要返回node.right == null ? node : rightLast

只有当左子树不为空的时候才需要把它插入到node和右子树之间

这次代码写得不好，参考前面写的

Runtime: 0 ms, faster than 100.00% of Java online submissions for Flatten Binary Tree to Linked List.

Memory Usage: 42.7 MB, less than 47.36% of Java online submissions for Flatten Binary Tree to Linked List.

/**

 * Definition for a binary tree node.

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode() {}

 *     TreeNode(int val) { this.val = val; }

 *     TreeNode(int val, TreeNode left, TreeNode right) {

 *         this.val = val;

 *         this.left = left;

 *         this.right = right;

 *     }

 * }

 */

class Solution {

    public void flatten(TreeNode root) {

        helper(root);

    }

    

    // Returns the last node after the subtree is flatterned

    private TreeNode helper(TreeNode node) {

        if (node == null) {

            return null;

        }

        TreeNode prev = node;

        TreeNode last = node;

        TreeNode leftLast = helper(node.left);

        TreeNode rightLast = helper(node.right);

        TreeNode rightRoot = node.right;

        if (leftLast != null) {

            prev.right = node.left;

            last = leftLast;

            prev = leftLast;

        }

        if (rightLast != null) {

            prev.right = rightRoot;

            last = rightLast;

        }

        node.left = null;

        return last;

    }

}

Version #2 Iterative

注意这里是先push right 再push left

Runtime: 2 ms, faster than 13.01% of Java online submissions for Flatten Binary Tree to Linked List.

Memory Usage: 42.6 MB, less than 53.16% of Java online submissions for Flatten Binary Tree to Linked List.

/**

 * Definition for a binary tree node.

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode() {}

 *     TreeNode(int val) { this.val = val; }

 *     TreeNode(int val, TreeNode left, TreeNode right) {

 *         this.val = val;

 *         this.left = left;

 *         this.right = right;

 *     }

 * }

 */

class Solution {

    public void flatten(TreeNode root) {

        if (root == null) {

            return;

        }

        Stack<TreeNode> stack = new Stack<>();

        stack.push(root);

        TreeNode prev = null;

        while (!stack.isEmpty()) {

            TreeNode curr = stack.pop();

            if (prev != null) {

                prev.left = null;

                prev.right = curr;

            }

             if (curr.right != null) {

                stack.push(curr.right);

            }

            if (curr.left != null) {

                stack.push(curr.left);

            }

            prev = curr;

        }

    }

}

三刷

Version #2 Iterative

71.35 %

class Solution {

    public void flatten(TreeNode root) {

        // Inorder traversal while keeping track of prev node

// link to prev when push

Deque<TreeNode> deque = new ArrayDeque<>();

TreeNode curr = root;

        TreeNode prev = null;

        while (curr != null) {

            if (curr.right != null) {

                deque.addFirst(curr.right);

            }

            if (curr.left != null) {

                deque.addFirst(curr.left);

            }

            if (prev != null) {

                prev.right = curr;

                prev.left = null;

            }

            prev = curr;

            curr = deque.isEmpty() ? null : deque.removeFirst();

        }

    }

}

Version #1 Recursive

三刷

没有考虑rightTail是Null 以及 leftTail & rightTail都是null的情况

需要都考虑全

root, left, right三个部分都有可能是Null

 24.56 %

public class Solution {

    public void flatten(TreeNode root) {

        flattenHelper(root);

    }

    //return the tail of the flatten partial of tree

    private TreeNode flattenHelper(TreeNode root) {

        if (root == null) return null;

        if (root.left == null && root.right == null) return root;

        TreeNode leftTail = flattenHelper(root.left);

        TreeNode rightTail = flattenHelper(root.right);

        if (root.left != null) {

            leftTail.right = root.right;

            root.right = root.left;

            root.left = null;

        }

        return rightTail == null ? leftTail : rightTail;

    }

}

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param root: a TreeNode, the root of the binary tree
     * @return: nothing
     */
    public void flatten(TreeNode root) {
        // write your code here
        helper(root);
    }
 
    //given the root
    //return the last node of the linkedlist
    public TreeNode helper(TreeNode root) {
        if(root == null) {
            return null;
        }
        TreeNode lastLeft = helper(root.left);
        TreeNode lastRight = helper(root.right);
        System.out.println("root.left = " + root.left.val + " lastLeft = " + lastLeft.val);

        if (root.left != null) {
            lastLeft.right = root.right;
            root.right = root.left;
            root.left = null;
        }
        if (root.right != null) {
            return lastRight;
        }
        if (root.left != null) {
            return lastLeft;
        }
        return root;
     
    }
}


二刷

public class Solution {
    /**
     * @param root: a TreeNode, the root of the binary tree
     * @return: nothing
     */
    public void flatten(TreeNode root) {
        // write your code here
        helper(root);
    }
 
    //given the root
    //return the last node of the linkedlist
    public TreeNode helper(TreeNode root) {
        if(root == null) {
            return null;
        }
        TreeNode lastLeft = helper(root.left);
        TreeNode lastRight = helper(root.right);
        //System.out.println("root.left = " + root.left.val + " lastLeft = " + lastLeft.val);

        if (root.left == null) {
            if (root.right != null) return lastRight;
            return root;
        }
        lastLeft.right = root.right;
        root.right = root.left;
        root.left = null;
        if (lastRight != null) return lastRight;
        return lastLeft;
    }
}

Segment Tree Build II

build之后不要忘记把当前Node和它的左右child连起来
/**
 * Definition of SegmentTreeNode:
 * public class SegmentTreeNode {
 *     public int start, end, max;
 *     public SegmentTreeNode left, right;
 *     public SegmentTreeNode(int start, int end, int max) {
 *         this.start = start;
 *         this.end = end;
 *         this.max = max
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     *@param A: a list of integer
     *@return: The root of Segment Tree
     */
    public SegmentTreeNode build(int[] A) {
        // write your code here
        return build(A, 0, A.length - 1);
    }
    private SegmentTreeNode build(int[] A, int start, int end) {
        if (start > end) return null;
        if (start == end) return new SegmentTreeNode(start, end, A[start]);
        int mid = (start + end) / 2;
        SegmentTreeNode left = build(A, start, mid);
        SegmentTreeNode right = build(A, mid + 1, end);
        SegmentTreeNode res = new SegmentTreeNode(start, end, Math.max(left.max, right.max));
        res.left = left;
        res.right = right;
        return res;
    }
}

Segment Tree Modify

/**
 * Definition of SegmentTreeNode:
 * public class SegmentTreeNode {
 *     public int start, end, max;
 *     public SegmentTreeNode left, right;
 *     public SegmentTreeNode(int start, int end, int max) {
 *         this.start = start;
 *         this.end = end;
 *         this.max = max
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     *@param root, index, value: The root of segment tree and
     *@ change the node's value with [index, index] to the new given value
     *@return: void
     */
    public void modify(SegmentTreeNode root, int index, int value) {
        // write your code here
        if (index < root.start || index > root.end) return;
        if (index == root.start && index == root.end) {
            root.max = value;
            return;
        }
        int mid = (root.start + root.end) / 2;
        if (index <= mid) modify(root.left, index, value);
        else modify(root.right, index, value);
       
        root.max = Math.max(root.left.max, root.right.max);
    }
}

Lint 202.Segment Tree Query

二刷
一刷的思路应该是错的
正确的做法是每次不改变传入的start和end
对每次的range分Partial Overlap, Total Overlap和No Overlap三种情况讨论

public class Solution {
    /**
     *@param root, start, end: The root of segment tree and
     *                         an segment / interval
     *@return: The maximum number in the interval [start, end]
     */
    public int query(SegmentTreeNode root, int start, int end) {
        // write your code here
        int left = root.start;
        int right = root.end;
        //1.No Overlap
        if (root == null || start > end || end < left || start > right) return Integer.MIN_VALUE;
        //2.Total Overlap
        if (start <= left && end >= right) return root.max;
        //3.Partial Overlap
        return Math.max(query(root.left, start, end), query(root.right, start, end));
    }
}


一刷

写了一个bug
 int mid = (root.start + root.end) / 2; 此处mid应该是树Node的mid
而不应该是query的mid
Time O(logn)

/**
 * Definition of SegmentTreeNode:
 * public class SegmentTreeNode {
 *     public int start, end, max;
 *     public SegmentTreeNode left, right;
 *     public SegmentTreeNode(int start, int end, int max) {
 *         this.start = start;
 *         this.end = end;
 *         this.max = max
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     *@param root, start, end: The root of segment tree and
     *                         an segment / interval
     *@return: The maximum number in the interval [start, end]
     */
    public int query(SegmentTreeNode root, int start, int end) {
        // write your code here
        if (start > end) throw new IllegalArgumentException();
        if (root.start == start && root.end == end) return root.max;
        int mid = (root.start + root.end) / 2;
        if (end <= mid) return query(root.left, start, end);
        else if (start > mid) return query(root.right, start, end);
        else return Math.max(query(root.left, start, mid), query(root.right, mid + 1, end));
    }
}

388. Longest Absolute File Path

三刷
本质上是dfs，走到leaf的时候update 结果
stack的作用是back track
99.90 %
class Solution {
    public int lengthLongestPath(String input) {
        if (input == null || input.length() == 0) {
            return 0;
        }
        int level = 0;
        int max = 0;
        int currLength = 0;
        Deque<Integer> deque = new ArrayDeque<>();
        String[] dirs = input.split("\n");
        for (String dir : dirs) {
            level = dir.lastIndexOf("\t") + 1;
            while (deque.size() > level) {
                deque.removeFirst();
            }
            currLength = dir.length() + (deque.isEmpty() ? 0 : deque.peekFirst()) - level + 1;
            if (dir.contains(".")) {
                max = Math.max(max, currLength - 1);
            }
            deque.addFirst(currLength);
        }
        return max;
    }
}

 31.56 %
class Solution {
    public int lengthLongestPath(String input) {
        if (input == null) {
            return 0;
        }
        String[] dirs = input.split("\n");
        Deque<Integer> stack = new ArrayDeque<>();
        int max = 0;
        for (String dir : dirs) {
            int level = dir.lastIndexOf("\t") + 1;
            while (stack.size() > level) {
                stack.removeFirst();
            }
            int len = (stack.isEmpty() ? 0 : stack.peekFirst()) + dir.length() - level + 1;
            stack.push(len);
            if (dir.contains(".")) {
                max = Math.max(max, len - 1);
            }
        }
        return max;
    }
}


看到以后完全懵逼，一点做过的印象都没有了
java String.length() treats "\t" as 1 character!

思路是如果是一个最长的path那么一定是一路走到底的，所以可以用一个array一路Update走过的各个level的length
一旦调回到某一个level，它之前的level Length依然有效，然后也会继续向更深的Level进行Update从而把之前的Length覆盖掉

-level是减掉path[i]里面相应个数的"\t"
+1是加 "\"
最后比max的时候"-1"是因为最后少一个"\"

二刷
44.77 %
class Solution {
    public int lengthLongestPath(String input) {
        if (input == null) return 0;
        String[] path = input.trim().split("\n");
        int[] levelLength = new int[path.length + 1];
        int maxLength = 0;
        int level = 0;
        for (int i = 0; i < path.length; i++) {
            // "-1" if not found
            level = path[i].lastIndexOf("\t") + 1;
            levelLength[level] = (level > 0 ? levelLength[level - 1] : 0) + path[i].length() - level + 1;
            if (path[i].contains(".")) maxLength = Math.max(maxLength, levelLength[level] - 1);
        }
        return maxLength;
    }
}


一刷

36.93 %
public class Solution {
    public int lengthLongestPath(String input) {
        if (input == null || input.length() == 0) return 0;
        String[] path = input.split("\n");
        //index -> level, value -> current length
        int[] stack = new int[path.length];
        int level;
        int maxLength = 0;
        for (String str : path) {
         
            level = str.lastIndexOf("\t") + 1;
            //System.out.println("level=" + level);
            //System.out.println("length=" + str.length());
            if (level == 0) {
                stack[level] = str.length();
            } else {
                stack[level] = stack[level - 1] + str.length() - level + 1;
            }
            //System.out.println(stack[level]);
            if (str.contains(".")) maxLength = Math.max(maxLength, stack[level]);
        }
        return maxLength;
    }
}