我刚刚搞砸了一次面试，而且我的面试问题几乎毫无进展。
给定一个数，找出下一个与之完全相同的更大的数 作为原始数字的数字集。例如:给定38276返回 38627
我想从找到第一个比个位小的数字的下标开始。然后我将旋转子集中的最后一个数字，这样它是由相同的数字组成的下一个最大的数字，但卡住了。
面试官还建议我试着一次换一个数字，但我搞不懂算法，只能盯着屏幕看20-30分钟。不用说，我想我还得继续找工作。
当前回答
@BlueRaja算法的javascript实现。
var Bar = function(num){
num = num.toString();
var max = 0;
for(var i=num.length-2; i>0; i--){
var numArray = num.substr(i).split("");
max = Math.max.apply(Math,numArray);
if(numArray[0]<max){
numArray.sort(function(a,b){return a-b;});
numArray.splice(-1);
numArray = numArray.join("");
return Number(num.substr(0,i)+max+numArray);
}
}
return -1;
};
其他回答
你的想法
我想从找到第一个比个位小的数字的下标开始。然后我将旋转子集中的最后一个数字，这样它是由相同的数字组成的下一个最大的数字，但卡住了。
其实还不错。您不仅要考虑最后一位数字，还要考虑所有比当前考虑的不那么重要的数字。在此之前，我们有一个单调的数字序列，即最右边的数字比它右边的邻居小。把
1234675
^
下一个有相同数字的大数是
1234756
将找到的数字交换为最后一位数字(考虑的数字中最小的数字)，其余数字按递增顺序排列。
如果你用c++编程，你可以使用next_permutation:
#include <algorithm>
#include <string>
#include <iostream>
int main(int argc, char **argv) {
using namespace std;
string x;
while (cin >> x) {
cout << x << " -> ";
next_permutation(x.begin(),x.end());
cout << x << "\n";
}
return 0;
}
这是我在Ruby中的实现:
def foo num
num = num.to_s.chars.map(&:to_i)
return num.join.to_i if num.size < 2
for left in (num.size-2).downto(0) do
for right in (num.size-1).downto(left+1) do
if num[right]>num[left]
num[left],num[right] = num[right],num[left]
return (num[0..left] + num[left+1..num.size-1].sort).join.to_i
end
end
end
return num.join.to_i
end
p foo 38276
#will print: 38627
#include<bits/stdc++.h>
using namespace std;
int main()
{
int i,j,k,min,len,diff,z,u=0,f=0,flag=0;
char temp[100],a[100]`enter code here`,n;
min=9999;
//cout<<"Enter the number\n";
cin>>a;
len=strlen(a);
for(i=0;i<len;i++)
{
if(a[i]<a[i+1]){flag=1;break;}
}
if(flag==0){cout<<a<<endl;}
else
{
for(i=len-1;i>=0;i--)if(((int)a[i-1])<((int)a[i]))break;
for(k=0;k<i-1;k++)cout<<a[k];
for(j=i;j<len;j++)
{
if(((int)a[j]-48)-((int)a[i-1]-48)>0)
{
diff=((int)a[j]-48)-((int)a[i-1]-48);
if(diff<min){n=a[j];min=diff;}
}
}
cout<<n;
for(z=i-1;z<len;z++)
{
temp[u]=a[z];
u++;
}
temp[u]='\0';
sort(temp,temp+strlen(temp));
for(z=0;z<strlen(temp);z++){if(temp[z]==n&&f==0){f=1;continue;}cout<<temp[z];}
}
return 0;
}
我很确定你的面试官是想委婉地让你说出这样的话:
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);
不一定是最有效或最优雅的解决方案，但它在两个循环中解决了所提供的示例，并像他建议的那样一次交换一个数字。
