我刚刚搞砸了一次面试，而且我的面试问题几乎毫无进展。
给定一个数，找出下一个与之完全相同的更大的数 作为原始数字的数字集。例如:给定38276返回 38627
我想从找到第一个比个位小的数字的下标开始。然后我将旋转子集中的最后一个数字，这样它是由相同的数字组成的下一个最大的数字，但卡住了。
面试官还建议我试着一次换一个数字，但我搞不懂算法，只能盯着屏幕看20-30分钟。不用说，我想我还得继续找工作。
当前回答
int t,k,num3,num5;
scanf("%d",&t);
int num[t];
for(int i=0;i<t;i++){
scanf("%d",&num[i]);
}
for(int i=0;i<t;i++){
k=(((num[i]-1)/3)+1);
if(k<0)
printf("-1");
else if(num[i]<3 || num[i]==4 || num[i]==7)
printf("-1");
else{
num3=3*(2*num[i] - 5*k);
num5=5*(3*k -num[i]);
for(int j=0;j<num3;j++)
printf("5");
for(int j=0;j<num5;j++)
printf("3");
}
printf("\n");
}
其他回答
至少，这里有几个基于字符串的暴力解决方案的例子，你应该能够马上想到:
38276中的数字排序为23678
38627排序的数字列表是23678
蛮力增量，排序和比较
沿着蛮力解决方案将转换为字符串 然后用这些数字强行找出所有可能的数字。
从它们中创建int，把它们放在一个列表中并排序， 获取目标条目之后的下一个条目。
如果你花了30分钟在这个问题上，却没有想出一个蛮力的方法，我也不会雇用你。
在商业世界中，一个不优雅、缓慢和笨拙但能完成工作的解决方案总是比没有解决方案更有价值，事实上，这几乎描述了所有不优雅、缓慢和笨拙的商业软件。
解决方案(在Java中)可能是以下(我相信这里的朋友可以找到更好的): 从字符串的末尾开始交换数字，直到得到一个更高的数字。 也就是说，首先从下位开始移动。然后到达下一个更高的地方，直到你到达下一个更高的地方。 然后对剩下的进行排序。 在你的例子中，你会得到:
38276 --> 38267 (smaller) --> 38627 Found it
^ ^ ^
public static int nextDigit(int number){
String num = String.valueOf(number);
int stop = 0;
char [] chars = null;
outer:
for(int i = num.length() - 1; i > 0; i--){
chars = num.toCharArray();
for(int j = i; j > 0; j--){
char temp = chars[j];
chars[j] = chars[j - 1];
chars[j - 1] = temp;
if(Integer.valueOf(new String(chars)) > number){
stop = j;
break outer;
}
}
}
Arrays.sort(chars, stop, chars.length);
return Integer.valueOf(new String(chars));
}
有很多不错的答案，但我没有找到一个像样的Java实现。以下是我的观点:
public void findNext(int[] nums) {
int i = nums.length - 1;
// nums[i - 1] will be the first non increasing number
while (i > 0 && nums[i] <= nums[i - 1]) {
i--;
}
if (i == 0) {
System.out.println("it has been the greatest already");
} else {
// Find the smallest digit in the second sequence that is larger than it:
int j = nums.length - 1;
while (j >= 0 && nums[j] < nums[i - 1]) {
j--;
}
swap(nums, i - 1, j);
Arrays.sort(nums, i, nums.length);
System.out.println(Arrays.toString(nums));
}
}
public void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
import java.util.Scanner;
public class Big {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter the number ");
String str = sc.next();
int t=0;
char[] chars = str.toCharArray();
for(int i=str.length()-1,j=str.length()-2;j>=0;j--)
{
if((int)chars[i]>(int)chars[j])
{
t = (int)chars[i];
chars[i] = chars[j];
chars[j]=(char)t;
for(int k=j+1;k<str.length()-1;k++)
{
for(int l=k+1;l<str.length();l++)
{
if(chars[k]>chars[l])
{
int m = (int)chars[k];
chars[k] = chars[l];
chars[l]=(char)m;
}
}
}
break;
}
}
System.out.print("The next Big number is: ");
for(int i=0;i<str.length();i++){
System.out.print(chars[i]);
}
sc.close();
}
}
取一个数，把它分成几位数。如果我们有一个5位数，我们就有5位数:abcde
现在交换d和e，并与原来的数字进行比较，如果它更大，你就得到了答案。
如果它不是很大，交换e和c。现在比较，如果它更小，再次交换d和e(注意递归)，取最小的。
一直算下去，直到找到一个更大的数字。通过递归，它应该相当于9行方案，或20行c#。
