Leetcode hot100
1. 两数之和
给定一个整数数组 nums
和一个整数目标值
target
,请你在该数组中找出 和为目标值
target
的那 两个
整数,并返回它们的数组下标。
你可以假设每种输入只会对应一个答案,并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
示例 1:
输入:nums = [2,7,11,15]
,
target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9
,返回
[0, 1]
Answer:
1 |
|
49. 字母异位词分组
给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例 1:
输入:strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:[["bat"],["nat","tan"],["ate","eat","tea"]]
Answer:
1 |
|
128. 最长连续序列
给定一个未排序的整数数组
nums
,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。
请你设计并实现时间复杂度为 \(O(n)\) 的算法解决此问题。
示例 1:
输入:nums = [100,4,200,1,3,2]
输出:4
解释:最长数字连续序列是
[1, 2, 3, 4]
。它的长度为 4
。
Answer:
排序的时间复杂度为O(nlogn)!!!因此不能排序 1
2
3
4
5
6
7
8
9
10
11
12class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
ans = 0
set_nums = set(nums) # 转为集合去重
for x in set_nums:
if x - 1 in set_nums:
continue
y = x + 1
while y in set_nums:
y += 1
ans = max(ans, y - x)
return ans
283. Move Zeroes
Given an integer array nums
, move all 0
's
to the end of it while maintaining the relative order of the non - zero
elements.
Note that you must do this in - place without making a copy of the array.
Example 1:
Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]
Example 2:
Input: nums = [0]
Output: [0]
Answer 1:
1 |
|
Answer 2:
1 |
|
11. Container With Most Water
You are given an integer array height
of length
n
. There are n
vertical lines drawn such that
the two endpoints of the i
th line are (i, 0)
and (i, height[i])
.
Find two lines that together with the x - axis form a container, such that the container contains the most water.
Return the maximum amount of water a container can store.
Notice that you may not slant the container.
Example 1:
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are
represented by the array [1,8,6,2,5,4,8,3,7]
. In this case,
the maximum area of water (the blue - shaded section) that the container
can hold is 49
.
Example 2
Input: height = [1,1]
Output: 1
Answer 1:
Brute-force search,NONONO 1
2
3
4
5
6
7class Solution:
def maxArea(self, height: List[int]) -> int:
maxarea = 0
for i in range(len(height)):
for j in range(i+1, len(height)):
maxarea = max(maxarea, (j-i)* min(height[j],height[i]))
return maxarea
Answer 2:
Great !!! 1
2
3
4
5
6
7
8
9
10
11class Solution:
def maxArea(self, height: List[int]) -> int:
i , j, maxarea = 0, len(height)-1, 0
while i < j:
if height[i] < height[j]:
maxarea = max(maxarea, (j-i) * height[i])
i += 1
else:
maxarea = max(maxarea, (j-i) * height[j])
j -= 1
return maxarea
15. 3Sum
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: nums[0] + nums[1] + nums[2] = (-1) + 0
+ 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.
Answer:
1 |
|
3. Longest Substring Without Repeating Characters
Given a string s
, find the length of the longest
substring without duplicate characters.
Example 1:
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
Answer:
1 |
|
438. Find All Anagrams in a String
Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.
Example 1:
Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation: The substring with start index = 0 is
"cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of
"abc".
Example 2:
Input: s = "abab", p = "ab"
Output: [0,1,2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of
"ab".
The substring with start index = 1 is "ba", which is an anagram of
"ab".
The substring with start index = 2 is "ab", which is an anagram of
"ab".
考察点是滑动窗口,与前一题有点像
Answer 1:
能够通过大部分样例的解法,比较笨 1
2
3
4
5
6
7
8
9
10
11
12
13class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
result = []
length = len(p)
p = "".join(sorted(p))
for i in range(len(s)-length+1):
string = ""
for j in range(length):
string += s[i+j]
string = "".join(sorted(string))
if string == p:
result.append(i)
return result
Answer 2:
采用了定长滑动窗口的解法 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
result = []
length = len(p)
cnt_p = Counter(p) # Counter 用于统计可哈希对象的出现次数
cnt_s = Counter()
for right, c in enumerate(s):
cnt_s[c]+=1
left = right - length + 1
if left < 0:
continue
if cnt_s == cnt_p:
result.append(left)
cnt_s[s[left]] -= 1 # 因为定长滑动窗口,所以需要把左边的元素减掉
return result
Answer 3:
采用不定长滑动窗口,思路参考:by 灵茶山艾府
枚举子串 s'
的右端点,如果发现 s'
其中一种字母的出现次数大于 p
的这种字母的出现次数,则右移 s'
的左端点。如果发现
s'
的长度等于 p
的长度,则说明 s'
的每种字母的出现次数,和 p
的每种字母的出现次数都相同,那么
s'
是 p
的异位词。
证明:内层循环结束后,s'
的每种字母的出现次数,都小于等于 p
的每种字母的出现次数。如果 s'
的其中一种字母的出现次数比
p
的小,那么 s'
的长度必然小于 p
的长度。所以只要 s'
的长度等于 p
的长度,就说明 s'
的每种字母的出现次数,和 p
的每种字母的出现次数都相同,s'
是 p
的异位词,把 s'
左端点下标加入答案。
代码实现时,可以把 cntS
和 cntP
合并成一个
cnt
: - 对于 p
的字母 c
,把
cnt[p]
加一。 - 对于 s'
的字母
c
,把 cnt[c]
减一。 - 如果
cnt[c] < 0
,说明窗口中的字母 c
的个数比
p
的多,右移左端点。
1 |
|
560. Subarray Sum Equals K
Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.
A subarray is a contiguous non-empty sequence of elements within an
array.
子数组是数组中元素的连续非空序列。
注意是连续的!!!
Example 1:
Input: nums = [1,1,1], k = 2
Output: 2
Example 2:
Input: nums = [1,2,3], k = 3
Output: 2
1 |
|
在解决本题之前,需要练习前缀和模板题303!!!
Answer 1:
前缀和问题,使用前缀和字典记录前缀和的出现次数,然后遍历数组,计算当前前缀和减去目标值k的差值在字典中出现的次数,累加到结果中。
1
2
3
4
5
6
7
8
9
10
11class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
prefix_sum = {0: 1} # 前缀和字典,初始值为前缀和为0出现1次
current_sum = 0
count = 0
for num in nums:
current_sum += num
if current_sum - k in prefix_sum:
count += prefix_sum[current_sum - k]
prefix_sum[current_sum] = prefix_sum.get(current_sum, 0) + 1
return count
Answer 2:
1 |
|
Answer 3:
还可以优化成一次遍历即可实现: 1
2
3
4
5
6
7
8
9
10
11
12class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
fsum = [0] * (len(nums) + 1)
ans = 0
cnt = defaultdict(int)
cnt[0] = 1
s = 0
for n in nums:
s += n
ans += cnt[s-k]
cnt[s] += 1
return ans
303. Range Sum Query - Immutable
Given an integer array nums
, handle multiple queries of
the following type:
- Calculate the sum of the elements of
nums
between indicesleft
andright
inclusive whereleft <= right
.
Implement the NumArray
class:
NumArray(int[] nums)
Initializes the object with the integer arraynums
.int sumRange(int left, int right)
Returns the sum of the elements ofnums
between indicesleft
andright
inclusive (i.e.nums[left] + nums[left + 1] + ... + nums[right]
).
Example 1:
Input
["NumArray", "sumRange", "sumRange", "sumRange"] [[-2, 0, 3, -5, 2, -1],
[0, 2], [2, 5], [0, 5]]
Output
[null, 1, -1, -3]
Explanation
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return (-2) + 0 + 3 = 1
numArray.sumRange(2, 5); // return 3 + (-5) + 2 + (-1) = -1
numArray.sumRange(0, 5); // return (-2) + 0 + 3 + (-5) + 2 + (-1) =
-3
303连题目都看不懂。。。绝了。。。
Answer 1:
1 |
|
303做完再回去看560应该就能看懂了