leetcode 344: 反转字符串
Write a function that reverses a string. The input string is given as an array of characters char[].
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
You may assume all the characters consist of printable ascii characters.
Example 1:
Input: ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]
- 思路：常数空间，不能递归。双指针一头一尾交换元素。
class Solution:
def reverseString(self, s: List[str]) -> None:
if len(s) <= 1:
return
head,tail = 0,len(s)-1
while head < tail:
s[head],s[tail] = s[tail],s[head]
head += 1
tail -= 1
leetcode 345: 反转字符串中的元音字母
编写一个函数，以字符串作为输入，反转该字符串中的元音字母。
示例 1:
输入: "hello"
输出: "holle"
示例 2:
输入: "leetcode"
输出: "leotcede"
- 一头一尾双指针，集合存原因字符，从两边遍历，遇到第一个元音时停止并交换，之后自增重复过程。O(N)
class Solution:
def reverseVowels(self, s: str) -> str:
vals = set(['a','e','i','o','u','A','E','I','O','U'])
s = list(s)
i,j = 0,len(s)-1
while i < j:
while s[i] not in vals and i<j:
i += 1
while s[j] not in vals and i<j:
j -= 1
if i <j:
s[i],s[j] = s[j],s[i]
i,j = i+1,j-1
return ''.join(s)
leetcode 125: 验证回文串
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
- python字符串相关判断函数：
- islower, isuppper, isdigit, isalpha, isalnum, upper, lower
- 双指针，先处理一遍字符串，排除掉不是字母和数字的字符。
class Solution:
def isPalindrome(self, s: str) -> bool:
if not s: return True
tmp = ""
for c in s:
if c.isalnum(): tmp += c.lower()
left ,right = 0,len(tmp)-1
while left <= right:
if tmp[left] != tmp[right]:
return False
left += 1
right -= 1
return True
*leetcode 438: 找到字符串中的所有字母异位词
[中等]给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
说明：
字母异位词指字母相同，但排列不同的字符串。 不考虑答案输出的顺序。
示例 1:
输入:
s: "cbaebabacd" p: "abc"
输出:
[0, 6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。
- 思路一 ：由于p存在重复字母，且匹配的结果跟顺序无关，因此可以考虑用dict来存储对应的字母和个数，之后遍历原字符串每次选长度相同的子串计算并进行比较。
- 在对p生成其字母对应个数时可以使用collections.Counter计算字母对应的频次，其使用格式与dict基本一致，结果为dict，并计算长度n
- 在对字符串进行遍历时，在每个位置生成一个counter，计算从开始到现在字母的频次，如果满足第i次的counter减去第i-n的counter结果为p对应的counter时证明找到了满足条件的子串。
def findAnagrams(s,p):
res = []
length = len(p)
p = Counter(p)
#便于处理开头存在的子串，在最开始部分初始化了一个空的counter
#每个counter存储对应上一个位置的计数dict，通过上一个dict加上一处字符完成
#每个counter存储的字符为[start,cur)
counters = [_ for _ in range(len(s)+1)]
counters[0] = Counter()
for i in range(1,len(s)+1):
counters[i] = counters[i-1].copy()
counters[i][s[i-1]]+=1
if i >=length and counters[i]-counters[i-length]==p:
res.append(i-length)
return res
- 思路二 ：滑动窗口法 用两个size为26的数组分别存储s和p里对应字母的计数，通过滑动窗口对s数组的值进行更改，当两个数组相等时即为满足条件的子串。
- 对于数组值和字母的对应可以巧妙的通过ascii码值计算来实现。字符串只包含小写，因此其ord()-97为数组索引。
from collections import Counter
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
res = []
p_count = [0 for i in range(26)]
s_count = [0 for i in range(26)]
for i in p:
p_count[ord(i)-97] += 1
#通过left right构造定长p的滑动窗口，之后同步移动
left = 0
for right in range(len(s)):
#构造长度为len(p)的窗口，因为right在for循环里，
#只判断 < len(p)-1即可
if right < len(p)-1:
s_count[ord(s[right])-97] += 1
continue
s_count[ord(s[right])-97] += 1
if s_count == p_count:
res.append(left)
#left右移，应减去left处的单词次数1
s_count[ord(s[left])-97] -= 1
left += 1
return res
*leetcode 3: 无重复字符的最长子串
[中等]给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
- 类似上面，用滑动窗口法，并用一个数组来确定每一个字母有没有重复(在本题中除字母外还有别的字符，因此不能用26大小的数组。)
int [26]用于字母 ‘a’ - ‘z’ 或 ‘A’ - ‘Z’int [128]用于ASCII码int [256]用于扩展ASCII码- 设立left，right=0，right遍历每一个字符，若对应的位置值不为零则说明有重复，因此移动left知道s[left]=是[right]，中间遇到的字符要设定其计数值为0，right位置不能改变。
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
vals = [0]*128
max_len = 0
left = 0
for right in range(len(s)):
if vals[ord(s[right])] == 0:
vals[ord(s[right])] = 1
max_len = max(max_len,right-left+1)
else:
while s[left] != s[right]:
vals[ord(s[left])] = 0
left += 1
#额外执行一次，跳过相同的结点 此时不用修改计数
left += 1
return max_len
- 优化 : 对上面所使用的计数数组vals,可以存储每个字母对应的在滑动窗口中的最后位置，这样不用left逐个遍历，可以直接走到字母出现的位置后面。
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
vals = [0]*128
max_len = 0
left = 0
for right in range(len(s)):
#每次只要遇到重复出现的，left立刻移向重复位置
#以此保证left,right之间绝对不重复
left = max(vals[ord(s[right])],left)
max_len = max(max_len,right-left+1)
#这里指向的定位直接时下一个字符，方便left跳转
#也可以指向字符 而在上面加一
vals[ord(s[right])] = right+1
return max_len
*leetcode 76: 最小覆盖子串
[困难]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:
If there is no such window in S that covers all characters in T, return the empty string “”. If there is such window, you are guaranteed that there will always be only one unique minimum window in S.
- 思路：滑动窗口法，右边满足条件后左指针开始遍历找最短的满足条件序列，到不满足状态时右指针移动。
- 对满足条件的判断：使用counter可以获取到t字符串对应字符的个数，使用formed统计匹配上的字符对数，当formed等于t长度时说明满足条件。
- 在遍历s字符串时需对s中的字符判断是不是在t中，为避免遍历同样使用dict来存储滑动窗口内的字符count，如果该字符在滑动窗口中和t中计数相同，则说明又有一个字符满足条件，对应formed加一。
- 在left指针右移时，对应字符计数减一，如果小于(存在多个重复字符)t中对应字符的计数，则formed减一，重新移动右指针。
- python语法相关：dict.get(key, default=None)，获取指定key的值，若没有该key返回default值，可以简化对key是否在dict的keys里的判断。
class Solution:
def minWindow(self, s: str, t: str) -> str:
from collections import Counter
t_cnt = Counter(t)
s_cnt = Counter()
res = int(1e5),0,0
left,right =0,0
formed = 0
while right < len(s):
s_cnt[s[right]] = s_cnt.get(s[right],0)+1
if s[right] in s_cnt and t_cnt[s[right]] == s_cnt[s[right]]:
formed += 1
#满足条件 left右移
while left <= right and formed == len(t_cnt):
if right - left + 1 < res[0]:
res = (right - left + 1,left,right)
s_cnt[s[left]] -= 1
if s[left] in s_cnt and s_cnt[s[left]] < t_cnt[s[left]]:
formed -= 1
left += 1
right += 1
return "" if res[0] == int(1e5) else s[res[1]:res[2]+1]
- 优化空间：对于只在s出现而没有在t中出现的字符，没有统计他们的必要，可以加一个处理，只计算相关的字符。
