给定一个数字N，找到最小的偶数E，使得E > N。

Question

给定一个数字N，找到最小的偶数E，使得E > N。

5

给定一个数字N，找到最小的偶数E，使得E> N且N和E中的数字相同。

   Print NONE otherwise.
    Sample:
Case1
    Input
    N = 34722641 
    Output
    E = 34724126
Case2
    Input
    N = 8234961
    Output
    E = 8236194 (instead of 8236149)

我的第二个案例通过了第一个案例，但是我得到了错误的输出

public static int nextDigit(int number) {
String num = String.valueOf(number);
int stop = 0;
char[] orig_chars = null;
char[] part1 = null;
char[] part2 = null;
orig_chars = num.toCharArray();

for (int i = orig_chars.length - 1; i > 0; i--) {
    String previous = orig_chars[i - 1] + "";
    String next = orig_chars[i] + "";
    if (Integer.parseInt(previous) < Integer.parseInt(next))
{
    if (Integer.parseInt(previous) % 2 == 0) {

        String partString1 = "";
        String partString2 = "";
        for (int j = 0; j <= i - 1; j++) {
            partString1 = partString1.concat(orig_chars[j] + "");
        }
        part1 = partString1.toCharArray();
        for (int k = i; k < orig_chars.length; k++) {
            partString2 = partString2.concat(orig_chars[k] + "");
        }
        part2 = partString2.toCharArray();
        Arrays.sort(part2);
        for (int l = 0; l < part2.length; l++) {
            char temp = '0';
            if (part2[l] > part1[i - 1]) {
                temp = part1[i - 1];
                part1[i - 1] = part2[l];
                part2[l] = temp;
                break;
            }
        }
        for (int m = 0; m < part2.length; m++) {
            char replace = '0';
            if (part2[m] % 2 == 0) {
                replace = part2[m];
                for (int n = m; n < part2.length - 1; n++) {
                    part2[n] = part2[n + 1];
                }
                part2[part2.length - 1] = replace;
                break;
            }
        }

        System.out.print(part1);
        System.out.println(part2);
        System.exit(0);
        }
    }
}
     System.out.println("NONE");

  return 0;
    }

- chiru

有多少位数字N？小于10位吗？ - Pham Trung

你的第二种情况看起来是正确的输出。它符合偶数且大于输入的条件... - Jamey

4个回答

1

尝试使用Haskell编写A. Webb答案中的新算法版本：

import qualified Data.Map as M
import Data.Ord (comparing)
import Data.List (sort,maximumBy)
import Data.Maybe (fromJust)

digs :: Integral x => x -> [x]
digs 0 = []
digs x = digs (x `div` 10) ++ [x `mod` 10]

