力扣天天练--week3-LeetCode75

topic75-9-t443:压缩字符串

题目描述：

给你一个字符数组 chars ，请使用下述算法压缩：

从一个空字符串 s 开始。对于 chars 中的每组 连续重复字符 ：

如果这一组长度为 1 ，则将字符追加到 s 中。
否则，需要向 s 追加字符，后跟这一组的长度。
压缩后得到的字符串 s 不应该直接返回 ，需要转储到字符数组 chars 中。需要注意的是，如果组长度为 10 或 10 以上，则在 chars 数组中会被拆分为多个字符。

请在 修改完输入数组后 ，返回该数组的新长度。

你必须设计并实现一个只使用常量额外空间的算法来解决此问题。

示例：

 思路：

1. 定义一个辅助函数 reverse，用于反转字符列表中指定位置之间的字符。
2. 定义变量 n，表示字符列表的长度。
3. 定义变量 write 和 left，表示压缩后的字符列表和当前字符的左边界。
4. 遍历字符列表，用 read 指针指向当前字符。
5. 如果 read 指针指向字符列表的最后一个元素，或者当前字符与下一个字符不同，执行以下操作：
   • 将当前字符写入压缩后的字符列表。
   • 计算相同字符的数量，即 read - left + 1。
   • 如果相同字符的数量大于 1，则将该数字转换为字符串，并写入压缩后的字符列表中。
   • 调用 reverse 函数，将数字字符串反转，使其顺序正确。
   • 将 left 指针移动到下一个字符的位置。
   • 将 write 指针移动到下一个位置，以准备写入下一个字符或数字。
6. 返回 write，表示压缩后的字符列表的长度。

 

class Solution:def compress(self, chars: List[str]) -> int:# 定义一个辅助函数 reverse，用于反转字符列表中指定位置之间的字符def reverse(left: int, right: int) -> None:while left < right:chars[left], chars[right] = chars[right], chars[left]left += 1right -= 1n = len(chars)write = left = 0 # write 表示压缩后的字符列表中当前位置，left 表示当前字符的左边界for read in range(n): # 遍历字符列表，用 read 指针指向当前字符if read == n - 1 or chars[read] != chars[read + 1]: # 如果当前字符是最后一个字符或者与下一个字符不同chars[write] = chars[read] # 将当前字符写入压缩后的字符列表write += 1 # 将 write 指针向右移动一位num = read - left + 1 # 计算相同字符的数量if num > 1: # 如果相同字符的数量大于 1anchor = write # 将 anchor 指针指向 write 指针当前位置，用于记录数字字符串的起始位置while num > 0: # 将数字转换为字符串，并写入压缩后的字符列表中chars[write] = str(num % 10)write += 1num //= 10reverse(anchor, write - 1) # 将数字字符串反转，使其顺序正确left = read + 1 # 将 left 指针移动到下一个字符的位置，用于记录下一段相同的字符的左边界return write # 返回 write，表示压缩后的字符列表的长度

topic75-10-t283:移动零

题目描述：

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例：

 思路：

1. 定义变量 i 和 j，分别表示当前遍历到的元素和当前非零元素的位置。
2. 遍历列表 nums，使用指针 i 指向当前遍历到的元素。
3. 如果 i 指向的元素不为 0，将其移到列表的非零元素区域，并将指针 j 向右移动一位，以便下一次将非零元素移到该位置。
4. 遍历结束后，将列表中剩余的元素全部赋值为 0，以将它们移到列表的末尾。

