第一天

第一题

题目

217. 存在重复元素

给你一个整数数组 nums 。如果任一值在数组中出现至少两次，返回 true ；如果数组中每个元素互不相同，返回 false 。

示例 1：

输入：nums = [1,2,3,1]

输出：true

示例 2：

nums = [1,2,3,4]

false

示例 3：

输入：nums = [1,1,1,3,3,4,3,2,4,2]

输出：true

提示：

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

代码

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        sets = set(nums)
        return len(nums) !=  len(sets)

解析

直接将输入的列表转为集合，因为集合将去除重复值。再判断长度与原始是否相同，如果不同则有重复数据，返回true。

第二题

题目

219. 存在重复元素 II

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [1,2,3,1], k = 3

输出：true

示例 2：

输入：nums = [1,0,1,1], k = 1

输出：true

示例 3：

输入：nums = [1,2,3,1,2,3], k = 2

输出：false

提示：

1 <= nums.length <= 105
-10^9 <= nums[i] <= 10^9
0 <= k <= 10^5

代码

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        pos = {}
        for i, num in enumerate(nums):
            if num in pos and i - pos[num] <= k:
                return True
            pos[num] = i
        return False

解析

pos = {} # 创建一个哈希表，其中key为nums的值，value为nums对应的最后一次出现的位置

for i, num in enumerate(nums): # 遍历nums，其中使用enumerate方法，返回nums值外还返回当前循环索引值

    if num in pos and i - pos[num] <= k: # 如果当前nums值存在在pos中，并且当前索引减去上一次出现索引小于k时，返回true

        return True 

    pos[num] = i # 如果超出要求(k)，则将当前的索引存入哈希表

return false # 遍历所有都不满足要求，返回false

相当于从左到右遍历nums列表，并记录每个值最后一次出现的位置，当再次出现，就和记录的最后一次进行减法，如果小于k直接返回true，如果大于则将现在的位置记录进pos覆盖之前的位置。

第三题

题目

36. 有效的数独

请你判断一个 9 x 9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

示例 1：

输入：board =
[[“5”,”3”,”.”,”.”,”7”,”.”,”.”,”.”,”.”]

,[“6”,”.”,”.”,”1”,”9”,”5”,”.”,”.”,”.”]

,[“.”,”9”,”8”,”.”,”.”,”.”,”.”,”6”,”.”]

,[“8”,”.”,”.”,”.”,”6”,”.”,”.”,”.”,”3”]

,[“4”,”.”,”.”,”8”,”.”,”3”,”.”,”.”,”1”]

,[“7”,”.”,”.”,”.”,”2”,”.”,”.”,”.”,”6”]

,[“.”,”6”,”.”,”.”,”.”,”.”,”2”,”8”,”.”]

,[“.”,”.”,”.”,”4”,”1”,”9”,”.”,”.”,”5”]

,[“.”,”.”,”.”,”.”,”8”,”.”,”.”,”7”,”9”]]

输出：true

示例 2：

输入：board =
[[“8”,”3”,”.”,”.”,”7”,”.”,”.”,”.”,”.”]

,[“6”,”.”,”.”,”1”,”9”,”5”,”.”,”.”,”.”]

,[“.”,”9”,”8”,”.”,”.”,”.”,”.”,”6”,”.”]

,[“8”,”.”,”.”,”.”,”6”,”.”,”.”,”.”,”3”]

,[“4”,”.”,”.”,”8”,”.”,”3”,”.”,”.”,”1”]

,[“7”,”.”,”.”,”.”,”2”,”.”,”.”,”.”,”6”]

,[“.”,”6”,”.”,”.”,”.”,”.”,”2”,”8”,”.”]

,[“.”,”.”,”.”,”4”,”1”,”9”,”.”,”.”,”5”]

,[“.”,”.”,”.”,”.”,”8”,”.”,”.”,”7”,”9”]]

输出：false

解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与示例1 相同。但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

提示：

board.length == 9
board[i].length == 9
board[i][j] 是一位数字（1-9）或者 ‘.’

