在一串没有分隔符的数字中找到缺失的数字
原文:https://www . geesforgeks . org/find-missing-number-string-numbers-no-separator/
给定一个由一些数字组成的字符串，没有用任何分隔符分隔。这些数字都是正整数，除了缺少的数字之外，每个数字的序列都增加 1。任务是找到丢失的号码。数字不超过六位。如果输入序列无效，打印-1。
示例:
Input : 89101113
Output : 12
Input : 9899101102
Output : 100
Input : 596597598600601602:
Output : 599
Input : 909192939495969798100101
Output : 99
Input : 11111211311411511
Output : -1
想法是尝试从 1 到 6 的所有长度。对于我们尝试的每个长度，我们检查当前长度是否满足所有连续数字和一个缺失的属性。一个有趣的事情是数字的数量可能会随着我们增加数字而变化。例如，当我们从 99 移动到 100 时。为了处理这种情况，我们使用对数基数 10 来计算位数。
下面是上述方法的实现:
C++
// C++ program to find a missing number in a
// string of consecutive numbers without any
// separator.
#include<bits/stdc++.h>
using namespace std;
const int MAX_DIGITS = 6;
// gets the integer at position i with length m,
// returns it or -1, if none
int getValue(const string& str, int i, int m)
{
if (i + m > str.length())
return -1;
// Find value at index i and length m.
int value = 0;
for (int j = 0; j < m; j++)
{
int c = str[i + j] - '0';
if (c < 0 || c > 9)
return -1;
value = value * 10 + c;
}
return value;
}
// Returns value of missing number
int findMissingNumber(const string& str)
{
// Try all lengths for first number
for (int m=1; m<=MAX_DIGITS; ++m)
{
// Get value of first number with current
// length/
int n = getValue(str, 0, m);
if (n == -1)
break;
// To store missing number of current length
int missingNo = -1;
// To indicate whether the sequence failed
// anywhere for current length.
bool fail = false;
// Find subsequent numbers with previous number as n
for (int i=m; i!=str.length(); i += 1 + log10l(n))
{
// If we haven't yet found the missing number
// for current length. Next number is n+2\. Note
// that we use Log10 as (n+2) may have more
// length than n.
if ((missingNo == -1) &&
(getValue(str, i, 1+log10l(n+2)) == n+2))
{
missingNo = n + 1;
n += 2;
}
// If next value is (n+1)
else if (getValue(str, i, 1+log10l(n+1)) == n+1)
n++;
else
{
fail = true;
break;
}
}
if (!fail)
return missingNo;
}
return -1; // not found or no missing number
}
// Driver code
int main()
{
cout << findMissingNumber("99101102");
return 0;
}
Java 语言(一种计算机语言，尤用于创建网站)
// Java program to find a missing number in a
// string of consecutive numbers without any
// separator.
class GFG {
static final int MAX_DIGITS = 6;
// gets the integer at position i with length m,
// returns it or -1, if none
static int getValue(String str, int i, int m) {
if (i + m > str.length()) {
return -1;
}
// Find value at index i and length m.
int value = 0;
for (int j = 0; j < m; j++) {
int c = str.charAt(i + j) - '0';
if (c < 0 || c > 9) {
return -1;
}
value = value * 10 + c;
}
return value;
}
// Returns value of missing number
static int findMissingNumber(String str) {
// Try all lengths for first number
for (int m = 1; m <= MAX_DIGITS; ++m) {
// Get value of first number with current
// length/
int n = getValue(str, 0, m);
if (n == -1) {
break;
}
// To store missing number of current length
int missingNo = -1;
// To indicate whether the sequence failed
// anywhere for current length.
boolean fail = false;
// Find subsequent numbers with previous number as n
for (int i = m; i != str.length(); i += 1 + Math.log10(n)) {
// If we haven't yet found the missing number
// for current length. Next number is n+2\. Note
// that we use Log10 as (n+2) may have more
// length than n.
if ((missingNo == -1)
&& (getValue(str, i, (int) (1 + Math.log10(n + 2))) == n + 2)) {
missingNo = n + 1;
n += 2;
} // If next value is (n+1)
else if (getValue(str, i, (int) (1 + Math.log10(n + 1))) == n + 1) {
n++;
} else {
fail = true;
break;
}
}
if (!fail) {
return missingNo;
}
}
return -1; // not found or no missing number
}
// Driver code
public static void main(String[] args) {
System.out.println(findMissingNumber("99101102"));
}
}
// This code is contributed by 29AjayKumar
Python 3
# Python3 program to find
# a missing number in a
# string of consecutive
# numbers without any
# separator.
import math
MAX_DIGITS = 6
# gets the integer at position
# i with length m, returns it
# or -1, if none
def getValue(Str, i, m):
if(i + m > len(Str)):
return -1
# Find value at index
# i and length m.
value = 0
for j in range(m):
c = (ord(Str[i + j]) -
ord('0'))
if(c < 0 or c > 9):
return -1
value = value * 10 + c
return value
# Returns value of missing
# number
def findMissingNumber(Str):
# Try all lengths for
#first number
for m in range(1, MAX_DIGITS + 1):
# Get value of first
# number with current
# length
n = getValue(Str, 0, m)
if(n == -1):
break
# To store missing number
# of current length
missingNo = -1
# To indicate whether
# the sequence failed
# anywhere for current
# length.
fail = False
# Find subsequent numbers
# with previous number as n
i = m
while(i != len(Str)):
# If we haven't yet found
# the missing number for
# current length. Next
# number is n+2\. Note
# that we use Log10 as
# (n+2) may have more
# length than n.
if((missingNo == -1) and
(getValue(Str, i, 1 +
int(math.log10(n + 2))) ==
n + 2)):
missingNo = n + 1
n += 2
# If next value is (n+1)
elif((getValue(Str, i, 1 +
int(math.log10(n + 1))) ==
n + 1)):
n += 1
else:
fail = True
break
i += 1 + int(math.log10(n))
if(not fail):
return missingNo
# not found or no
# missing number
return -1
# Driver code
print(findMissingNumber("99101102"))
# This code is contributed by avanitrachhadiya2155
C
// C# program to find a missing number in a
// string of consecutive numbers without any
// separator.
using System;
public class GFG {
static readonly int MAX_DIGITS = 6;
// gets the integer at position i with length m,
// returns it or -1, if none
static int getValue(String str, int i, int m) {
if (i + m > str.Length) {
return -1;
}
// Find value at index i and length m.
int value = 0;
for (int j = 0; j < m; j++) {
int c = str[i + j] - '0';
if (c < 0 || c > 9) {
return -1;
}
value = value * 10 + c;
}
return value;
}
// Returns value of missing number
static int findMissingNumber(String str) {
// Try all lengths for first number
for (int m = 1; m <= MAX_DIGITS; ++m) {
// Get value of first number with current
// length/
int n = getValue(str, 0, m);
if (n == -1) {
break;
}
// To store missing number of current length
int missingNo = -1;
// To indicate whether the sequence failed
// anywhere for current length.
bool fail = false;
// Find subsequent numbers with previous number as n
for (int i = m; i != str.Length; i += 1 + (int)Math.Log10(n)) {
// If we haven't yet found the missing number
// for current length. Next number is n+2\. Note
// that we use Log10 as (n+2) may have more
// length than n.
if ((missingNo == -1)
&& (getValue(str, i, (int) (1 + Math.Log10(n + 2))) == n + 2)) {
missingNo = n + 1;
n += 2;
} // If next value is (n+1)
else if (getValue(str, i, (int) (1 + Math.Log10(n + 1))) == n + 1) {
n++;
} else {
fail = true;
break;
}
}
if (!fail) {
return missingNo;
}
}
return -1; // not found or no missing number
}
// Driver code
public static void Main() {
Console.WriteLine(findMissingNumber("99101102"));
}
}
//This code is contributed by PrinciRaj1992
java 描述语言
<script>
// Javascript program to find a missing number
// in a string of consecutive numbers without any
// separator.
let MAX_DIGITS = 6;
// Gets the integer at position i
// with length m, returns it or -1,
// if none
function getValue(str, i, m)
{
if (i + m > str.length)
{
return -1;
}
// Find value at index i and length m.
let value = 0;
for(let j = 0; j < m; j++)
{
let c = str[i + j].charCodeAt(0) -
'0'.charCodeAt(0);
if (c < 0 || c > 9)
{
return -1;
}
value = value * 10 + c;
}
return value;
}
// Returns value of missing number
function findMissingNumber(str)
{
// Try all lengths for first number
for(let m = 1; m <= MAX_DIGITS; ++m)
{
// Get value of first number with
// current length
let n = getValue(str, 0, m);
if (n == -1)
{
break;
}
// To store missing number of
// current length
let missingNo = -1;
// To indicate whether the sequence
// failed anywhere for current length.
let fail = false;
// Find subsequent numbers with
// previous number as n
for(let i = m;
i != str.length;
i += 1 + Math.floor(Math.log10(n)))
{
// If we haven't yet found the missing number
// for current length. Next number is n+2\. Note
// that we use Log10 as (n+2) may have more
// length than n.
if ((missingNo == -1) &&
(getValue(str, i, Math.floor(1 + Math.log10(n + 2))) == n + 2)) {
missingNo = n + 1;
n += 2;
}
// If next value is (n+1)
else if (getValue(str, i, Math.floor(
1 + Math.log10(n + 1))) == n + 1)
{
n++;
}
else
{
fail = true;
break;
}
}
if (!fail)
{
return missingNo;
}
}
// Not found or no missing number
return -1;
}
// Driver code
document.write(findMissingNumber("99101102"));
// This code is contributed by ab2127
</script>
输出:
100
本文由 Roshni Agarwal 供稿。如果你喜欢 GeeksforGeeks 并想投稿，你也可以使用write.geeksforgeeks.org写一篇文章或者把你的文章邮寄到 review-team@geeksforgeeks.org。看到你的文章出现在极客博客主页上，帮助其他极客。 如果你发现任何不正确的地方，或者你想分享更多关于上面讨论的话题的信息，请写评论。
版权属于：月萌API www.moonapi.com，转载请注明出处
