我刚刚搞砸了一次面试,而且我的面试问题几乎毫无进展。
给定一个数,找出下一个与之完全相同的更大的数 作为原始数字的数字集。例如:给定38276返回 38627
我想从找到第一个比个位小的数字的下标开始。然后我将旋转子集中的最后一个数字,这样它是由相同的数字组成的下一个最大的数字,但卡住了。
面试官还建议我试着一次换一个数字,但我搞不懂算法,只能盯着屏幕看20-30分钟。不用说,我想我还得继续找工作。
我刚刚搞砸了一次面试,而且我的面试问题几乎毫无进展。
给定一个数,找出下一个与之完全相同的更大的数 作为原始数字的数字集。例如:给定38276返回 38627
我想从找到第一个比个位小的数字的下标开始。然后我将旋转子集中的最后一个数字,这样它是由相同的数字组成的下一个最大的数字,但卡住了。
面试官还建议我试着一次换一个数字,但我搞不懂算法,只能盯着屏幕看20-30分钟。不用说,我想我还得继续找工作。
当前回答
这是我的代码,它是这个例子的修改版本
库:
class NumPermExample
{
// print N! permutation of the characters of the string s (in order)
public static void perm1(String s, ArrayList<String> perm)
{
perm1("", s);
}
private static void perm1(String prefix, String s, ArrayList<String> perm)
{
int N = s.length();
if (N == 0)
{
System.out.println(prefix);
perm.add(prefix);
}
else
{
for (int i = 0; i < N; i++)
perm1(prefix + s.charAt(i), s.substring(0, i)
+ s.substring(i+1, N));
}
}
// print N! permutation of the elements of array a (not in order)
public static void perm2(String s, ArrayList<String> perm)
{
int N = s.length();
char[] a = new char[N];
for (int i = 0; i < N; i++)
a[i] = s.charAt(i);
perm2(a, N);
}
private static void perm2(char[] a, int n, ArrayList<String> perm)
{
if (n == 1)
{
System.out.println(a);
perm.add(new String(a));
return;
}
for (int i = 0; i < n; i++)
{
swap(a, i, n-1);
perm2(a, n-1);
swap(a, i, n-1);
}
}
// swap the characters at indices i and j
private static void swap(char[] a, int i, int j)
{
char c;
c = a[i]; a[i] = a[j]; a[j] = c;
}
// next higher permutation
public static int nextPermutation (int number)
{
ArrayList<String> perm = new ArrayList<String>();
String cur = ""+number;
int nextPerm = 0;
perm1(cur, perm);
for (String s : perm)
{
if (Integer.parseInt(s) > number
&& (nextPerm == 0 ||
Integer.parseInt(s) < nextPerm))
{
nextPerm = Integer.parseInt(s);
}
}
return nextPerm;
}
}
测试:
public static void main(String[] args)
{
int a = 38276;
int b = NumPermExample.nextPermutation(a);
System.out.println("a: "+a+", b: "+b);
}
其他回答
我很确定你的面试官是想委婉地让你说出这样的话:
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);
不一定是最有效或最优雅的解决方案,但它在两个循环中解决了所提供的示例,并像他建议的那样一次交换一个数字。
解决方案(在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));
}
#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;
}
至少,这里有几个基于字符串的暴力解决方案的例子,你应该能够马上想到:
38276中的数字排序为23678
38627排序的数字列表是23678
蛮力增量,排序和比较
沿着蛮力解决方案将转换为字符串 然后用这些数字强行找出所有可能的数字。
从它们中创建int,把它们放在一个列表中并排序, 获取目标条目之后的下一个条目。
如果你花了30分钟在这个问题上,却没有想出一个蛮力的方法,我也不会雇用你。
在商业世界中,一个不优雅、缓慢和笨拙但能完成工作的解决方案总是比没有解决方案更有价值,事实上,这几乎描述了所有不优雅、缓慢和笨拙的商业软件。
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