1. 存在重复元素
给定一个整数数组，判断是否存在重复元素。
如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
示例 1:
输入: [1,2,3,1]
输出: true
示例 2:
输入: [1,2,3,4]
输出: false
示例 3:
输入: [1,1,1,3,3,4,3,2,4,2]
输出: true
出处：
https://edu.csdn.net/practice/24183905
代码：
from typing import List class Solution: def containsDuplicate(self, nums: List[int]) -> bool: nums.sort() count = 0 while count < len(nums) - 1: if nums[count] == nums[count + 1]: return True count += 1 return False
输出：
略
2. 矩阵置零
给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
进阶：
一个直观的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
你能想出一个仅使用常量空间的解决方案吗？
示例 1：
输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]
示例 2：
输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]
提示：
m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
-2^31 <= matrix[i][j] <= 2^31 - 1
出处：
https://edu.csdn.net/practice/24183904
代码：
class Solution(object): def setZeroes(self, matrix): """ :type matrix: List[List[int]] :rtype: void Do not return anything, modify matrix in-place instead. """ if not matrix: return m = len(matrix) if m == 0: return r = [] c = [] n = len(matrix[0]) for i in range(m): for j in range(n): if matrix[i][j] == 0: r.append(i) c.append(j) r = set(r) c = set(c) for i in r: for j in range(n): matrix[i][j] = 0 for i in range(m): for j in c: matrix[i][j] = 0 return matrix # %% s = Solution() print(s.setZeroes(matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]))
输出：
[[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]]
3. 回文对
给定一组 互不相同 的单词， 找出所有 不同 的索引对 (i, j)，使得列表中的两个单词， words[i] + words[j] ，可拼接成回文串。
示例 1：
输入：words = ["abcd","dcba","lls","s","sssll"]
输出：[[0,1],[1,0],[3,2],[2,4]]
解释：可拼接成的回文串为 ["dcbaabcd","abcddcba","slls","llssssll"]
示例 2：
输入：words = ["bat","tab","cat"]
输出：[[0,1],[1,0]]
解释：可拼接成的回文串为 ["battab","tabbat"]
示例 3：
输入：words = ["a",""]
输出：[[0,1],[1,0]]
提示：
1 <= words.length <= 5000
0 <= words[i].length <= 300
words[i] 由小写英文字母组成
出处：
https://edu.csdn.net/practice/24183903
代码：
from typing import List class Solution: def palindromePairs(self, words: List[str]) -> List[List[int]]: def is_palindrome(str, start, end): """检查子串是否是回文串 """ part_word = str[start : end + 1] return part_word == part_word[::-1] def find_reversed_word(str, start, end): """查找子串是否在哈希表中 Return: 不在哈希表中，返回 -1 否则返回对应的索引 """ part_word = str[start : end + 1] ret = hash_map.get(part_word, -1) return ret hash_map = {} for i in range(len(words)): word = words[i][::-1] hash_map[word] = i res = [] for i in range(len(words)): word = words[i] word_len = len(word) if is_palindrome(word, 0, word_len - 1) and "" in hash_map and word != "": res.append([hash_map.get(""), i]) for j in range(word_len): if is_palindrome(word, j, word_len - 1): left_part_index = find_reversed_word(word, 0, j - 1) if left_part_index != -1 and left_part_index != i: res.append([i, left_part_index]) if is_palindrome(word, 0, j - 1): right_part_index = find_reversed_word(word, j, word_len - 1) if right_part_index != -1 and right_part_index != i: res.append([right_part_index, i]) return res s = Solution() words = ["abcd","dcba","lls","s","sssll"] print(s.palindromePairs(words))
输出：
[[1, 0], [0, 1], [3, 2], [2, 4]]
