Practice 280

¹

LeetCode 56. Merge Intervals

input: list of intervals
output: list of intervals after merging all overlapping intervals including equals.

时间复杂度 O(nlogn), 空间 O(1).

1. 按 start 大小排序 O(nlogn)
2. 排序之后 2 种情况需要 merge,
   1. 后面元素的 start 小于或等于前面元素的 end.
      • 所以需要一个 prev 记录一下前一个元素的 end 是什么(包括已经 merge 了的元素).
   2. 后面元素的 start 要大于前一个元素的 end.
      • 更新 prev, 存入这个 candidate, 继续 merge.

public class MergeIntervals {
    class Interval {
        int start, end;

        Interval(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

    /**
     * @param intervals: interval list.
     * @return: A new interval list.
     */
    public List<Interval> merge(List<Interval> intervals) {
        if (intervals == null || intervals.size() == 0) {
            return new ArrayList<>();
        }

        Collections.sort(intervals, new Comparator<Interval>() {
            @Override
            public int compare(Interval o1, Interval o2) {
                return o1.start < o2.start ? -1 : o1.start == o2.start ? 0 : 1;
            }
        });

        Interval prev = null;
        List<Interval> res = new ArrayList<>();
        for (Interval in : intervals) {
            if (prev == null || in.start > prev.end) {
                prev = in;
                res.add(prev);
                continue;
            }
            prev.end = Math.max(in.end, prev.end);
        }
        return res;
    }
}

LeetCode 643 Maximum Average Subarray I

input: int array and window size k.
ouput: return the maximum average sum of subarray of size k.

时间复杂度 O(n), 空间复杂度 O(1).
固定窗口问题, 取窗口和的最大值, 然后返回平均值.

public class MaximumAverageSubarrayI {
    public double maxAveSub(int[] input, int k) {
        if (input == null || input.length == 0) {
            return 0;
        }

        double sum = 0;
        for (int i = 0; i < k; i++) {
            sum += input[i];
        }

        double prev = sum;
        int i = 0, j = k;
        while (j < input.length) {
            prev = sum - input[i++] + input[j++];
            sum = Math.max(sum, prev);
        }
        return sum / k;
    }

    private class MaximumAverageSubarrayITest{
        @Test
        void check() {
            assertEquals(12.75, maxAveSub(new int[]{1, 12, -5, -6, 50, 3}, 4));
        }
    }
}

LeetCode 293 FlipGameI

input: a string with “+” or “-“.
output: return list of string with all possible moves.

时间复杂度 O(n), 空间复杂度 O(1).
只有相邻的两个元素才可以翻转, 找出所有可能的路径, 从头开始翻转, 翻转之后存到结果里面, 然后再翻转回来.

public class FlipGameI {
    /**
     * @param s
     * @return
     */
    public List<String> generatePossibleNextMoves(String s) {
        if (s == null || s.length() == 0) {
            return new ArrayList<>();
        }

        char[] set = s.toCharArray();
        List<String> res = new ArrayList<>();
        for (int i = 1; i < s.length(); i++) {
            if (set[i] == '+' && set[i - 1] == '+') {
                set[i] = '-';
                set[i - 1] = '-';
                res.add(new String(set));
                set[i] = '+';
                set[i - 1] = '+';
            }
        }
        return res;
    }
}

LeetCode 415 Add Strings

input: two strings with digits numbers only.
output: return a string of the sum of input strings.

时间复杂度 O(n), 空间复杂度 O(n^2).
使用 String concatenation, 避免了翻转 String, 但是增加了空间复杂度. 因为每一次都生成了一个新的 string.

public class AddStrings {
    /**
     * @param num1: a non-negative integers
     * @param num2: a non-negative integers
     * @return: return sum of num1 and num2
     */
    public String addStrings(String num1, String num2) {
        if (num1 == null || num1.length() == 0) {
            return num2;
        }

        if (num2 == null || num2.length() == 0) {
            return num1;
        }

        int flag = 0;
        String res = "";        //// string 可以直接加, 所以就免去了 reverse.
        int i = num1.length() - 1, j = num2.length() - 1;
        while (i >= 0 || j >= 0) {
            int a = 0, b = 0;
            if (i >= 0) {
                a = num1.charAt(i--) - '0';
            }
            if (j >= 0) {
                b = num2.charAt(j--) - '0';
            }

            int sum = a + b + flag;
            flag = sum / 10;
            sum %= 10;
            res = sum + res; ///////////3 + "23" 从后往前加
        }

        return flag == 1 ? flag + res : res;
    }
}

LeetCode 346 Moving Average from Data Stream

Implement a method that calculates avarage certain numbers from a data stream.

使用一个 queue 来存放需要计算的元素, 因为 queue 的容量是固定的, 如果超出规定数量, 则先进来的元素要被删除.

public class MovingAverageFromDataStream {
        /*
         * @param size: An integer
         */
        private Queue<Integer> q = new LinkedList<>();
        private final int size
        private double sum;

