java如何从没有空格的一串数字中找到丢失的数字？

Question

Input Format

The first line will contain the set of numbers in the sequence. Number are listed in ascending order.

Boundary Conditions

1<=M<=99999 Length of string S is from 5 to 200.

Output Format

The first line will contain the missing number M.

Example Input /Output 1

Input: 12346789

Output: 5

Input /Output 2 Input 596597598600601602

Output : 599

The numbers a sequence in the sequence are 596 597 598 599 600 601 602. 599 is the missing numbers

我的Java解决方案是：

我使用了split(("?<=\\G..."))等，将数字分成一、二、三、四和五位数。并将数字保存到相应的数组中。然后我检查了数组中两个相邻数字之间的差异——如果是一个，那么它将调用一个函数来查找缺少的数字

但问题是，当：

输入：

999899991000110002 

输出：

10000

序列号是9998999100011002。丢失的数字是10000

当可以从4位数字转换为5位数字时，如何分割字符串？有没有更好的办法解决这个问题

public void test(Scanner in)
{
    String n = in.nextLine();
    int n1 = n.length();
    System.out.println(n1);
    if (n1 % 2 == 0)
    {

    } else {
      n = "0" + n;
    }
    System.out.println(n);
    String[] one = n.split("(?<=\\G.)");
    String[] two = n.split("(?<=\\G..)");
    String[] three = n.split("(?<=\\G...)");
    String[] four = n.split("(?<=\\G....)");
    String[] five = n.split("(?<=\\G.....)");
    int x = one.length;
    int y = two.length;
    int z = three.length;
    int u = four.length;
    int v = five.length;
    int[] aa1 = new int [x];
    int[] aa2 = new int [y];
    int[] aa3 = new int [z];
    int[] aa4 = new int [u];
    int[] aa5 = new int [v];
    for (int i = 0; i < x; i++)
    {
        aa1[i] = Integer.parseInt(one[i]);
    }
    if (aa1[1] == aa1[3] - 2)
    {
        findmissing(aa1, x);          
    }
    for (int i = 0; i < y; i++)
    {
        aa2[i] = Integer.parseInt(two[i]);
    }
    if (aa2[1] == aa2[3] - 2)
    {
        findmissing(aa2, y);
    }
    for (int i = 0; i < z; i++)
    {
        aa3[i] = Integer.parseInt(three[i]);
    }
    if (aa3[1] == aa3[3] - 2)
    {
        findmissing(aa3, z);
    }
    for (int i = 0; i < u; i++)
    {
        aa4[i] = Integer.parseInt(four[i]);
    }
    if (aa4[1] == aa4[3] - 2)
    {
        findmissing(aa4, u);
    }
    for (int i = 0; i < v; i++)
    {
        aa5[i] = Integer.parseInt(five[i]);
    }
    if (aa5[1] == aa5[3] - 2)
    {
        findmissing(aa5, v);
    }
    in.close();
}

public static void findmissing(int[] bb, int value)
{
    for (int i = 0; i < value - 1; i++)
    {
        if (bb[i] == bb[i + 1] - 1)
        {

        } else {
            System.out.println(bb[i + 1] - 1);
        }
    }
}

Answer 1

如果你已经知道第一个数字，这应该是可行的。不过，确定第一个数字可能很棘手

public class SeqTest
{
    public static void main(String[] args)
    {
        new SeqTest().test("999899991000110002", 9998);
        System.exit(0);
    }

    public void test(String line, int nextExpectedNumber)
    {
        String remainingLine = line;
        boolean expected = true;
        Integer nextNumber = nextExpectedNumber;

        while (expected)
        {
            String expectedString = nextNumber.toString();

            if (!remainingLine.startsWith(expectedString))
            {
                expected = false;
                System.out.println("Missing " + expectedString + " from " + remainingLine);
            } else {
                // prune remainingLine
                remainingLine = remainingLine.substring(expectedString.length());
            }
            nextNumber = this.nextInSequence(nextNumber);
        }

        return;
    }

    public Integer nextInSequence(int current)
    {
        return ++current;
    }
}

Answer 2

除了解决OP给出的问题外，您还必须解决另外两个问题

1. 当数字从一个长度到另一个长度+1时会发生什么
2. 如果您有一对长度较短的初始数字，如9899&；9900? 你可以将这些数字检测为98、99、99、00

无论如何，下面是我针对代码运行的测试用例。第一行是数字字符串。第二行是字符串中的数字数组。第三行是丢失的号码

1234678910
[1, 2, 3, 4, 6, 7, 8, 9, 10]
5

