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”]
这也是Google Interview的电面题目。
[分析]
一遍线性扫描即可。
[注意事项]
1)针对一些特殊情况,询问面试官,比如说如果array是个空的,或者array包含区间内的所有元素,相应的返回值是什么
2)可以给出一些有意思的test case,另外就是不需要限制给出的范围是[0, 99],用start和end表示就行。在面试的时候可以先提一下,写出[0, 99]的代码,然后在稍作修改,变成start和end的版本。
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; }
另外一种写法:
public String missingRanges(int[] A) { int prev = -1, n = A.length; StringBuilder sb = new StringBuilder(); for(int i=0; i<=n; i++) { int val = (i==n) ? 100 : A[i]; if(val != prev+1) { int low = prev+1; int high = val-1; if(sb.length() != 0) sb.append(","); if(low == high) sb.append(low); else sb.append(low + "-" + high); } prev = val; } return sb.toString(); }
相关推荐
大佬的leetcode刷题笔记(c++版本)
leetcode-cli-plugins leetcode-cli 的第 3 方插件。 什么是 如何使用 如何使用 插件 名称 描述 增强的命令 按公司或标签过滤问题 list 不要在同一台计算机上使 Chrome 的会话过期 login 不要在同一台计算机上使 ...
LeetCode题解 - Java语言实现-181页.pdf
leetcode 答案Leetcode---数据库 我对 Leetcode 数据库问题的回答
彩色版本 正版 pdf 精讲数据结构 + 算法 链表 树 图表 贪心算法 指针 动态规划 查找算法
leetcode1-300.docx
leetcode 答案leetcode--python Leetcode 的答案
500195422331430LeetCode题解 - Java语言实现.zip
leetcode 答案LeetCode--哈希表 以上是我对“哈希表”问题的回答,都被leetcode的判断所接受。
Algorithm-LeetCode-Sol-Res.zip,干净,易懂的解决方案和资源,为leetcode在线判断算法问题。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
leetcode-cli 注意:这个存储库是为了临时使用而分叉的。 注意:从 webbrowser 复制 cookie 并使用leetcode user -c可以临时修复不能。 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的...
leetcode 1 -200题所有源码 有问题私聊我
leetcode1-240题中文题解,md格式,java版本 有题目有题解有代码 需要使用markdown打开
leetcode26 algo 算法与数据结构,练习代码 语言:java 8 开发工具:vscode,安装插件Java Extension Pack vscode有智能提示,可调试,有重构支持,满足代码练习要求,相比IDEA更轻量级,普通笔记本即可流畅运行。 ...
leetcode 答案Leetcode---算法 我对 Leetcode 算法问题的回答
本书包含了 LeetCode Online Judge所有题目的答案,所有代码经过精心编写,编码规范良好,适合读者反复揣摩,模仿,甚至在纸上默写