Posted on | In

[LeetCode: No.5]

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

1
2
3
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

1
2
Input: "cbbd"
Output: "bb"

最长回文子串的中间子串也是回文串，换言之，回文串是否最长，可以看回文串两边的字符是否相同。例如“dabcba”的最长回文子串是“abcba”，其可看出回文子串“bcb”的拓展，判断“bab”两边的字符是否相同决定是否进行回文子串拓展（可以利用切片的索引左右移动实现）

由这个想法下， 写出第一个代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if len(s) < 2:
            return s
        self.res = ""
        for i in range(len(s)):
            left = right = i
            while left>=0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            if right -left -1 > len(self.res):
                self.res = s[left+1:right]
        return self.res
Read more »

Posted on | In

[LeetCode: No.4]

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

仔细分析题目，nums1和nums2都已经是排好序了的，这就大大的降低了难度，让找到两个列表的中间值，其实我们可以拓展为找到两个列表的第k个值。当然这个是拓展部分了，对于这个题目，有不同的思路，最简单粗暴的就是将两个列表合并，之后进行排序，拍好序后进行寻找中间值就简单了。但是用传统的先合并再排序，效率想必会很低~

我们发现对于两个已经有序的列表（从小到大），其实有一个更优的排序方式：从小到大，依次进行列表元素的比较，较小值放到一个新列表中，比如A中该位置的值较小，将其放到新的列表C中，同时将A列表下一个值继续与B中当前位置元素进行比较，以此类推。这样的比较次数就比先合并在排序小很多啦！代码如下：

Read more »