p*****2
发帖数: 21240 | 1 给两个number，m和n，找到m个 >=n 的 Palindromic Numbers
1. m = 26, n =0
0 1 2 3 4 5 6 7 8 9
11 22 33 44 55 66 77 88 99
101 111 121 131 141 151 161
2. m=16, n=162
171 181 191 202
212 222 232 242
252 262 272 282
292 303 313 323 |
o********d
发帖数: 22 | 2 is mlog(n) fast enough? er ye. |
A*********c
发帖数: 430 | 3 先乱说一下不知道靠谱不，要实现的话要用生成法，从m起生成n次吧。
string GenNextPalindrome(const string &s);
要是一个一个的话验证太慢了。
再想想实现。
【在 p*****2 的大作中提到】
: 给两个number，m和n，找到m个 >=n 的 Palindromic Numbers
: 1. m = 26, n =0
: 0 1 2 3 4 5 6 7 8 9
: 11 22 33 44 55 66 77 88 99
: 101 111 121 131 141 151 161
: 2. m=16, n=162
: 171 181 191 202
: 212 222 232 242
: 252 262 272 282
: 292 303 313 323
|
p*****2
发帖数: 21240 | 4
感觉应该够。说说算法？
【在 o********d 的大作中提到】
: is mlog(n) fast enough? er ye.
|
p*****2
发帖数: 21240 | 5
我感觉这样可以。细节想清楚了吗？
【在 A*********c 的大作中提到】
: 先乱说一下不知道靠谱不，要实现的话要用生成法，从m起生成n次吧。
: string GenNextPalindrome(const string &s);
: 要是一个一个的话验证太慢了。
: 再想想实现。
|
o********d
发帖数: 22 | |
p*****2
发帖数: 21240 | 7
跟我想的基本一样。我就是觉得细节太多了，你看他下边的comments，还是不能涵盖所
有的case。
【在 o********d 的大作中提到】
: http://www.ardendertat.com/2011/12/01/programming-interview-que
: 见过而已~ 第一次见也不会做
|
m*****k
发帖数: 731 | 8 应该是找到最小的m个 >=n 的 Palindromic Numbers吧
否者就太简单了， 呵呵。
【在 p*****2 的大作中提到】
: 给两个number，m和n，找到m个 >=n 的 Palindromic Numbers
: 1. m = 26, n =0
: 0 1 2 3 4 5 6 7 8 9
: 11 22 33 44 55 66 77 88 99
: 101 111 121 131 141 151 161
: 2. m=16, n=162
: 171 181 191 202
: 212 222 232 242
: 252 262 272 282
: 292 303 313 323
|
p*****2
发帖数: 21240 | 9
是。大牛眼尖。
【在 m*****k 的大作中提到】
: 应该是找到最小的m个 >=n 的 Palindromic Numbers吧
: 否者就太简单了， 呵呵。
|
l*********8
发帖数: 4642 | 10 他的程序是有问题，改了改：
def nextPalindrome(num):
oddDigits = (len(str(num)) %2 != 0)
leftHalf = getLeftHalf(num)
newNum = getPalin(leftHalf, oddDigits)
if newNum > num:
return newNum
nextLeftHalf = str(int(leftHalf) + 1)
if len(nextLeftHalf) == len(leftHalf):
return getPalin(nextLeftHalf, oddDigits)
if oddDigits:
return getPalin(nextLeftHalf[:-1], 0)
else:
return getPalin(nextLeftHalf, 1)
def getLeftHalf(num):
return str(num)[:(len(str(num))+1)/2]
def getPalin(leftHalf, overlap):
return int( leftHalf + leftHalf[::-1][overlap:] )
【在 p*****2 的大作中提到】
:
: 是。大牛眼尖。
|
|
|
A*********c
发帖数: 430 | 11 想了一下，好像比想象的复杂，case比较多，关键是进位比较麻烦。
还写不出代码，胡说一下讨论讨论。
从任意数字生成palindrome比较复杂，
先假定输入已经是palindrome，生成下一个palindrome，因为这个可以解决第二个以后
的数字
给定任意一个palindome，设两个index，都放在中间。
如果是奇数位aaaxbbb, i,j 都指x
如果是偶数位aaxxbb，则i指第一个x，j指第二个。
最接近的下一个数字就是就是把x＋1。如果x是9，就把x置零，对i-1,j+1加1
如果生成的最终数字多了一位如9999->10000, 就把个位数再加1.
现在就是怎么生成第一个palindrome，这个可以考虑用暴力，那就比较简单了。
如果不暴，是不是也可以用相似的双指针想法。但是好像情况比较复杂。
abcd efgh，还是俩index i j，从两边往中间扫。s[j] < s[i], 就把
s[j]变s[i]，如果s[j] > s[i] ，还是s[j]变s[i]，但是要把s[j-1]， s[i+1]加一。
思路好像不是很elegent. 先走，有空再想想。
【在 p*****2 的大作中提到】
:
: 是。大牛眼尖。
|
b*******e
发帖数: 123 | 12 就是考虑前一半数字
就贴怎么得到下个palinedrome吧。是不是有什么boundary case没考
虑到？
string frompaline(string s){
int isodd = s.size() % 2;
int half = stoi(s.substr(0,(s.size()+1)/2));
string res = to_string(half+1);
string ires = res.substr(0,res.size()-isodd);
reverse(ires.begin(),ires.end());
res += ires;
if(res.size() > s.size()+1){
res = string(s.size(),'0');
res[0] = '1';
res += '1';
}
return res;
} |
l*********8
发帖数: 4642 | 13 10, 结果是22？
【在 b*******e 的大作中提到】
: 就是考虑前一半数字
: 就贴怎么得到下个palinedrome吧。是不是有什么boundary case没考
: 虑到？
: string frompaline(string s){
: int isodd = s.size() % 2;
: int half = stoi(s.substr(0,(s.size()+1)/2));
: string res = to_string(half+1);
: string ires = res.substr(0,res.size()-isodd);
: reverse(ires.begin(),ires.end());
: res += ires;
|
b*******e
发帖数: 123 | 14 10 不是palinedrome. 第一个可以用try and error once...
Full code 太烦了。。
vector getall(int m, int n){
string nstr = to_string(n);
vector res;
function func = [](string s,bool addone){
int isodd = s.size() % 2;
int half = stoi(s.substr(0,(s.size()+1)/2));
string res = to_string(half+(addone?1:0));
string ires = res.substr(0,res.size()-isodd);
reverse(ires.begin(),ires.end());
res += ires;
if(res.size() > s.size()+1){
res = string(s.size()+1,'0');
res[0] = '1';
res.back() = '1';
}
return res;
};
string last = func(nstr,false); //试一次，不行下一个。
if(stoi(last) < n)
last = func(last,true);
while(res.size() < m){
res.push_back(last);
last = func(last,true);
}
return res;
}
【在 l*********8 的大作中提到】
: 10, 结果是22？
|
l*********8
发帖数: 4642 | 15 用ruby写了个任意非负整数的下一个Palindrome:
class Integer
def nextPalin
num = self.to_s.toPalin!.to_i
return num if num > self
self.to_s.nextPalin.to_i
end
end
class String
def toPalin!
self[(size+1)/2...size] = self[0...size/2].reverse
self
end
def nextPalin
(self[0...(size+1)/2].next + self[(size+1)/2...size]).toPalin!
end
end |
l*********8
发帖数: 4642 | 16 Test:
irb > 0.nextPalin
=> 1
irb > 1.nextPalin
=> 2
irb > 9.nextPalin
=> 11
irb > 10.nextPalin
=> 11
irb > 11.nextPalin
=> 22
irb > 99.nextPalin
=> 101
irb > 100.nextPalin
=> 101
irb > 101.nextPalin
=> 111
irb > 110.nextPalin
=> 111
irb > 111.nextPalin
=> 121
irb > 191.nextPalin
=> 202
irb > 898.nextPalin
=> 909
irb > 909.nextPalin
=> 919
irb > 999.nextPalin
=> 1001
irb > 1000.nextPalin
=> 1001
irb > 1091.nextPalin
=> 1111
irb > 1997.nextPalin
=> 2002
irb > 129913.nextPalin
=> 129921
【在 l*********8 的大作中提到】
: 用ruby写了个任意非负整数的下一个Palindrome:
: class Integer
: def nextPalin
: num = self.to_s.toPalin!.to_i
: return num if num > self
: self.to_s.nextPalin.to_i
: end
: end
: class String
: def toPalin!
|
d******o
发帖数: 3 | 17 haha 刚开始学java, 测试过了,方法不知道对不对，把int 变成string, 然后reverse(
). 如果 reverse 后 两个string 一样，就可以了
import java.util.ArrayList;
import java.util.List;
public class PalindromicNumbers {
public PalindromicNumbers() {
// TODO Auto-generated constructor stub
}
public static void main(String[] args) {
// TODO Auto-generated method stub
pNum(16, 162);
}
public static void pNum(int m, int n)
{
List intL= new ArrayList();
int count=0;
while (count < m) {
for (int i=0; i<1000000; i++)
{
int result= n+i;
String strResult=String.valueOf(result);
StringBuilder sb= new StringBuilder();
sb.append(strResult);
String reverStrResult=sb.reverse().toString();
//conver to int
int reverseInt = Integer.parseInt(reverStrResult);
if (result==reverseInt)
{
intL.add(result);
count=count+1;
if(count==m)
{
break;
}
}
}
}
System.out.println(intL);
}
}
【在 p*****2 的大作中提到】
: 给两个number，m和n，找到m个 >=n 的 Palindromic Numbers
: 1. m = 26, n =0
: 0 1 2 3 4 5 6 7 8 9
: 11 22 33 44 55 66 77 88 99
: 101 111 121 131 141 151 161
: 2. m=16, n=162
: 171 181 191 202
: 212 222 232 242
: 252 262 272 282
: 292 303 313 323
|
p*****2
发帖数: 21240 | 18
longway大牛出马了呀？我确实觉得你来解这题最合适不过了。一会儿研究一下大牛的
解法。
【在 l*********8 的大作中提到】
: 用ruby写了个任意非负整数的下一个Palindrome:
: class Integer
: def nextPalin
: num = self.to_s.toPalin!.to_i
: return num if num > self
: self.to_s.nextPalin.to_i
: end
: end
: class String
: def toPalin!
|
p*****2
发帖数: 21240 | 19
大牛，我跪了。按照你类似的思路写了一个，还是过不了OJ。
(fn toPalin [num]
(let [toInt #(Long/parseLong %)
s (str num)
len (count s)
mid (quot (inc len) 2)
mid- (quot len 2)
first (subs s 0 mid)
first- (subs s 0 mid-)
palin (toInt (str first (clojure.string/reverse first-)))
next (str ((comp str inc toInt) first) (apply str (repeat mid- \0)))]
(if (>= palin num) (cons palin (lazy-seq (toPalin (inc palin))))
(toPalin (toInt next)))))
【在 l*********8 的大作中提到】
: Test:
: irb > 0.nextPalin
: => 1
: irb > 1.nextPalin
: => 2
: irb > 9.nextPalin
: => 11
: irb > 10.nextPalin
: => 11
: irb > 11.nextPalin
|
l*********8
发帖数: 4642 | 20 跪了，二爷你这是什么语言？
【在 p*****2 的大作中提到】
:
: 大牛，我跪了。按照你类似的思路写了一个，还是过不了OJ。
: (fn toPalin [num]
: (let [toInt #(Long/parseLong %)
: s (str num)
: len (count s)
: mid (quot (inc len) 2)
: mid- (quot len 2)
: first (subs s 0 mid)
: first- (subs s 0 mid-)
|
|
|
p*****2
发帖数: 21240 | 21
Clojure。大牛现在的Ruby真是出神入化呀。
【在 l*********8 的大作中提到】
: 跪了，二爷你这是什么语言？
|
A*********c
发帖数: 430 | 22 请教二爷这说的是哪个OJ？
给个连接吧
【在 p*****2 的大作中提到】
:
: Clojure。大牛现在的Ruby真是出神入化呀。
|
r*c
发帖数: 167 | 23 The ardendertat.com's code is not always correct. For an example, it will
return 121121121 as the next palin for input 120798387, where there exists a
smaller one: 120808021 .
The following code has no such shortcoming. The key idea is greedy +
heuristic.
#include
#include
#include
#include
#include
using namespace std;
class NextPalinSolution
{
public:
vector NextPalin(const vectorssrc){
vectorsrc(ssrc);
int len = src.size();
int half = len >> 1;
bool isOdd = (len % 2 == 1);
bool isLeftBigger = IsLeftBigger(src);
OverWriteRightWithLeft(src); //greedy
if(isLeftBigger)
return src;
//minimal raise: raise the last digit on the lhs by 1
if(isOdd)
{
if(src[half] == 9)
{
src[half] = 0;
int i= (isOdd) ? half -1 : half;
return RippleToLeftAndPostProcess(src, i);
}else
{
src[half] += 1;
return src;
}
}else
return RippleToLeftAndPostProcess(src, half-1);
}
vector& RippleToLeftAndPostProcess(vector&src, int idx){
int nCarry = 1;
int i = idx;
for(; i>=0, nCarry > 0; i--)
{
int temp = src[i] + nCarry;
src[i] = temp % 10;
nCarry = temp - src[i];
}
//heuristic post processing after rippling
OverWriteRightWithLeft(src);
return src;
}
void OverWriteRightWithLeft(vector& src){
int len = src.size();
bool isOdd = (len % 2 == 1);
int i= (len >>1 ) -1; //the starting index for the left half
int j = (isOdd) ? (i +2) : (i + 1); //the starting index for the
right half
for(; i>=0, j
src[j] = src[i];
}
}
bool IsLeftBigger(const vectorsrc)
{
int len = src.size();
bool isOdd = (len % 2 == 1);
int i= (len >>1 ) -1; //the starting index for the left half
int j = (isOdd) ? (i + 2) : (i + 1); //the starting index for the
right half
for(; i>=0, j
{
if(src[i] < src[j])
return false;
}
return true;
}
}; |
p*****2
发帖数: 21240 | 24
http://www.4clojure.com/problem/150
【在 A*********c 的大作中提到】
: 请教二爷这说的是哪个OJ？
: 给个连接吧
|
p*****2
发帖数: 21240 | 25 终于过了OJ了。
(fn f [num]
(let [toInt (fn [s] (reduce #(+ (* % 10) (- (int %2) 48)) 0 s))
pow (fn [m n] (reduce #(* % %2) 1 (repeat n m)))
s (str num)
len (count s)
mid (quot (inc len) 2)
mid- (quot len 2)
first (subs s 0 mid)
first- (subs s 0 mid-)
palin (toInt (str first (clojure.string/reverse first-)))
next (* (inc (toInt first)) (pow 10 mid-))]
(if (>= palin num) (cons palin (lazy-seq (f (inc palin))))
(f next)))) |
l*********8
发帖数: 4642 | 26 Ruby我也就是会皮毛而已。
而且Ruby的前景不明朗啊。 看看二爷一会儿搞node.js, 一会儿搞Clojure, 我觉得很
多东西我也要学啊
【在 p*****2 的大作中提到】
: 终于过了OJ了。
: (fn f [num]
: (let [toInt (fn [s] (reduce #(+ (* % 10) (- (int %2) 48)) 0 s))
: pow (fn [m n] (reduce #(* % %2) 1 (repeat n m)))
: s (str num)
: len (count s)
: mid (quot (inc len) 2)
: mid- (quot len 2)
: first (subs s 0 mid)
: first- (subs s 0 mid-)
|
l*********8
发帖数: 4642 | 27 Zan! 二爷睡得真晚啊
【在 p*****2 的大作中提到】
: 终于过了OJ了。
: (fn f [num]
: (let [toInt (fn [s] (reduce #(+ (* % 10) (- (int %2) 48)) 0 s))
: pow (fn [m n] (reduce #(* % %2) 1 (repeat n m)))
: s (str num)
: len (count s)
: mid (quot (inc len) 2)
: mid- (quot len 2)
: first (subs s 0 mid)
: first- (subs s 0 mid-)
|
p*****2
发帖数: 21240 | 28
大牛现在工作用什么呢？
【在 l*********8 的大作中提到】
: Ruby我也就是会皮毛而已。
: 而且Ruby的前景不明朗啊。 看看二爷一会儿搞node.js, 一会儿搞Clojure, 我觉得很
: 多东西我也要学啊
|
b*****c
发帖数: 1103 | |
p*****2
发帖数: 21240 | 30
大牛又重出江湖了呀？
【在 b*****c 的大作中提到】
: 不会做
|
|
|
w**7
发帖数: 22 | 31 This question can be solved by (assume n has even digits for easy notation)
1. divide n in left and right, denoted as LR
2. n's closest palindrome has to be one of:
a. (L+1)(L+1), b. LL, c. (L-1)(L-1)
3. find the smallest of (a, b, c) that' greater than n, denoted as lr.
4. the rest are (l+1)(l+1), (l+2)(l+2),.... (l+m-1)(l+m-1).
when n has odd digits, the solution is the same. |
