Massive Algorithms: [LeetCode] Missing Ranges

[LeetCode] Missing Ranges | 程序员达达

[LeetCode] Missing Ranges | 程序员达达
Given a sorted integer array where the range of elements are [0, 99] inclusive, return its missing ranges.
For example, given [0, 1, 3, 50, 75], return ["2", "4->49", "51->74", "76->99"]

https://leetcode.com/discuss/45508/accepted-java-solution-with-explanation
public List<String> findMissingRanges(int[] a, int lo, int hi) { List<String> res = new ArrayList<String>(); // the next number we need to find int next = lo; for (int i = 0; i < a.length; i++) { // not within the range yet if (a[i] < next) continue; // continue to find the next one if (a[i] == next) { next++; continue; } // get the missing range string format res.add(getRange(next, a[i] - 1)); // now we need to find the next number next = a[i] + 1; } // do a final check if (next <= hi) res.add(getRange(next, hi)); return res; } String getRange(int n1, int n2) { return (n1 == n2) ? String.valueOf(n1) : String.format("%d->%d", n1, n2); }
http://segmentfault.com/a/1190000003790309

我们用一个指针prev记录上次range的结尾，一个指针curr记录当前遍历到的数字，如果curr和prev相差大于1，说明一个missing range，我们将其加入结果列表中就行了。这题主要是有几个corner case要解决：

如何处理lower到第一个数，和最后一个数到upper的missing range？
如何区分range中只有一个数和多个数？
如何有效的得到missing range的起始和结束值，同时保证不会包含数组中的数字？

对于第一个问题，我们要做的就是在让for循环多判断两次。想象一下假设数组前有一段连续的负无穷到lower-1，数组后有一段upper+1到正无穷，这样是等价与上下界的。本来如果不考虑头尾，那for循环本应是从1到length-1的，但是为了判断头，我们从0开始，将下标为0的数和lower-1比较得到第一个range。最后循环到length停止，当下标为length时，我们将当前指针指向upper+1，并判断upper+1和数组末尾是否能构成最后一个区间。

对于第二个问题，我们只要判断这个区间的起止是否一样就行了

对于第三个问题，我们用prev+1和curr-1来标记这个区间的起止，因为prev和curr都是数组中的数，所以解决了每个区间的边界问题

    public List<String> findMissingRanges(int[] nums, int lower, int upper) {
        List<String> res = new LinkedList<String>();
        // 初始化prev为lower-1，判断是否存在“第一个”区间
        int prev = lower - 1, curr = 0;
        for(int i = 0 ; i <= nums.length; i++){
            // 当遍历到length时，设置curr为upper+1，判断是否存在“最后一个”区间
            curr = i == nums.length ? upper + 1 : nums[i];
            // 如果上一个数和当前数相差大于1，说明之间有区间
            if(curr - prev > 1){
                res.add(getRanges(prev+1, curr-1));
            }
            prev = curr;
        }
        return res;
    }
    
    private String getRanges(int from, int to){
        return from == to ? String.valueOf(from) : from + "->" + to;
    }

X.
http://buttercola.blogspot.com/2015/08/leetcode-missing-ranges.html
The problem itself is not hard at all. The key is to handle several corner cases. e.g.
-- If the array is empty, the missing ranges should be from lower to upper, inclusive.
-- For the leading missing range, e.g. -2 , [-1], -1. The output should be "-2". Note that the lower bound is inclusive.
-- For the trailing missing range, e.g. -2, [-2], 1, the output should be "-1->1". The upper bound is inclusive as well.

    public List<String> findMissingRanges(int[] nums, int lower, int upper) {

        List<String> result = new ArrayList<String>();

        if (nums == null || nums.length == 0) {

            outputToResult(lower, upper, result);

            return result;

}

        // leading missing range

        if (nums[0] - lower > 0) {

            outputToResult(lower, nums[0] - 1, result);

}

        for (int i = 1; i < nums.length; i++) {

            if (nums[i] - nums[i - 1] > 1) {

                outputToResult(nums[i - 1] + 1, nums[i] - 1, result);

}

}

        // trailing missage ranges

        if (upper - nums[nums.length - 1] > 0) {

            outputToResult(nums[nums.length - 1] + 1, upper, result);

}

        return result;

}

    private void outputToResult(int start, int end, List<String> result) {

        StringBuffer sb = new StringBuffer();

        if (start == end) {

            sb.append(start);

        } else {

            sb.append(start + "->" + end);

}

        result.add(sb.toString());

}

这道题其实不难，但是就是要考虑清楚各种情况。根据题意，[lower, upper]一定是包含这个array所有元素的，不会存在不包含甚至没有交集的情况。只是要特别考虑一下A[0]和lower的关系，以及A[N]与upper的关系，它们所以存在的情况：

1. lower == A[0] && upper == A[N]
2. lower < A[0] && upper == A[N]
3. lower == A[0] && upper > A[N]
4. lower < A[0] && upper > A[N]
整体来说，需要考虑如下所有case：

1. 为空，lower 与 upper 之间关系。
2. lower 与 A[0] 之间关系
3. A[i]~A[i+1] 之间关系
4 A[A.length-1] 与 upper 之间关系
--Extract functions.

   public List<String> findMissingRanges(int[] A, int lower, int upper) { 
        ArrayList<String> res = new ArrayList<String>();
        if (A.length == 0) {
            if (lower != upper) {
                res.add(Integer.toString(lower) + "->" + Integer.toString(upper));
            }
            else {
                res.add(Integer.toString(lower));
            }
            return res;
        }
        if (lower < A[0]) {
            if (lower == A[0] - 1) {
                res.add(Integer.toString(lower));
            }
            else {
                res.add(Integer.toString(lower) + "->" + Integer.toString(A[0]-1));
            }
        }
        for (int i=0; i<A.length-1; i++) {
            if (A[i+1] - A[i] > 2) {
                res.add(Integer.toString(A[i]+1) + "->" + Integer.toString(A[i+1]-1));
            }
            else if (A[i+1] - A[i] == 2) {
                res.add(Integer.toString(A[i]+1));
            }
            else continue;
        }
        if (upper > A[A.length-1]) {
            if (upper == A[A.length-1] + 1) {
                res.add(Integer.toString(upper));
            }
            else {
                res.add(Integer.toString(A[A.length-1]+1) + "->" + Integer.toString(upper));
            }
        }
        return res;
    }

 public List<String> findMissingRanges(int[] vals, int start, int end) {
        List<String> ranges = new ArrayList<String>();
        int prev = start - 1;
        for (int i=0; i<=vals.length; ++i) {
            int curr = (i==vals.length) ? end + 1 : vals[i];
            if ( cur-prev>=2 ) {
                ranges.add(getRange(prev+1, curr-1));
            }
            rev = curr;
        }
        return ranges;
    }
 
    private String getRange(int from, int to) {
        return (from==to) ? String.valueOf(from) : from + "->" to;
    }

http://leetcode0.blogspot.com/2015/03/missing-ranges.html
每看一个数字，表示之前的都处理完了。
最后再处理最后面一个数字。

    public List<String> findMissingRanges(int[] A, int lower, int upper) {

        // assume all elements in A are in range (lower, upper)

        List<String> list = new LinkedList();

        for(int i =0;i<A.length;i++){

            if(lower>upper) // not used

                break;

            if(A[i] == lower){

                lower++;

            }else if(A[i] >lower){

                // add from lower to A[i];

                String tmp  = ""+lower;

                if(lower+1!=A[i])

                    tmp += "->"+ (A[i]-1);

                list.add(tmp);

                lower = A[i]+1;

}

}

        // check the last element

        if(lower <= upper){

            String tmp = ""+lower;

            if(lower != upper)

                tmp += "->"+upper;

            list.add(tmp);

}

        return list;

}

    public List<String> findMissingRanges(int[] nums, int lower, int upper) {

        List<String> list = new LinkedList();

        for(int i =0;i<nums.length; i++){

            int val = nums[i];

            if(val>lower){

                String range = getRange(lower,Math.min(val-1,upper)) ;

                if(range.length()>0)

                    list.add(range);

                lower=val+1;

            }else if(val == lower){

                lower++;

}

}

        if(lower<=upper){

            list.add(getRange(lower,upper));

}

        return list;

}

    private String getRange(int start, int end){

        if(start>end)

            return "";

        else if(start==end)

            return ""+start;

        else

            return ""+start+"->"+end;

}

http://www.cnblogs.com/EdwardLiu/p/4249626.html
Read full article from [LeetCode] Missing Ranges | 程序员达达

[LeetCode] Missing Ranges | 程序员达达

Labels

Popular Posts