class Solution:def moveZeroes(self, nums: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""i = 0 # 定义指针 i，表示当前遍历到的元素j = 0 # 定义指针 j，表示当前非零元素的位置# 遍历列表 numswhile i < len(nums):# 如果当前元素不为 0，将其移到列表的非零元素区域if nums[i] != 0:nums[j] = nums[i]j += 1 # 将指针 j 向右移动一位，以便下一次将非零元素移到该位置i += 1 # 将指针 i 向右移动一位，遍历下一个元素# 将列表中剩余的元素全部赋值为 0，以将它们移到列表的末尾while j < len(nums):nums[j] = 0j += 1# 算法结束，返回 None

topic75-11-t392:判断子序列

题目描述：

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

示例：

 思路：

1. 定义两个指针 first 和 second，分别指向 t 和 s 的开头。
2. 计算字符串 t 和 s 的长度 lengtht 和 lengths，如果 s 的长度为 0，则直接返回 True。
3. 使用 while 循环遍历字符串 t，直到 first 指针到达 t 的末尾。
4. 如果 s[second] 和 t[first] 相等，则将 first 和 second 指针分别向右移动一位，继续进行比较。
5. 如果 s[second] 和 t[first] 不相等，则将 first 指针向右移动一位，继续进行比较。
6. 如果 second 指针到达了 s 的末尾，说明 s 是 t 的子序列，返回 True。
7. 如果 first 指针到达了 t 的末尾，说明已经遍历完了整个字符串 t，但是没有找到 s，返回 False。

 

class Solution:def isSubsequence(self, s: str, t: str) -> bool:first, second = 0, 0 # 初始化双指针lengtht, lengths = len(t), len(s)if lengths == 0: # 如果 s 的长度为 0，则直接返回 Truereturn Truewhile first < lengtht: # 使用 while 循环遍历字符串 tif s[second] == t[first]: # 如果 s[second] 和 t[first] 相等，则将指针分别向右移动一位，继续进行比较first += 1second += 1elif s[second] != t[first]: # 如果 s[second] 和 t[first] 不相等，则将 first 指针向右移动一位，继续进行比较first += 1if second == lengths: # 如果 second 指针到达 s 的末尾，说明 s 是 t 的子序列，返回 Truereturn Truereturn False # 如果 first 指针到达 t 的末尾，说明已经遍历完了整个字符串 t，但是没有找到 s，返回 False

topic75-13-t1679:K和数对的最大数目

题目描述：

给你一个整数数组 nums 和一个整数 k 。

每一步操作中，你需要从数组中选出和为 k 的两个整数，并将它们移出数组。

返回你可以对数组执行的最大操作数。

示例：

 思路1：先对数组排序，然后左右指针逼近，统计其中符合条件的个数，最后返回count。时间复杂度O(nlogn)

class Solution:def maxOperations(self, nums: List[int], k: int) -> int:# 思路：先排序，再左右指针逼近count = 0 # 用来存储结果length = len(nums)nums.sort() # 对 nums 排序left, right = 0, length - 1 # 定义左右指针，分别指向 nums 的开头和结尾while left < right: # 使用 while 循环遍历 numsif nums[left] + nums[right] == k: # 如果 nums[left] + nums[right] == k，说明找到了一对元素的和等于 kcount += 1 # 将 count 值加 1left += 1 # 将 left 指针向右移动一位right -= 1 # 将 right 指针向左移动一位elif nums[left] + nums[right] > k: # 如果 nums[left] + nums[right] > k，说明当前两个元素的和太大，将 right 指针向左移动一位right -= 1else: # 如果 nums[left] + nums[right] < k，说明当前两个元素的和太小，将 left 指针向右移动一位left += 1return count # 返回 count 的值

思路2：时间复杂度O(n)

1. 使用 Python 的 Counter 类对列表 nums 进行统计，得到一个字典 tmp，其中键为列表中的元素，值为该元素在列表中出现的次数。
2. 初始化变量 ans，用于存储结果，将其初始化为 0。
3. 遍历字典 tmp，对于每个键值对 (num, count)，根据其值的大小和键的值与 k 的关系，计算符合条件的数对数量，并将其加入 ans 中。
4. 算法结束，返回结果。

 

from collections import Counterclass Solution:def maxOperations(self, nums: List[int], k: int) -> int:tmp = Counter(nums) # 使用 Counter 统计 nums 中每个元素出现的次数ans = 0 # 初始化变量 ans，用于存储结果for num in tmp: # 遍历 Counter 对象 tmpif num * 2 < k: # 如果 num * 2 < k，则说明可以找到与 num 相加等于 k 的数ans += min(tmp[num], tmp.get(k-num, 0)) # 将 num 和 k - num 中较小值的出现次数加入 ans 中elif num * 2 == k: # 如果 num * 2 == k，则说明 num 和 k - num 相等ans += tmp[num] // 2 # 将 num 的出现次数的一半加入 ans 中else: # 如果 num * 2 > k，则说明再往后的数都比 k - num 大，不可能找到符合条件的数对breakreturn ans # 返回结果 ans