标签 leetcode 下的文章

5. Longest Palindromic Substring最长回文子串

解法1:中心拓展算法

思路

首先,我们知道回文串一定是对称的,所以我们可以选择一个对称中心,进行左右扩展,判断左右字符是否相等即可。
由于存在奇数的字符串和偶数的字符串,所以我们需要从一个字符开始扩展,或者从两个字符之间开始扩展,所以总共有 n+n-1 个中心。

实现代码

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        Max,sub = 0,s[0:1]
        for i in range(n):
            tmp = self.searchPalindrome(i-1,i+1,s)
            if len(tmp) > Max:
                Max = len(tmp)
                sub = tmp
            tmp = self.searchPalindrome(i-1,i,s)
            if len(tmp) > Max:
                Max = len(tmp)
                sub = tmp    
        return sub
    
    def searchPalindrome(self, left: int, right: int, s: str) -> int:
        sub = ""
        while left != -1 and right != len(s):
            if s[left] == s[right]:
                sub = s[left:right+1]
                left-=1
                right+=1
            else : break
        return sub

马拉车算法

class Solution:
    # Manacher 算法
    def longestPalindrome(self, s: str) -> str:
        # 特判 
        if len(s) < 2 or s == s[::-1]:
            return s

        # 得到预处理字符串
        t = "#" + "#".join(s) + "#"

        # 新字符串的长度
        t_len = len(t)

        # 数组 p 记录了扫描过的回文子串的信息
        p = [0]*t_len

        # 双指针,它们是一一对应的,须同时更新
        max_right = 0
        center = 0

        # 当前遍历的中心最大扩散步数,其值等于原始字符串的最长回文子串的长度
        max_len = 1
        # 原始字符串的最长回文子串的起始位置,与 max_len 必须同时更新
        start = 1

        for i in range(t_len):
            if i < max_right:
                mirror = 2 * center - i
                # 这一行代码是 Manacher 算法的关键所在,要结合图形来理解
                p[i] = min(max_right - i, p[mirror])

            # 下一次尝试扩散的左右起点,能扩散的步数直接加到 p[i] 中
            left = i - (1 + p[i])
            right = i + (1 + p[i])

            # left >= 0 and right < t_len 保证不越界
            # t[left] == t[right] 表示可以扩散 1 次
            while left >= 0 and right < t_len and t[left] == t[right]:
                p[i] += 1
                left -= 1
                right += 1

            # 根据 max_right 的定义,它是遍历过的 i 的 i + p[i] 的最大者
            # 如果 max_right 的值越大,进入上面 i < max_right 的判断的可能性就越大,这样就可以重复利用之前判断过的回文信息了
            if i + p[i] > max_right:
                # max_right 和 center 需要同时更新
                max_right = i + p[i]
                center = i

            if p[i] > max_len:
                # 记录最长回文子串的长度和相应它在原始字符串中的起点
                max_len = p[i]
                start = (i - max_len) // 2
        return s[start: start + max_len]

成果

2020-01-19T15:04:32.png

【leetcode】4. Median of Two Sorted Arrays寻找两个有序数组的中位数

我的初次实现

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        newList = nums1 + nums2
        newList.sort()
        result = 0
        if(len(newList)%2 != 0) :
            result = newList[math.ceil(len(newList)/2-1)]
        else:
            index = int(len(newList)/2)
            result = (newList[index] + newList[index-1])/2
        return result

成果

2020-01-16T13:40:45.png

问题

但是我们仔细观察,可以发现这个的时间复杂度是不够的。

题目描述

思路

查找无重复的字符子串,然后滑动窗口

初次解

每次滑动一格窗口

class Solution:
    def isUnique(self, s: str) -> bool:
        for ch in s:
            if s.count(ch) > 1:
                return False
            else:
                continue
        return True
    def lengthOfLongestSubstring(self, s: str) -> int:
        i,j,Max=0,0,0
        j+=1
        while j <= len(s):
            if self.isUnique(s[i:j]):
                print(s[i:j],"is Unique",i,j)
                Max=max(j-i,Max)
                j+=1
            else:
                i+=1
        return Max

成果

