我刚刚搞砸了一次面试,而且我的面试问题几乎毫无进展。
给定一个数,找出下一个与之完全相同的更大的数 作为原始数字的数字集。例如:给定38276返回 38627
我想从找到第一个比个位小的数字的下标开始。然后我将旋转子集中的最后一个数字,这样它是由相同的数字组成的下一个最大的数字,但卡住了。
面试官还建议我试着一次换一个数字,但我搞不懂算法,只能盯着屏幕看20-30分钟。不用说,我想我还得继续找工作。
我刚刚搞砸了一次面试,而且我的面试问题几乎毫无进展。
给定一个数,找出下一个与之完全相同的更大的数 作为原始数字的数字集。例如:给定38276返回 38627
我想从找到第一个比个位小的数字的下标开始。然后我将旋转子集中的最后一个数字,这样它是由相同的数字组成的下一个最大的数字,但卡住了。
面试官还建议我试着一次换一个数字,但我搞不懂算法,只能盯着屏幕看20-30分钟。不用说,我想我还得继续找工作。
当前回答
I didn't know anything about the brute force algorithm when answering this question, so I approached it from another angle. I decided to search the entire range of possible solutions that this number could possibly be rearranged into, starting from the number_given+1 up to the max number available (999 for a 3 digit number, 9999 for 4 digits, etc.). I did this kind of like finding a palindrome with words, by sorting the numbers of each solution and comparing it to the sorted number given as the parameter. I then simply returned the first solution in the array of solutions, as this would be the next possible value.
下面是我的Ruby代码:
def PermutationStep(num)
a = []
(num.to_s.length).times { a.push("9") }
max_num = a.join('').to_i
verify = num.to_s.split('').sort
matches = ((num+1)..max_num).select {|n| n.to_s.split('').sort == verify }
if matches.length < 1
return -1
else
matches[0]
end
end
其他回答
至少,这里有几个基于字符串的暴力解决方案的例子,你应该能够马上想到:
38276中的数字排序为23678
38627排序的数字列表是23678
蛮力增量,排序和比较
沿着蛮力解决方案将转换为字符串 然后用这些数字强行找出所有可能的数字。
从它们中创建int,把它们放在一个列表中并排序, 获取目标条目之后的下一个条目。
如果你花了30分钟在这个问题上,却没有想出一个蛮力的方法,我也不会雇用你。
在商业世界中,一个不优雅、缓慢和笨拙但能完成工作的解决方案总是比没有解决方案更有价值,事实上,这几乎描述了所有不优雅、缓慢和笨拙的商业软件。
我很确定你的面试官是想委婉地让你说出这样的话:
local number = 564321;
function split(str)
local t = {};
for i = 1, string.len(str) do
table.insert(t, str.sub(str,i,i));
end
return t;
end
local res = number;
local i = 1;
while number >= res do
local t = split(tostring(res));
if i == 1 then
i = #t;
end
t[i], t[i-1] = t[i-1], t[i];
i = i - 1;
res = tonumber(table.concat(t));
end
print(res);
不一定是最有效或最优雅的解决方案,但它在两个循环中解决了所提供的示例,并像他建议的那样一次交换一个数字。
你的想法
我想从找到第一个比个位小的数字的下标开始。然后我将旋转子集中的最后一个数字,这样它是由相同的数字组成的下一个最大的数字,但卡住了。
其实还不错。您不仅要考虑最后一位数字,还要考虑所有比当前考虑的不那么重要的数字。在此之前,我们有一个单调的数字序列,即最右边的数字比它右边的邻居小。把
1234675
^
下一个有相同数字的大数是
1234756
将找到的数字交换为最后一位数字(考虑的数字中最小的数字),其余数字按递增顺序排列。
这是另一个Java实现,可以开箱即用,并通过测试完成。 这个解决方案是O(n)个空间和时间,使用老式的动态规划。
如果你想用蛮力,有两种蛮力:
排列所有的东西,然后选择最小值更高的:O(n!) 与此实现类似,但不是DP,而是强制填充的步骤 indexToIndexOfNextSmallerLeft映射将在O(n²)中运行。
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import org.junit.Test;
import static org.junit.Assert.assertEquals;
public class NextHigherSameDigits {
public long next(final long num) {
final char[] chars = String.valueOf(num).toCharArray();
final int[] digits = new int[chars.length];
for (int i = 0; i < chars.length; i++) {
digits[i] = Character.getNumericValue(chars[i]);
}
final Map<Integer, Integer> indexToIndexOfNextSmallerLeft = new HashMap<>();
indexToIndexOfNextSmallerLeft.put(1, digits[1] > digits[0] ? 0 : null);
for (int i = 2; i < digits.length; i++) {
final int left = digits[i - 1];
final int current = digits[i];
Integer indexOfNextSmallerLeft = null;
if (current > left) {
indexOfNextSmallerLeft = i - 1;
} else {
final Integer indexOfnextSmallerLeftOfLeft = indexToIndexOfNextSmallerLeft.get(i - 1);
final Integer nextSmallerLeftOfLeft = indexOfnextSmallerLeftOfLeft == null ? null :
digits[indexOfnextSmallerLeftOfLeft];
if (nextSmallerLeftOfLeft != null && current > nextSmallerLeftOfLeft) {
indexOfNextSmallerLeft = indexOfnextSmallerLeftOfLeft;
} else {
indexOfNextSmallerLeft = null;
}
}
indexToIndexOfNextSmallerLeft.put(i, indexOfNextSmallerLeft);
}
Integer maxOfindexOfNextSmallerLeft = null;
Integer indexOfMinToSwapWithNextSmallerLeft = null;
for (int i = digits.length - 1; i >= 1; i--) {
final Integer indexOfNextSmallerLeft = indexToIndexOfNextSmallerLeft.get(i);
if (maxOfindexOfNextSmallerLeft == null ||
(indexOfNextSmallerLeft != null && indexOfNextSmallerLeft > maxOfindexOfNextSmallerLeft)) {
maxOfindexOfNextSmallerLeft = indexOfNextSmallerLeft;
if (maxOfindexOfNextSmallerLeft != null && (indexOfMinToSwapWithNextSmallerLeft == null ||
digits[i] < digits[indexOfMinToSwapWithNextSmallerLeft])) {
indexOfMinToSwapWithNextSmallerLeft = i;
}
}
}
if (maxOfindexOfNextSmallerLeft == null) {
return -1;
} else {
swap(digits, indexOfMinToSwapWithNextSmallerLeft, maxOfindexOfNextSmallerLeft);
reverseRemainingOfArray(digits, maxOfindexOfNextSmallerLeft + 1);
return backToLong(digits);
}
}
private void reverseRemainingOfArray(final int[] digits, final int startIndex) {
final int[] tail = Arrays.copyOfRange(digits, startIndex, digits.length);
for (int i = tail.length - 1; i >= 0; i--) {
digits[(digits.length - 1) - i] = tail[i];
}
}
private void swap(final int[] digits, final int currentIndex, final int indexOfNextSmallerLeft) {
int temp = digits[currentIndex];
digits[currentIndex] = digits[indexOfNextSmallerLeft];
digits[indexOfNextSmallerLeft] = temp;
}
private long backToLong(int[] digits) {
StringBuilder sb = new StringBuilder();
for (long i : digits) {
sb.append(String.valueOf(i));
}
return Long.parseLong(sb.toString());
}
@Test
public void test() {
final long input1 = 34722641;
final long expected1 = 34724126;
final long output1 = new NextHigherSameDigits().next(input1);
assertEquals(expected1, output1);
final long input2 = 38276;
final long expected2 = 38627;
final long output2 = new NextHigherSameDigits().next(input2);
assertEquals(expected2, output2);
final long input3 = 54321;
final long expected3 = -1;
final long output3 = new NextHigherSameDigits().next(input3);
assertEquals(expected3, output3);
final long input4 = 123456784987654321L;
final long expected4 = 123456785123446789L;
final long output4 = new NextHigherSameDigits().next(input4);
assertEquals(expected4, output4);
final long input5 = 9999;
final long expected5 = -1;
final long output5 = new NextHigherSameDigits().next(input5);
assertEquals(expected5, output5);
}
}
public static void findNext(long number){
/* convert long to string builder */
StringBuilder s = new StringBuilder();
s.append(number);
int N = s.length();
int index=-1,pivot=-1;
/* from tens position find the number (called pivot) less than the number in right */
for(int i=N-2;i>=0;i--){
int a = s.charAt(i)-'0';
int b = s.charAt(i+1)-'0';
if(a<b){
pivot = a;
index =i;
break;
}
}
/* if no such pivot then no solution */
if(pivot==-1) System.out.println(" No such number ")
else{
/* find the minimum highest number to the right higher than the pivot */
int nextHighest=Integer.MAX_VALUE, swapIndex=-1;
for(int i=index+1;i<N;i++){
int a = s.charAt(i)-'0';
if(a>pivot && a<nextHighest){
nextHighest = a;
swapIndex=i;
}
}
/* swap the pivot and next highest number */
s.replace(index,index+1,""+nextHighest);
s.replace(swapIndex,swapIndex+1,""+pivot);
/* sort everything to right of pivot and replace the sorted answer to right of pivot */
char [] sort = s.substring(index+1).toCharArray();
Arrays.sort(sort);
s.replace(index+1,N,String.copyValueOf(sort));
System.out.println("next highest number is "+s);
}
}