上一道小题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

上一道小题

上一道小题# JobHunting - 待字闺中

p*22013-11-20 08:11

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*d2013-11-20 08:11

2 楼

is mlog(n) fast enough? er ye.

A*c2013-11-20 08:11

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*22013-11-20 08:11

4 楼

感觉应该够。说说算法？

【在 o********d 的大作中提到】

: is mlog(n) fast enough? er ye.

p*22013-11-20 08:11

5 楼

我感觉这样可以。细节想清楚了吗？

【在 A*********c 的大作中提到】

: 先乱说一下不知道靠谱不，要实现的话要用生成法，从m起生成n次吧。
: string GenNextPalindrome(const string &s);
: 要是一个一个的话验证太慢了。
: 再想想实现。

o*d2013-11-20 08:11

6 楼

http://www.ardendertat.com/2011/12/01/programming-interview-que
见过而已~ 第一次见也不会做

【在 p*****2 的大作中提到】

:
: 我感觉这样可以。细节想清楚了吗？

p*22013-11-20 08:11

7 楼

跟我想的基本一样。我就是觉得细节太多了，你看他下边的comments，还是不能涵盖所
有的case。

【在 o********d 的大作中提到】

: http://www.ardendertat.com/2011/12/01/programming-interview-que
: 见过而已~ 第一次见也不会做

m*k2013-11-20 08:11

8 楼

应该是找到最小的m个 >=n 的 Palindromic Numbers吧
否者就太简单了，呵呵。

【在 p*****2 的大作中提到】

p*22013-11-20 08:11

9 楼

是。大牛眼尖。

【在 m*****k 的大作中提到】

: 应该是找到最小的m个 >=n 的 Palindromic Numbers吧
: 否者就太简单了，呵呵。

l*82013-11-20 08:11

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*c2013-11-20 08:11

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*e2013-11-20 08:11

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*82013-11-20 08:11

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*e2013-11-20 08:11

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*82013-11-20 08:11

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*82013-11-20 08:11

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*o2013-11-20 08:11

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 的大作中提到】

p*22013-11-20 08:11

18 楼

longway大牛出马了呀？我确实觉得你来解这题最合适不过了。一会儿研究一下大牛的
解法。

【在 l*********8 的大作中提到】

p*22013-11-20 08:11

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*82013-11-20 08:11

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*22013-11-20 08:11

21 楼

Clojure。大牛现在的Ruby真是出神入化呀。

【在 l*********8 的大作中提到】

: 跪了，二爷你这是什么语言？

A*c2013-11-20 08:11

22 楼

请教二爷这说的是哪个OJ？
给个连接吧

【在 p*****2 的大作中提到】

:
: Clojure。大牛现在的Ruby真是出神入化呀。

r*c2013-11-20 08:11

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, jsrc[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*22013-11-20 08:11

24 楼

http://www.4clojure.com/problem/150

【在 A*********c 的大作中提到】

: 请教二爷这说的是哪个OJ？
: 给个连接吧

p*22013-11-20 08:11

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*82013-11-20 08:11

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*82013-11-20 08:11

27 楼

Zan! 二爷睡得真晚啊

【在 p*****2 的大作中提到】

p*22013-11-20 08:11

28 楼

大牛现在工作用什么呢？

【在 l*********8 的大作中提到】

: Ruby我也就是会皮毛而已。
: 而且Ruby的前景不明朗啊。看看二爷一会儿搞node.js, 一会儿搞Clojure, 我觉得很
: 多东西我也要学啊

b*c2013-11-20 08:11

29 楼

不会做

p*22013-11-20 08:11

30 楼

大牛又重出江湖了呀？

【在 b*****c 的大作中提到】

: 不会做

w*72013-11-20 08:11

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.