品牌网站建设有那两种模式,精准客户电话号码购买,北京高端企业网站,忻州建设厅官方网站题目一#xff1a;最长无重复子串长度 给定一个字符串#xff0c;找出其中不含有重复字符的最长子串的长度。 示例#xff1a; 输入: abcabcbb 输出: 3 解释: 最长无重复子串是 abc#xff0c;长度为 3。 解答#xff1a;
def length_of_longest…题目一最长无重复子串长度 给定一个字符串找出其中不含有重复字符的最长子串的长度。 示例 输入: abcabcbb 输出: 3 解释: 最长无重复子串是 abc长度为 3。 解答
def length_of_longest_substring(s):max_length 0start 0char_index {}for i, char in enumerate(s):if char in char_index and char_index[char] start:start char_index[char] 1char_index[char] imax_length max(max_length, i - start 1)return max_length 题目二验证回文字符串 给定一个字符串验证它是否是回文串。只考虑字母和数字忽略大小写。 示例 输入: A man, a plan, a canal: Panama 输出: True 解答
def is_palindrome(s):s .join(filter(str.isalnum, s)).lower()return s s[::-1] 题目三翻转字符串中的单词顺序 给定一个字符串逐个翻转字符串中的每个单词。 示例 输入: the sky is blue 输出: blue is sky the 解答
def reverse_words(s):words s.split()return .join(words[::-1]) 题目四字符串转换整数 (atoi) 实现一个函数来将字符串转换成整数。 示例 输入: 42 输出: 42 解答
def my_atoi(s):s s.strip()if not s:return 0sign 1if s[0] in [, -]:if s[0] -:sign -1s s[1:]num 0for char in s:if not char.isdigit():breaknum num * 10 int(char)num min(max(num * sign, -2**31), 2**31 - 1)return num 题目五最长回文子串 给定一个字符串找到其中最长的回文子串。 示例 输入: babad 输出: bab 解答
def longest_palindrome(s):def expand_around_center(left, right):while left 0 and right len(s) and s[left] s[right]:left - 1right 1return s[left 1:right]longest for i in range(len(s)):# 奇数长度回文串palindrome_odd expand_around_center(i, i)# 偶数长度回文串palindrome_even expand_around_center(i, i 1)if len(palindrome_odd) len(longest):longest palindrome_oddif len(palindrome_even) len(longest):longest palindrome_evenreturn longest 题目一最长公共前缀 编写一个函数来查找字符串数组中的最长公共前缀。 示例 输入: [flower,flow,flight] 输出: fl 解答
def longest_common_prefix(strs):if not strs:return min_length min(len(s) for s in strs)common_prefix for i in range(min_length):char strs[0][i]if all(s[i] char for s in strs):common_prefix charelse:breakreturn common_prefix 题目二字符串转换 给定一个字符串将该字符串中的大写字母转换为小写字母小写字母转换为大写字母。 示例 输入: Hello World 输出: hELLO wORLD 解答
def swap_case(s):return s.swapcase() 题目三最后一个单词的长度 给定一个字符串包含多个单词其中单词由空格分隔。找出最后一个单词的长度。 示例 输入: Hello World 输出: 5 解答
def length_of_last_word(s):words s.split()if words:return len(words[-1])return 0
题目四反转字符串中的元音字母 编写一个函数以字符串作为输入反转字符串中的元音字母。 示例 输入: hello 输出: holle 解答
def reverse_vowels(s):vowels aeiouAEIOUs list(s)left, right 0, len(s) - 1while left right:while left right and s[left] not in vowels:left 1while left right and s[right] not in vowels:right - 1s[left], s[right] s[right], s[left]left 1right - 1return .join(s)
题目五验证有效的括号序列 给定一个只包含三种字符的字符串(, ){}[]判断字符串是否有效。 示例 输入: ()[]{} 输出: True 解答
def is_valid(s):stack []mapping {): (, }: {, ]: [}for char in s:if char in mapping:top_element stack.pop() if stack else #if mapping[char] ! top_element:return Falseelse:stack.append(char)return not stack
题目六字符串中的第一个唯一字符 给定一个字符串找到它的第一个不重复的字符并返回它的索引。如果不存在则返回 -1。 示例 输入: leetcode 输出: 0 解答
def first_uniq_char(s):char_count {}for char in s:char_count[char] char_count.get(char, 0) 1for i, char in enumerate(s):if char_count[char] 1:return ireturn -1
题目七字符串中的所有变位词 给定两个字符串 s 和 p找到 s 中所有 p 的变位词的起始索引。 示例 输入: s cbaebabacd, p abc 输出: [0, 6] 解答
def find_anagrams(s, p):p_count [0] * 26s_count [0] * 26result []for char in p:p_count[ord(char) - ord(a)] 1for i in range(len(s)):s_count[ord(s[i]) - ord(a)] 1if i len(p):s_count[ord(s[i - len(p)]) - ord(a)] - 1if s_count p_count:result.append(i - len(p) 1)return result
题目八分割回文串 给定一个字符串将字符串分割成一些子串使每个子串都是回文串。返回所有可能的分割方案。 示例 输入: aab 输出: [[aa,b], [a,a,b]] 解答
def partition(s):def is_palindrome(sub):return sub sub[::-1]def backtrack(start, path):if start len(s):result.append(path[:])returnfor end in range(start 1, len(s) 1):if is_palindrome(s[start:end]):path.append(s[start:end])backtrack(end, path)path.pop()result []backtrack(0, [])return result
题目九最小覆盖子串 给定一个字符串 S 和一个字符串 T请在 S 中找出包含 T 所有字母的最小子串。 示例 输入: S ADOBECODEBANC, T ABC 输出: BANC 解答
def min_window(s, t):from collections import Counterif not s or not t:return t_count Counter(t)required_chars len(t_count)left, right 0, 0formed_chars 0window_count {}ans float(inf), None, Nonewhile right len(s):char s[right]window_count[char] window_count.get(char, 0) 1if char in t_count and window_count[char] t_count[char]:formed_chars 1while left right and formed_chars required_chars:char s[left]if right - left 1 ans[0]:ans right - left 1, left, rightwindow_count[char] - 1if char in t_count and window_count[char] t_count[char]:formed_chars - 1left 1right 1return if ans[0] float(inf) else s[ans[1]:ans[2] 1]
题目十字符串的排列 给定两个字符串 s1 和 s2写一个函数来判断 s2 是否包含 s1 的排列。 示例 输入: s1 ab s2 eidbaooo 输出: True 解答
def check_inclusion(s1, s2):from collections import Counters1_count Counter(s1)window_count Counter()left, right 0, 0required_chars len(s1)while right len(s2):char s2[right]window_count[char] window_count.get(char, 0) 1if char in s1_count and window_count[char] s1_count[char]:required_chars - 1while left right and window_count[s2[left]] s1_count[s2[left]]:window_count[s2[left]] - 1left 1if required_chars 0:return Trueright 1return False
题目频率最高的单词 给定一段英文文章的文本找出其中出现频率最高的前k个单词并返回这些单词按频率降序排列的列表。请忽略单词的大小写。 示例 输入: text This is a sample text. This text contains some sample words. k 3 输出: [sample, this, text] 解答 def top_k_frequent_words(text, k):from collections import Counter # 导入Counter类用于统计元素频率import re # 导入正则表达式模块# 去除标点符号转换为小写然后按空格分割文本words re.findall(r\w, text.lower()) # 使用正则表达式找出所有单词转换为小写# 统计单词频率word_count Counter(words) # 使用Counter统计单词出现的频率# 按频率降序排列单词sorted_words sorted(word_count, keylambda word: (-word_count[word], word))# 使用sorted函数对单词按照频率降序排列如果频率相同则按字典序升序排列# 返回前k个单词return sorted_words[:k] # 返回按照要求排序后的前k个单词
示例给定文本This is a sample text. This text contains some sample words. 和 k 3。文本处理去除标点符号后得到this is a sample text this text contains some sample words转换为小写this is a sample text this text contains some sample words按空格分割[this, is, a, sample, text, this, text, contains, some, sample, words]单词统计
统计后得到{this: 2, is: 1, a: 1, sample: 2, text: 2, contains: 1, some: 1, words: 1}按频率降序排列
排序后得到[sample, text, this, is, a, contains, some, words]返回前k个单词
返回前3个单词[sample, text, this]综合起来题目要求将一段英文文本进行处理找出其中频率最高的前k个单词并按频率降序排列返回。
解答思路文本处理 首先我们需要对给定的英文文本进行处理。我们要去除标点符号将所有单词转换为小写并按空格分割文本以便后续的单词统计。单词统计 使用Python的collections.Counter模块我们可以方便地统计文本中每个单词的出现次数。将单词作为键出现次数作为值创建一个单词计数器。按频率降序排列 接下来我们将计数器中的单词按照频率降序排列。这里需要注意如果频率相同我们按字典序排列单词以保证结果的正确性。返回前k个单词 最后从排序后的单词列表中取出前k个单词作为答案。题目一最小覆盖子串的变体 给定一个字符串s和一组字符t找出s中包含t中所有字符的最小子串。要求时间复杂度为O(n)。
输入: s ADOBECODEBANC, t ABC 输出: BANC
def min_window_substring(s, t):from collections import Countert_count Counter(t) # 统计目标字符 t 中每个字符的频率required_chars len(t_count) # 需要匹配的不同字符的数量left, right 0, 0 # 滑动窗口的左右指针formed_chars 0 # 已经匹配到的字符数量window_count {} # 滑动窗口中字符的频率计数ans float(inf), None, None # 存储结果的变量初始化为一个极大值min_window # 最小覆盖子串while right len(s):char s[right] # 右指针指向的字符window_count[char] window_count.get(char, 0) 1 # 统计字符频率if char in t_count and window_count[char] t_count[char]:formed_chars 1 # 已匹配字符的数量满足要求while left right and formed_chars required_chars:char s[left] # 左指针指向的字符if right - left 1 ans[0]:ans right - left 1, left, right # 更新最小覆盖子串的长度和位置min_window s[left:right1] # 更新最小覆盖子串window_count[char] - 1 # 缩小窗口左指针右移if char in t_count and window_count[char] t_count[char]:formed_chars - 1 # 一个字符的频率不满足要求更新已匹配字符数量left 1 # 左指针右移right 1 # 右指针右移return min_window # 返回最小覆盖子串使用了滑动窗口的思想来解决最小覆盖子串问题。
题目二最长连续子序列 给定一个字符串s找出s中最长的连续子序列使得子序列中的每个字符的前后相邻字符在原始字符串中也是相邻的。 输入: abacdefg 输出: abcdefg
def longest_continuous_subsequence(s):if not s:return max_length 1 # 最长连续子序列的长度start 0 # 连续子序列的起始索引end 0 # 连续子序列的结束索引longest_subsequence s[0] # 最长连续子序列for i in range(1, len(s)):if ord(s[i]) ord(s[i - 1]) 1:end i # 连续序列继续else:start i # 连续序列中断更新起始索引if end - start 1 max_length:max_length end - start 1 # 更新最长长度longest_subsequence s[start:end 1] # 更新最长连续子序列return longest_subsequence # 返回最长连续子序列通过遍历字符串来找到最长连续子序列。每次遇到断开的情况更新起始索引并根据最长长度更新最长连续子序列。
