Redian新闻
>
Huawei P8 lite 回国能用 3G 4G 吗?
avatar
Huawei P8 lite 回国能用 3G 4G 吗?# PDA - 掌中宝
d*4
1
Longest Palindromic Substring这一题. 同样的O(n^2)算法,java能过,python不能
过。
python exceeds time limit 了.
The following is java version:
public String longestPalindrome(String s) {
if(s == null || s.length()==0)
return "";
int maxLen = 0;
String res = "";
for(int i=0;i<2*s.length()-1;i++)
{
int left = i/2;
int right = i/2;
if(i%2==1)
right++;
String str = lengthOfPalindrome(s,left,right);
if(maxLen{
maxLen = str.length();
res = str;
}
}
return res;
}
private String lengthOfPalindrome(String s, int left, int right)
{

while(left>=0 && right{
left--;
right++;
}
return s.substring(left+1,right);
}
avatar
s*t
2
去年11月份140就 approve了,但是人不在国内,LD办理出生公证耽误了不少时间,再
加上律师事务所放假,所以485直到今年年初才递交上去。貌似一切都还比较顺利,希
望485早点拿到。:-)
也祝愿版上所有xdjm们2013好运,心想事成!
140 RD: 11/08/12
140 AD: 11/15/12
485 RD: 01/16/13
Fingerprint Notice DATE:01/28/13
Fingerprint DATE: 01/30/13 (walk in)
Fingerprint DATE: 02/06/13(scheduled)
EAD/AP Approval Date:02/11/13
avatar
C*n
3
怎么查这个是否可以用?谢谢
avatar
i*h
4
我也用python寫的,一開始試過各種O(n^2)方法都不行,估計預期是要manacher之類O(
n)的算法;不過我後來用一些trick把它給過了,主要是對於長字串和短字段分別處理
class Solution:
# @return a string
def longestPalindrome(self, s):
if s is None or len(s) == 0:
return ''
def max_palindrome(left, right, min_length):
if right - left < min_length:
return ''
start = left
while left < right:
if s[left] != s[right]:
if right - left < min_length:
return ''
start = left + 1
left += 1
right -= 1
length = (left - start) * 2 + (right - left + 1)
return s[start:start+length]
def is_palindrome(left, right):
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
def get_max(left, cur_s, right, max_palin):
while left >= 0 and right < len(s) and s[left] == s[right]:
cur_s = s[left] + cur_s + s[right]
left -= 1
right += 1
return cur_s if len(cur_s) > len(max_palin) else max_palin
def process_short(max_palin):
for distance in xrange(half + 1):
for sign in (-1, 1):
i = half + sign * distance
# even palindrome
max_palin = get_max(i - 1, '', i, max_palin)
# odd palindrome
if i < len(s):
max_palin = get_max(i - 1, s[i], i + 1, max_palin)
max_half = min(i, len(s) - i)
if len(max_palin) == max_half * 2:
return max_palin
return max_palin
half = len(s) / 2
if len(s) <= 300:
return process_short(s[0])
if is_palindrome(0, len(s) - 1):
return s
max_palin = ''
for i in range(1, half):
if is_palindrome(i, len(s) - 1) and len(s[i:len(s)]) > len(max_
palin):
max_palin = s[i:len(s)]
for j in range(half, len(s) - 1):
if is_palindrome(0, j) and len(s[:j + 1]) > len(max_palin):
max_palin = s[:j + 1]
if not max_palin:
cur_max = self.longestPalindrome(s[:half])
if len(cur_max) > len(max_palin):
max_palin = cur_max
cur_max = self.longestPalindrome(s[half:])
if len(cur_max) > len(max_palin):
max_palin = cur_max
if len(max_palin) >= half:
return max_palin
return process_short(max_palin)
avatar
b*j
5
Cong!
avatar
h*k
6
找当地技术支持查支持什么制式,再跟国内的比较一下就可以确定了
avatar
d*4
7
That's great. But it's hard to figure out the way in interview.

O(

【在 i***h 的大作中提到】
: 我也用python寫的,一開始試過各種O(n^2)方法都不行,估計預期是要manacher之類O(
: n)的算法;不過我後來用一些trick把它給過了,主要是對於長字串和短字段分別處理
: class Solution:
: # @return a string
: def longestPalindrome(self, s):
: if s is None or len(s) == 0:
: return ''
: def max_palindrome(left, right, min_length):
: if right - left < min_length:
: return ''

avatar
i*1
8
avatar
l*s
10
my accepted codes. seems different algorithm than the one found online
class Solution:
# @return a string
def longestPalindrome(self, s):
le = len(s)
if not s:
return ''
table=[] #record longest so far and longest ending at i
table.append(((0,0), 1))
for i in xrange(1,le):
curind=table[-1][0]
lastsofar=curind[1]-curind[0]+1
lastending=table[-1][1]
for j in xrange(i-lastending-1, i+1):
if j<0:
continue
elif self.isPalindrome(s[j:i+1]):
curending=i-j+1
if curending>lastsofar:
curind=(j, i)
table.append((curind, curending))
break
curind=table[-1][0]
return s[curind[0]:curind[1]+1]
def isPalindrome(self, s):
le = len(s)
i=0
j=le-1
if le<=1:
return True
while iwhile not s[i].isalnum():
i+=1
if i>=j:
return True
while not s[j].isalnum():
j-=1
if i>=j:
return True
if s[i] != s[j] and abs(ord(s[i])-ord(s[j])) !=32:
return False
else:
i+=1
j-=1
return True

【在 d******4 的大作中提到】
: Longest Palindromic Substring这一题. 同样的O(n^2)算法,java能过,python不能
: 过。
: python exceeds time limit 了.
: The following is java version:
: public String longestPalindrome(String s) {
: if(s == null || s.length()==0)
: return "";
: int maxLen = 0;
: String res = "";
: for(int i=0;i<2*s.length()-1;i++)

avatar
s*s
11
cong~~~~~~~~

【在 s*******t 的大作中提到】
: 去年11月份140就 approve了,但是人不在国内,LD办理出生公证耽误了不少时间,再
: 加上律师事务所放假,所以485直到今年年初才递交上去。貌似一切都还比较顺利,希
: 望485早点拿到。:-)
: 也祝愿版上所有xdjm们2013好运,心想事成!
: 140 RD: 11/08/12
: 140 AD: 11/15/12
: 485 RD: 01/16/13
: Fingerprint Notice DATE:01/28/13
: Fingerprint DATE: 01/30/13 (walk in)
: Fingerprint DATE: 02/06/13(scheduled)

avatar
D*3
12

其实这个java解本身就不是最优的。因为跑了很多根本没可能是最长susbtring的解。
Leetcode对python的速度比较高。我在你的算法上改进了下:
从中间开始选对称轴,向两边移动。当剩下的最长可能palindrome substring都没当前
最长的palindrome subtring长的时候,立刻返回当前最长的解。

【在 d******4 的大作中提到】
: Longest Palindromic Substring这一题. 同样的O(n^2)算法,java能过,python不能
: 过。
: python exceeds time limit 了.
: The following is java version:
: public String longestPalindrome(String s) {
: if(s == null || s.length()==0)
: return "";
: int maxLen = 0;
: String res = "";
: for(int i=0;i<2*s.length()-1;i++)

avatar
s*s
13
Cong
avatar
D*3
14

我原来给的解还能refactor一下。给个新的吧:
--------
其实这个java解本身就不是最优的。因为跑了很多根本没可能是最长susbtring的解。
Leetcode对python的速度比较高。我在你的算法上改进了下:
从中间开始选对称轴,向两边移动。当剩下的最长可能palindrome substring都没当前
最长的palindrome subtring长的时候,立刻返回当前最长的解。
class Solution:
def longestPalindrome(self, s):
longest, mid = "", (len(s) - 1) / 2
i, j = mid, mid
while i >= 0 and j < len(s):
args = [(s, i, i), (s, i, i + 1), (s, j, j), (s, j, j + 1)]
for arg in args:
tmp = self.longestPalindromeByAxis(*arg)
if len(tmp) > len(longest):
longest = tmp
if len(longest) >= i * 2:
return longest
i, j = i - 1, j + 1
return longest

def longestPalindromeByAxis(self, s, left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left, right = left - 1, right + 1
return s[left + 1 : right]
---
source: https://github.com/jw2013/Leetcode/

【在 d******4 的大作中提到】
: Longest Palindromic Substring这一题. 同样的O(n^2)算法,java能过,python不能
: 过。
: python exceeds time limit 了.
: The following is java version:
: public String longestPalindrome(String s) {
: if(s == null || s.length()==0)
: return "";
: int maxLen = 0;
: String res = "";
: for(int i=0;i<2*s.length()-1;i++)

avatar
a*n
15
gx
avatar
l*c
16
cong
avatar
s*u
17
cong
avatar
d*p
18
恭喜,baozi
avatar
m*5
19
cong~~~~~~~~
TSC就是神速啊
avatar
G5
20
avatar
z*e
21
cong!
avatar
h*1
22
恭喜,神速啊,住485早批

【在 s*******t 的大作中提到】
: 去年11月份140就 approve了,但是人不在国内,LD办理出生公证耽误了不少时间,再
: 加上律师事务所放假,所以485直到今年年初才递交上去。貌似一切都还比较顺利,希
: 望485早点拿到。:-)
: 也祝愿版上所有xdjm们2013好运,心想事成!
: 140 RD: 11/08/12
: 140 AD: 11/15/12
: 485 RD: 01/16/13
: Fingerprint Notice DATE:01/28/13
: Fingerprint DATE: 01/30/13 (walk in)
: Fingerprint DATE: 02/06/13(scheduled)

avatar
G*n
23
Big cong!
avatar
k*g
24
Cong!
avatar
e*p
25
Bless!
avatar
m*r
26
cong
avatar
s*7
27
cong, baozi
avatar
y*9
28
GXGX and bless for your 485!
avatar
A*n
29
cong
avatar
V*A
30
gx
\baozi!
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。