我刚刚搞砸了一次面试,而且我的面试问题几乎毫无进展。
给定一个数,找出下一个与之完全相同的更大的数 作为原始数字的数字集。例如:给定38276返回 38627
我想从找到第一个比个位小的数字的下标开始。然后我将旋转子集中的最后一个数字,这样它是由相同的数字组成的下一个最大的数字,但卡住了。
面试官还建议我试着一次换一个数字,但我搞不懂算法,只能盯着屏幕看20-30分钟。不用说,我想我还得继续找工作。
我刚刚搞砸了一次面试,而且我的面试问题几乎毫无进展。
给定一个数,找出下一个与之完全相同的更大的数 作为原始数字的数字集。例如:给定38276返回 38627
我想从找到第一个比个位小的数字的下标开始。然后我将旋转子集中的最后一个数字,这样它是由相同的数字组成的下一个最大的数字,但卡住了。
面试官还建议我试着一次换一个数字,但我搞不懂算法,只能盯着屏幕看20-30分钟。不用说,我想我还得继续找工作。
当前回答
非常简单的实现使用Javascript,下一个最高的数字与相同的数字
/*
Algorithm applied
I) Traverse the given number from rightmost digit, keep traversing till you find a digit which is smaller than the previously traversed digit. For example, if the input number is “534976”, we stop at 4 because 4 is smaller than next digit 9. If we do not find such a digit, then output is “Not Possible”.
II) Now search the right side of above found digit ‘d’ for the smallest digit greater than ‘d’. For “534976″, the right side of 4 contains “976”. The smallest digit greater than 4 is 6.
III) Swap the above found two digits, we get 536974 in above example.
IV) Now sort all digits from position next to ‘d’ to the end of number. The number that we get after sorting is the output. For above example, we sort digits in bold 536974. We get “536479” which is the next greater number for input 534976.
*/
function findNext(arr)
{
let i;
//breaking down a digit into arrays of string and then converting back that array to number array
let arr1=arr.toString().split('').map(Number) ;
//started to loop from the end of array
for(i=arr1.length;i>0;i--)
{
//looking for if the current number is greater than the number next to it
if(arr1[i]>arr1[i-1])
{// if yes then we break the loop it so that we can swap and sort
break;}
}
if(i==0)
{console.log("Not possible");}
else
{
//saving that big number and smaller number to the left of it
let smlNum =arr1[i-1];
let bigNum =i;
/*now looping again and checking if we have any other greater number, if we have one AFTER big number and smaller number to the right.
A greater number that is of course greater than that smaller number but smaller than the first number we found.
Why are doing this? Because that is an algorithm to find next higher number with same digits.
*/
for(let j=i+1;j<arr1.length;j++)
{//What if there are no digits afters those found numbers then of course loop will not be initiated otherwise...
if(arr1[j]> smlNum && arr1[j]<arr1[i])
{// we assign that other found number here and replace it with the one we found before
bigNum=j;
}
} //now we are doing swapping of places the small num and big number , 3rd part of alogorithm
arr1[i-1]=arr1[bigNum];
arr1[bigNum]=smlNum;
//returning array
//too many functions applied sounds complicated right but no, here is the trick
//return arr first then apply each function one by one to see output and then further another func to that output to match your needs
// so here after swapping , 4th part of alogorithm is to sort the array right after the 1st small num we found
// to do that first we simple take part of array, we splice it and then we apply sort fucntion, then check output (to check outputs, pls use chrome dev console)
//and then simply the rest concat and join to main one digit again.
return arr1.concat((arr1.splice(i,arr1.length)).sort(function(a, b){return a-b})).join('');
// Sorry to make it too long but its fun explaining things in much easier ways as much as possible!!
}
}
findNext(1234);
因为有很多评论,所以你最好把它复制到你的文本编辑器。 谢谢!
其他回答
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();
}
}
下面是生成一个数字的所有排列的代码..不过必须先使用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;
}
非常简单的实现使用Javascript,下一个最高的数字与相同的数字
/*
Algorithm applied
I) Traverse the given number from rightmost digit, keep traversing till you find a digit which is smaller than the previously traversed digit. For example, if the input number is “534976”, we stop at 4 because 4 is smaller than next digit 9. If we do not find such a digit, then output is “Not Possible”.
II) Now search the right side of above found digit ‘d’ for the smallest digit greater than ‘d’. For “534976″, the right side of 4 contains “976”. The smallest digit greater than 4 is 6.
III) Swap the above found two digits, we get 536974 in above example.
IV) Now sort all digits from position next to ‘d’ to the end of number. The number that we get after sorting is the output. For above example, we sort digits in bold 536974. We get “536479” which is the next greater number for input 534976.
*/
function findNext(arr)
{
let i;
//breaking down a digit into arrays of string and then converting back that array to number array
let arr1=arr.toString().split('').map(Number) ;
//started to loop from the end of array
for(i=arr1.length;i>0;i--)
{
//looking for if the current number is greater than the number next to it
if(arr1[i]>arr1[i-1])
{// if yes then we break the loop it so that we can swap and sort
break;}
}
if(i==0)
{console.log("Not possible");}
else
{
//saving that big number and smaller number to the left of it
let smlNum =arr1[i-1];
let bigNum =i;
/*now looping again and checking if we have any other greater number, if we have one AFTER big number and smaller number to the right.
A greater number that is of course greater than that smaller number but smaller than the first number we found.
Why are doing this? Because that is an algorithm to find next higher number with same digits.
*/
for(let j=i+1;j<arr1.length;j++)
{//What if there are no digits afters those found numbers then of course loop will not be initiated otherwise...
if(arr1[j]> smlNum && arr1[j]<arr1[i])
{// we assign that other found number here and replace it with the one we found before
bigNum=j;
}
} //now we are doing swapping of places the small num and big number , 3rd part of alogorithm
arr1[i-1]=arr1[bigNum];
arr1[bigNum]=smlNum;
//returning array
//too many functions applied sounds complicated right but no, here is the trick
//return arr first then apply each function one by one to see output and then further another func to that output to match your needs
// so here after swapping , 4th part of alogorithm is to sort the array right after the 1st small num we found
// to do that first we simple take part of array, we splice it and then we apply sort fucntion, then check output (to check outputs, pls use chrome dev console)
//and then simply the rest concat and join to main one digit again.
return arr1.concat((arr1.splice(i,arr1.length)).sort(function(a, b){return a-b})).join('');
// Sorry to make it too long but its fun explaining things in much easier ways as much as possible!!
}
}
findNext(1234);
因为有很多评论,所以你最好把它复制到你的文本编辑器。 谢谢!
回答在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; }
至少,这里有几个基于字符串的暴力解决方案的例子,你应该能够马上想到:
38276中的数字排序为23678
38627排序的数字列表是23678
蛮力增量,排序和比较
沿着蛮力解决方案将转换为字符串 然后用这些数字强行找出所有可能的数字。
从它们中创建int,把它们放在一个列表中并排序, 获取目标条目之后的下一个条目。
如果你花了30分钟在这个问题上,却没有想出一个蛮力的方法,我也不会雇用你。
在商业世界中,一个不优雅、缓慢和笨拙但能完成工作的解决方案总是比没有解决方案更有价值,事实上,这几乎描述了所有不优雅、缓慢和笨拙的商业软件。