PeterQwQ
0%

发表于 更新于

给你一个正整数 n， 如果一个二进制字符串 x 的所有长度为 2 的子字符串中包含 至少 一个 “1”，则称 x 是一个 有效 字符串。

返回所有长度为 n 的 有效 字符串，可以以任意顺序排列。

例如， n=3 就会有 ["010", "011", "101", "110", "111"]。

CS61A里面有类似的题目，递归即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def validStrings(self, n: int) -> List[str]:
        ans = []
        
        def helper(s: str, n: int):
            if n == 0:
                ans.append(s)
                return
            if s[-1] == '0':
                helper(s + '1', n - 1)
            else:
                helper(s + '1', n - 1)
                helper(s + '0', n - 1)
        
        helper('0', n - 1)
        helper('1', n - 1)
        return ans

发表于 更新于

给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数。子数组是数组中的一个连续序列。

想都没想，直接用了双指针，也是直接WA，然后才发现有负数数据。

思考了一下，这个题目实际上就是需要求解 sum(i, j) = k (i < j) 的个数，那么可以变成前缀和的问题。实际上，sum(i, j) = sum(0, j) - sum(0, i)，那么只需要求解 sum(0, i) = sum(0, j) - k 的个数即可。

那么在实际实现的过程中，可以使用一个哈希表来存储前缀和的个数，然后遍历数组，对于每一个元素，计算当前的前缀和，然后查找哈希表中是否存在 sum(0, i) - k 的前缀和，如果存在，那么就说明存在一个子数组的和为 k。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        hash_prefix = {}
        n = len(nums)
        ans = 0
        prefix = [0]
        for i in range(n):
            prefix.append(prefix[-1] + nums[i])

        for i in range(len(prefix)):
            ans += hash_prefix.get(prefix[i]-k, 0)
            hash_prefix[prefix[i]] = hash_prefix.get(prefix[i], 0) + 1

        return ans

这里有一些可以注意的地方，例如代码 ans += hash_prefix.get(prefix[i]-k, 0) 和 hash_prefix[prefix[i]] = hash_prefix.get(prefix[i], 0) + 1，前后不能够交换，举个简单的例子比如 nums = [2], k = 0 ，那么实际上答案是 0，但是如果交换了顺序，那么答案就会变成 1。

发表于 更新于

给定两个非空字符串 s 和 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

一开始写了暴力，也能过但是太慢了：

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        length_s = len(s)
        length_p = len(p)
        sorted_p = ''.join(sorted(p))
        ans = []
        for i in range(length_s-length_p+1):
            now_str = ''.join(sorted(s[i:i+length_p]))
            if now_str == sorted_p:
                ans.append(i)
        return ans

后来观察这道题，其实只需要存储字母数量然后再滑动窗口就行了，因为如果是字母异位词，那么他们的字母数量是一样的，可以左右指针滑动窗口，然后比较两个字典是否相等：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:    
        n_s, n_p = len(s), len(p)
        if n_s < n_p:
            return []
        ans = []
        hash_table_p = {}
        hash_table_current = {}
        for i in range(n_p):
            hash_table_p[p[i]] = hash_table_p.get(p[i], 0) + 1
            hash_table_current[s[i]] = hash_table_current.get(s[i], 0) + 1
        for i in range(n_s-n_p+1):
            right = n_p+i
            if hash_table_p == hash_table_current:
                ans.append(i)
            hash_table_current[s[i]] -= 1
            if hash_table_current[s[i]] == 0:
                del hash_table_current[s[i]]
            if right != n_s:
                hash_table_current[s[right]] = hash_table_current.get(s[right], 0) + 1
            else:
                break
        return ans

发表于 更新于

给你一个字符串 target 。

Alice 将会使用一种特殊的键盘在她的电脑上输入 target ，这个键盘 只有两个按键：

按键 1：在屏幕上的字符串后追加字符 ‘a’。
按键 2：将屏幕上字符串的 最后一个 字符更改为英文字母表中的 下一个 字符。例如，’c’ 变为 ‘d’，’z’ 变为 ‘a’。
注意，最初屏幕上是一个空字符串 “”，所以她 只能 按按键 1。

请你考虑按键次数 最少 的情况，按字符串出现顺序，返回 Alice 输入 target 时屏幕上出现的所有字符串列表。

模拟就行了，不过我写的有点蠢

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from typing import List