26272829313233
[26, 27, 28, 29, 31, 32, 33]
30

9293949596979899101
[92, 93, 94, 95, 96, 97, 98, 99, 101]
100

99101102103104105106107108109110111112
[99, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112]
100

596597598600601602
[596, 597, 598, 600, 601, 602]
599

989999009901990299049905
[9899, 9900, 9901, 9902, 9904, 9905]
9903

98999901990299039904990599069907
[9899, 9901, 9902, 9903, 9904, 9905, 9906, 9907]
9900

9998999910000100011000210004
[9998, 9999, 10000, 10001, 10002, 10004]
10003

这段代码的要点是尝试你能想到的所有边缘情况。除非我写了代码，否则我不会想到989900序列

package com.ggl.testing;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class MissingNumber implements Runnable {

    private String numberString;

    public static void main(String[] args) {
        MissingNumber missingNumber = new MissingNumber();
        missingNumber.setNumberString("1234678910");
        missingNumber.run();
        missingNumber.setNumberString("26272829313233");
        missingNumber.run();
        missingNumber.setNumberString("9293949596979899101");
        missingNumber.run();
        missingNumber.setNumberString("99101102103104105106107108109110111112");
        missingNumber.run();
        missingNumber.setNumberString("596597598600601602");
        missingNumber.run();
        missingNumber.setNumberString("989999009901990299049905");
        missingNumber.run();
        missingNumber.setNumberString("98999901990299039904990599069907");
        missingNumber.run();
        missingNumber.setNumberString("9998999910000100011000210004");
        missingNumber.run();
    }

    public void setNumberString(String numberString) {
        this.numberString = numberString;
    }

    @Override
    public void run() {
        System.out.println(numberString);
        Integer[] numbers = getNumbers(numberString);
        System.out.println(Arrays.toString(numbers));
        int missingNumber = findMissingNumber(numbers);
        System.out.println(missingNumber + "\n");
    }

    private Integer[] getNumbers(String numberString) {
        List<Integer> numbers = new ArrayList<>();
        int index1 = 0;
        int index2 = 1;
        int length = 1;
        boolean isAdjacent = false;

        while (!isAdjacent) {
            Integer test1 = getSubstring(numberString, index1, length);
            Integer test2 = getSubstring(numberString, index2, length);
            Integer test3 = getSubstring(numberString, index2, length + 1);
            if (isValidDifference(test2, test1)) {
                numbers.add(test1);
                numbers.add(test2);
                try {
                    getRemainingNumbers(numberString, numbers, index2, length,
                            test2);
                    isAdjacent = true;
                } catch (NumberFormatException e) {
                    numbers.clear();
                    length++;
                    index1 = 0;
                    index2 = index1 + length;
                }
            } else if (isValidDifference(test3, test1)) {
                numbers.add(test1);
                numbers.add(test3);
                length++;
                try {
                    getRemainingNumbers(numberString, numbers, index2, length,
                            test3);
                    isAdjacent = true;
                } catch (NumberFormatException e) {
                    numbers.clear();
                    length++;
                    index1 = 0;
                    index2 = index1 + length;
                }
            } else {
                length++;
                index2 = index1 + length;
            }
        }

        return numbers.toArray(new Integer[numbers.size()]);
    }

    private void getRemainingNumbers(String numberString,
            List<Integer> numbers, int index2, int length, Integer previousTest)
            throws NumberFormatException {
        int index = index2 + length;
        while (index <= (numberString.length() - length)) {
            Integer test = getSubstring(numberString, index, length);
            if (isValidDifference(test, previousTest)) {
                numbers.add(test);
                previousTest = test;
                index += length;
            } else {
                length++;
            }
        }
    }

    private Integer getSubstring(String string, int index, int length)
            throws NumberFormatException {
        return Integer.valueOf(string.substring(index, index + length));
    }

    private boolean isValidDifference(int number2, int number1) {
        int diff = number2 - number1;
        return (diff == 1 || diff == 2);
    }

    private int findMissingNumber(Integer[] numbers) {
        int lastNumber = numbers[0];
        for (int i = 1; i < numbers.length; i++) {
            int diff = numbers[i] - lastNumber;
            if (diff == 2) {
                return numbers[i] - 1;
            }
            lastNumber = numbers[i];
        }

        return Integer.MIN_VALUE;
    }

}

Answer 3

这是一个递归的、可运行的解决方案

