总结:所有题目都已做,有些Easy没有做第二遍,有两道没有accept,请戳 link-en, link-cn
滑动窗口算法的思路是这样:
1、我们在字符串 S 中使用双指针中的左右指针技巧,初始化 left = right = 0,把索引闭区间 [left, right] 称为一个「窗口」。
2、我们先不断地增加 right 指针扩大窗口 [left, right],直到窗口中的字符串符合要求(包含了 T 中的所有字符)。
3、此时,我们停止增加 right,转而不断增加 left 指针缩小窗口 [left, right],直到窗口中的字符串不再符合要求(不包含 T 中的所有字符了)。同时,每次增加 left,我们都要更新一轮结果。
4、重复第 2 和第 3 步,直到 right 到达字符串 S 的尽头。
int left = 0, right = 0;
// 先移动 right 寻找可行解
while (right < s.size()) {
window.add(s[right]);
right++;
// 找到(不)可行解后,开始移动 left 缩小窗口
while (valid) {
window.remove(s[left]);
left++;
}
}
两种:
1. 是初始已经可行,是向右一直寻找最大可行解,当不可行了就while(not_valid)left++缩小窗口直到再次可行更新解
2. 初始不可行,向右寻找可行,当可行了就while(valid)left++缩小窗口直到再次找到不可行(之前更新解),再向右增大窗口
https://leetcode.com/problems/minimum-window-substring/
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
Example:
Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"
Note:
Solution
from collections import Counter, defaultdict
class Solution:
def minWindow(self, s: str, t: str) -> str:
if not s or not t: return ""
start, end = 0, 0
res, min_len = "", float("inf")
t_c = Counter(t)
s_c = defaultdict(int)
while end < len(s):
s_c[s[end]] += 1
end += 1
while all(map(lambda x: s_c[x] >= t_c[x], t_c.keys())):
if min_len>end-start:
res = s[start:end]
min_len = end-start
s_c[s[start]] -= 1
start += 1
return res
思路看模板
待做:不用counter的方法(Refer),counter太难记了
https://leetcode.com/problems/longest-substring-without-repeating-characters/
Given a string, find the length of thelongest substringwithout repeating characters.
Example 1:
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Solution
from collections import defaultdict
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
if len(s) <= 1: return len(s)
window = defaultdict(int)
max_len = 0
start, end = 0, 0
while end < len(s):
window[s[end]] += 1
while window[s[end]] > 1:
window[s[start]] -= 1
start += 1
end += 1
max_len = max(max_len, end-start)
return max_len
知道思路了就是很简单的题,但是debug了一个小时吧一直各种出错,再做一遍吧
Given a string, find the length of the longest substring T that contains at most k distinct characters.
For example, Given s = “eceba” and k = 2,
T is "ece" which its length is 3.
Example 1:
输入: "A man, a plan, a canal: Panama"
输出: true
Example 2:
输入: s = "aa", k = 1
输出: 2
解释: 则 T 为 "aa",所以长度为 2。
Solution
from collections import defaultdict
class Solution(object):
def lengthOfLongestSubstringKDistinct(self, s, k):
if len(s) <= k : return len(s)
start, end = 0, 0
res = 0
di = defaultdict(int)
while end < len(s):
di[s[end]] += 1
while len(di.keys()) > k:
di[s[start]] -= 1
# 记得pop if value == 0
if not di[s[start]]: di.pop(s[start])
start += 1
end += 1
res = max(res, end-start)
return res
自己的思路自己做的,但是漏了pop掉value为0的key
On时间,Ok空间
Longest Substring with At Least K Repeating Characters
Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.
Example 1:
Input:
s = "aaabb", k = 3
Output:
3
The longest substring is "aaa", as 'a' is repeated 3 times.
Example 2:
Input:
s = "ababbc", k = 2
Output:
5
The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.
Solution
from collections import defaultdict
class Solution:
def longestSubstring(self, s: str, k: int) -> int:
res = 0
start, end = 0, 0
for start in range(len(s)):
di = defaultdict(int)
for end in range(start, len(s)):
di[s[end]] += 1
end += 1
if all(map(lambda x:di[x]>=k, di.keys())):
res = max(end-start, res)
return res
非常丑陋,冥冥之中感觉有更好的解法,一开始用滑动窗口做,错了,做成了最短包含K重复,和340题搞混了
二维DP初始化很重要,初始化空串情况
动态规划思路:明确dp
数组的含义;写状态转移方程;定义base case(非常重要!!)
Given a strings, find the longest palindromic substring ins. You may assume that the maximum length ofsis 1000.
Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd"
Output: "bb"
Solution
要分析清楚二维dp的对状态转移的依赖,dp[i][j] = dp[i+1][j-1]的情况,要for j再for i,这样dp[i+1][j-1]就已经被赋值
class Solution(object):
def longestPalindrome(self, s):
if len(s) <= 1: return s
res = s[0]
dp = [[False for _ in range(len(s))] for _ in range(len(s))]
dp[0][0] = True
for r in range(1, len(s)):
for l in range(r):
if s[l] == s[r] and (r-l <= 2 or dp[l+1][r-1]):
dp[l][r] = True
#更新结果
if dp[l][r]:
res = s[l:r+1] if r-l >= len(res) else res
return res
Given two strings text1 and text2, return the length of their longest common subsequence.
A subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, "ace" is a subsequence of "abcde" while "aec" is not). A common subsequence of two strings is a subsequence that is common to both strings.
If there is no common subsequence, return 0.
Example 1:
Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.
Constraints:
Solution
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
dp = [[0 for _ in range(len(text2)+1)] for _ in range(len(text1)+1)]
for i in range(1,len(text1)+1):
for j in range(1, len(text2)+1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1]+1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[-1][-1]
没啥问题,优秀的我自己写的
注意:初始化很重要,这里要从空串开始初始化,方便计算
A message containing letters from A-Z
is being encoded to numbers using the following mapping:
'A' -> 1
'B' -> 2
...
'Z' -> 26
Given a non-empty string containing only digits, determine the total number of ways to decode it.
Example 1:
Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).
Example 2:
Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
Solution
dp[i] = dp[i-1] + dp[i-2] (有条件的)
class Solution:
def numDecodings(self, s: str) -> int:
if not s or s[0] == "0": return 0
dp = [1] + [0]*(len(s)-1)
if len(s) == 1: return dp[-1]
if s[1] != "0":
dp[1] += 1
if 10<=int(s[:2])<=26:
dp[1] += 1
for i in range(2, len(s)):
if s[i-1:i+1] == "00": return 0
if s[i] != "0":
dp[i] += dp[i-1]
if 10<=int(s[i-1:i+1])<=26:
dp[i] += dp[i-2]
return dp[-1]
https://leetcode.com/problems/implement-strstr/
ImplementstrStr().
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Example 1:
Input: haystack = "hello", needle = "ll"
Output: 2
Example 2:
Input: haystack = "aaaaa", needle = "bba"
Output: -1
Clarification:
What should we return when needle is an empty string? This is a great question to ask during an interview.
For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().
Solution
思路:两种解法,暴力法O((m-n)*n)没必要;KMP
待做:KMP,Reference
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
for i in range(len(haystack) - len(needle)+1):
if haystack[i:i+len(needle)] == needle:
return i
return -1
https://leetcode.com/problems/longest-common-prefix/
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string "".
Example 1:
Input: ["flower","flow","flight"]
Output: "fl"
Example 2:
Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
Note:
All given inputs are in lowercase letters a-z.
Solution -1
class Solution:
def longestCommonPrefix(self, strs):
res = ""
for z in zip(*strs):
if len(set(z)) == 1:
res += z[0]
else: break
return res
抄的,zip(*)这个有点不是很明白,zip使用
思路:zip所有string,set所有第i个char,set后数量为1则是common prefix
Solution - 2
class Solution:
def longestCommonPrefix(self, strs):
if not strs: return ""
res = ""
strs.sort()
fir, la = strs[0], strs[-1]
for i in range(len(fir)):
if i < len(la) and fir[i] == la[i]:
res += fir[i]
else: break
return res
sort(strs),第一个和最后一个的common prefix则为整个序列的common prefix
https://leetcode.com/problems/valid-palindrome/
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
Note: For the purpose of this problem, we define empty string as valid palindrome.
Example 1:
Input: "A man, a plan, a canal: Panama"
Output: true
Example 2:
Input: "race a car"
Output: false
Solution
双指针:一个从后往前,一个从前往后,一个一个匹配
class Solution:
def isPalindrome(self, s: str) -> bool:
if len(s) <= 1: return True
start, end = 0, len(s)-1
while start<end:
while start < len(s) and not s[start].isalnum():
start += 1
while end >= 0 and not s[end].isalnum():
end -= 1
if start>end: return True
if s[start].upper() != s[end].upper(): return False
start += 1
end -= 1
return True
https://leetcode.com/problems/group-anagrams/
Given an array of strings, group anagrams together.
Example:
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
Note:
Solution
Sort每个string,dict count
from collections import defaultdict
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
di = defaultdict(list)
for s in strs:
# key code
di["".join(sorted(s))].append(s)
return list(di.values())
Implement atoi which converts a string to an integer.
Note:
Example 1:
Input: "42"
Output: 42
Example 2:
Input: " -42"
Output: -42
Explanation: The first non-whitespace character is '-', which is the minus sign.
Then take as many numerical digits as possible, which gets 42.
Example 3:
Input: "4193 with words"
Output: 4193
Explanation: Conversion stops at digit '3' as the next character is not a numerical digit.
Example 4:
Input: "words and 987"
Output: 0
Explanation: The first non-whitespace character is 'w', which is not a numerical
digit or a +/- sign. Therefore no valid conversion could be performed.
Example 5:
Input: "-91283472332"
Output: -2147483648
Explanation: The number "-91283472332" is out of the range of a 32-bit signed integer.
Thefore INT_MIN (−231) is returned.
Solution
注意:except: break; outOfRange control
class Solution:
def myAtoi(self, str: str) -> int:
str = str.lstrip()
if not str: return 0
res = 0
idx = 2 if str[0] in ["-","+"] else 1
while idx <= len(str):
try:
res = int(str[:idx])
idx += 1
except:
break
if res > 2147483647: return 2147483647
if res < -2147483648: return -2147483648
return res
Basic Calculator II
Implement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.
Example 1:
Input: "3+2*2"
Output: 7
Example 2:
Input: " 3/2 "
Output: 1
Example 3:
Input: " 3+5 / 2 "
Output: 5
Note:
Solution
先算乘除,最后算加减
class Solution(object):
def calculate(self, s):
stack = []
idx, res = 0, 0
while idx < len(s):
# 数字
if s[idx].isdigit():
num = 0
while idx<len(s) and s[idx].isdigit():
num = num*10+int(s[idx])
idx += 1
stack.append(num)
#数字添加结束就看能不能算乘除
while len(stack)>=2 and stack[-2] in ["*", "/"]:
stack.pop()
opt = stack.pop()
if opt == "*":
stack.append(stack.pop() * num)
else:
stack.append(stack.pop() // num)
# 符号
elif s[idx] in ["*", "/", "+", "-"]:
stack.append(s[idx])
idx += 1
# 其他
else:
idx += 1
# 开始算加减
opt = 1
for ch in stack:
if ch == "+":
opt = 1
elif ch == "-":
opt = -1
else:
res += opt * ch
return res
10.24 调了半天还是没能bug free
11.7 看了思路,写了,抄了,懂了
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。