代码

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        row = [[0] * 10 for _ in range(9)]
        col = [[0] * 10 for _ in range(9)]
        box = [[0] * 10 for _ in range(9)]
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    continue
                curNum = ord(board[i][j]) - ord('0')
                if row[i][curNum] != 0 or col[j][curNum] != 0 or box[j // 3 + (i // 3) * 3][curNum] != 0:
                    return False
                row[i][curNum], col[j][curNum],box[j // 3 + (i // 3) * 3][curNum] = 1, 1, 1
        return True

解析

创建3*9个list来记录每行、每列以及每块的数值是否出现。当当前格子中为数字，则进行判断是否在每行每列中。对于所在格子的计算：

用当前位置的行数除以子块的行数并向下取整： j // 3 ，先初步得到列数，比如对于board[5][5] 可以算出在所有3*3的子块中的第 5//3 = 1 列(下标从0开始)
同理计算出所在的行数：i // 3 ,用上边的例子计算出为 5 // 3 = 1 行
最后将列数加上行数乘3 ： j // 3 + (i // 3) * 3 ，因为每行有3个子块，所以乘三，对于board[5][5]则可以算出所在子块为4

对与代码解释，将带数值的格子中数值取出来，并转换为整数，对与所在行列及子块list下标进行查询，如果不为0则返回false，否则将list中对应位置置为1。

第二天

第一题

题目

349. 两个数组的交集

给定两个数组 nums1 和 nums2 ，返回它们的交集。输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]

输出：[2]

示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]

输出：[9,4]

解释：[4,9] 也是可通过的

提示：

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000

代码

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        ans = []
        for nums in nums2:   
        
            if nums in nums1:
                if nums in ans:
                    continue
                else:
                    ans.append(nums)
            else: 
                continue
        return ans

解析

将第二个列表中的值直接判断是否存在在第一个列表，存在的话判断是否已经加入答案列表，不在则加入答案列表。

第二题

题目

350. 两个数组的交集 II

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]

输出：[2,2]

示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]

输出：[4,9]

提示：

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000

代码

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        if len(nums1) > len(nums2):
            return self.intersect(nums2, nums1)
        
        m = collections.Counter()
        for num in nums1:
            m[num] += 1
        
        intersection = list()
        for num in nums2:
            if (count := m.get(num, 0)) > 0:
                intersection.append(num)
                m[num] -= 1
                if m[num] == 0:
                    m.pop(num)
        
        return intersection

解析

先将第一个列表中的所有值和其出现的次数存入哈希表中，key为值，value为次数。再遍历第二个列表，如果存在在之前的哈希表中，则value减一，并加入到答案列表。如果value值为0则移出哈希表。

第三题

题目

706. 设计哈希映射

不使用任何内建的哈希表库设计一个哈希映射（HashMap）。

实现 MyHashMap 类：

MyHashMap() 用空映射初始化对象
void put(int key, int value) 向 HashMap 插入一个键值对 (key, value) 。如果 key 已经存在于映射中，则更新其对应的值 value 。
int get(int key) 返回特定的 key 所映射的 value ；如果映射中不包含 key 的映射，返回 -1 。
void remove(key) 如果映射中存在 key 的映射，则移除 key 和它所对应的 value 。

示例：

输入：[“MyHashMap”, “put”, “put”, “get”, “get”, “put”, “get”, “remove”, “get”]
[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]

输出：[null, null, null, 1, -1, null, 1, null, -1]

解释：
MyHashMap myHashMap = new MyHashMap();
myHashMap.put(1, 1); // myHashMap 现在为 [[1,1]]
myHashMap.put(2, 2); // myHashMap 现在为 [[1,1], [2,2]]
myHashMap.get(1); // 返回 1 ，myHashMap 现在为 [[1,1], [2,2]]
myHashMap.get(3); // 返回 -1（未找到），myHashMap 现在为 [[1,1], [2,2]]
myHashMap.put(2, 1); // myHashMap 现在为 [[1,1], [2,1]]（更新已有的值）
myHashMap.get(2); // 返回 1 ，myHashMap 现在为 [[1,1], [2,1]]
myHashMap.remove(2); // 删除键为 2 的数据，myHashMap 现在为 [[1,1]]
myHashMap.get(2); // 返回 -1（未找到），myHashMap 现在为 [[1,1]]

提示：

0 <= key, value <= 10^6
最多调用 10^4 次 put、get 和 remove 方法

代码

class MyHashMap(object):

    def __init__(self):
        self.map = [-1] * 1000001https://leetcode.cn/problems/valid-palindrome/

    def put(self, key, value):
        self.map[key] = value

    def get(self, key):
        return self.map[key]

    def remove(self, key):
        self.map[key] = -1

解析

直接创造一个超大数组，以此来避免哈希碰撞。

第三天

第一题

题目

125. 验证回文串

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个回文串。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是回文串，返回 true ；否则，返回 false 。

示例 1：

输入：s = “A man, a plan, a canal: Panama”

输出：true

解释：”amanaplanacanalpanama” 是回文串。

示例 2：

输入：s = “race a car”Panama”

输出：false

解释：”raceacar” 不是回文串。

示例 3：

