我刚刚搞砸了一次面试,而且我的面试问题几乎毫无进展。
给定一个数,找出下一个与之完全相同的更大的数 作为原始数字的数字集。例如:给定38276返回 38627
我想从找到第一个比个位小的数字的下标开始。然后我将旋转子集中的最后一个数字,这样它是由相同的数字组成的下一个最大的数字,但卡住了。
面试官还建议我试着一次换一个数字,但我搞不懂算法,只能盯着屏幕看20-30分钟。不用说,我想我还得继续找工作。
我刚刚搞砸了一次面试,而且我的面试问题几乎毫无进展。
给定一个数,找出下一个与之完全相同的更大的数 作为原始数字的数字集。例如:给定38276返回 38627
我想从找到第一个比个位小的数字的下标开始。然后我将旋转子集中的最后一个数字,这样它是由相同的数字组成的下一个最大的数字,但卡住了。
面试官还建议我试着一次换一个数字,但我搞不懂算法,只能盯着屏幕看20-30分钟。不用说,我想我还得继续找工作。
当前回答
只是使用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
其他回答
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
至少,这里有几个基于字符串的暴力解决方案的例子,你应该能够马上想到:
38276中的数字排序为23678
38627排序的数字列表是23678
蛮力增量,排序和比较
沿着蛮力解决方案将转换为字符串 然后用这些数字强行找出所有可能的数字。
从它们中创建int,把它们放在一个列表中并排序, 获取目标条目之后的下一个条目。
如果你花了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;
}
这是另一个Java实现,可以开箱即用,并通过测试完成。 这个解决方案是O(n)个空间和时间,使用老式的动态规划。
如果你想用蛮力,有两种蛮力:
排列所有的东西,然后选择最小值更高的:O(n!) 与此实现类似,但不是DP,而是强制填充的步骤 indexToIndexOfNextSmallerLeft映射将在O(n²)中运行。
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import org.junit.Test;
import static org.junit.Assert.assertEquals;
public class NextHigherSameDigits {
public long next(final long num) {
final char[] chars = String.valueOf(num).toCharArray();
final int[] digits = new int[chars.length];
for (int i = 0; i < chars.length; i++) {
digits[i] = Character.getNumericValue(chars[i]);
}
final Map<Integer, Integer> indexToIndexOfNextSmallerLeft = new HashMap<>();
indexToIndexOfNextSmallerLeft.put(1, digits[1] > digits[0] ? 0 : null);
for (int i = 2; i < digits.length; i++) {
final int left = digits[i - 1];
final int current = digits[i];
Integer indexOfNextSmallerLeft = null;
if (current > left) {
indexOfNextSmallerLeft = i - 1;
} else {
final Integer indexOfnextSmallerLeftOfLeft = indexToIndexOfNextSmallerLeft.get(i - 1);
final Integer nextSmallerLeftOfLeft = indexOfnextSmallerLeftOfLeft == null ? null :
digits[indexOfnextSmallerLeftOfLeft];
if (nextSmallerLeftOfLeft != null && current > nextSmallerLeftOfLeft) {
indexOfNextSmallerLeft = indexOfnextSmallerLeftOfLeft;
} else {
indexOfNextSmallerLeft = null;
}
}
indexToIndexOfNextSmallerLeft.put(i, indexOfNextSmallerLeft);
}
Integer maxOfindexOfNextSmallerLeft = null;
Integer indexOfMinToSwapWithNextSmallerLeft = null;
for (int i = digits.length - 1; i >= 1; i--) {
final Integer indexOfNextSmallerLeft = indexToIndexOfNextSmallerLeft.get(i);
if (maxOfindexOfNextSmallerLeft == null ||
(indexOfNextSmallerLeft != null && indexOfNextSmallerLeft > maxOfindexOfNextSmallerLeft)) {
maxOfindexOfNextSmallerLeft = indexOfNextSmallerLeft;
if (maxOfindexOfNextSmallerLeft != null && (indexOfMinToSwapWithNextSmallerLeft == null ||
digits[i] < digits[indexOfMinToSwapWithNextSmallerLeft])) {
indexOfMinToSwapWithNextSmallerLeft = i;
}
}
}
if (maxOfindexOfNextSmallerLeft == null) {
return -1;
} else {
swap(digits, indexOfMinToSwapWithNextSmallerLeft, maxOfindexOfNextSmallerLeft);
reverseRemainingOfArray(digits, maxOfindexOfNextSmallerLeft + 1);
return backToLong(digits);
}
}
private void reverseRemainingOfArray(final int[] digits, final int startIndex) {
final int[] tail = Arrays.copyOfRange(digits, startIndex, digits.length);
for (int i = tail.length - 1; i >= 0; i--) {
digits[(digits.length - 1) - i] = tail[i];
}
}
private void swap(final int[] digits, final int currentIndex, final int indexOfNextSmallerLeft) {
int temp = digits[currentIndex];
digits[currentIndex] = digits[indexOfNextSmallerLeft];
digits[indexOfNextSmallerLeft] = temp;
}
private long backToLong(int[] digits) {
StringBuilder sb = new StringBuilder();
for (long i : digits) {
sb.append(String.valueOf(i));
}
return Long.parseLong(sb.toString());
}
@Test
public void test() {
final long input1 = 34722641;
final long expected1 = 34724126;
final long output1 = new NextHigherSameDigits().next(input1);
assertEquals(expected1, output1);
final long input2 = 38276;
final long expected2 = 38627;
final long output2 = new NextHigherSameDigits().next(input2);
assertEquals(expected2, output2);
final long input3 = 54321;
final long expected3 = -1;
final long output3 = new NextHigherSameDigits().next(input3);
assertEquals(expected3, output3);
final long input4 = 123456784987654321L;
final long expected4 = 123456785123446789L;
final long output4 = new NextHigherSameDigits().next(input4);
assertEquals(expected4, output4);
final long input5 = 9999;
final long expected5 = -1;
final long output5 = new NextHigherSameDigits().next(input5);
assertEquals(expected5, output5);
}
}
有很多不错的答案,但我没有找到一个像样的Java实现。以下是我的观点:
public void findNext(int[] nums) {
int i = nums.length - 1;
// nums[i - 1] will be the first non increasing number
while (i > 0 && nums[i] <= nums[i - 1]) {
i--;
}
if (i == 0) {
System.out.println("it has been the greatest already");
} else {
// Find the smallest digit in the second sequence that is larger than it:
int j = nums.length - 1;
while (j >= 0 && nums[j] < nums[i - 1]) {
j--;
}
swap(nums, i - 1, j);
Arrays.sort(nums, i, nums.length);
System.out.println(Arrays.toString(nums));
}
}
public void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}