t********e
发帖数: 344 | 1 先问如何判断一个Integer是否Palindrome，熟题了。
然后接着问如何找比一个int大的下一个palindrome。 Write a function
which returns the next palindrome greater than the given number n.
e.g., f(231) = 232
f(999) = 1001
f(111) = 121
大家有什么思路？除了naive的exhaustive search (其实这个方法也不差吧，因为一般
n加1几次以后就能找到答案了……) |
s******e
发帖数: 493 | 2 first thing in my mind.
1. count #digits
2. divide #digits (be careful of odd and even) into two parts
3. compare the lower part to the higher part in a reverse order. If samller,
replace lower part with the higher part; if bigger, then add one to last
digit of higher part and reverse higher part to be your lower part. |
t********e
发帖数: 344 | 3 Not sure why need to treat odd and even differently...
Feel this method does not work for f(999)= 1001
samller,
【在 s******e 的大作中提到】
: first thing in my mind.
: 1. count #digits
: 2. divide #digits (be careful of odd and even) into two parts
: 3. compare the lower part to the higher part in a reverse order. If samller,
: replace lower part with the higher part; if bigger, then add one to last
: digit of higher part and reverse higher part to be your lower part.
|
d*s
发帖数: 699 | 4 这个做法对特殊情况不成立，比如题里面的 f(999) = 1001
我觉得naive approach没什么问题，如果只是要一个数字的话
如果要不断的生成，可以产生一个palindrome list，然后做binsearch
samller,
【在 s******e 的大作中提到】
: first thing in my mind.
: 1. count #digits
: 2. divide #digits (be careful of odd and even) into two parts
: 3. compare the lower part to the higher part in a reverse order. If samller,
: replace lower part with the higher part; if bigger, then add one to last
: digit of higher part and reverse higher part to be your lower part.
|
s******e
发帖数: 493 | 5 oops. how about adding this. if the number is already a palindrome, add 1
and continue... |
s******e
发帖数: 493 | 6 odd and even # digits will matter when you try to add 1 to higher part. |
z********i
发帖数: 568 | 7 231: 2>1, 改1为2。中间的3为回文。返回。
999： 9=9，中间的为回文，但没法增加，改两端的9为10&01，中间设为位数减1全0--
〉1001。
9999：--〉10001
989: 9=9，中间的为回文，但可增加，--->999
假设没有leading 0s
用两个函数：
1。isP（int x): return true如果x是回文，否则false.
2. isMaxP(int x): return true如果x=99...9。
find_next_palindrome_int(ax..zb)
if(isMaxP(x..z) or x..z is empty)
if(a==9)
if(b==9)
x..z=0..0
return 10x..z01
else
return ax...z9
else
if(b>=a)
a=a+1;
b=a;
else
b=a;
else
m=find_next_palindrome_int(x..z)
return ama
【在 t********e 的大作中提到】
: 先问如何判断一个Integer是否Palindrome，熟题了。
: 然后接着问如何找比一个int大的下一个palindrome。 Write a function
: which returns the next palindrome greater than the given number n.
: e.g., f(231) = 232
: f(999) = 1001
: f(111) = 121
: 大家有什么思路？除了naive的exhaustive search (其实这个方法也不差吧，因为一般
: n加1几次以后就能找到答案了……)
|
b***e
发帖数: 1419 | 8 Just do a recursive call on the substring [1..n-2]. If that’s not failing,
it’s done, otherwise, increase the current digit (and the mirror position)
by 1 and turn all the digits in between to 0. If the current digit is 9
already, report failure. At the top level, if it is failing, then that
means all digits are 9. In this case +2.
This way you solve the problem of +1. But not general +n problem. For that
, just define the transformation as follows:
encode(a[1..n]) =
Corresponding decoding is:
decode() = a[1..n..1]
decode() = a[1..nn..1]
Then define +1 on the pair:
+ 1 = , if n+1 is of the same length as n
+ 1 = <(n+1) / 10, even>, if n+1 is longer than n
+ 1 = , if n+1 is of the same length as n
+ 1 = , if n + 1 is longer than n
Then the result is:
decode(encode(n) + 1)
【在 t********e 的大作中提到】
: 先问如何判断一个Integer是否Palindrome，熟题了。
: 然后接着问如何找比一个int大的下一个palindrome。 Write a function
: which returns the next palindrome greater than the given number n.
: e.g., f(231) = 232
: f(999) = 1001
: f(111) = 121
: 大家有什么思路？除了naive的exhaustive search (其实这个方法也不差吧，因为一般
: n加1几次以后就能找到答案了……)
|
s**s
发帖数: 70 | 9 输入n， 检查n+1
数一下位数， 从中点开始找第一个与对称位置不等的数字
如果偶数， 比如： 12354678
先找到中点后一个，4
比较对称的位置： 5和4， 如果小，那么该位可以不用变。
设置成1235000， 然后把后面的0反着换成前面的数字
如果大， 12345678， 4+1， 然后同上。
奇数位数同理
【在 t********e 的大作中提到】
: 先问如何判断一个Integer是否Palindrome，熟题了。
: 然后接着问如何找比一个int大的下一个palindrome。 Write a function
: which returns the next palindrome greater than the given number n.
: e.g., f(231) = 232
: f(999) = 1001
: f(111) = 121
: 大家有什么思路？除了naive的exhaustive search (其实这个方法也不差吧，因为一般
: n加1几次以后就能找到答案了……)
|
t********e
发帖数: 344 | 10 和我答的差不多
我一开始没想到要从n+1开始检查， sigh。 后面的逻辑基本一样
【在 s**s 的大作中提到】
: 输入n， 检查n+1
: 数一下位数， 从中点开始找第一个与对称位置不等的数字
: 如果偶数， 比如： 12354678
: 先找到中点后一个，4
: 比较对称的位置： 5和4， 如果小，那么该位可以不用变。
: 设置成1235000， 然后把后面的0反着换成前面的数字
: 如果大， 12345678， 4+1， 然后同上。
: 奇数位数同理
|
