我刚刚搞砸了一次面试,而且我的面试问题几乎毫无进展。
给定一个数,找出下一个与之完全相同的更大的数 作为原始数字的数字集。例如:给定38276返回 38627
我想从找到第一个比个位小的数字的下标开始。然后我将旋转子集中的最后一个数字,这样它是由相同的数字组成的下一个最大的数字,但卡住了。
面试官还建议我试着一次换一个数字,但我搞不懂算法,只能盯着屏幕看20-30分钟。不用说,我想我还得继续找工作。
我刚刚搞砸了一次面试,而且我的面试问题几乎毫无进展。
给定一个数,找出下一个与之完全相同的更大的数 作为原始数字的数字集。例如:给定38276返回 38627
我想从找到第一个比个位小的数字的下标开始。然后我将旋转子集中的最后一个数字,这样它是由相同的数字组成的下一个最大的数字,但卡住了。
面试官还建议我试着一次换一个数字,但我搞不懂算法,只能盯着屏幕看20-30分钟。不用说,我想我还得继续找工作。
当前回答
给定n位数字加9。然后检查它是否在限制范围内(第一个(n+1)位数)。如果是,则检查新号码中的数字是否与原号码中的数字相同。 重复加9,直到两个条件都为真。 当数字超过限制时停止算法。
对于这种方法,我想不出一个与之相矛盾的测试用例。
其他回答
一个几乎相同的问题出现了Code Jam问题,这里有一个解决方案:
http://code.google.com/codejam/contest/dashboard?c=186264#s=a&a=1
下面用一个例子总结一下这个方法:
34722641
A.将数字序列分成两部分,使右边的部分尽可能长,同时保持递减顺序:
34722 641
(如果整个数字是递减的,就没有比这个数字更大的数字了。)
在这一点上,你知道没有从左边开始的更大的数了,因为右边的剩余数字已经尽可能大了。
责任。选择第一个序列的最后一位:
3472(2) 641
B.2。找出第二个序列中比它大的最小的数字:
3472(2) 6(4)1
你要做的就是找到左边可能的最小增量。
B.3。交换:
3472(2) 6(4)1
->
3472(4) 6(2)1
->
34724 621
C.将第二个序列按递增顺序排序:
34724 126
d .完成了!
34724126
你把这个数字分开,这样你就知道没有更大的数字具有相同的左边部分,你把左边部分增加了尽可能小的量,你让剩下的右边部分尽可能小,所以你可以确保这个新数字是用相同的数字集合可以得到的最小的更大的数字。
function foo(num){
sortOld = num.toString().split("").sort().join('');
do{
num++;
sortNew = num.toString().split("").sort().join('');
}while(sortNew!==sortOld);
return num;
}
只是使用python的另一个解决方案:
def PermutationStep(num):
if sorted(list(str(num)), reverse=True) == list(str(num)):
return -1
ls = list(str(num))
n = 0
inx = 0
for ind, i in enumerate(ls[::-1]):
if i < n:
n = i
inx = -(ind + 1)
break
n = i
ls[inx], ls[inx + 1] = ls[inx + 1], ls[inx]
nl = ls[inx::-1][::-1]
ln = sorted(ls[inx+1:])
return ''.join(nl) + ''.join(ln)
print PermutationStep(23514)
输出:
23541
private static int GetNextHigherNumber(int num)
{
//given 38276 return 38627
string numberstring = num.ToString();
char[] sNum = numberstring.ToCharArray();
for (int i = sNum.Length - 1; i > 0; i--)
{
for (int j = i - 1; j > 0; j--)
{
if (sNum[i] > sNum[j])
{
for (int x = i; x > j; x--)
{
char chr = sNum[x];
sNum[x] = sNum[x - 1];
sNum[x - 1] = chr;
}
i = 0;
break;
}
}
}
numberstring = string.Empty;
for(int x= 0 ; x<sNum.Length;x++)
{
numberstring += sNum[x].ToString();
}
return Convert.ToInt32(numberstring);
}
至少,这里有几个基于字符串的暴力解决方案的例子,你应该能够马上想到:
38276中的数字排序为23678
38627排序的数字列表是23678
蛮力增量,排序和比较
沿着蛮力解决方案将转换为字符串 然后用这些数字强行找出所有可能的数字。
从它们中创建int,把它们放在一个列表中并排序, 获取目标条目之后的下一个条目。
如果你花了30分钟在这个问题上,却没有想出一个蛮力的方法,我也不会雇用你。
在商业世界中,一个不优雅、缓慢和笨拙但能完成工作的解决方案总是比没有解决方案更有价值,事实上,这几乎描述了所有不优雅、缓慢和笨拙的商业软件。