第一次优化

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if(len(s)==1): 
            return 1
        i,j,Max=0,0,0
        while j <= len(s):
            st = s[i:j+1]
            if(j+1 < len(s)):
                index = st.find(s[j+1])
                if index > -1:
                    i+=(index+1)
                j+=1
                Max=max(j-i+1,Max)
            else:
                break
        return Max

成果

2020-01-15T07:27:31.png

【leetcode】2. Add Two Numbers两数相加

描述

给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。

如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外,这两个数都不会以 0 开头。

示例:
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807

思路

我看到这个题的第一感觉就是用递归把数获取出来,然后再相加,之后再把得数结构化。问题就被细分为了两个方面:

  1. 加数的提取
  2. 得数的结构化

我的初次实现

class Solution:
    def getStr(self,node: ListNode) -> str:
        if node.next == None:
            return node.val
        else:
            last = self.getStr(node.next)
            return  str(last) + str(node.val)

    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        num1 = self.getStr(l1)
        num2 = self.getStr(l2)
        result = int(num1) + int(num2)
        resultList = list(str(result))
        tmp = ListNode(int(resultList.pop(0)))
        List = tmp
        while resultList:
            tmp = ListNode(int(resultList.pop(0)))
            tmp.next = List
            List = tmp
        return List

成果

成果

改进思路

利用人列竖式算法的方法,计算每一列的值

改进代码

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        # if l1.next == None and l1.val == 0:
        #    return l2
        # if l2.next == None and l2.val == 0:
        #    return l1
        l1_iter = l1
        l2_iter = l2
        Sum = l1_iter.val + l2_iter.val
        carry = 1 if Sum >= 10 else 0
        Sum %= 10
        List = ListNode(Sum)
        l1_iter = l1_iter.next
        l2_iter = l2_iter.next
        Site = List
        while(l1_iter != None and l2_iter != None):
            Sum = l1_iter.val + l2_iter.val + carry
            carry = 1 if Sum >= 10 else 0
            Sum %= 10
            tmp = ListNode(Sum)
            Site.next = tmp
            Site = Site.next
            l1_iter = l1_iter.next
            l2_iter = l2_iter.next
        last = Site
        if(l1_iter == None and l2_iter == None) :
            if(carry == 1):
                tmp = ListNode(carry)
                last.next = tmp
            return List
        else:
            Site = l1_iter if l2_iter == None else l2_iter
            tail = Site
            while(Site != None and carry == 1):
                Sum = Site.val + carry
                Site.val = Sum % 10
                carry = 0 if Sum < 10 else 1
                if(Site.next == None and carry == 1):
                    tmp = ListNode(carry)
                    Site.next = tmp
                    break
                Site = Site.next
            last.next = tail
        return List

成果

Add Two Numbers超越100%的Python用户

leetcode(1): two sum

Description

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

0. My solution(Brute Force)

var twoSum = function(nums, target) {
    for(let i = 0; i < nums.length; i++) {
        for(let j = 0; j < nums.length; j++) {
            if(nums[i] + nums[j] === target && i != j) {
                return [i, j]
            }
        }
    }
};

· Time complexity: O(n^2), For each element, I try to find its complement by looping through the rest of array which takes O(n)*O(n) time. Therefore, the time complexity is O(n^2).

· Space complexity : O(1).

1. Improve

var twoSum = function(nums, target) {
    for(let i = 0; i < nums.length; i++) {
        for(let j = i + 1; j < nums.length; j++) {
            if(nums[i] + nums[j] === target) {
                return [i, j]
            }
        }
    }
};

2. Improve again

var twoSum = function(nums, target) {
    for(var i = 0; i< nums.length; i++){
        var complement = target - nums[i];
        var found = nums.indexOf(complement, i + 1);
        if(found !== -1){
            return [i, found];
        }
    }
    return [0, 0];
};

3. Improve again

var twoSum = function(nums, target) {
    if (nums.length === 2) return [0, 1];
    const len = nums.length;
    let hashTable = {};
    for(let i = 0; i < len; i++){
        // Add a new obj to the hashTable where key = nums[i] and value = i
        hashTable[nums[i]] = i;
    }
    
    for(let i = 0; i < len; i++) {
        let complement = target - nums[i];
        let found = hashTable[complement]; // Determine whether the complement exist in the hashTable
        if(found !== undefined && found != i) return [i, found];
    }
    return [0,0];
}

B站视频地址