我刚刚搞砸了一次面试,而且我的面试问题几乎毫无进展。
给定一个数,找出下一个与之完全相同的更大的数 作为原始数字的数字集。例如:给定38276返回 38627
我想从找到第一个比个位小的数字的下标开始。然后我将旋转子集中的最后一个数字,这样它是由相同的数字组成的下一个最大的数字,但卡住了。
面试官还建议我试着一次换一个数字,但我搞不懂算法,只能盯着屏幕看20-30分钟。不用说,我想我还得继续找工作。
我刚刚搞砸了一次面试,而且我的面试问题几乎毫无进展。
给定一个数,找出下一个与之完全相同的更大的数 作为原始数字的数字集。例如:给定38276返回 38627
我想从找到第一个比个位小的数字的下标开始。然后我将旋转子集中的最后一个数字,这样它是由相同的数字组成的下一个最大的数字,但卡住了。
面试官还建议我试着一次换一个数字,但我搞不懂算法,只能盯着屏幕看20-30分钟。不用说,我想我还得继续找工作。
当前回答
#include<stdio.h>
#include<cstring>
#include<iostream>
#include<string.h>
#include<sstream>
#include<iostream>
using namespace std;
int compare (const void * a, const void * b)
{
return *(char*)a-*(char*)b;
}
/*-----------------------------------------------*/
int main()
{
char number[200],temp;
cout<<"please enter your number?"<<endl;
gets(number);
int n=strlen(number),length;
length=n;
while(--n>0)
{
if(number[n-1]<number[n])
{
for(int i=length-1;i>=n;i--)
{
if(number[i]>number[n-1])
{
temp=number[i];
number[i]=number[n-1];
number[n-1]=temp;
break;
}
}
qsort(number+n,length-n,sizeof(char),compare);
puts(number);
return 0;
}
}
cout<<"sorry itz the greatest one :)"<<endl;
}
其他回答
只是使用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
至少,这里有几个基于字符串的暴力解决方案的例子,你应该能够马上想到:
38276中的数字排序为23678
38627排序的数字列表是23678
蛮力增量,排序和比较
沿着蛮力解决方案将转换为字符串 然后用这些数字强行找出所有可能的数字。
从它们中创建int,把它们放在一个列表中并排序, 获取目标条目之后的下一个条目。
如果你花了30分钟在这个问题上,却没有想出一个蛮力的方法,我也不会雇用你。
在商业世界中,一个不优雅、缓慢和笨拙但能完成工作的解决方案总是比没有解决方案更有价值,事实上,这几乎描述了所有不优雅、缓慢和笨拙的商业软件。
回答在java与一个更多的条件添加
Next number should also be an Even number 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(); System.out.println("vivek c r"); 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; }
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
我知道这是一个非常老的问题,但我仍然没有在c#中找到简单的代码。这可能会对参加面试的男士有所帮助。
class Program
{
static void Main(string[] args)
{
int inputNumber = 629;
int i, currentIndexOfNewArray = 0;
int[] arrayOfInput = GetIntArray(inputNumber);
var numList = arrayOfInput.ToList();
int[] newArray = new int[arrayOfInput.Length];
do
{
int temp = 0;
int digitFoundAt = 0;
for (i = numList.Count; i > 0; i--)
{
if (numList[i - 1] > temp)
{
temp = numList[i - 1];
digitFoundAt = i - 1;
}
}
newArray[currentIndexOfNewArray] = temp;
currentIndexOfNewArray++;
numList.RemoveAt(digitFoundAt);
} while (arrayOfInput.Length > currentIndexOfNewArray);
Console.WriteLine(GetWholeNumber(newArray));
Console.ReadKey();
}
public static int[] GetIntArray(int num)
{
IList<int> listOfInts = new List<int>();
while (num > 0)
{
listOfInts.Add(num % 10);
num = num / 10;
}
listOfInts.Reverse();
return listOfInts.ToArray();
}
public static double GetWholeNumber(int[] arrayNumber)
{
double result = 0;
double multiplier = 0;
var length = arrayNumber.Count() - 1;
for(int i = 0; i < arrayNumber.Count(); i++)
{
multiplier = Math.Pow(10.0, Convert.ToDouble(length));
result += (arrayNumber[i] * multiplier);
length = length - 1;
}
return result;
}
}