时间戳

首页 > 解决方案 > 我正在做一个关于代码大战的任务，但它不起作用

java - 我正在做一个关于代码大战的任务，但它不起作用

问题描述

我在代码大战 4 kuy 上做了一项任务（下一个具有相同数字的更大数字），在我看来，问题甚至不在我的代码中，而是在网站上。当您单击测试时，程序可以正常运行，但当您单击尝试时，它不会。

以下是说明：

Create a function that takes a positive integer and returns the next bigger number that can be formed by rearranging its digits. For example:

12 ==> 21
513 ==> 531
2017 ==> 2071
nextBigger(num: 12)   // returns 21
nextBigger(num: 513)  // returns 531
nextBigger(num: 2017) // returns 2071

9 ==> -1
111 ==> -1
531 ==> -1

这是我的代码：

public static long nextBiggerNumber(long n) {

        int count = 1;
        char tmp;
        char[] array = Long.toString(n).toCharArray();

        for (int i = 0; i < Long.toString(n).length() - 1; i++) {
            if (array[array.length - (count + 1)] < array[array.length - count]) {
                tmp = array[array.length - count];
                array[array.length - count] = array[array.length - (count + 1)];
                array[array.length - (count + 1)] = tmp;
                break;
            }
            count++;
            tmp = 0;
        }
        if (Long.parseLong(String.valueOf(array)) == n) return -1;

/********************************************************************************************************************************/

        char[] second = new char[count];
        String.valueOf(array).getChars(array.length - count , array.length, second, 0);

        int N = 1;
        for (int i = 0; i < second.length - 1; i++) {
            for (int j = N; j < second.length; j++) {
                if (second[i] > second[j]){
                    tmp = second[i];
                    second[i] = second[j];
                    second[j] = tmp;
                }
            }
            N++;
        }
        String mainString = String.valueOf(array).substring(0,array.length - count) + String.valueOf(second);

        long mainLong = Long.parseLong(mainString);

        System.out.println(mainLong);
        return mainLong;
    }

这是错误：

Test Results:
 KataTests
 basicTests
 randomTests
 Log
335686145
expected:<335685146> but was:<335686145>
 Stack Trace
Completed in 6ms
 biggerTests
 Log
123456798
1234567908
59884848493558
expected:<59884848483559> but was:<59884848493558>
 Stack Trace
Completed in 1ms
Completed in 30ms

也许我不明白一些东西，但似乎网站上的程序本身无法正常工作，因为在 randomTests 和更大的Tests 中显示的数字不超过第一个，但更少。

标签： java

解决方案

问题

说abcdef的下一个数字将类似于abcefd，具有固定前缀。

应该注意的是，1357 是最低值（增加），而 7531 是最高值（减少）。

看着

467468
467486   decreasing order 86 = largest, replace 4 with next higher 6 and inc 48
467648
467684
467846
467864
...

所以算法是（让人想起带有进位的学校加法）：

  • 取最后递减（最高）的数字，例如85441in [...][2]85441。
  • 下一个更高的数字2是4
  • 创建...[4][12458]具有递增数字（最低）的下一个数字。

编码

我不会通过解决方案破坏您的编码工作，但总的来说：

迭代必须从递减的最高索引开始。

public static long nextBiggerNumber(long num) {
    char[] digits = Long.toString(num).toCharArray();
    int n = digits.length;

    int i = n - 1;
    --i;
    while (i >= 0 && digits[i] >= digits[i + 1]) {
        --i;
    }
    if (i < 0) {
        return -1L; // No higher number.
    }

    // Now digits[i] must be replaced with next higher digit [>i].
    // Mind that digits[i+1]..[n-1] are decreasing.
    // And then at [i+1]..[n-1] everything must be increasing.
    ...
    return Long.valueOf(new String(digits));
}

必须注意重复数字（>=，下一个更高的数字）。

完整的解决方案，根据要求：

public static long nextBiggerNumber(long num) {
    char[] digits = Long.toString(num).toCharArray();
    int n = digits.length;

    int i = n - 1;
    --i;
    while (i >= 0 && digits[i] >= digits[i + 1]) {
        --i;
    }
    if (i < 0) {
        return -1L; // No higher number.
    }

    // Now digits[i] must be replaced with next higher digit [>i].
    // Mind that digits[i+1]..[n-1] are decreasing.
    // And then at [i+1]..[n-1] everything must be increasing.

    // Swap middle digit with a higher one.
    char middle = digits[i];
    for (int j = n - 1; j > i; --j) { // start with smalles in decreasing right subarray.
        if (digits[j] > middle) {
            digits[i] = digits[j];
            digits[j] = middle;
            // Right subarray still is decreasing.
            break;
        }
    }
    // Reverse right to lowest value (increasing subarray).
    for (int k = i + 1, j = n - 1; k < j; ++k, --j) {
        char digit = digits[k];
        digits[k] = digits[j];
        digits[j] = digit;
    }

    return Long.valueOf(new String(digits));
}

为了测试这一点，单元测试将是理想的（可以检查下一个更大的数字确实更大），这里是 main.

public static void main(String[] args) {
    long[] nums = {24354L, 3832L };
    for (long num : nums) {
        System.out.printf("* %d%n", num);
        long numi = num;
        do {
            numi = nextBiggerNumber(numi);
            if (numi == -1L) {
                break;
            }
            System.out.printf("  --> %d%n", numi);
        } while (numi != -1L);
    }
}

编译；测试结果只是敷衍了事。

这样的问题应该充分“可视化”——在纸上玩电脑。

ASCII 艺术

                  ___
Number           |   |___
                 |   |   |___ ___
              ___|...|...|...|...|.......
             | a |   |   |   | b |___
             |   |   |   |   |   |   |___
...          |   |   |   |   |   |   |   |
_____________|___|___|___|___|___|___|___|
               ^               ^ 
               '------swap-----'
               
                  ___
                 |   |___
              ___|   |   |___ 
             |...|...|...|...|___........
             | b |   |   |   | a |___
             |   |   |   |   |   |   |___
...          |   |   |   |   |   |   |   |
_____________|___|___|___|___|___|___|___|
                   [                   ] 
                   '------reverse------'                   
               
                                      ___
Next Number                       ___|   |
              ___             ___|   |   |
             |   |....... ___|...|...|...|
             | b |    ___| a |   |   |   |
             |   |___|   |   |   |   |   |
...          |   |   |   |   |   |   |   |
_____________|___|___|___|___|___|___|___|
  1. 在a数组减少之后，该子数组中没有更高的组合。
  2. 因此，下一个更高的组合涉及所有 from 和包括a。
  3. 取b> a，其余的增加将给出下一个数字。

推荐阅读