【LeetCode】Missing Ranges
LeetCode missing
2023-09-11 14:20:27 时间
Missing Ranges
Given a sorted integer array where the range of elements are [lower, upper] inclusive, return its missing ranges.
For example, given [0, 1, 3, 50, 75], lower = 0 and upper = 99, return ["2", "4->49", "51->74", "76->99"].
逐个数组元素遍历,将间隙取出即可。注意两边的情况。
class Solution { public: vector<string> findMissingRanges(int A[], int n, int lower, int upper) { vector<string> ret; if(n == 0) return ret; string str; if(lower < A[0]) { if(lower < A[0]-1) str = to_string((long long)lower) + "->" + to_string((long long)A[0]-1); else //lower == A[0]-1 str = to_string((long long)lower); ret.push_back(str); } for(int i = 1; i < n; i ++) { if(A[i] - A[i-1] < 2) continue; if(A[i] - A[i-1] > 2) str = to_string((long long)A[i-1]+1) + "->" + to_string((long long)A[i]-1); else //A[i] - A[i-1] == 2 str = to_string((long long)A[i-1]+1); ret.push_back(str); } if(A[n-1] < upper) { if(A[n-1] < upper-1) str = to_string((long long)A[n-1]+1) + "->" + to_string((long long)upper); else //upper == A[n-1]+1 str = to_string((long long)upper); ret.push_back(str); } return ret; } };
以下是我的测试用例,全部通过:
void display(vector<string>& ret) { for(int i = 0; i < ret.size(); i ++) { cout << ret[i] << " "; } cout << endl; } int main() { Solution s; int A[1]; //expect: ["0->9"] vector<string> ret = s.findMissingRanges(A, 0, 0, 9); display(ret); int B[1] = {6}; //expect: ["0->5", "7->9"] ret = s.findMissingRanges(B, 1, 0, 9); display(ret); int C[3] = {0, 1, 2}; //expect: [] ret = s.findMissingRanges(C, 3, 0, 2); display(ret); int D[5] = {0, 1, 3, 50, 75}; //expect: ["2", "4->49", "51->74", "76->99"] ret = s.findMissingRanges(D, 5, 0, 99); display(ret); }
相关文章
- Java实现 LeetCode 710 黑名单中的随机数(黑白名单)
- Java实现 LeetCode 598 范围求和 II(最小值相乘)
- Java实现 LeetCode 575 分糖果(看看是你的长度小还是我的种类少)
- Java实现 LeetCode 563 二叉树的坡度(又是一个遍历树)
- Java实现 LeetCode 470 用 Rand7() 实现 Rand10()
- Java实现 LeetCode 103 二叉树的锯齿形层次遍历
- Java实现 LeetCode 100 相同的树
- Java实现 LeetCode 46 全排列
- Java实现 Leetcode 88 合并两个有序数组
- 【链表】leetcode 19. 删除链表的倒数第 N 个结点【中等】
- LeetCode(43):字符串相乘
- [LeetCode] Missing Number
- LeetCode-1200. 最小绝对差【数组,排序】
- leetcode - First Missing Positive
- leetcode 1019. 链表中的下一个更大节点 js实现
- 【Leetcode刷题Python】LeetCode 478. 在圆内随机生成点
- 【Leetcode刷题Python】剑指 Offer 11. 旋转数组的最小数字