nextE n
  | e == -1   = "NONE"
  | otherwise = concatMap show $ take (ie' + 1) (M.elems s)
              ++ sort (drop (ie' + 1) (M.elems s')) ++ [r]
 where ds = M.fromList (zip [0..] (digs n))
       rightMost (-1) _  = [(-1,0),(-1,0)]
       rightMost ix   xs
         | even (x) && not (null $ filter (>x) xs) = [(x,ix),(y,iy)]
         | otherwise                               = rightMost (ix - 1) (x:xs)
        where x = fromJust (M.lookup ix ds)
              (y,iy) = minimum . filter ((>= x) . fst) 
                     $ zip xs [ix + 1..M.size ds - 1]
       [(e,ie),(l,il)] = rightMost (M.size ds - 1) []
       s = M.insert il e . M.insert ie l $ ds
       (ir,r) = maximumBy (comparing snd) . M.toList 
              . M.filter even . snd $ M.split ie s
       s' = M.delete ir s
       ie' = fromIntegral ie

main = print (map (\x -> (x,nextE x)) [34722641,8234961,13244351359135913,3579])

输出：

*Main> main
[(34722641,"34724126"),(8234961,"8236194")
,(13244351359135913,"13245111333355994"),(3579,"NONE")]
(0.02 secs, 563244 bytes)

- גלעד ברקן

参考答案现已更改为由גלעד ברקן在评论中提出的更优算法。 - A. Webb

1

许多人建议使用排列，但对于这个问题，位掩码动态规划将是另一种解决方案。

对于动态规划，数字的数量可以高达20位数字，而普通排列只能在N小于12位数字时使用。（时间限制为1秒，通常用于竞技编程）

因此，思路是从最高有效位到最低有效位开始，在每个步骤中，我们尝试找到从该位开始到末尾的最小值，在每个数字处，我们有两种情况：

如果已创建的数字已经大于N，例如N为12345，当前为23xxx。（我们需要在此情况下找到最小的xxx）。
如果数字还没有大于N，例如N为12345，我们有12xxx。

此外，在最后一位上，我们需要确定所创建的数字是偶数还是奇数。

因此，我们有简单的递归代码：

public int cal(boolean[] selected, int[] num, int digit, boolean larger) {
    //Arrays selected will tell which digit in N has already selected, 
    //int digit will tell currently, which digit we are checking
    //boolean larger tells is the number already larger than N

    if (digit + 1 == selected.length) {//Last digit
        for (int i = 0; i < selected.length; i++) {
            if (!selected[i]) {
                if (num[i] % 2 != 0) {
                    return -1; // -1 means this is an invalid value
                } else {
                    if (larger) {
                        return num[i];
                    } else {
                        return -1;
                    }
                }
            }
        }
    }
    int result = -1;
    for (int i = 0; i < selected.length; i++) {
        if (!selected[i]) {
            if (larger) {
                selected[i] = true;
                int val = (int) (num[i] * Math.pow(10, digit) + cal(selected, num, digit + 1, larger));
                if (val != -1 && (result == -1 || result > val)) {
                    result = val;
                }
            } else if (num[i] >= num[digit]) {
                int val = (int) (num[i] * Math.pow(10, digit) + cal(selected, num, digit + 1, num[i] > num[digit]));
                if (val != -1 && (result == -1 || result > val)) {
                    result = val;
                }
            }
        }
    }
    return result;
}

从这个状态开始，我们注意到实际上，boolean [] selected 可以被位掩码值替换（阅读有关位掩码的内容链接），因此我们可以通过这个数组 int [mask][larger] dp 轻松表示递归的状态。

请注意，参数 digit 不是必需的，因为我们可以通过计算剩余要选择的数字数量来轻松确定我们正在检查的数字。

最后，我们有了我们的解决方案：

import java.util.Arrays;


/**
 *
 * @author Trung Pham
 */
public class Test {

    public static void main(String[] args) {
        Test test = new Test();

        System.out.println(test.largest(2135791357913579L));

    }
    long[][] dp;

    public long largest(long N) {
        String val = "" + N;

        int[] num = new int[val.length()];
        for (int i = 0; i < num.length; i++) {
            num[i] = val.charAt(i) - '0';
         //   System.out.println(num[i] + " " + i);
        }
        dp = new long[1 << num.length][2];
        for (long[] a : dp) {
            Arrays.fill(a, -2);
        }
        return cal(0, num, 0);

    }

    public long cal(int mask, int[] num, int larger) {
        //Arrays selected will tell which digit in N has already selected, 
        //int digit will tell currently, which digit we are checking
        //int larger tells is the number already larger than N, if it is 1, it is larger, 0 is not.
        int digit = 0;
        for (int i = 0; i < num.length; i++) {
            if (((1 << i) & mask) != 0) {
                digit++;
            }
        }
        if (dp[mask][larger] != -2) {
            return dp[mask][larger];
        }
        if (digit + 1 == num.length) {//Last digit
            //System.out.println(mask + "  " + digit);
            for (int i = 0; i < num.length; i++) {
                if (((1 << i) & mask) == 0) {
                    if (num[i] % 2 != 0) {
                        return -1; // -1 means this is an invalid value
                    } else {
                        if (larger == 1) {
                            //  System.out.println(num[i] + " " + i);
                            return num[i];
                        } else {
                            return -1;
                        }
                    }
                }
            }
            return -1;
        }
        long result = -1;
        int l = num.length;
        for (int i = 0; i < num.length; i++) {
            if (((1 << i) & mask) == 0) {
                if (larger == 1) {
                    //System.out.println(num[i]* Math.pow(10,l - digit) + " " + digit);
                    long val = (long) (cal(mask | (1 << i), num, larger));


                    if (val != -1) {
                        val += num[i] * Math.pow(10, l - digit - 1);
                        if (result == -1 || result > val) {
                            result = val;
                        }
                    }
                } else if (num[i] >= num[digit]) {
                    long val = (long) (cal(mask | (1 << i), num, num[i] > num[digit] ? 1 : 0));
                    if (val != -1) {
                        val += num[i] * Math.pow(10, l - digit - 1);
                        if (result == -1 || result > val) {
                            result = val;
                        }
                    }
                }
            }
        }

        return dp[mask][larger] = result;
    }
}

注意，如果您注意到在每个数字处，我们仅选择了从0到9的值一次，则仍可以改进此解决方案，并且起始数字不能以0开头。

- Pham Trung

@גלעדברקן 你可以尝试使用9223372036854775807，这是long类型的最大值。 - Pham Trung

@גלעדברקן 排列的时间复杂度为O(n!)，在这种情况下将是18！。但使用动态规划和位掩码，则为O(n*(2^(n + 1)))，其中n是数字的数量。 - Pham Trung

@PhamTrung 在我的回答中，Clojure 实现大约需要 0.3 毫秒计算出结果为 9223372036854775870（必须调整 digits->long，因为答案比 long 还要大）。该实现并没有生成所有排列，只是按顺序生成下一个（如果不是偶数，则生成下一个等等）。 - A. Webb

@A.Webb，您的解决方案与生成所有排列有何不同？（抱歉，我不了解Clojure），所以您是从N开始生成并向前移动一个排列对吗？ - Pham Trung

1

它只生成N和第一个偶排列之间的排列数。伪代码算法在维基百科文章中链接。如果d是数字的数量，则查找下一个排列的复杂度为O(d)。我不知道在最坏情况下需要遍历多少个排列才能找到一个偶数排列，但在某些输入上可能会非常糟糕。 - A. Webb

显示剩余4条评论

-1

结果为“无”的情况：

从给定的数字中找出最小偶数位数（0、2、4、6、8）。让这个数字为x。
取其他数字，按降序排序。假设这个子字符串是S。

E = S + x（此处+表示连接）

如果在步骤1中找不到任何偶数，则不存在这样的数字。
如果步骤2后E≤N，则不存在这样的数字。

由于只有5个可能的数字可以放置在E的最后一位，因此我们首先考虑每个数字。让当前的偶数数字为e。我们将扫描N以查找e是否出现。如果N中没有e，则跳过。否则，我们删除N中的1个e并将其添加到E的末尾。假设剩下的数字连接到E1。

如果e > N % 10，则我们需要找到E1的排列，使得E1> = N / 10且E1最小。如果e <= N％10，则我们需要E1的排列，使得E1> N / 10并且E1是每个这样的排列中最小的。因此，问题归结为查找数字E1的排列，该排列大于或等于E1（根据e的值）且最小。

您可以从这里开始解决此问题，因为它只需要从这里进行一些仔细的编码即可解决下一个问题的部分。

- Fallen

2

-1：这是错误的。如果您将最小数字放在最后，那么您将在更高位数上拥有一个更大的数字，从而导致更大的数字。即使在第二个示例中也显然是错误的。 - IVlad

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- A. Webb · Accepted Answer

首先的想法是生成下一个排列，直到找到一个偶数排列。这种方法对小输入或者当附近有偶数排列时效果很好，但对于大的输入，如2135791357913579，需要发生许多排列才能将唯一的偶数数字移动到正确位置。

גלעד ברקן提出了一个补丁，经过小调整即可提供更优秀的算法。

与下一个排列算法一样，我们找到索引i和j，其中ith数字小于jth数字。当我们交换这些数字时，会得到比N更大的数字。
应用额外的约束条件，即在交换后i右侧存在一个偶数。
选取索引右侧最大的偶数（可能不是刚刚交换的数字），将其移动到末尾。这保证了偶数性。
然后按升序对中间剩余数字进行排序。这提供了可用的最小排列。

Clojure中的算法可以编写如下。我试图坚持比较命令式的风格。看看你能否翻译。

(defn num->digits [n] (mapv #(Character/getNumericValue %) (str n)))

(defn digits->num [v] (when (seq v) (read-string (apply str v))))

(defn swap 
  "Swap elements at index i and j in vector v"
  [v i j]
  (assoc (assoc v i (v j)) j (v i)))

(defn find-max-where
  "Find index i in vector v such that (v i) is the largest satisfying pred"
  [pred v] 
  (first 
    (reduce-kv 
      (fn [[k m] i x] 
        (if (and m (> m x)) 
          [k m] 
          (if (pred x) [i x] [k m]))) 
      [nil nil] 
      v)))

(defn next-even-perm [v] 
  (->>
    (for [j (range (count v))
          i (range j) 
          :when (< (v i) (v j))
          :let [v (swap v i j)
                k (find-max-where even? (vec (subvec v (inc i))))]
          :when k
          :let [v (swap v (+ (inc i) k) (dec (count v)))]] 
      (concat (subvec v 0 (inc i)) 
              (sort (subvec v (inc i) (dec (count v)))) 
              [(peek v)])) 
    (map vec) sort first))

(defn next-even-num [n] (-> n num->digits next-even-perm digits->num))

提供的示例：

 (next-even-num 34722641) 
 ;=> 34724126

 (next-even-num 8234961)
 ;=> 8236194

 (next-even-num 4321) 
 ;=> nil (no solution)

以前算法的难点

(time (next-even-num 2135791357913579))
; "Elapsed time: 1.598446 msecs"
;=> 3111335557779992

(time (next-even-num 13244351359135913))
; "Elapsed time: 1.713501 msecs"
;=> 13245111333355994

(time (next-even-num 249999977777555553333311111N))
; "Elapsed time: 1.874579 msecs"
;=> 251111133333555577777999994N

最新的编辑修复了一个问题，我们之前总是希望在向右移动时与偶数相交换，而不仅仅是想要与右侧的任何偶数交换，无论它是否参与到交换中。例如，以下示例在上一次编辑中失败，现在已被修复。

(next-even-num 1358) 
;=> 1538