j***n
发帖数: 301 | 1 1）给一个string，如何通过插入最少的字符使得它变成palindrome？
2) Given an integer, print the closest number to it that is a palindrome
input: 1224
return: 1221.
谁能给个链接，谢谢 |
K******g
发帖数: 1870 | 2 这还是老题啊？从没有见过这两题。我已经在这里混了2个多月了。。。
【在 j***n 的大作中提到】
: 1）给一个string，如何通过插入最少的字符使得它变成palindrome？
:
: 2) Given an integer, print the closest number to it that is a palindrome
: input: 1224
: return: 1221.
: 谁能给个链接，谢谢
|
K******g
发帖数: 1870 | 3 第二题，感觉好像不难？
找到中间那个数字，假设是第i个，比较i+1和i-1位置的数字，如果相同，则比较i+2和
i-2,如果不同了，就把i-2的数字换成i+2的就行了?
【在 j***n 的大作中提到】
: 1）给一个string，如何通过插入最少的字符使得它变成palindrome？
:
: 2) Given an integer, print the closest number to it that is a palindrome
: input: 1224
: return: 1221.
: 谁能给个链接，谢谢
|
c*********n
发帖数: 1057 | 4
~~~~~~~~~~~~~~~~~~~~~~~i+2的换成i-2的吧？这样才是最接近的
【在 K******g 的大作中提到】
: 第二题，感觉好像不难？
: 找到中间那个数字，假设是第i个，比较i+1和i-1位置的数字，如果相同，则比较i+2和
: i-2,如果不同了，就把i-2的数字换成i+2的就行了?
|
R***Z
发帖数: 1167 | 5 直接从两头比起不行吗？
【在 K******g 的大作中提到】
: 第二题，感觉好像不难？
: 找到中间那个数字，假设是第i个，比较i+1和i-1位置的数字，如果相同，则比较i+2和
: i-2,如果不同了，就把i-2的数字换成i+2的就行了?
|
b***u
发帖数: 61 | 6 还需要考虑有奇数个数字还是偶数个数字吧
【在 K******g 的大作中提到】
: 第二题，感觉好像不难？
: 找到中间那个数字，假设是第i个，比较i+1和i-1位置的数字，如果相同，则比较i+2和
: i-2,如果不同了，就把i-2的数字换成i+2的就行了?
|
c******f
发帖数: 2144 | |
j***n
发帖数: 301 | 8 第二题，输入1299. This should return 1331 and not 1221
【在 R***Z 的大作中提到】
: 直接从两头比起不行吗？
|
c*********n
发帖数: 1057 | 9 1是不是用DP？
I[i][j] = min # of char added to make substring from i to j become
palindrome
S[i][j] = the corresponding palindrome string converted from substring i to
j
then I[i][i]=0;I[i+1][i]=0
I[i][j] = min( I[i][j-1], I[i+1][j]) + 1 //if charAt[i] != charAt[j]
= I[i+1][j-1] //otherwise
S[i][j] modified accordingly
return S[0][N]
【在 j***n 的大作中提到】
: 1）给一个string，如何通过插入最少的字符使得它变成palindrome？
:
: 2) Given an integer, print the closest number to it that is a palindrome
: input: 1224
: return: 1221.
: 谁能给个链接，谢谢
|
j***n
发帖数: 301 | 10 嗯，这个是对的。还有一种做法是就longest common sequence of (s, reverse(s))
to
【在 c*********n 的大作中提到】
: 1是不是用DP？
: I[i][j] = min # of char added to make substring from i to j become
: palindrome
: S[i][j] = the corresponding palindrome string converted from substring i to
: j
: then I[i][i]=0;I[i+1][i]=0
: I[i][j] = min( I[i][j-1], I[i+1][j]) + 1 //if charAt[i] != charAt[j]
: = I[i+1][j-1] //otherwise
: S[i][j] modified accordingly
: return S[0][N]
|
r****o
发帖数: 1950 | 11 LCS的方法怎么做啊?
【在 j***n 的大作中提到】
: 嗯，这个是对的。还有一种做法是就longest common sequence of (s, reverse(s))
:
: to
|
j***n
发帖数: 301 | 12 想了一下，求一个可能得到的Palindrome还是可行的。不过要是想求所有的可能的Pali
ndrome有没有什么优雅的解法？
举例：To make "RACE" into a palindrome, we must add at least three letters.
However, there are eight ways to do this by adding exactly three letters:
"ECARACE" "ECRARCE" "ERACARE" "ERCACRE"
"RACECAR" "RAECEAR" "REACAER" "RECACER"
【在 r****o 的大作中提到】
: LCS的方法怎么做啊?
|
c*********n
发帖数: 1057 | 13 用我之前那个方法，稍微该下就可以实现了，S存 a list of string，就可以了
Pali
【在 j***n 的大作中提到】
: 想了一下，求一个可能得到的Palindrome还是可行的。不过要是想求所有的可能的Pali
: ndrome有没有什么优雅的解法？
: 举例：To make "RACE" into a palindrome, we must add at least three letters.
: However, there are eight ways to do this by adding exactly three letters:
: "ECARACE" "ECRARCE" "ERACARE" "ERCACRE"
: "RACECAR" "RAECEAR" "REACAER" "RECACER"
|