public class FindGaps {
  public static void main(String... args) throws Exception {
    System.out.println(gapFinder("12345789"));//6 expected
    System.out.println(gapFinder("99101"));//100 expected
    System.out.println(gapFinder("124126"));//123 expected
    System.out.println("fail expected: " + gapFinder("124125"));
    System.out.println("fail expected: " + gapFinder("123456A8"));
    System.out.println("fail expected: " + gapFinder("9910010210"));
    System.out.println("fail expected: " + gapFinder("10121416"));
  }

  public static int gapFinder(final String sequence) throws Exception {
    for (int digits = 1; digits <= sequence.length() / 2; digits++) {
      final Integer currentNumber = Integer.parseInt(sequence.substring(0, digits));
      final Integer ret = recursiveGapChecker(currentNumber + 1, sequence.substring(digits));
      if (ret != null && ret >= 0) {
        return ret;
      }
    }
    return -1;
  }

  /**
   * @return null if the sequence is validated, the missing number if a gap is found, return<0 if the sequence is invalid
   */
  private static Integer recursiveGapChecker(final Integer nextNumber, final String remainder) {
    final String numAsString = nextNumber.toString();
    final int numLength = numAsString.length();
    final Integer numPlus1 = nextNumber + 1;
    final String numPlus1AsString = numPlus1.toString();
    final int numPlus1Length = numPlus1AsString.length();
    if (remainder.isEmpty()) {
      return null;//cleanly parsed the remainer
    } else if (remainder.length() < numLength) {
      return -1;//invalid length
    } else if (remainder.startsWith(numAsString)) {
      return recursiveGapChecker(nextNumber + 1, remainder.substring(numLength));
    } else if (remainder.startsWith(numPlus1AsString)) {
      Integer ret = recursiveGapChecker(numPlus1 + 1, remainder.substring(numPlus1Length));
      if (ret == null) {
        return nextNumber;//found it!
      } else if (ret < 0) {
        return -1;//problem parsing the rest of the string
      } else {
        return -2;//found more than one gap
      }
    } else {
      return -1;//the remainder doesn't match the given number
    }
  }
}

Answer 4

如果（我假设）数字是按顺序列出的，那么一个非常简单的算法将起作用：

• 对于每个可能的数字长度1<；=d<；=第一个数字中的5：
  • 调用try(toInt(S[1 .. d]), S[d+1 .. |S|])尝试以S[1..d]编码的数字开始的数字序列。如果此序列“起作用”，则将其输出并停止

上面的主循环在d=5处停止，因为您给出了M<；=99999，但它可以很容易地与任意大的数字一起工作，只需让d一直增加到| S |

第二步（“尝试…”）这很容易，因为您已经拥有此（候选）序列中的第一个数字x，因此您可以轻松生成对应于下一个应出现的数字（即对应于x+1）的数字字符串，并将其与S的其余部分进行比较。如果对应于x+1的数字字符串与S的前几个字符不匹配，然后尝试对应于x+2的数字字符串。如果匹配，则设置一个标记，记录x+1可能是丢失的数字，然后继续。如果x+1和x+2都不匹配，或者如果x+1不匹配且标志已设置，我们知道初始值不可能正确，因此返回并让主循环尝试下一个较长的初始值：

try(x, S):
    x1str = asString(x + 1)
    x2str = asString(x + 2)
    missing = -1        # Flag value to indicate "not found"
    while |S| >= |x1str|:
        if S[1 .. |x1str|] = x1str:
            Delete first |x1str| characters of S
            x = x + 1
            x1str = asString(x + 1)
            x2str = asString(x + 2)
        else if S[1 .. |x2str|] = x2str and missing = -1:
            Delete first |x2str| characters of S
            missing = x + 1
            x = x + 2
            x1str = asString(x + 1)
            x2str = asString(x + 2)
        else
            return -1    # Flag value to indicate "invalid sequence"
    if |S| > 0 then return -1    # Some gunk was left over
    return missing

显然，您可以将“先删除…S个字符”步骤替换为只在（不变）字符串中使用偏移量，但我觉得上面的解释更容易

Answer 5

for a sequence, (3, 4, 6, 7) 
or              (13, 14, 16, 17) 
or              (113, 114, 116, 117) 

您将始终以last first==序列结束。大小（）//即7-3=4

这样，就很容易检测到正确的编号长度（至少要显著减少要检查的列表编号）

为了提高性能，您可以检查字符串（如果有）。长度可被数字长度整除，否则陷阱将是：

1230124如果只选择前3个和最后3个字符，则测试数字长度3

import java.util.*;

public class NumberGap {

