我刚刚搞砸了一次面试,而且我的面试问题几乎毫无进展。
给定一个数,找出下一个与之完全相同的更大的数 作为原始数字的数字集。例如:给定38276返回 38627
我想从找到第一个比个位小的数字的下标开始。然后我将旋转子集中的最后一个数字,这样它是由相同的数字组成的下一个最大的数字,但卡住了。
面试官还建议我试着一次换一个数字,但我搞不懂算法,只能盯着屏幕看20-30分钟。不用说,我想我还得继续找工作。
我刚刚搞砸了一次面试,而且我的面试问题几乎毫无进展。
给定一个数,找出下一个与之完全相同的更大的数 作为原始数字的数字集。例如:给定38276返回 38627
我想从找到第一个比个位小的数字的下标开始。然后我将旋转子集中的最后一个数字,这样它是由相同的数字组成的下一个最大的数字,但卡住了。
面试官还建议我试着一次换一个数字,但我搞不懂算法,只能盯着屏幕看20-30分钟。不用说,我想我还得继续找工作。
当前回答
下面是生成一个数字的所有排列的代码..不过必须先使用string . valueof (integer)将该整数转换为字符串。
/**
*
* Inserts a integer at any index around string.
*
* @param number
* @param position
* @param item
* @return
*/
public String insertToNumberStringAtPosition(String number, int position,
int item) {
String temp = null;
if (position >= number.length()) {
temp = number + item;
} else {
temp = number.substring(0, position) + item
+ number.substring(position, number.length());
}
return temp;
}
/**
* To generate permutations of a number.
*
* @param number
* @return
*/
public List<String> permuteNumber(String number) {
List<String> permutations = new ArrayList<String>();
if (number.length() == 1) {
permutations.add(number);
return permutations;
}
// else
int inserterDig = (int) (number.charAt(0) - '0');
Iterator<String> iterator = permuteNumber(number.substring(1))
.iterator();
while (iterator.hasNext()) {
String subPerm = iterator.next();
for (int dig = 0; dig <= subPerm.length(); dig++) {
permutations.add(insertToNumberStringAtPosition(subPerm, dig,
inserterDig));
}
}
return permutations;
}
其他回答
我很确定你的面试官是想委婉地让你说出这样的话:
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);
不一定是最有效或最优雅的解决方案,但它在两个循环中解决了所提供的示例,并像他建议的那样一次交换一个数字。
我们需要找到最右边的0位,后面是1,然后将最右边的0位翻转为1。
例如,我们的输入是487,也就是二进制的111100111。
我们把后面有1的0往右翻转最多
所以我们得到 111101111
但是现在我们多了一个1,少了一个0,所以我们减少了右边1的个数 位增加1,并将0位的no增加1,得到
111101011 -二进制491
int getNextNumber(int input)
{
int flipPosition=0;
int trailingZeros=0;
int trailingOnes=0;
int copy = input;
//count trailing zeros
while(copy != 0 && (copy&1) == 0 )
{
++trailingZeros;
//test next bit
copy = copy >> 1;
}
//count trailing ones
while(copy != 0 && (copy&1) == 1 )
{
++trailingOnes;
//test next bit
copy = copy >> 1;
}
//if we have no 1's (i.e input is 0) we cannot form another pattern with
//the same number of 1's which will increment the input, or if we have leading consecutive
//ones followed by consecutive 0's up to the maximum bit size of a int
//we cannot increase the input whilst preserving the original no of 0's and
//1's in the bit pattern
if(trailingZeros + trailingOnes == 0 || trailingZeros + trailingOnes == 31)
return -1;
//flip first 0 followed by a 1 found from the right of the bit pattern
flipPosition = trailingZeros + trailingOnes+1;
input |= 1<<(trailingZeros+trailingOnes);
//clear fields to the right of the flip position
int mask = ~0 << (trailingZeros+trailingOnes);
input &= mask;
//insert a bit pattern to the right of the flip position that will contain
//one less 1 to compensate for the bit we switched from 0 to 1
int insert = flipPosition-1;
input |= insert;
return input;
}
#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;
}
在Java中,这个算法比这个算法更简洁
public static int permutate2(int number){
String[] numArray = String.valueOf(number).split("");
for(int i = numArray.length - 1; i > 0; i--){
int current = Integer.valueOf(numArray[i]);
int previous = Integer.valueOf(numArray[i - 1]);
if(previous < current){
String[] rest = String.valueOf(number).substring(i, numArray.length).split("");
Arrays.sort(rest);
String picker = rest[0];
int pickerIndex = 0;
for(int n = 0; n < rest.length ; n++){
if(Integer.valueOf(rest[n]) > previous){
picker = rest[n];
pickerIndex = n;
break;
}
}
numArray[i - 1] = picker;
rest[pickerIndex] = String.valueOf(previous);
Arrays.sort(rest);
String newNumber = "";
for(int z = 0; z <= i - 1; z++){
newNumber += numArray[z];
}
for(String z : rest){
newNumber += z;
}
return Integer.valueOf(newNumber);
}
}
return number;
}
这里是Java实现
public static int nextHigherNumber(int number) {
Integer[] array = convertToArray(number);
int pivotIndex = pivotMaxIndex(array);
int digitInFirstSequence = pivotIndex -1;
int lowerDigitIndexInSecondSequence = lowerDigitIndex(array[digitInFirstSequence], array, pivotIndex);
swap(array, digitInFirstSequence, lowerDigitIndexInSecondSequence);
doRercursiveQuickSort(array, pivotIndex, array.length - 1);
return arrayToInteger(array);
}
public static Integer[] convertToArray(int number) {
int i = 0;
int length = (int) Math.log10(number);
int divisor = (int) Math.pow(10, length);
Integer temp[] = new Integer[length + 1];
while (number != 0) {
temp[i] = number / divisor;
if (i < length) {
++i;
}
number = number % divisor;
if (i != 0) {
divisor = divisor / 10;
}
}
return temp;
}
private static int pivotMaxIndex(Integer[] array) {
int index = array.length - 1;
while(index > 0) {
if (array[index-1] < array[index]) {
break;
}
index--;
}
return index;
}
private static int lowerDigitIndex(int number, Integer[] array, int fromIndex) {
int lowerMaxIndex = fromIndex;
int lowerMax = array[lowerMaxIndex];
while (fromIndex < array.length - 1) {
if (array[fromIndex]> number && lowerMax > array[fromIndex]) {
lowerMaxIndex = fromIndex;
}
fromIndex ++;
}
return lowerMaxIndex;
}
public static int arrayToInteger(Integer[] array) {
int number = 0;
for (int i = 0; i < array.length; i++) {
number+=array[i] * Math.pow(10, array.length-1-i);
}
return number;
}
这里是单元测试
@Test
public void nextHigherNumberTest() {
assertThat(ArrayUtils.nextHigherNumber(34722641), is(34724126));
assertThat(ArrayUtils.nextHigherNumber(123), is(132));
}