LeetCode 笔记

[TOC]

动态规划

# 1.给定无序整数序列，求连续非空子串最大和，例如{-23 17 -7 11 -2 1 -34}，子串为{17,-7,11}，最大和为21
nums = [int(i) for i in input().split(' ')]

for i in range(len(nums) - 1):
    if nums[i] > 0:
        nums[i + 1] += nums[i]

print(max(nums))

搜索

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

class Solution: def lengthOfLongestSubstring(self, s): """ :type s: str :rtype: int """ from collections import defaultdict lookup = defaultdict(int) start = 0 end = 0 max_len = 0 counter = 0 while end < len(s): if lookup[s[end]] > 0: counter += 1 lookup[s[end]] += 1 end += 1 while counter > 0: if lookup[s[start]] > 1: counter -= 1 lookup[s[start]] -= 1 start += 1 max_len = max(max_len, end - start) return max_len

76. 最小覆盖子串

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 159. 至多包含两个不同字符的最长子串

class Solution: def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int: from collections import defaultdict lookup = defaultdict(int) start = 0 end = 0 max_len = 0 counter = 0 while end < len(s): if lookup[s[end]] == 0: counter += 1 lookup[s[end]] += 1 end +=1 while counter > 2: if lookup[s[start]] == 1: counter -= 1 lookup[s[start]] -= 1 start += 1 max_len = max(max_len, end - start) return max_len 340. 至多包含 K 个不同字符的最长子串

class Solution: def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int: from collections import defaultdict lookup = defaultdict(int) start = 0 end = 0 max_len = 0 counter = 0 while end < len(s): if lookup[s[end]] == 0: counter += 1 lookup[s[end]] += 1 end += 1 while counter > k: if lookup[s[start]] == 1: counter -= 1 lookup[s[start]] -= 1 start += 1 max_len = max(max_len, end - start) return max_len 滑动窗口题目:

3. 无重复字符的最长子串
4. 串联所有单词的子串
5. 最小覆盖子串
6. 至多包含两个不同字符的最长子串
7. 长度最小的子数组
8. 滑动窗口最大值
9. 字符串的排列
10. 最小区间
11. 最小窗口子序列