LeetCode Top Interview Questions 163. Missing Ranges (Java版; Medium)

港控/mmm° 2023-07-03 08:29 1阅读 0赞

### [welcome to my blog][] ###

## LeetCode Top Interview Questions 163. Missing Ranges (Java版; Medium) ##

#### 题目描述 ####

Given a sorted integer array nums, where the range of elements are in
    the inclusive range [lower, upper], return its missing ranges.
    
    Example:
    
    Input: nums = [0, 1, 3, 50, 75], lower = 0 and upper = 99,
    Output: ["2", "4->49", "51->74", "76->99"]

#### 第一次做; 精简了一下代码; 核心: 1) 跳过重复元素 2) 避免溢出 ####

class Solution { 
        public List<String> findMissingRanges(int[] nums, int lower, int upper) { 
            List<String> res = new ArrayList<>();
            int l = lower;
            for(int i=0; i<nums.length; i++){ 
                //处理重复元素
                if(i>0 && nums[i]==nums[i-1])
                    continue;
                if(l<nums[i])
                    res.add(nums[i]==l+1? l+"" : l+"->"+(nums[i]-1));
                //防止溢出
                if(nums[i]==Integer.MAX_VALUE)
                    return res;
                l = nums[i]+1;      
            }
            //here, l=nums[-1]+1
            //处理nums[-1]和upper之间的数
            if(l<=upper)
                res.add(l==upper? l+"" : l+"->"+upper);
            return res;
        }
    }

#### 第一次做; 感觉是个面试好题; 精简了一下代码; 核心: 1) 跳过重复元素 2) 避免溢出 ####

/* 题目约束了upper>nums[-1] 需要小心处理的两个地方: 1.跳过重复元素 2.涉及++的操作就可能出现溢出! */
    class Solution { 
        public List<String> findMissingRanges(int[] nums, int lower, int upper) { 
            List<String> res = new ArrayList<>();
            int l = lower, r;
            for(int i=0; i<nums.length; i++){ 
                //处理重复元素
                if(i>0 && nums[i]==nums[i-1])
                    continue;
                r =nums[i];
                if(l<r){ 
                    String tmp = r==l+1? l+"" : l+"->"+(r-1);
                    res.add(tmp);
                }
                //防止溢出
                if(r==Integer.MAX_VALUE)
                    return res;
                l = r+1;      
            }
            //here, l=nums[-1]+1
            //处理nums[-1]和upper之间的数
            if(l<=upper)
                res.add(l==upper? l+"" : l+"->"+upper);
            return res;
        }
    }

#### 第一次做; 一点一点改出来的, 代码很乱; 需要考虑: 溢出, 重复元素 ####

/* upper>nums[-1] 跳过重复元素 */
    class Solution { 
        public List<String> findMissingRanges(int[] nums, int lower, int upper) { 
            List<String> res = new ArrayList<>();
            int p = lower;
            for(int i=0; i<nums.length; i++){ 
                //相邻元素相等则不处理
                if(i>0 && nums[i]==nums[i-1])
                    continue;
                if(nums[i]==p){ 
                    //考虑溢出
                    if(nums[i]==Integer.MAX_VALUE)
                        return res;
                    p++;
                }
                else if(nums[i]==p+1){ 
                    res.add(""+p);
                    p = nums[i]+1;
                }
                else{ 
                    res.add(p+"->"+(nums[i]-1));
                    //考虑溢出
                    if(nums[i]==Integer.MAX_VALUE)
                        return res;
                    p = nums[i]+1;
                }
                //超过上界后就不处理了
                if(p>upper)
                    break;
            }
            
            if(p==upper)
                res.add(""+p);
            else if(p<upper)
                res.add(p+"->"+upper);
            return res;
        }
    }

#### [力扣题解][Link 1] ####

class Solution { 
        public List<String> findMissingRanges(int[] nums, int lower, int upper) { 
            List<String> res = new ArrayList<>();
            long pre = (long)lower - 1; // prevent 'int' overflow
            for (int i = 0; i < nums.length; i++) { 
                if (nums[i] - pre == 2) res.add(String.valueOf(pre + 1));
                else if (nums[i] - pre > 2) res.add((pre + 1) + "->" + (nums[i] - 1));
                pre = nums[i]; // 'int' to 'long'
            }
            if (upper - pre == 1) res.add(String.valueOf(pre + 1));
            else if (upper - pre > 1) res.add((pre + 1) + "->" + upper);
            return res;
        }
    }

[welcome to my blog]: https://littlehaes.com
[Link 1]: https://leetcode-cn.com/problems/missing-ranges/solution/missing-ranges-shuang-zhi-zhen-fa-by-jyd/