class Solution:
    def stringSequence(self, target: str) -> List[str]:
        ans = ["a"]
        alphabet_list = [chr(i) for i in range(ord('a'), ord('z') + 1)]
        for i, s in enumerate(target):
            length = int(ord(s) - ord('a'))
            lst_word = ans[-1]
            if i == 0 and length == 0:
                continue
            if i == 0 and length != 0:
                for i in range(1, length+1):
                    change_alpha = alphabet_list[i]
                    ans.append(change_alpha)
                continue
            for i in range(length+1):
                append_words = lst_word + alphabet_list[i]
                ans.append(append_words)
        return ans

看题解之后比较简洁的写法

1
2
3
4
5
6
7
8
9
class Solution:
    def stringSequence(self, target: str) -> List[str]:
        ans = []
        s = []
        for c in target:
            s.append('')
            for s[-1] in ascii_lowercase[:ord(c) - ord('a') + 1]:
                ans.append(''.join(s))
        return ans

发表于 更新于

给定一个字符串 s，请你找出其中不含有重复字符的 最长子串 的长度。

写个时间复杂度是 O(n^2) 的暴力，过了但是只击败了 5% 的用户。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        if n == 0:
            return 0
        ans = 1
        for i in range(n):
            now_length = 1
            seen = set()
            seen.add(s[i])
            for j in range(i+1, n):
                if s[j] not in seen:
                    seen.add(s[j])
                    now_length += 1
                    ans = max(now_length, ans)
                else:
                    break
        return ans

用滑动窗口的思想进行优化，一般来说，滑动窗口类型的题目可以模板化为这样的代码：

1
2
3
4
5
6
7
for i in range(n):
    window = set()
    while right < n and (window not in valid):
        window.add(s[right])
        right += 1
    ans = max(ans, right - i)
    window.remove(s[i])

滑动窗口的时间复杂度是 O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        if n == 0:
            return 0
        if n == 1:
            return 1
        seen = set()
        right = 0
        ans = 0
        for i in range(n-1):       
            while right < n and s[right] not in seen:
                seen.add(s[right])
                right += 1
            ans = max(ans, right - i)
            seen.remove(s[i])
        return ans

发表于 更新于

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

首先，最暴力的方法就是 O(n^3) 的时间复杂度，直接三重循环，找到所有的三元组，然后再去重。

但是在固定一个数之后，本质上又转化成了两数之和的问题，所以可以用双指针来优化一下。

这是一个复杂度为 O(n^2) 的算法，通过了 308/313 的测试用例。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        ans = []
        for i in range(len(nums)):
            target = -nums[i]
            seen = {}
            for j in range(i+1, len(nums)):
                target_list = sorted([-target, nums[j], target-nums[j]])
                if target - nums[j] in seen and target_list not in ans:
                    ans.append(target_list)
                seen[nums[j]] = j        
        return ans

上面的算法在中间的去重操作上还需要遍历一次 ans 数组，所以可以用一个 set 来代替 ans 数组，这样就不需要再去重了。而且在python中，set 的查找操作 in 是 O(1) 的时间复杂度，所以这样的优化是可行的。

这种算法时间复杂度是 O(n^2)，通过了 312/313 的测试用例。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        ans = set()  # 用集合去重
        for i in range(len(nums)):
            target = -nums[i]
            seen = {}
            for j in range(i + 1, len(nums)):
                if target - nums[j] in seen:
                    triplet = tuple(sorted([-target, nums[j], target - nums[j]]))
                    ans.add(triplet)  # 直接将结果加入集合
                seen[nums[j]] = j
        return [list(triplet) for triplet in ans]  # 将最终结果转为列表返回

看起来暴力是不行的，那么就换一种思路。对于原数组我们在一开始就进行排序，然后固定一个数，再用双指针来找另外两个数。在寻找另外两个数的时候，如果两个数的和大于目标值，那么右指针左移；如果两个数的和小于目标值，那么左指针右移；如果两个数的和等于目标值，那么就找到了一个三元组。这种算法的时间复杂度是 O(n^2)。同时在这里，固定第一个元素的时候，如果和上一个元素相同，那么就跳过这个元素，因为这个元素已经找过了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        sorted_list = sorted(nums)
        ans = set()
        for i in range(len(sorted_list)):
            if i > 0 and sorted_list[i] == sorted_list[i-1]:
                continue
            target = -sorted_list[i]
            left = i+1
            right = len(sorted_list)-1
            while left < right:
                if sorted_list[left] + sorted_list[right] > target:
                    right -= 1
                    continue
                if sorted_list[left] + sorted_list[right] < target:
                    left += 1
                    continue
                if sorted_list[left] + sorted_list[right] == target:
                    triplet = tuple(sorted([-target, sorted_list[left], sorted_list[right]]))
                    ans.add(triplet)
                    right -= 1
                    continue
        return [list(triplet) for triplet in ans]

