f********e
发帖数: 166 | 1 careercup上的
123 的下个数是啥？用相同的数字 |
S**I
发帖数: 15689 | 2 132?
【在 f********e 的大作中提到】
: careercup上的
: 123 的下个数是啥？用相同的数字
|
f********e
发帖数: 166 | |
f********e
发帖数: 166 | |
f********e
发帖数: 166 | |
S**I
发帖数: 15689 | 6 next_permutation in C++ std will do it, a sample implementation is shown below:
http://wordaligned.org/articles/next-permutation
【在 f********e 的大作中提到】
: 要求写代码的，这只是一个input
|
f********e
发帖数: 166 | |
r*******y
发帖数: 1081 | 8 like the idea to find the permutation ?
【在 f********e 的大作中提到】
: 要求写代码的，这只是一个input
|
p*******n
发帖数: 10 | 9 I don't think we need do permutation.
how about this solution?
int FindNext( int x)
{
int base = 1;
int current = x % 10 ;
int temp = x /10;
while (temp)
{
if (temp %10
{
int y = (current - temp%10)*9*base ;
return x+y;
}
else {
base *= 10;
current = temp%10 ;
temp /=10;
}
}
return 0;
} |
q*****t
发帖数: 3 | 10 import java.util.ArrayList;
import java.util.List;
public class NextLargerNumberWithSameDigits {
public static void main(String[] args) throws Exception {
int a = 1245963;
System.out.println(findnext(a));
a = 698754;
System.out.println(findnext(a));
}
public static int findnext(int a) throws Exception {
List d = new ArrayList();
while (a != 0) {
d.add(a % 10);
a /= 10;
}
Integer[] digits = d.toArray(new Integer[d.size()]);
// find the first digit that is out of order
// digits[i] < digits[i-1] >= digits[i-2] >= ... >= digits[1] >= digits[0]
int i;
for (i = 1; i < digits.length; i++) {
if (digits[i] < digits[i - 1])
break;
}
if (i >= digits.length) {
throw new Exception("Not found!");
}
// find in digits[i-1], digits[i-2], ..., digits[1], digits[0]
// the smallest digit that is larger than digits[i]
// Because digits[i] is out of order, i.e. digits[i-1]>digits[i],
// it's guaranteed to find one
for (int j = 0; j <= i - 1; j++) {
if (digits[j] > digits[i]) {
int t = digits[j];
digits[j] = digits[i];
digits[i] = t;
break;
}
}
// reverse digits[i-1], digits[i-2], ..., digits[1], digits[0]
for (int j = 0; j < i / 2; j++) {
int t = digits[j];
digits[j] = digits[i - 1 - j];
digits[i - 1 - j] = t;
}
int b = digits[digits.length - 1];
for (int j = digits.length - 2; j >= 0; j--) {
b = b * 10 + digits[j];
}
return b;
}
} |
|
|
e***s
发帖数: 799 | 11 大哥您CODE不对啊， 1321 return 3121, should be 2113啊
【在 p*******n 的大作中提到】
: I don't think we need do permutation.
: how about this solution?
: int FindNext( int x)
: {
: int base = 1;
: int current = x % 10 ;
: int temp = x /10;
: while (temp)
: {
: if (temp %10
|
e***s
发帖数: 799 | 12 public static int FindNext(int x)
{
ArrayList tempa = new ArrayList();
int current = x % 10;
int temp = x / 10;
int result;
while (temp > 0)
{
tempa.Add(current);
//find the falling edge from right to left, e.g. "1321" 1->2
->3->(1)falling edge
if (current > temp % 10)
{
//switch the fall edge with first element which greater
than itself
for (int i = 0; i < tempa.Count; i++)
if ((temp % 10) < (int)tempa[i])
{
result = (temp / 10) * 10 + (int)tempa[i];
tempa[i] = temp % 10;
int j = 0;
//put the elements back to the result
while (j < tempa.Count)
{
result = result * 10 + (int)tempa[j];
++j;
}
return result;
}
}
//if the number is raising, add the digit to ArrayList and
keep finding
else
{
current = temp % 10;
temp /= 10;
}
}
//Can't find the next number return 0
return 0;
} |
B******5
发帖数: 4676 | 13 这是careercup的第几题？我怎么没见过。。。 |
p*******n
发帖数: 10 | 14 大哥我很羞惭啊，竟然有BUG。谢谢兄弟提醒啊，我研究一下你的啊。
>2
【在 e***s 的大作中提到】
: public static int FindNext(int x)
: {
: ArrayList tempa = new ArrayList();
: int current = x % 10;
: int temp = x / 10;
: int result;
: while (temp > 0)
: {
: tempa.Add(current);
: //find the falling edge from right to left, e.g. "1321" 1->2
|
p*******n
发帖数: 10 | 15 嗯。兄弟你的很正确！ scan过的digit不能丢 |
f********e
发帖数: 166 | 16 qqshoot 的代码是对的，而且思路很清晰
【在 q*****t 的大作中提到】
: import java.util.ArrayList;
: import java.util.List;
: public class NextLargerNumberWithSameDigits {
: public static void main(String[] args) throws Exception {
: int a = 1245963;
: System.out.println(findnext(a));
: a = 698754;
: System.out.println(findnext(a));
: }
: public static int findnext(int a) throws Exception {
|
f********e
发帖数: 166 | 17 careercup上的
123 的下个数是啥？用相同的数字 |
S**I
发帖数: 15689 | 18 132?
【在 f********e 的大作中提到】
: careercup上的
: 123 的下个数是啥？用相同的数字
|
f********e
发帖数: 166 | |
f********e
发帖数: 166 | |
|
|
f********e
发帖数: 166 | |
S**I
发帖数: 15689 | 22 next_permutation in C++ std will do it, a sample implementation is shown below:
http://wordaligned.org/articles/next-permutation
【在 f********e 的大作中提到】
: 要求写代码的，这只是一个input
|
f********e
发帖数: 166 | |
r*******y
发帖数: 1081 | 24 like the idea to find the permutation ?
【在 f********e 的大作中提到】
: 要求写代码的，这只是一个input
|
p*******n
发帖数: 10 | 25 I don't think we need do permutation.
how about this solution?
int FindNext( int x)
{
int base = 1;
int current = x % 10 ;
int temp = x /10;
while (temp)
{
if (temp %10
{
int y = (current - temp%10)*9*base ;
return x+y;
}
else {
base *= 10;
current = temp%10 ;
temp /=10;
}
}
return 0;
} |
q*****t
发帖数: 3 | 26 import java.util.ArrayList;
import java.util.List;
public class NextLargerNumberWithSameDigits {
public static void main(String[] args) throws Exception {
int a = 1245963;
System.out.println(findnext(a));
a = 698754;
System.out.println(findnext(a));
}
public static int findnext(int a) throws Exception {
List d = new ArrayList();
while (a != 0) {
d.add(a % 10);
a /= 10;
}
Integer[] digits = d.toArray(new Integer[d.size()]);
// find the first digit that is out of order
// digits[i] < digits[i-1] >= digits[i-2] >= ... >= digits[1] >= digits[0]
int i;
for (i = 1; i < digits.length; i++) {
if (digits[i] < digits[i - 1])
break;
}
if (i >= digits.length) {
throw new Exception("Not found!");
}
// find in digits[i-1], digits[i-2], ..., digits[1], digits[0]
// the smallest digit that is larger than digits[i]
// Because digits[i] is out of order, i.e. digits[i-1]>digits[i],
// it's guaranteed to find one
for (int j = 0; j <= i - 1; j++) {
if (digits[j] > digits[i]) {
int t = digits[j];
digits[j] = digits[i];
digits[i] = t;
break;
}
}
// reverse digits[i-1], digits[i-2], ..., digits[1], digits[0]
for (int j = 0; j < i / 2; j++) {
int t = digits[j];
digits[j] = digits[i - 1 - j];
digits[i - 1 - j] = t;
}
int b = digits[digits.length - 1];
for (int j = digits.length - 2; j >= 0; j--) {
b = b * 10 + digits[j];
}
return b;
}
} |
e***s
发帖数: 799 | 27 大哥您CODE不对啊， 1321 return 3121, should be 2113啊
【在 p*******n 的大作中提到】
: I don't think we need do permutation.
: how about this solution?
: int FindNext( int x)
: {
: int base = 1;
: int current = x % 10 ;
: int temp = x /10;
: while (temp)
: {
: if (temp %10
|
e***s
发帖数: 799 | 28 public static int FindNext(int x)
{
ArrayList tempa = new ArrayList();
int current = x % 10;
int temp = x / 10;
int result;
while (temp > 0)
{
tempa.Add(current);
//find the falling edge from right to left, e.g. "1321" 1->2
->3->(1)falling edge
if (current > temp % 10)
{
//switch the fall edge with first element which greater
than itself
for (int i = 0; i < tempa.Count; i++)
if ((temp % 10) < (int)tempa[i])
{
result = (temp / 10) * 10 + (int)tempa[i];
tempa[i] = temp % 10;
int j = 0;
//put the elements back to the result
while (j < tempa.Count)
{
result = result * 10 + (int)tempa[j];
++j;
}
return result;
}
}
//if the number is raising, add the digit to ArrayList and
keep finding
else
{
current = temp % 10;
temp /= 10;
}
}
//Can't find the next number return 0
return 0;
} |
B******5
发帖数: 4676 | 29 这是careercup的第几题？我怎么没见过。。。 |
p*******n
发帖数: 10 | 30 大哥我很羞惭啊，竟然有BUG。谢谢兄弟提醒啊，我研究一下你的啊。
>2
【在 e***s 的大作中提到】
: public static int FindNext(int x)
: {
: ArrayList tempa = new ArrayList();
: int current = x % 10;
: int temp = x / 10;
: int result;
: while (temp > 0)
: {
: tempa.Add(current);
: //find the falling edge from right to left, e.g. "1321" 1->2
|
|
|
p*******n
发帖数: 10 | 31 嗯。兄弟你的很正确！ scan过的digit不能丢 |
f********e
发帖数: 166 | 32 qqshoot 的代码是对的，而且思路很清晰
【在 q*****t 的大作中提到】
: import java.util.ArrayList;
: import java.util.List;
: public class NextLargerNumberWithSameDigits {
: public static void main(String[] args) throws Exception {
: int a = 1245963;
: System.out.println(findnext(a));
: a = 698754;
: System.out.println(findnext(a));
: }
: public static int findnext(int a) throws Exception {
|
z****u
发帖数: 104 | 33 C version，求指正
int NextNumber(int i)
{
int max_length = 1;
int* digits = (int*) malloc(sizeof(int) * max_length);
/* break number down to digits */
int idx = 0;
while(i)
{
if (idx > max_length - 1)
{
max_length *= 2;
digits = (int*) realloc(digits, sizeof(int) * max_length);
}
digits[idx++] = i % 10;
i /= 10;
}
int length = idx;
/* find the break digit */
for (idx = 1; idx < length; idx++)
{
if (digits[idx] < digits[idx - 1])
{
break;
}
}
int break_idx = idx;
/* i is already maximum */
if (break_idx == length)
{
return -1;
}
/* find the min digit before break digit, which is > break digit */
int min = -1;
int min_idx = 0;
for (idx = 0; idx < break_idx; idx++)
{
if (digits[idx] > digits[break_idx])
{
if ((min == -1) || digits[idx] < min)
{
min = digits[idx];
min_idx = idx;
}
}
}
/* switch min digit and break digit */
int tmp = digits[break_idx];
digits[break_idx] = digits[min_idx];
digits[min_idx] = tmp;
/* sort after break digit */
QuickSort(digits, break_idx);
/* reconstruct result */
int result = 0;
for (idx = length - 1; idx >= 0; idx--)
{
result = result * 10 + digits[idx];
}
free(digits);
return result;
} |
q****x
发帖数: 7404 | 34 白板都写不下吧。
【在 f********e 的大作中提到】
: qqshoot 的代码是对的，而且思路很清晰
|
z****u
发帖数: 104 | 35 又看了一下 qqshot 的解法，发现我的后边的排序是不需要的，因为那个 digit array
肯定是升续的，reverse 变成降续就好了
【在 z****u 的大作中提到】
: C version，求指正
: int NextNumber(int i)
: {
: int max_length = 1;
: int* digits = (int*) malloc(sizeof(int) * max_length);
: /* break number down to digits */
: int idx = 0;
: while(i)
: {
: if (idx > max_length - 1)
|