        public MovingAverageFromDataStream(int size) {
            this.size = size;
        }

        /*
         * @param val: An integer
         * @return:
         */
        public double next(int val) {
            sum += val;
            q.offer(val);
            if (q.size() > size) {
                sum -= q.poll();
            }
            return sum / q.size();
        }
    }

    class MovingAverageFromDataStreamTest{
        private MovingAverageFromDataStream m = new MovingAverageFromDataStream(3);
        @Test
        void check() {
            assertEquals(1.00000, m.next(1));
            assertEquals(5.50000, m.next(10));
            assertEquals(6.00000, m.next(1));
            assertEquals(6.00000, m.next(1));
        }
    }

LeetCode 66 Plus One

input: int array represents one negative integer.
output: plus one to the integer.

时间复杂度 O(n), 空间复杂度 O(1).
从后往前加, 如果最后需要进位, 则新建一个长度加 1 的 array. 和 Add Strings 几乎一样.

public class PlusOne {
    /**
     * @param digits: a number represented as an array of digits
     * @return: the result
     */
    public int[] plusOne(int[] digits) {
        if (digits == null || digits.length == 0) {
            return new int[0];
        }

        int i = digits.length - 1;
        int flag = 1;
        while (i >= 0) {
            int sum = digits[i] + flag;
            flag = sum / 10;
            digits[i--] = sum % 10;
        }

        if (flag == 1) {
            int[] res = new int[digits.length + 1];
            res[0] = 1;
            for (int j = 1; j < res.length; j++) {
                res[j] = digits[j - 1];
            }
            return res;
        }
        return digits;
    }
}

LeetCode 356 Line Reflection

input: 2D array represents points on a coordinate plane.
output: Whether the points has a reflectional line that parallel to y-axis.

所有的点都存在一条与 y 轴平行的线, 那么只需要考虑 x 轴上面的值就可以了, 直观想到就是先用 HashMap<y 值, Set<x 值>> 这样一个数据结构把每一组 x 存起来. 因为所有元素都与这一条 y 轴平行, 那么只需要确定 x 轴上面的左右边界, 然后遍历 x 上面的点, 看是否存在其对称轴的值.

时间复杂度 O(n). 第一次遍历, 存 map, 第二次遍历, 看 x 值, 总的时间复杂度应该是所有元素的 2 倍, 也就是 2 _ 2 _ n, 所以是 O(n). 空间复杂度也是 O(n), n 是 array 里面所含元素的数量.

public class LineReflection {
    /**
     * @param points: n points on a 2D plane
     * @return: if there is such a line parallel to y-axis that reflect the given points
     */
    public boolean isReflex(int[][] points) {
        //y-axiel 对称也就是说 y 值相等
        if (points == null || points.length == 0 || points[0] == null || points[0].length == 0) {
            return true;
        }

        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        Map<Integer, Set<Integer>> pair = new HashMap<>();
        for (int[] n : points) {
            Set<Integer> xAxs = pair.get(n[1]);
            if (xAxs == null) {
                xAxs = new HashSet<>();
            }
            max = Math.max(max, n[0]);
            min = Math.max(min, n[0]);
            xAxs.add(n[0]);
            pair.put(n[1], xAxs);
        }


        for (int[] n : points) {
            int y = n[1];
            int x = n[0];
            if (!pair.get(y).contains(max + min - x)) {
                return false;
            }
        }
        return true;
    }

}

LeetCode 270 Closest Binary Search Tree Value

input: A root node of a binary search tree, and a target number which is type of double.
output: return the closest value of the tree to the target.

既然是 binary search tree 还是可以用二分的思想, 如果 root 的值小于 target, 那么就往右看, 否则往左看. 可以使用 2 种方法, binary search 和 inorder traverse. Inorder traverse 的方法时间复杂度是 O(n)的, 空间是 O(h) 的. 所以 binary search 要好一些.

1. Iteration. 时间复杂度 O(h), 空间 O(1). 遍历过程中如果有需要, update 结果.

public class ClosestBSTValue {
    /**
     * @param root: the given BST
     * @param target: the given target
     * @return: the value in the BST that is closest to the target
     */
    public int closestValue(TreeNode root, double target) {
        if (root == null) {
            return Integer.MAX_VALUE;
        }
        int res = root.val;
        while (root != null) {
            if (Math.abs(root.val - target) < Math.abs(res - target)) {
                res = root.val;
            }
            if (root.val == target) {
                return root.val;
            }
            if (root.val < target) {
                root = root.right;
            } else {
                root = root.left;
            }
        }
        return res;
    }
}

2. Recursion. 找到左子树的左右节点, 以及右子树的最左节点. 也就是找到比 target 小的最大值, 以及比 target 大的最小值. 然后比较哪一个更接近.
   binary search 时间复杂度 O(h), 空间复杂度 O(h), 递归调用 call stack.

public class ClosestBSTValue {
    public int closestValue(TreeNode root, double target) {
        if (root == null) {
            return Integer.MAX_VALUE;
        }

        TreeNode left = findLower(root, target);
        TreeNode right = findUpper(root, target);

        if (left == null) {
            return right.val;
        }

        if (right == null) {
            return left.val;
        }

        return target - left.val < target - right.val ? left.val : right.val;
    }

