【PythonCode】力扣Leetcode26~30题Python版
前言
力扣Leetcode是一个集学习、刷题、竞赛等功能于一体的编程学习平台,很多计算机相关专业的学生、编程自学者、IT从业者在上面学习和刷题。
在Leetcode上刷题,可以选择各种主流的编程语言,如C++、JAVA、Python、Go等。还可以在线编程,实时执行代码,如果代码通过了平台准备的测试用例,就可以通过题目。
本系列中的文章从Leetcode的第1题开始,记录我用Python语言提交的代码和思路,供Python学习参考。
26. 删除有序数组中的重复项
给你一个 非严格递增排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k ,你需要做以下事情确保你的题解可以被通过:
-
更改数组 nums ,使 nums 的前 k 个元素包含唯一元素,并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
-
返回 k 。
判题标准:
系统会用下面的代码来测试你的题解:
int[] nums = [...]; // 输入数组 int[] expectedNums = [...]; // 长度正确的期望答案 int k = removeDuplicates(nums); // 调用 assert k == expectedNums.length; for (int i = 0; i < k; i++) { assert nums[i] == expectedNums[i]; }
如果所有断言都通过,那么您的题解将被 通过。
示例 1:
输入:nums = [1,1,2]
输出:2, nums = [1,2,_]
解释:
函数应该返回新的长度 2 ,并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
示例 2:
输入:nums = [0,0,1,1,1,2,2,3,3,4]
输出:5, nums = [0,1,2,3,4]
解释:
函数应该返回新的长度 5 , 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
提示:
1 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按 非严格递增 排列
代码实现:
class Solution: def removeDuplicates(self, nums: List[int]) -> int: if not nums: return 0 fast, slow = 1, 1 while fast < len(nums): if nums[fast] != nums[fast-1]: nums[slow] = nums[fast] slow += 1 fast += 1 return slow
解题思路:删除有序数组中的重复项,这个功能并不难实现,本题的难点是必须原地修改,也就是不能创建新的数组,不能增加空间复杂度。
数组是有序的,说明数组中重复元素的位置都是相邻的,在寻找重复元素时,如果当前元素与它的前一个元素相等,则它是重复元素,反之。
题目要求将数组中非重复的元素按原始相对顺序排到数组前面,这就需要找到非重复元素,并且知道将非重复元素放到数组中的哪个位置。
可以用两个指针来实现,第一个指针用来寻找非重复元素,从数组的第二个元素(索引1)开始,依次后移,如果当前元素与前一个元素相等,则跳过,如果当前元素与前一个元素不相等则是非重复元素。第二个指针用来标记将非重复元素修改到哪个位置,也就是标记数组中待修改的索引,从数组的第二个位置(索引1)开始,每找到一个非重复值,就把数组中该索引的值修改成非重复值,然后指针后移。这种方法就是常说的快慢指针。
题目要求返回非重复元素的个数,慢指针的值刚好就等于非重复元素的个数。(慢指针从索引1开始,最终停在修改后最后一个非重复元素的下一个索引,数组索引是从0开始的,所以慢指针指向的索引值与非重复元素个数相等)。
27. 移除元素
给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。
不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
说明:
为什么返回数值是整数,但输出的答案是数组呢?
请注意,输入数组是以「引用」方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说,不对实参作任何拷贝 int len = removeElement(nums, val); // 在函数里修改输入数组对于调用者是可见的。 // 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。 for (int i = 0; i < len; i++) { print(nums[i]); }
示例 1:
输入:nums = [3,2,2,3], val = 3
输出:2, nums = [2,2]
解释:
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如,函数返回的新长度为 2 ,而 nums = [2,2,3,3] 或 nums = [2,2,0,0],也会被视作正确答案。
示例 2:
输入:nums = [0,1,2,2,3,0,4,2], val = 2
输出:5, nums = [0,1,3,0,4]
解释:函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
提示:
0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100
代码实现:
class Solution: def removeElement(self, nums: List[int], val: int) -> int: fast, slow = 0, 0 while fast < len(nums): if nums[fast] != val: nums[slow] = nums[fast] slow += 1 fast += 1 return slow
解题思路:本题与上一题基本相同,上一题是删除重复元素,本题是删除某一个指定元素,所以解题思路完全一样,使用快慢指针。
上题中指针从索引1开始,是因为数组的第一个元素(索引0)不可能是被删除的重复元素(即使第二个元素与第一个元素相等,也是删第二个)。本题中指针从索引0开始,是因为数组的第一个元素可能与指定值相等。
28. 找出字符串中第一个匹配项的下标
给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标(下标从 0 开始)。如果 needle 不是 haystack 的一部分,则返回 -1 。
示例 1:
输入:haystack = “sadbutsad”, needle = “sad”
输出:0
解释:“sad” 在下标 0 和 6 处匹配。 第一个匹配项的下标是 0 ,所以返回 0 。
示例 2:
输入:haystack = “leetcode”, needle = “leeto”
输出:-1
解释:“leeto” 没有在 “leetcode” 中出现,所以返回 -1 。
提示:
1 <= haystack.length, needle.length <= 104
haystack 和 needle 仅由小写英文字符组成
代码实现:
class Solution: def strStr(self, haystack: str, needle: str) -> int: for i in range(0, len(haystack)-len(needle)+1): if haystack[i:i+len(needle)] == needle: return i return -1
解题思路:本题比较简单,重要的是先理解题意,可以看题目描述中的示例。
要判断haystack中是否包含了needle,并返回needle第一次匹配时的开始索引。解决思路是从索引0开始遍历,在haystack中截取与needle长度相等的字符,将截取的字符与needle比较,如果相等则说明匹配上了,返回当前的索引就是结果。如果遍历到haystack中剩余的字符长度小于needle,说明haystack中不包含needle,返回-1。
29. 两数相除
给你两个整数,被除数 dividend 和除数 divisor。将两数相除,要求 不使用 乘法、除法和取余运算。
整数除法应该向零截断,也就是截去(truncate)其小数部分。例如,8.345 将被截断为 8 ,-2.7335 将被截断至 -2 。
返回被除数 dividend 除以除数 divisor 得到的 商 。
注意:假设我们的环境只能存储 32 位 有符号整数,其数值范围是 [−231, 231 − 1] 。本题中,如果商 严格大于 231 − 1 ,则返回 231 − 1 ;如果商 严格小于 -231 ,则返回 -231 。
示例 1:
输入: dividend = 10, divisor = 3
输出: 3
解释:
10/3 = 3.33333… ,向零截断后得到 3 。
示例 2:
输入: dividend = 7, divisor = -3
输出: -2
解释:
7/-3 = -2.33333… ,向零截断后得到 -2 。
提示:
-231 <= dividend, divisor <= 231 - 1
divisor != 0
代码实现:
class Solution: def divide(self, dividend: int, divisor: int) -> int: if dividend == -2**31: if divisor == 1: return dividend if divisor == -1: return 2**31-1 if divisor == -2**31: return 1 if dividend == divisor else 0 if dividend == 0: return 0 is_minus = False if dividend < 0: dividend = -dividend is_minus = not is_minus if divisor < 0: divisor = -divisor is_minus = not is_minus dichotomy = [divisor] while dichotomy[-1] <= dividend - dichotomy[-1]: dichotomy.append(dichotomy[-1] + dichotomy[-1]) result = 0 for i in range(len(dichotomy)-1, -1, -1): if dichotomy[i] <= dividend: result += 2**i dividend -= dichotomy[i] return -result if is_minus else result
解题思路:除法运算是最基本的四则运算,除法的基本原理是减法的重复。用被除数不断地减除数,每减1次,商增加1,直到被除数被减到比除数小,剩余的部分为余数。这也是本题求解的最基本方法,不过一直循环地做减法,对于被除数非常大的情况(本题的数据边界是223-1),时间复杂度很高,提交代码会超时。
题目要求实现两数相除时不能使用乘法、除法和取余运算,所以不能直接调用这些运算符,必须采用间接的算法来实现。虽然直接用减法会因时间复杂度太大而超时,但减法是除法的基础,超时并不是说不能用减法,而是减法的执行次数太多了,要减少次数。因此可以降低减法的次数来降低时间复杂度,使代码不超时,通过测试用例。
如何降低减法的次数呢,参考二分法解决问题的思路,如果不是每次都减除数,而是依次减除数的1倍,2倍,4倍,8倍,… 就可以使减法次数的复杂度从O(n)降到O(logn)。并且,被除数是越减越小的,应该先减更大的数,再减更小的数,才能保证最后的余数小于除数。为了知道先从除数的多少倍开始减,可以用除数不断增加两倍(用加法)来逼近被除数,得到一个数组,用被除数从数组的最大数开始减。
举个例子说明,假设被除数dividend为25,除数divisor为3,先将除数不断按两倍增大,列出所有不大于被除数的数,将这些数添加到一个数组中,得到的数组是[3, 6, 12, 24],在计算两数相除时,从此数组中最大的数开始减,用25减24剩1,减掉24,对应的商是23=8(因为3*23=24),再判断剩的1能不能再减数组中的其他数(从大到小)。判断完发现1比数组中的数都小,不能再减了,所以直接得出商为8,只执行了一次减法操作(这里执行了四次判断)。
再看一个例子,假设被除数dividend为46,除数divisor为3,除数不断增长两倍,得到的数组也是[3, 6, 12, 24],用46减24剩22,商为23=8,用22减12剩10,商为22=4,用10减6剩4,商为21=2,用4减3剩1,商为20=1,最终结果为8+4+2+1=15,只执行了4次减法,如果用被除数一直减3,要执行15次减法,对于被除数与除数相差更大的情况,这个差异会更明显。
根据前面的分析,可以开始实现代码了,先根据被除数和除数的值生成每次减的数组,然后用被除数从数组中最大的数开始减,并根据数组的位置(索引)关系计算出减去某个数时的商(这里要用到幂运算或位运算)。
根据题目条件,在执行两数相除的代码前,还需要对数字做一些处理。首先,环境只能存储32位的有符号整数,所以要先对数据的边界做处理,避免结果超出边界。其次,被除数和除数都可能是正数或负数,这样就有四种组合,为了方便计算,可以将所有数字全部转换成正数来执行计算,这样在计算时不用考虑数字的正负,只需要处理一种情况。同时,因为结果原本是正负都有可能,所以用一个标志位来记录结果的正负,如果被除数和除数正负相同,则标志位为正,如果被除数和除数正负相反,则标志位为负,在计算出结果后,根据标志位将结果转换成对应的正负值。
此外,本题具有一定的争议,题目要求实现两数相除时不能用乘法、除法和取余运算,根据推理应该只能用减法来实现,但时间复杂度不满足,只有降低复杂度才能体现算法的考点和匹配本题的难度,但这又引入一个矛盾,要降低复杂度会用到幂运算或位运算,某种意义上其实是用了乘法。不过,不用纠结这么多了。
30. 串联所有单词的子串
给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。
例如,如果 words = [“ab”,“cd”,“ef”], 那么 “abcdef”, “abefcd”,“cdabef”, “cdefab”,“efabcd”, 和 “efcdab” 都是串联子串。 “acdbef” 不是串联子串,因为他不是任何 words 排列的连接。
返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。
示例 1:
输入:s = “barfoothefoobarman”, words = [“foo”,“bar”]
输出:[0,9]
解释:
因为 words.length == 2 同时 words[i].length == 3,连接的子字符串的长度必须为 6。
子串 “barfoo” 开始位置是 0。它是 words 中以 [“bar”,“foo”] 顺序排列的连接。
子串 “foobar” 开始位置是 9。它是 words 中以 [“foo”,“bar”] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。
示例 2:
输入:s = “wordgoodgoodgoodbestword”, words = [“word”,“good”,“best”,“word”]
输出:[]
解释:因为 words.length == 4 并且 words[i].length == 4,所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。
示例 3:
输入:s = “barfoofoobarthefoobarman”, words = [“bar”,“foo”,“the”]
输出:[6,9,12]
解释:因为 words.length == 3 并且 words[i].length == 3,所以串联子串的长度必须为 9。
子串 “foobarthe” 开始位置是 6。它是 words 中以 [“foo”,“bar”,“the”] 顺序排列的连接。
子串 “barthefoo” 开始位置是 9。它是 words 中以 [“bar”,“the”,“foo”] 顺序排列的连接。
子串 “thefoobar” 开始位置是 12。它是 words 中以 [“the”,“foo”,“bar”] 顺序排列的连接。
提示:
1 <= s.length <= 104
1 <= words.length <= 5000
1 <= words[i].length <= 30
words[i] 和 s 由小写英文字母组成
代码实现:
class Solution: def findSubstring(self, s: str, words: List[str]) -> List[int]: first_len = len(words[0]) all_len = len(words) * first_len n = len(s) words_ct = dict() for w in words: # 统计words中各元素的次数 if w not in words_ct: words_ct[w] = 1 else: words_ct[w] += 1 result = [] for i in range(0, n-all_len+1): tmp = s[i:i+all_len] # 遍历字符串s,每次截取长度为all_len长度的子串 c_tmp = [] for j in range(0, all_len, first_len): # 将子串拆分成与words一样的结构 c_tmp.append(tmp[j:j+first_len]) c_ct = dict() for c in c_tmp: # 统计截取到列表中各元素的次数 if c not in c_ct: c_ct[c] = 1 else: c_ct[c] += 1 if c_ct == words_ct: result.append(i) return result
解题思路:求解本题,首先要理解题意,先知道串联子串具有什么特点。根据题意,words中的所有字符串长度相等,串联子串是将words中所有的字符串按任意可能的顺序拼接组合在一起。
可以从题目描述中提取出串联子串的特点:
- 假设words的长度为n(有n个字符串),每个字符串的长度为m,则串联子串的长度为n*m。
- words中的每个字符串在串联子串中不能被拆分,只能拼接在一起。
- words的每个字符串在串联子串中只出现一次。(特殊情况,words有相同的字符串,在代码中也可以当成不同字符串来处理)。
根据这三个特点,假如将一个串联子串(长度为n*m)截断成n个长为m的字符串,统计这n个字符串的次数,得到的结果与统计words中各字符串的次数相同,这就是解题的关键。
举个例子,words=[“ab”, “cd”, “ef”],统计words中各字符串的次数,结果为{“ab” : 1, “cd” : 1, “ef” : 1},"efabcd"作为一个串联子串,将它截取成长度为2的字符串,结果为[“ef”, “ab”, “cd”],统计截取结果中各字符串的次数,结果为{“ab” : 1, “cd” : 1, “ef” : 1},这与words中各字符串的次数相等,所以"efabcd"是串联子串。
根据前面的分析,要在字符串s中找到所有的串联子串,并返回这些串联子串的开始索引,可以从s的第一个字符开始遍历,每次从s中截取长度为n*m的字符串,将此字符串再截成n个长度为m的字符串,统计这n个字符串的次数,如果与words中各字符串的次数相等,则找到一个串联子串,记录此时遍历到的s中的索引。遍历到s中剩余的字符数小于n*m时,就可以找到所有的结果。
分析到这里,可以实现代码了,上面的代码中写了注释,可以将代码和分析结合起来看。
对于比较两个数组中的元素个数是否相等,不考虑元素先后顺序的情况,可以使用Python中的Counter计数器,使代码更简洁。参考:详解Python中非常好用的计数器Counter。调用Counter计数器,修改后的代码如下。
class Solution: def findSubstring(self, s: str, words: List[str]) -> List[int]: from collections import Counter # 导入Counter first_len = len(words[0]) all_len = len(words) * first_len n = len(s) result = [] for i in range(0, n-all_len+1): tmp = s[i:i+all_len] c_tmp = [] for j in range(0, all_len, first_len): c_tmp.append(tmp[j:j+first_len]) if Counter(c_tmp) == Counter(words): # 比较截取的各字符数是否与words中各字符的数量相同 result.append(i) return result
相关阅读
【PythonCode】力扣Leetcode21~25题Python版
📢欢迎 点赞👍 收藏⭐ 评论📝 关注❤ 如有错误敬请指正!
☟ 学Python,点击下方名片关注我。☟