f********a
发帖数: 165 | 1 就是找Missing int,但是输入不是int arr,而是一个string.
比如 123456891011 output 7
9991000100110021004 output 1003
主要就是在分string成array of substring的时候，长度会从999的3变成1000的4，如
果从1到100000之间缺一个数，得考虑所有9，99等的情况来分string。感
觉用recursion有可能，但也不知道怎么写。 |
n******f
发帖数: 318 | 2 个人觉得用普通循环就好了。 case情况较多，8，98，998 等需要特殊考虑。每次就先
从一位数考虑分割，看此分割是否合理。不合理就考虑两位分割。遇到8，98等以及9，
99等，添加进位标识。
就是找Missing int,但是输入不是int arr,而是一个string.比如 123456891011
output 7
【在 f********a 的大作中提到】
: 就是找Missing int,但是输入不是int arr,而是一个string.
: 比如 123456891011 output 7
: 9991000100110021004 output 1003
: 主要就是在分string成array of substring的时候，长度会从999的3变成1000的4，如
: 果从1到100000之间缺一个数，得考虑所有9，99等的情况来分string。感
: 觉用recursion有可能，但也不知道怎么写。
|
f********x
发帖数: 2086 | 3
如果像你这些例子都是按顺序给的话
那就是一个个读+判断吧，记录下当前valid位数
感觉这个和missing number还是差别挺大的，这个就是纯的处理字符串
【在 f********a 的大作中提到】
: 就是找Missing int,但是输入不是int arr,而是一个string.
: 比如 123456891011 output 7
: 9991000100110021004 output 1003
: 主要就是在分string成array of substring的时候，长度会从999的3变成1000的4，如
: 果从1到100000之间缺一个数，得考虑所有9，99等的情况来分string。感
: 觉用recursion有可能，但也不知道怎么写。
|
n******f
发帖数: 318 | 4 同意。。。貌似就考察字符串处理，和细心。没算法可言
如果像你这些例子都是按顺序给的话那就是一个个读 判断吧，记录下当前valid位数感
觉这个和missing number还是差别挺大的，这个就是纯的处理字符串
【在 f********x 的大作中提到】
:
: 如果像你这些例子都是按顺序给的话
: 那就是一个个读+判断吧，记录下当前valid位数
: 感觉这个和missing number还是差别挺大的，这个就是纯的处理字符串
|
s*******n
发帖数: 305 | 5 直接分， 找区间：
substring(0,9), 看最后1位是不是9
substring(9, 189), 看最后2位是不是99，
substring(189,2889), 看最后3位是不是999
......
这样子就能确定出来那个区间miss了， 你也知道miss的这个数的长度了
也麻烦， 需要算之前的位数 |
t**********r
发帖数: 2153 | 6 只差一个数的话就统计digits出现的次数好了。
【在 f********a 的大作中提到】
: 就是找Missing int,但是输入不是int arr,而是一个string.
: 比如 123456891011 output 7
: 9991000100110021004 output 1003
: 主要就是在分string成array of substring的时候，长度会从999的3变成1000的4，如
: 果从1到100000之间缺一个数，得考虑所有9，99等的情况来分string。感
: 觉用recursion有可能，但也不知道怎么写。
|
f********a
发帖数: 165 | 7 是啊。但是这case也太多了吧8,9,98,99。。。都要考虑，想是这么想，写对感觉不容
易。
【在 n******f 的大作中提到】
: 个人觉得用普通循环就好了。 case情况较多，8，98，998 等需要特殊考虑。每次就先
: 从一位数考虑分割，看此分割是否合理。不合理就考虑两位分割。遇到8，98等以及9，
: 99等，添加进位标识。
:
: 就是找Missing int,但是输入不是int arr,而是一个string.比如 123456891011
: output 7
|
f********a
发帖数: 165 | 8 第一个不一定从1开始吧。任何数都可以。
【在 s*******n 的大作中提到】
: 直接分， 找区间：
: substring(0,9), 看最后1位是不是9
: substring(9, 189), 看最后2位是不是99，
: substring(189,2889), 看最后3位是不是999
: ......
: 这样子就能确定出来那个区间miss了， 你也知道miss的这个数的长度了
: 也麻烦， 需要算之前的位数
|
f********a
发帖数: 165 | 9 任意开始和任意结束的数怎么数digits的次数？比如345689101113的话。
【在 t**********r 的大作中提到】
: 只差一个数的话就统计digits出现的次数好了。
|
l*******g
发帖数: 82 | 10 我说个思路，你看看。
首先i从1开始循环一直到1000000
num = String.valueOf(i)(
判断string.indexOf(num) == 0
如果是true
string = string.subString(num.length - 1, string.length-1);
如果是false
Return i;
就是找Missing int,但是输入不是int arr,而是一个string.比如 123456891011
output 7
【在 f********a 的大作中提到】
: 就是找Missing int,但是输入不是int arr,而是一个string.
: 比如 123456891011 output 7
: 9991000100110021004 output 1003
: 主要就是在分string成array of substring的时候，长度会从999的3变成1000的4，如
: 果从1到100000之间缺一个数，得考虑所有9，99等的情况来分string。感
: 觉用recursion有可能，但也不知道怎么写。
|
|
|
l*******g
发帖数: 82 | 11 不好意思，忘了些一个代码了，
boolean isStarted = false;
第一次true时候要吧isStarted=true
然后那个false判断加上 isStarted == true
手机打得代码没办法整理格式了。 |
f********a
发帖数: 165 | 12 不懂。。你思路是什么？
【在 l*******g 的大作中提到】
: 我说个思路，你看看。
: 首先i从1开始循环一直到1000000
: num = String.valueOf(i)(
: 判断string.indexOf(num) == 0
: 如果是true
: string = string.subString(num.length - 1, string.length-1);
: 如果是false
: Return i;
:
: 就是找Missing int,但是输入不是int arr,而是一个string.比如 123456891011
|
A*********c
发帖数: 430 | 13 这个题目的核心是不是这个问题：
如何确定第一个数字是什么。因为第一个数字一旦确定，数字序列就确定了。
从第一个数字开始，不停得生成后面得数字，然后和字符串比较，跃进，这个过程找出
缺少的数字就很trivial了。
【在 f********a 的大作中提到】
: 就是找Missing int,但是输入不是int arr,而是一个string.
: 比如 123456891011 output 7
: 9991000100110021004 output 1003
: 主要就是在分string成array of substring的时候，长度会从999的3变成1000的4，如
: 果从1到100000之间缺一个数，得考虑所有9，99等的情况来分string。感
: 觉用recursion有可能，但也不知道怎么写。
|
A*********c
发帖数: 430 | 14 还没想出efficient得办法来猜第一个数字，
比如说123124123125。没法猜什么时候才是新得数字加一
就算是1234568后面跟1234569也是可能的。
不行就暴力，从假设长度为一，验证是不是缺了一个数字，并且其他数字连续，不对就
early stop并且增加猜测的长度。
长度不能大于n/2 obviously。即假设最少含两个数字，要不然所有输入都有trivial解
stoi(input) +1了。
复杂度n^2.
【在 A*********c 的大作中提到】
: 这个题目的核心是不是这个问题：
: 如何确定第一个数字是什么。因为第一个数字一旦确定，数字序列就确定了。
: 从第一个数字开始，不停得生成后面得数字，然后和字符串比较，跃进，这个过程找出
: 缺少的数字就很trivial了。
|
l*******g
发帖数: 82 | 15 哈，不好意思，晚上睡前没仔细思考。这个应该用suffix tree做。吧整个字符串序列
存入suffix tree，然后搜索1234这样子。比如 1234 1235 1237 1238
当搜索suffix tree的时候只要搜索到123，那么1234，1235，1236，1238都会返回，这
样在判断返回的序列是不是连续的就可了。
只要遇到999之类的加一搜索就可以了。
就是找Missing int,但是输入不是int arr,而是一个string.比如 123456891011
output 7
【在 f********a 的大作中提到】
: 就是找Missing int,但是输入不是int arr,而是一个string.
: 比如 123456891011 output 7
: 9991000100110021004 output 1003
: 主要就是在分string成array of substring的时候，长度会从999的3变成1000的4，如
: 果从1到100000之间缺一个数，得考虑所有9，99等的情况来分string。感
: 觉用recursion有可能，但也不知道怎么写。
|
l*********8
发帖数: 4642 | 16 看你题目的例子， string转换成的int array是有序的吧？ 用suffix tree保存的话
，怎么知道这个顺序？
【在 l*******g 的大作中提到】
: 哈，不好意思，晚上睡前没仔细思考。这个应该用suffix tree做。吧整个字符串序列
: 存入suffix tree，然后搜索1234这样子。比如 1234 1235 1237 1238
: 当搜索suffix tree的时候只要搜索到123，那么1234，1235，1236，1238都会返回，这
: 样在判断返回的序列是不是连续的就可了。
: 只要遇到999之类的加一搜索就可以了。
:
: 就是找Missing int,但是输入不是int arr,而是一个string.比如 123456891011
: output 7
|
l*******g
发帖数: 82 | 17 通过搜索123得到1234 1235 1237 1238
然后substring之后得到4,5,7,8，从0到9暴力的话我想这是一个constant time
complex。应该可以忽略不记得。
我是这么理解的，这道题看上去是求number，其实，这是一个string pattern搜索的题。
这也是为什么他给了string而不是int类型。因为，要确定这个开始的数其实是要对比
整个字符串之后才能知道，而suffixtree恰恰是用来进行string set搜索的数据结构。
看你题目的例子， string转换成的int array是有序的吧？
【在 l*********8 的大作中提到】
: 看你题目的例子， string转换成的int array是有序的吧？ 用suffix tree保存的话
: ，怎么知道这个顺序？
|
c*******2
发帖数: 60 | 18 Can anyone state the well-defined problem?
e.g. What are valid inputs? What does "missing number" mean? Can there be
more than one missing number and we just need to find the first one?
e.g. input: "3891215", is it valid?
If it is, what is the output? 4? 39? 390? |
f********a
发帖数: 165 | 19 例子看是连续递增序列中间缺一个 至少2个数中间缺一个 比如99101缺100。一个数不
考虑。已经well defined 了啊。仅考虑所有都是valid的case.
★ 发自iPhone App: ChineseWeb 8.1
★ 发自iPhone App: ChineseWeb 8.1
【在 c*******2 的大作中提到】
: Can anyone state the well-defined problem?
: e.g. What are valid inputs? What does "missing number" mean? Can there be
: more than one missing number and we just need to find the first one?
: e.g. input: "3891215", is it valid?
: If it is, what is the output? 4? 39? 390?
|
r****s
发帖数: 42 | 20 用StringBuffer 做，StringBuffer在增长，同时与原string的前i位比较内容，一出现
不相等的，就找到了位置。我简单写了个，先考虑0-99以内的：100-999，类似吧，多
加个else if
StringBuffer sb=new StringBuffer(); String string="
0123456789101112131415161718192022";
int m=1;
for(int i=0;i
sb.append(i);
if(i<10){
if(! sb.toString().equals(string.subSequence(0, i+1))){
System.out.println("result: "+i);break;
}
}
else if(i>=10 && i<=99){
m++;
if(! sb.toString().equals(string.subSequence(0, i+m))){
System.out.println(sb+" result: "+i);break;
}
}
}
System.out.println(sb.toString());
【在 f********a 的大作中提到】
: 就是找Missing int,但是输入不是int arr,而是一个string.
: 比如 123456891011 output 7
: 9991000100110021004 output 1003
: 主要就是在分string成array of substring的时候，长度会从999的3变成1000的4，如
: 果从1到100000之间缺一个数，得考虑所有9，99等的情况来分string。感
: 觉用recursion有可能，但也不知道怎么写。
|
|
|
c********p
发帖数: 1969 | |
a****o
发帖数: 45 | |
h*******e
发帖数: 1377 | 23 先检查首位为一位的情况 a****** a a+ 1 a+ 2... check 唯一
之后 分情况 a != 9 ab***** b!= 9 这时候 如果 两位 ab ab+ 1 ab +
2
的搜 或者 ab ab 的搜 ab cdefgh ab **** ab**** 的情况 abcdefgh +1 在不
在下一个 如没有 则 abcdefgh abijklmnopqab**** abcdefgh abijklmnopq 的下一
个
a!= 9 ab**** b== 9 两位 ab (a+ 1) 0 唯一 或者
a b****ab**** ab**** 的搜 同上
a == 9 a b***** b!= 9 两位 多位 都 搜 同上
a == 9 b == 9 ab **** 两位 100 往下搜 否则 99* 同上
a == 9 b == 9 c == 9 三位 搜 1000 否则 搜 999
一直递推 q位都是 9 的情况
上面 数种情况有一种满足 每种 有1到2 种情况 每种的算法复杂度o(n)所以一共是O
(n) 复杂度 |
P**H
发帖数: 1897 | 24 暴力呢,从1位开始验证.然后2, 3, 直到 N / 2位数的各种组合.
跟验证9,99,的复杂度也差不多了吧. |
x*****0
发帖数: 452 | |
x*******6
发帖数: 262 | |