    static private boolean laengeFits (String numbers, int len, int start, int stop) {
        String front = numbers.substring (start, len);
        String back  = numbers.substring (stop - len, stop);
        // System.out.printf ("front - back = %s %s\n", front, back);
        int first = Integer.parseInt (front);
        int last  = Integer.parseInt (back);
        return (last - first == numbers.length () / len);
    }

    static private boolean isCandidate (String numbers, int len) {
        return (numbers.length() % len == 0 && laengeFits (numbers, len, 0, numbers.length ()));
    }

    static List <Integer> string2ints (String snum, int i) {
        List <Integer> vals = new ArrayList<> ();
        for (int n = 0; n < snum.length (); n+= i){
             String s = snum.substring (n, n+i);
             vals.add (Integer.parseInt (s));
        }
        return vals;
    }

    static private void findGap (String numbers) {
        System.out.printf ("\nSearching for: %s \n", numbers);
        for (int i = 1; i < 6; ++i) {
            if (isCandidate (numbers, i)) {
                List <Integer> vals = string2ints (numbers, i);
                // System.out.printf ("\telems: %d :\n", vals.size ());
                List <Integer> res = new ArrayList<> ();
                for (int j = 1; j < vals.size (); ++j) {
                    if (vals.get(j) != vals.get(j-1) + 1) {
                        res.add (vals.get(j-1) + 1);
                        if (res.size () > 1) {
                           System.out.printf ("Error multiple gaps: %d %d\n", res.get (0), res.get(1));
                           break;
                        }
                    }
                }
                if (res.size() == 1) {
                    System.out.printf (" * * *   Gap: %d   * * *\n", res.get (0));
                    continue;
                }
            }
        }
    }

    public static void main(String[] args) {
        findGap ("012346789");
        findGap ("1234678910");
        findGap ("26272829313233");
        findGap ("26272829313333");
        findGap ("9293949596979899101");
        findGap ("99101102103104105106107108109110111112");
        findGap ("596597598600601602");
        findGap ("989999009901990299049905");
        findGap ("98999901990299039904990599069907");
        findGap ("9998999910000100011000210004");
    }
}

我首先写了一个Scala解决方案，一行代码，承认了一条很长的线：

(1 to 5).map (i => {s.sliding (i, i)}.map (_.toInt).toVector).filter (v => (v(v.size - 1) - v(0) == v.size)).flatten .sliding (2, 1).filter {l => l(0) != l(1)-1}.map {l => l(1) -1}.mkString (":")

或可读性更好：

(1 to 5).map (i => {s.sliding (i, i)}.
    map (_.toInt).toVector).
    filter (v => (v(v.size - 1) - v(0) == v.size)).
    flatten.
    sliding (2, 1).
    filter {l => l(0) != l(1)-1}.
    map {l => l(1) -1}.mkString (":")

s是要分析的字符串。集合函数集更加丰富，从数组到列表或向量的转换不那么麻烦，因为一个方便的函数只在这里定义，另一个函数只在那里定义。在幕后流畅地将int转换为整数

Answer 6

我认为您可以改进此代码，但请尝试：

public static void main(String[] args) {
    String pattern = "(\\d{%s})(\\d{0,%s})";
    String toVerify = "9979989991000100110021004";
    String toVerifyCopy = toVerify;

    List<Integer> items = new LinkedList<>();

    Integer found = null;

    for (int i = 1; i < toVerifyCopy.length(); i++) {
        int first = 0;
        Integer second = 0;

        int secondSize = i;
        boolean isSize = false;

        for (int j = 1; j < i + 2; j++) {
            Pattern patron = Pattern.compile(String.format(pattern, i, j));

            Matcher matcher = patron.matcher(toVerifyCopy);

            if (matcher.find()) {
                first = Integer.parseInt(matcher.group(1));
                second = Integer.parseInt(matcher.group(2));

                if (second == first + 1) {
                    secondSize = j;
                    isSize = true;

                    j++;
                } else if (second == first + 2) {
                    found = first + 1;
                    secondSize = j;

                    isSize = true;
                    j++;
                } else {
                    isSize = false;
                }
            }
        }

        if (isSize) {
            toVerifyCopy = toVerifyCopy.substring(i);
            i = i - 1;

            if (items.size() < 2 ||
                toVerifyCopy.length() == i + secondSize) {
                items.add(first);
            }

            items.add(second);
        } else {
            if (items.size() > 0) {
                if (first == items.get(items.size() - 1)) {
                    items.clear();

                    toVerifyCopy = toVerify;
                }
            }
        }
    }

    for (Integer item : items) {
        System.out.println(item);
    }

    if (found != null) {
        System.out.println("Found: " + found);
    }
}