输入：s = “ “Panama”

输出：true

解释：在移除非字母数字字符之后，s 是一个空字符串 “” 。
由于空字符串正着反着读都一样，所以是回文串。

提示：

1 <= s.length <= 2 * 10^5
s 仅由可打印的 ASCII 字符组成

代码

class Solution:
    def isPalindrome(self, s: str) -> bool:
        tmp = ''.join(ch for ch in s if ch.isalnum())
        res = tmp[::-1].lower()
        return res == tmp.lower()

解析

先将字符串中非字母元素去除，在将大写字母转为小写字母，最后进行翻转，返回翻转后的字符串与原始字符串是否相等

第二题

题目

344. 反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

示例 1：

输入：s = [“h”,”e”,”l”,”l”,”o”]

输出：[“o”,”l”,”l”,”e”,”h”]

示例 2：

输入：s = [“H”,”a”,”n”,”n”,”a”,”h”]

输出：[“h”,”a”,”n”,”n”,”a”,”H”]

提示：

1 <= s.length <= 10^5
s[i] 都是 ASCII 码表中的可打印字符

代码

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        for i in range(len(s)//2):
            tmp = s[i]
            s[i] = s[len(s)-1-i]
            s[len(s)-1-i] = tmp
        return s

解析

直接从最左边到中间，进行镜像交换即可。

第三题

题目

557. 反转字符串中的单词 III

给定一个字符串 s ，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

示例 1：

输入：s = “Let’s take LeetCode contest”

输出：”s’teL ekat edoCteeL tsetnoc”

示例 2：

输入：s = “God Ding”

输出：”doG gniD”

提示：

1 <= s.length <= 5*10^4
s 包含可打印的 ASCII 字符。
s 不包含任何开头或结尾空格。
s 里至少有一个词。
s 中的所有单词都用一个空格隔开。

代码

1
2
3

class Solution:
    def reverseWords(self, s: str) -> str:
        return " ".join(word[::-1] for word in s.split(" "))

解析

根据空格将字符串切片，再将切片后的单词进行翻转。

第四天

第一题

题目

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 <= 10^4
haystack 和 needle 仅由小写英文字符组成

代码

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        n = len(needle)
        for i in range(len(haystack)):
            if haystack[i:i+n] == needle:
                return i
        return -1

解析

直接进行枚举

第二题

题目

459. 重复的子字符串

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

示例 1：

输入：s = “abab”

输出：true

解释：可由子串 “ab” 重复两次构成。

示例 2：

输入：s = “aba”

输出：false

示例 3：

输入：s = “abcabcabcabc”

输出: true

解释: 可由子串 “abc” 重复四次构成。 (或子串 “abcabc” 重复两次构成。)：

1 <= s.length <= 10^4
s 由小写英文字母组成

代码

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        return s in (s+s)[1:-1]

解析

假设 s 可由子串 x 重复 n 次构成，即 s = nx
则有 s+s = 2nx

移除 s+s 开头和结尾的字符，变为 (s+s)[1:-1]，则破坏了开头和结尾的子串 x
此时只剩 2n-2 个子串

若 s 在 (s+s)[1:-1] 中，则有 2n-2 >= n，即 n >= 2

即 s 至少可由 x 重复 2 次构成

否则，n < 2，n 为整数，只能取 1，说明 s 不能由其子串重复多次构成

第三题

题目

686. 重复叠加字符串匹配

给定两个字符串 a 和 b，寻找重复叠加字符串 a 的最小次数，使得字符串 b 成为叠加后的字符串 a 的子串，如果不存在则返回 -1。

注意：字符串 “abc” 重复叠加 0 次是 “”，重复叠加 1 次是 “abc”，重复叠加 2 次是 “abcabc”。

示例 1：

输入：a = “abcd”, b = “cdabcdab”

输出：3

解释：a 重复叠加三遍后为 “abcdabcdabcd”, 此时 b 是其子串。

示例 2：

输入：a = “a”, b = “aa”

输出：2

示例 3：

输入：a = “a”, b = “a”

输出: 1

示例 4：

输入：a = “abc”, b = “wxyz”

输出: -1

1 <= a.length <= 10^4
1 <= b.length <= 10^4
a 和 b 由小写英文字母组成

代码

class Solution:
    def repeatedStringMatch(self, a: str, b: str) -> int:
        i = 1
        a_plus = a
        while len(a_plus) <= 10**4:
            a_plus = a * i
            if b in a_plus:
                return i
            i += 1
        return -1

解析

循环添加a的字符串，并记录添加次数，如果b在a_plus中则返回添加次数。直到a_plus超出范围，返回-1。