发表于 更新于

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

一开始想到的暴力O(n^2)的方法，遍历所有的组合，找到最大的面积。不过显然会TLE。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def maxArea(self, height: List[int]) -> int:
        ans = 0
        for i in range(len(height)-1):
            for j in range(i+1, len(height)):
                bigger_height = min(height[i], height[j])
                area = bigger_height * (j - i)
                # print(area)
                if area <= ans:
                    continue
                else:
                    ans = area
        return ans

假设我们有两个指针，指向数组的两个位置，分别对应着高度 x, y (x <= y)，不妨假设他们之间的距离是 t 。那么这两个指针之间的面积就是 min(x, y) * t = x * t 。此时我们如果移动高的指针，得到新的 y_1。分两种情况讨论，如果 y_1 < y，那么新的面积就是 min(x, y_1) * (t-1) <= min(x, y) * t。如果 y_1 >= y，那么新的面积就是 min(x, y_1) * (t-1) = x * (t-1)。这样可以看出，如果我们移动高的指针，面积只会变小，所以我们应该移动矮的指针。

换句话说，其实可以类比木桶的“短板效应”，我们应该移动短的那一边，因为移动长的那一边，不管怎么移动，都不会使得面积变大。最终的时间复杂度是 O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def maxArea(self, height: List[int]) -> int:
        i, j = 0, len(height)-1
        ans = (len(height)-1) * min(height[i], height[j])
        while i != j:
            if height[i] <= height[j]:
                i += 1
            else:
                j -= 1
            now_area = (j - i) * min(height[i], height[j])
            if now_area > ans:
                ans = now_area
        return ans

发表于 更新于

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

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

想到的第一种方法用的是python的 remove 函数，但是这个函数的时间复杂度是 $O(n)$，所以这个方法的时间复杂度是 $O(n^2)$，不是很好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        count = 0
        i = 0
        while i < len(nums):
            if nums[i] == 0:
                nums.remove(0)
                count += 1
            else:
                i += 1
        for _ in range(0, count):
            nums.append(0)

还可以用双指针来优化一下结果，只需要遍历一次数组，时间复杂度是 $O(n)$。主体思想是用一个指针 j 来记录非零元素的位置，然后遍历数组，如果当前元素不是0，就把当前元素赋值给 nums[j]，然后 j 自增1，最后再把 j 后面的元素全部赋值为0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        j = 0
        count = 0
        for i in range(len(nums)):
            if nums[i] != 0:
                nums[j] = nums[i]
                j += 1
            else:
                count += 1 
        for k in range(0, count):
            nums[j+k] = 0

发表于 更新于

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

题目的意思是要找出一个连续的序列，不要求在原数组中连续，只要求数字连续即可。同时对于这种数据: [0, 0, 1, 2, 3, 4] ，其实只需要找到 [0, 1, 2, 3, 4] 即可，所以可以先去重 set() ，然后排序 sorted() ，然后遍历一遍即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if nums == []:
            return 0
        new_list = sorted(set(nums))
        ans = 1
        longest = 1
        # print(new_list)
        for i in range(0, len(new_list)-1):
            if new_list[i+1] == new_list[i] + 1:
                ans += 1
                if ans >= longest:
                    longest = ans
                continue
            ans = 1
        return longest

发表于 更新于

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

Python里面的sorted函数可以直接对字符串排序，最后返回的是列表，可以用''.join()来转换成字符串。

我的解法时间复杂度是$O(n)$。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        seen = {}
        for i, word in enumerate(strs):
            sorted_word = ''.join(sorted(word))
            if sorted_word not in seen:
                seen[sorted_word] = [word]
            else:   
                seen[sorted_word].append(word)     
        # for key, value in seen.items():
        #     ans.append(value)
        return list(seen.values())

力扣官网给的是用了collections.defaultdict的方法，这样就不用判断key是否在字典里面了。