练习题-题目来自力扣

一、3.12

1. 两数之和

• 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。
  你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
  你可以按任意顺序返回答案。
• 举例
  输入：nums = [2,7,11,15], target = 9
  输出：[0,1]
  解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1]

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        a=[]
        for i in range(len(nums)) :
            for j in range(i+1,len(nums)):
                if nums[i]+nums[j]==target:
                    a.append(i)
                    a.append(j)
        return a

• 因为不能重复，所以利用i+1来避开重复计算
• append每次只能传一次参数

2.两数相加

• 给你两个 非空 的列表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个只能存储 一位 数字。
  请你将两个数相加，并以相同形式返回一个表示和的列表。
  你可以假设除了数字 0 之外，这两个数都不会以 0 开头
• 举例
  输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
  输出：[8,9,9,9,0,0,0,1]
  输入：l1 = [2,4,3], l2 = [5,6,4]
  输出：[7,0,8]
  解释：342 + 465 = 807.

class Solution:
    def addTwoNumbers(self, l1: List, l2: List) -> List:
        a=''
        b=''
        c=[]
        for i in (l1[::-1]):
            a=a+str(i)
        for j in (l2[::-1]):
            b=b+str(j)
        for i in str(int(a)+int(b)):
            c.append(int(i))
        c[::-1]

• string不能用append,列表才可以，字符串直接相加合并
• 不能对列表直接转化位字符串，只能诶个访问转化

3.无重复字符的最长子串

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

输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

## 我的解答，速度慢
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        a=[0]  
        for i in range(len(s)):
            b=[s[i]]
            j=i+1
            while j <len(s):
                if s[j] in b :
                    a.append(j-i)
                    break
                else:
                    b.append(s[j])
                j+=1
            else:
                a.append(len(s)-i)
        return max(a)

• 用嵌套循环，用每一个i为开头，从这个数开始往后数到几个会出现重复的，出现就停止循环，并把长度记录下来，

滑动窗口

思路：
这道题主要用到思路是：滑动窗口

• 其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！
• 如何移动？
  我们只要把队列的重复的元素移出就行了，直到满足题目要求！
  一直维持这样的队列，找出队列出现最长的长度时候，求出解！
  时间复杂度：O(n)

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:return 0
        left = 0 ##左边的数
        lookup = set() ##队伍
        n = len(s)
        max_len = 0 ##最长的长度
        cur_len = 0  ##现在的长度
        for i in range(n):
            cur_len += 1
            while s[i] in lookup:
                lookup.remove(s[left])
                left += 1
                cur_len -= 1
            if cur_len > max_len:max_len = cur_len 
            lookup.add(s[i])
        return max_len

• 求取最长的长度，可以if cur_len > max_len:max_len = cur_len 用这个，如果大于就把数存给最大值，而不是用列表存储，列表存储占内存而且空列表不能用max()
• while循环初始值的没有发生变化也能循环两次，可以用来删除重复值

4. 寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

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

• 合并数组并排序
• 初始值是0，所以要网前移一位

5.最长回文子串

# 方法一：暴力匹配 （Brute Force）
class Solution:
    # 暴力匹配（超时）
    def longestPalindrome(self, s: str) -> str:
        # 特判
        size = len(s)
        if size < 2:
            return s
        max_len = 1
        res = s[0]
        # 枚举所有长度大于等于 2 的子串
        for i in range(size - 1):
            for j in range(i + 1, size):
                if j - i + 1 > max_len and self.__valid(s, i, j):
                    max_len = j - i + 1
                    res = s[i:j + 1]
        return res

    def __valid(self, s, left, right):
        # 验证子串 s[left, right] 是否为回文串
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True

复杂度分析：

时间复杂度：O(N^3)，这里 N 是字符串的长度，枚举字符串的左边界、右边界，然后继续验证子串是否是回文子串，这三种操作都与 N 相关；
空间复杂度：O(1)，只使用到常数个临时变量，与字符串长度无关。

76. 最小覆盖子串

• 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。

• 注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。

• 输入：s = “ADOBECODEBANC”, t = “ABC”
  输出：“BANC”

class Solution:
   def minWindow(self, s: 'str', t: 'str') -> 'str':
       from collections import defaultdict
       lookup = defaultdict(int)
       for c in t:
           lookup[c] += 1
       start = 0
       end = 0
       min_len = float("inf")
       counter = len(t)
       res = ""
       while end < len(s):
           if lookup[s[end]] > 0:
               counter -= 1
           lookup[s[end]] -= 1
           end += 1
           while counter == 0:
               if min_len > end - start:
                   min_len = end - start
                   res = s[start:end]
               if lookup[s[start]] == 0:
                   counter += 1
               lookup[s[start]] += 1
               start += 1
       return res

最后

以上就是搞怪龙猫为你收集整理的python练习题练习题-题目来自力扣的全部内容，希望文章能够帮你解决python练习题练习题-题目来自力扣所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。