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"
|