    private TreeNode findLower(TreeNode root, double target) {
        if (root == null) {
            return root;
        }

        if (root.val > target) {
            return findLower(root.left, target);
        }
        TreeNode right = findLower(root.right, target);
        return right == null ? root : right;
    }

    private TreeNode findUpper(TreeNode root, double target) {
        if (root == null) {
            return root;
        }

        if (root.val <= target) {
            return findUpper(root.right, target);
        }
        TreeNode left = findUpper(root.left, target);
        return left == null ? root : left;
    }
}

LeetCode 293 Flip GameI

input: a string consist of ‘+’ and ‘-‘.
output: return all valid states after one valid move.

只有 “++” 才可以被翻转为 “–”, 那么只需要考虑 “++” 的状态就好了. 从做到有扫一遍, 每次只做一次翻转, 把 state 存起来, 然后恢复之前的状态, 继续右移指针, 知道 string 结尾.
时间复杂度 O(n), 空间 O(n). 对于 java 来说需要把 string 转换成 char[], 否则无法进行 inplace 的更改操作, 所以需要使用额外的数据结构以及空间来存放 input.

public class FlipGameI {
    /**
     * @param s
     * @return
     */
    public List<String> generatePossibleNextMoves(String s) {
        if (s == null || s.length() == 0) {
            return new ArrayList<>();
        }

        char[] set = s.toCharArray();
        List<String> res = new ArrayList<>();
        for (int i = 1; i < s.length(); i++) {
            if (set[i] == '+' && set[i - 1] == '+') {
                set[i] = '-';
                set[i - 1] = '-';
                res.add(new String(set));
                set[i] = '+';
                set[i - 1] = '+';
            }
        }
        return res;
    }
}

—

---

1. 1.图片引用自网络，如有侵权请联系删除. ↩