cxy
0%

leetcode自测答题——2019-01-13

发表于 更新于 分类于 Valine：
本文字数： 1.7k 阅读时长 ≈ 2 分钟

emmmm决定从今天开始刷leetcode。。。在这里记录一下我的答题思路和结果吧。可能不是最棒的。如果大家有更好的解题思路请多多指教～

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

原题：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
在这里插入图片描述

这里利用了窗口滑动的效果。当已经确定[i, j]中没有重复元素的时候，就可以直接看j+1在不在[i-1, j]中就可以了。最后不要忘记，如果字符串长度为1的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        no_same = []
        i = 0
        max_len = 0
        while i < len(s):
            if s[i] not in no_same:
                no_same.append(s[i])
                i += 1
            else:
                max_len = max([max_len, len(no_same)])
                no_same.pop(0)
        max_len = max([max_len, len(no_same)])
        return max_len

寻找两个有序数组的中位数

原题：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/

在这里插入图片描述
这里我用了最简单的合并，排序。但是时间复杂度是O(m+n)，并不符合题目= =。(待完成)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        nums1.extend(nums2)
        new = sorted(nums1)
        if len(new) % 2 == 0:
            i = (0 + len(new)) // 2
            middle = (new[i-1] + new[i]) / 2
        else:
            i = (0 + len(new) - 1) // 2
            middle = new[i]
        return middle

最长回文子串

原题：https://leetcode-cn.com/problems/longest-palindromic-substring/

在这里插入图片描述

回文，说简单了就是顺序读和倒序读是一样的。或者说，从中心开始，依次往外依次扩散的字符都相同。因此，以这个为思路，从中心出发。但是，字符串长度可能是奇数，也可能是偶数。因此需要考虑这两种情况，以下是图解：

在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        longest_str = str()
        for i in range(len(s)):
            lstr = get_around_string(s, i, i)
            rstr = get_around_string(s, i, i+1)
            longe_str = lstr if len(lstr) >= len(rstr) else rstr
            longest_str = longe_str if len(longe_str) >= len(longest_str) else longest_str
        return longest_str

def get_around_string(s, left, right):
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    left += 1
    return s[left: right]