我刚刚搞砸了一次面试,而且我的面试问题几乎毫无进展。
给定一个数,找出下一个与之完全相同的更大的数 作为原始数字的数字集。例如:给定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;
}
其他回答
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);
}
}
只是使用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
回答在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; }
关于如何做到这一点,请参阅Knuth的“计算机编程艺术:生成所有排列”(.ps.gz)中的“算法L”。
Ruby的解决方案
def next_bigger(num)
char_array = num.to_s.split('')
return -1 if char_array.uniq.size == 1
arr, target_idx, target_char = [], nil, nil
# get first left-digit less than the right from right side
(char_array.count - 1).times do |i|
arr.unshift(char_array[-(i+1)])
if char_array[-(i+2)] < char_array[-(i+1)]
target_idx = char_array.count - (i + 2)
target_char = char_array[-(i+2)]
arr.unshift(char_array[-(i+2)])
break
end
end
return -1 unless target_idx
# first smallest digit larger than target_char to the right
((target_char.to_i + 1)..9).to_a.each do |ch|
if arr.index(ch.to_s)
flip_char = arr.delete_at(arr.index(ch.to_s))
# sort the digits to the right of flip_char
arr.sort!
# place flip_char to the left of target_char
arr.unshift(flip_char)
break
end
end
(char_array[0...target_idx] + arr).join().to_i
end