C++實現(xiàn)LeetCode(163.缺失區(qū)間)
[LeetCode] 163. Missing Ranges 缺失區(qū)間
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"]
這道題讓我們求缺失區(qū)間，跟之前那道 Summary Ranges 很類似，給了一個空間的范圍 [lower upper]，缺失的區(qū)間的范圍需要在給定的區(qū)間范圍內(nèi)。遍歷 nums 數(shù)組，假如當(dāng)前數(shù)字 num 大于 lower，說明此時已經(jīng)有缺失區(qū)間，至少缺失一個 lower 數(shù)字，此時若 num-1 大于 lower，說明缺失的是一個區(qū)間 [lower, num-1]，否則就只加入一個數(shù)字即可。由于 OJ 之后加入了許多 tricky 的 test cases，使得論壇上很多解法都 fail 了。其實很多是跪在了整型溢出，當(dāng)數(shù)組中有整型最大值時，此時 lower 更新為 num+1 時就會溢出，所以在更新之前要先判斷一下，若 num 已經(jīng)是整型最大值了，直接返回結(jié)果 res 即可；否則才更新 lower 繼續(xù)循環(huán)。for 循環(huán)退出后，此時可能還存在缺失區(qū)間，就是此時 lower 還小于等于 upper 時，可以會缺失 lower 這個數(shù)字，或者 [lower, upper] 區(qū)間，最后補上這個區(qū)間就可以通過啦，參見代碼如下：
class Solution {
public:
vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
vector<string> res;
for (int num : nums) {
if (num > lower) res.push_back(to_string(lower) + (num - 1 > lower ? ("->" + to_string(num - 1)) : ""));
if (num == upper) return res;
lower = num + 1;
}
if (lower <= upper) res.push_back(to_string(lower) + (upper > lower ? ("->" + to_string(upper)) : ""));
return res;
}
};
Github 同步地址：
https://github.com/grandyang/leetcode/issues/163
類似題目：
參考資料：
https://leetcode.com/problems/missing-ranges/
https://leetcode.com/problems/missing-ranges/discuss/50468/Accepted-Java-solution-8-lines-and-0ms
到此這篇關(guān)于C++實現(xiàn)LeetCode(163.缺失區(qū)間)的文章就介紹到這了,更多相關(guān)C++實現(xiàn)缺失區(qū)間內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
- C++實現(xiàn)LeetCode(171.求Excel表列序號)
- C++實現(xiàn)LeetCode(168.求Excel表列名稱)
- C++實現(xiàn)LeetCode(167.兩數(shù)之和之二 - 輸入數(shù)組有序)
- C++實現(xiàn)LeetCode(166.分?jǐn)?shù)轉(zhuǎn)循環(huán)小數(shù))
- C++實現(xiàn)LeetCode165.版本比較)
- C++實現(xiàn)LeetCode(164.求最大間距)
- C++實現(xiàn)LeetCode(228.總結(jié)區(qū)間)
- C++實現(xiàn)LeetCode(169.求大多數(shù))
相關(guān)文章
深入淺析C/C++語言結(jié)構(gòu)體指針的使用注意事項
這篇文章主要介紹了C/C++語言結(jié)構(gòu)體指針的使用,大家都知道指針在32位系統(tǒng)占用4Byte，在64位系統(tǒng)占用8Byte，下面看下c語言代碼例子2021-12-12
PS中的高光命令是一種校正由于太接近相機閃光燈而有些發(fā)白的焦點的方法，對高光區(qū)和非高光區(qū)的邊緣作平滑處理，接下來通過本文給大家分享C++之OpenCV圖像高光調(diào)整具體流程，感興趣的朋友一起看看吧2021-09-09
今天小編就為大家分享一篇C實現(xiàn)不定長數(shù)組的示例，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-07-07
c++中的volatile和variant關(guān)鍵字詳解
大家好，本篇文章主要講的是c++中的volatile和variant關(guān)鍵字詳解，感興趣的同學(xué)趕快來看一看吧，對你有幫助的話記得收藏一下2022-01-01
用C/C++實現(xiàn)linux下檢測網(wǎng)絡(luò)接口狀態(tài)
這篇文章主要為大家詳細(xì)介紹了用c/c++實現(xiàn)linux下檢測網(wǎng)絡(luò)接口狀態(tài)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-06-06
除了可以直接使用C提供的標(biāo)準(zhǔn)類型名（如：int ,char ,float,double,long等）和自己聲明的結(jié)構(gòu)體、共用體、枚舉類型外，還可以使用typedef聲明 新的類型名 來代替 已有的 類型名2013-08-08
這篇文章主要為大家詳細(xì)介紹了如何基于Qt實現(xiàn)可拖動自定義控件，文中的示例代碼講解詳細(xì)，具有一定的借鑒價值，感興趣的小伙伴可以了解一下2023-04-04
本文給大家匯總了3個版本的C++實現(xiàn)添加桌面右鍵新建菜單的代碼，陸陸續(xù)續(xù)寫的，有需要的小伙伴可以根據(jù)自己的需求來選擇2016-01-01
這篇文章主要介紹了C++實現(xiàn)的求解多元一次方程,涉及C++矩陣運算相關(guān)操作技巧,需要的朋友可以參考下2018-01-01
json格式解析和libjson的用法介紹(關(guān)于cjson的使用方法)
下面小編就為大家?guī)硪黄猨son格式解析和libjson的用法介紹(關(guān)于cjson的使用方法)。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-12-12