2021年 LeetCode 刷题笔记。
LeetCode 1566. Detect Pattern of Length M Repeated K or More Times
简单题目，在$O(n)$ 时间复杂度。
python 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution:
# m 表示重复的 subarry，k 表示重复的次数
def containsPattern(self, arr: List[int], m: int, k: int) -> bool:
n =len(arr)
counter =0
# 按顺序遍历保证了 consecutively
for i in range(n-m):
if arr[i] ==arr[i+m]:
counter +=1
else:
# 一旦当前数字不能作为重复的数字，那么之前的记录也都不能用了
counter =0
if counter == m*(k-1):
return True
return False
|
c++ 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution {
public:
bool containsPattern(vector<int>& arr, int m, int k) {
int n =arr.size();
int counter =0;
for(int i =0; i+m< n; i++)
{
if(arr[i] ==arr[(i +m )])
counter +=1;
else
counter =0;
if (counter == m *(k-1))
return true;
}
return false;
}
};
|
1567. Maximum Length of Subarray With Positive Product
时间复杂度是$O(n)$，递推求解（dp，递归）。
python实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution:
def getMaxLen(self, nums: List[int]) -> int:
pos =neg =ans =0
for n in nums:
if n ==0:
pos, neg =0, 0 # 递归中有一种情况：重置。
elif n >0:
# 从执行顺序上说，等号右边都计算完成之后，然后再重新赋值给左边 （体现了本题中的递推or dp 的思路）
pos, neg =pos +1, neg +(1 if neg >0 else 0)
# 注意不能将这一句分开写成两句。
#pos =pos +1
#neg =neg +(1 if neg >0 else 0)
else:
neg, pos =pos +1 , neg+ (1 if neg >0 else 0)
#neg =pos +1
#pos = neg+ (1 if neg>0 else 0)
ans =max(ans, pos)
return ans
|
c++ 代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
class Solution {
public:
int getMaxLen(vector<int>& nums) {
int n =nums.size();
vector<int> pos(n, 0), neg(n, 0);
int res =0;
if(nums[0] >0)
{
pos[0] =1;
res =1;
}
else if(nums[0] <0) neg[0] =1;
for(int i =1; i<n; i++)
{
int t =nums[i];
if (t >0)
{
pos[i] =pos[i-1] +1;
if(neg[i-1] > 0)
neg[i] = neg[i-1] +1;
else
neg[i] =neg[i-1];
}
else if (t <0)
{
neg[i] =pos[i-1] +1;
if(neg[i-1] >0)
pos[i] =neg[i-1] +1;
else
pos[i] =neg[i-1];
}
res =max(res, pos[i]);
}
return res;
}
};
|
1576. Replace All ?’s to Avoid Consecutive Repeating Characters
c++ 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution {
public:
string modifyString(string s) {
int n =s.size();
for(int i =0; i<n; i++)
{
if(s[i] !='?' ) continue;
// 26字母进行遍历
for( char ch ='a'; ch<='z'; ch++)
{
if(i && s[i-1] ==ch) continue;
if( i+1<n && s[i+1] ==ch) continue;
s[i] =ch;
}
}
return s;
}
};
|
python 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution:
def modifyString(self, s: str) -> str:
n =len(s)
s =list(s)
alpha ='abcdefghijklmnopqrstuvwxyz'
for i in range(n):
if s[i] !='?':
continue
for ch in alpha:
if i>0 and s[i-1] ==ch: continue
if i+1 < n and s[i+1] ==ch: continue
s[i] =ch # 将 s[i] 字母进行替换
return ''.join(s)
|
1577. Number of Ways Where Square of Number Is Equal to Product of Two Numbers
python 解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
class Solution:
# 数据范围是 10^3, 所以 O(n^2) 的时间复杂度是可以接受的
from collections import Counter
def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
square1 = [ v*v for v in nums1]
square2= [v*v for v in nums2]
square1 =Counter(square1)
square2 =Counter(square2)
res =0
n1, n2 =len(nums1), len(nums2)
for i in range(n1-1):
for j in range(i+1, n1):
val =nums1[i] * nums1[j]
if val in square2:
res += square2[val]
for i in range(n2-1):
for j in range(i+1, n2):
val = nums2[i] * nums2[j]
if val in square1:
res += square1[val]
return res
|
可以优化的点：nums1 和nums2 的操作基本上类同的，所以可以写成一个函数，然后调用两次。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution:
from collections import Counter
def fun(self, nums1: List[int], nums2: List[int]) -> int:
nums2 =[val*val for val in nums2]
dic =Counter(nums2)
res =0
n =len(nums1)
for i in range(n-1):
for j in range(i+1, n):
res += dic[nums1[i] *nums1[j]]
return res
def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
return self.fun(nums1, nums2) +self.fun(nums2, nums1)
|
（至少从代码的结构上看，这个版本是更加简洁的）
c++ 中如何定义dictionary unordered_map<long long, int> hash 这样进行书写。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
public:
typedef long long LL;
int fun(vector<int>& nums1, vector<int>& nums2)
{
unordered_map<LL, int> dic;
for(auto num :nums2)
dic[(LL)num*num] +=1;
int res =0;
int n =nums1.size();
for(int i =0; i< n-1; i++)
for(int j =i +1; j< n; j++)
res += dic[(LL)nums1[i] *nums1[j]];
return res;
}
int numTriplets(vector<int>& nums1, vector<int>& nums2) {
return fun(nums1, nums2) +fun(nums2, nums1);
}
};
|
1578. Minimum Deletion Cost to Avoid Repeating Letters
python求解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution:
def minCost(self, s: str, cost: List[int]) -> int:
# 避免重复的最小删除代价
# 反向思维：统计最大删除代价，然后使用总的删除代价减去最大删除代价
# python 中没有连等
res =0
total , m =0, 0
for i in range(len(s)):
if i ==0 or s[i-1] != s[i]:
res += total -m
total =m =cost[i]
else:
total += cost[i]
m =max(m, cost[i])
res += total -m
return res
|
c++ 求解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class Solution {
public:
int minCost(string s, vector<int>& cost) {
int res =0;
int total=0, m =0;
for(int i =0; i< s.size(); i++)
{
if(i ==0 || s[i-1] !=s[i])
{
res += total -m;
total =m =cost[i];
}
else
{
total += cost[i];
m =max(m, cost[i]);
}
}
res += total -m;
return res;
}
};
|
1582. Special Positions in a Binary Matrix
c++解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution {
public:
// 如果 [i, j] 是一个special case，那么该行和该列相加起来都是 1
int numSpecial(vector<vector<int>>& mat) {
int rows =mat.size(), cols =mat[0].size();
vector<int> a(rows, 0), b(cols, 0);
for(int i =0 ; i< rows; i++)
for(int j =0 ; j< cols ; j++)
{
a[i] += mat[i][j];
b[j] += mat[i][j];
}
int res =0;
for(int i =0; i< rows; i++)
for(int j =0 ; j<cols ; j++)
if(mat[i][j] ==1 && mat[i][j] == a[i] && mat[i][j] == b[j])
res +=1;
return res;
}
};
|
python 解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution:
def numSpecial(self, mat: List[List[int]]) -> int:
rows, cols =len(mat), len(mat[0])
a, b = [0] * rows, [0] * cols
# a、b 是按照行、列统计所有数字，所以两个是相同的内容，但是不同的计数方式
for i in range(rows):
for j in range(cols):
a[i] += mat[i][j]
b[j] += mat[i][j]
res =0
for i in range(rows):
for j in range(cols):
if mat[i][j] ==1 and mat[i][j] ==a[i] and mat[i][j] ==b[j]:
res += 1
return res
|
378. 有序矩阵中第 K 小的元素
(1) 思路一：暴力解法
python 解法， $n^2log(n)$ 时间复杂度。 这种是最差的解法
1
2
3
4
5
6
7
8
|
class Solution:
# 因为这个 n 数据范围是 300，所以
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
lst =[]
for row in matrix:
lst.extend(row)
lst.sort()
return lst[k -1]
|
(2) 大根堆、小根堆解法
数字中第 K 小的元素 对应的是 K 个元素的大根（顶）堆的堆顶元素（这里有点绕，可以多想想）。
遍历整个数组，如果当前元素小于堆顶元素，那么替换掉；如果堆顶的元素不足 k 个，那么加上。 c++ 中使用 priority_queue 默认表示大根堆。
（大根堆的顶层是相对底层要大的元素）
时间复杂度： $n^2logk$，空间复杂度 $k$
该解法没有利用行有序或者列有序的信息
c++ 中默认是大根堆
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
public:
int kthSmallest(vector<vector<int>>& matrix, int k) {
int n =matrix.size();
priority_queue<int> q;
for(int i =0; i< n; i++)
for(int j =0 ; j< n; j++)
{
if (q.size() < k)
q.push(matrix[i][j]);
else
if(matrix[i][j] < q.top())
{
q.pop();
q.push(matrix[i][j]);
}
}
return q.top();
}
};
|
python 解法, python 中默认是小根堆， $O(nlogn)$
1
2
3
4
5
6
7
8
9
10
11
|
class Solution:
# 学习记忆 python 中使用小根堆
# 思路很简单，建立一个小根堆，然后返回第 k 个元素
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
heap =[]
for i in range(len(matrix)):
for j in range(len(matrix[0])):
heapq.heappush(heap, matrix[i][j])
for _ in range(k):
res = heapq.heappop(heap)
return res
|
（3）二分解法
二分搜索的题型分为两种，一种是索引二分（在有序数组中的二分查找），一种是值域二分（可行解在一个区间内查找，判断这个解是否成立）。该题目最小结是左上角的 $matrix[0][0]$， 最大解是右下角 $matrix[n-1][n-1]$，那么第
c++ 解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
class Solution {
public:
// 二分搜索的题型有两种：一种是索引二分（在有序数组中二分查找）；一种是值域二分（可行解在一个区间内查找）。
// 这个题目是典型的值域二分问题，最小值是左上角，最大值是右下角
int search(vector<vector<int>> & matrix, int target, int n)
{
int count =0;
int row =n -1, col =0;
while(row >=0 && col <n)
{
if(matrix[row][col] <= target)
{count += row +1;
col +=1;
}
else
row -= 1;
}
return count;
}
int kthSmallest(vector<vector<int>>& matrix, int k) {
int n =matrix.size();
int left =matrix[0][0], right = matrix[n -1][n -1];
while(left < right)
{
int mid =left +right >>1;
//cout << mid<< endl;
int count = search(matrix, mid, n);
if(count >=k)
right =mid;
else
left =mid +1;
}
return left;
}
};
|
python 解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
class Solution:
def search(self, matrix, target, n):
row, col = n -1, 0
count =0
while row >= 0 and col <n:
if matrix[row][col] <= target:
count += row +1
col += 1
else:
row -= 1
return count
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
n =len(matrix)
left, right = matrix[0][0], matrix[n-1][n-1]
while left< right:
mid = left + right >>1
count = self.search(matrix, mid, n)
if count >= k:
right =mid
else:
left =mid +1
return left
|
144. 二叉树的前序遍历
二叉树的非递归遍历
c++ 解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
if(root == NULL) return vector<int>{};
stack<TreeNode*> stk;
vector<int> res;
stk.push(root);
while( !stk.empty())
{
TreeNode* t = stk.top();
if(t)
{
res.push_back(t -> val);
stk.pop();
if(t ->right)
stk.push(t-> right);
if(t ->left)
stk.push(t-> left);
}
}
return res;
}
};
|
python 解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
if not root: return []
stk =[]
res =[]
stk.append(root)
while stk:
t =stk.pop()
if t:
res.append(t.val)
if t.right:
stk.append(t.right)
if t.left:
stk.append(t.left)
return res
|
最优的解法是 $O(n)$，使用堆排序是 $O(nlogn)$
python 解法
1
2
3
4
5
6
7
8
9
10
11
|
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
lst =[]
# python 中默认是小根堆
for num in nums:
heapq.heappush(lst, -1 *num)
while k:
val = heapq.heappop(lst)
k -=1
return -val
|
这个是python 解法，时间复杂度是$O(n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
class Solution:
# 可以参考快排的思路，如果 key 值最后的 index 是 k，那么返回该值，以这个index 数值作为 二分的依据
def quick_sort(self,nums, l, r):
key = nums[r]
left, right =l, r
while l <r:
while l<r and nums[l] >= key: l +=1
nums[r] = nums[l]
while l <r and nums[r] <=key: r -=1
nums[l] = nums[r]
nums[r] =key
return l
def findKthLargest(self, nums: List[int], k: int) -> int:
if len(nums) ==1 and k ==1: return nums[0]
l, r =0, len(nums) -1
while l <=r:
index = self.quick_sort(nums, l, r)
if index == k-1:
return nums[index]
elif index > k -1:
r = index -1
else:
l = index +1
return -1
|
python 解法，这种解法是无法考察指针的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if not head: return head
lst =[]
while head:
lst.append(head.val)
head = head.next
lst =lst[::-1]
head =ListNode(lst[0])
dummy =head
for i in range(1, len(lst)):
node =ListNode(lst[i])
head.next =node
head =head.next
return dummy
|
python 正规的解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
pre =None
cur =head
while cur:
nex =cur.next
cur.next =pre
pre =cur
cur =nex
return pre
|
c++ 解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
// 一般 linkedlist 有三种类型：三个指针（这道题）；使用 dummy 指针
ListNode* reverseList(ListNode* head) {
ListNode* pre =nullptr;
ListNode* cur =head;
while(cur)
{
ListNode* next = cur ->next;
cur->next =pre;
pre =cur, cur =next;
}
return pre;
}
};
|
python 解法
因为 $n = 10^4$ ，所以时间复杂度 $nlogn$ 是可以满足要求的。 python 中对元组进行排序，那么首先是按照第一个元素有序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution:
#
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
if not intervals: return []
intervals.sort()
#print(intervals)
res =[]
a, b = intervals[0]
for i in range(1, len(intervals)):
a1, b1 = intervals[i]
if a1 <= b:
b = max(b, b1)
else:
res.append([a, b])
a, b = a1,b1
res.append([a, b])
return res
|
c++ 解法
sort() 函数默认首先按照第一个元素进行增排序，如果第一个相同的话，按照第二个元素进行增排序。
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 {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if(intervals.empty()) return vector<vector<int>>{};
sort(intervals.begin(), intervals.end());
int a = intervals[0][0], b =intervals[0][1];
vector<vector<int>> res;
for(int i =1; i< intervals.size(); i ++)
{
int a1 =intervals[i][0], b1 =intervals[i][1];
if(a1 <=b)
b =max(b, b1);
else
{
res.push_back(vector<int>{a, b});
a =a1, b =b1;
}
}
res.push_back(vector<int>{a, b});
return res;
}
};
|
这个和上面题目的要求是不一样的，上面是合并，这里是说得到不重合的区间的合集。
python 解法
以下时间复杂度是 $O(nlogn)$， 这种解法不是最优的，因为没有用到原先的 interval 是有序的这条信息。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
if not intervals: return [newInterval]
intervals.append(newInterval)
intervals.sort()
n =len(intervals)
if n ==1: return intervals
a, b = intervals[0][0], intervals[0][1]
res =[]
for i in range(1, n):
a1,b1 =intervals[i][0], intervals[i][1]
if a1 <=b:
b =max(b, b1)
else:
res.append([a, b])
a, b = a1, b1
res.append([a, b])
return res
|
Python 解法： 时间复杂度 $O(n)$。分为两个步骤，第一步骤是合并数组，第二步骤是合并重叠部分。第一步可以进一步优化成 $logn $的时间复杂度，但是总的时间复杂度还是不变的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
if not intervals: return [newInterval]
n =len(intervals)
t =[]
i =0
while i <n:
if intervals[i][0] < newInterval[0] or (intervals[i][0] == newInterval[0] and intervals[i][1] < newInterval[1]):
t.append(intervals[i])
i +=1
else:
break
t.append(newInterval)
while i <n:
t.append(intervals[i])
i +=1
res =[]
a, b = t[0][0], t[0][1]
for i in range(1, len(t)):
a1, b1 = t[i][0], t[i][1]
if a1 <= b:
b =max(b, b1)
else:
res.append([a, b])
a, b =a1, b1
res.append([a, b])
return res
|
给出一个从逻辑上处理的问题。在遍历的过程中，将 newInterval 进行插入。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
int n =intervals.size();
bool is_in =false;
vector<vector<int>> res;
for(auto item : intervals)
{
if( newInterval[1] < item[0])
{
if(!is_in)
{
res.push_back(newInterval);
is_in =true;
}
res.push_back(item);
}
else if ( item[1] < newInterval[0])
res.push_back(item);
else
{
newInterval[0] =min(item[0], newInterval[0]);
newInterval[1] =max(item[1], newInterval[1]);
//res.push_back(item);
}
}
if(!is_in)
res.push_back(newInterval);
return res;
}
};
|
c++ 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
public:
// 算法核心思想： 需要维护最大值pos,和最小值neg，如果当前 nums[i] >0，那么最大值就是pos * nums[i]， 如果 nums[i] <0，那么
int maxProduct(vector<int>& nums) {
int maxv =nums[0], minv =nums[0];
int res =nums[0];
for(int i =1; i< nums.size() ; i++)
{
int t1= maxv, t2 =minv;
maxv =max(nums[i], max(t1 * nums[i], t2 * nums[i]));
minv =min(nums[i], min(t1 * nums[i], t2* nums[i]));
res =max(res, maxv);
}
return res;
}
};
|
python 代码
1
2
3
4
5
6
7
8
9
|
class Solution:
def maxProduct(self, nums: List[int]) -> int:
maxv, minv, res =nums[0], nums[0], nums[0]
for i in range(1, len(nums)):
t1, t2 =maxv, minv
maxv =max(nums[i], max(t1 * nums[i], t2 * nums[i]))
minv =min(nums[i], min(t1 * nums[i], t2 * nums[i]))
res =max(res, maxv)
return res
|
首先这里指的是单链表。本身对题意就没有把握好。如果单链表相交，那么之后的结点都是相交的，不存在先相交，然后再分离的情况。
然后再想怎么做
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def helper(self, p1, p2, dif):
while dif:
p1 =p1.next
dif -=1
while p1 and p2:
if p1 ==p2: return p1
p1 =p1.next
p2 =p2.next
return None
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
head =headA
lena =0
while head:
lena +=1
head =head.next
lenb =0
head =headB
while head:
lenb +=1
head =head.next
if lena> lenb:
dif = lena -lenb
return self.helper(headA, headB, dif)
else:
dif =lenb - lena
return self.helper(headB, headA, dif)
|
# 需要提供两种解法，一种是递归；一种是动态规划。在解答的时候，优先考虑动态规划
# 下面是递归的解答，但还是有错
1
2
3
4
5
6
7
8
9
10
|
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
mincoins =amount
if amount in coins:
return 1
else:
for i in [c for c in coins if c <= amount]:
numcoins = 1 + self.coinChange(coins, amount -i)
mincoins =min(mincoins, numcoins)
return mincoins
|
动态规划
时间复杂度是 $O(mn)$, 其中 $m$ 表示 len(coins) , $n$ 表示 $amount$。
背包问题，相同的体积，使用最少的物品可以装满。注意枚举物体重点的时候，是从小到大进行枚举（j =coins[i] ）
c++ 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int INF =10000000;
vector<int> f(amount +1, INF);
f[0] = 0;
for(int i =0; i< coins.size() ; i++)
{
for(int j = coins[i]; j <= amount; j ++)
f[j] =min(f[j], f[j -coins[i]] +1);
}
if(f[amount] ==INF)
f[amount] =-1;
return f[amount];
}
};
|
python 代码
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
INF =1000000
# f[j] 表示金额为 j 时候需要使用的最少的数量
f =[INF] *(amount +1)
f[0] =0
for c in coins:
for j in range(c, amount+1):
f[j] =min(f[j], f[j - c] +1)
if f[amount] == INF:
f[amount] =-1
return f[amount]
|
1
2
3
4
5
6
7
8
9
10
11
|
class Solution:
# 完全背包问题， amount 可以当做背包的总体积，coins 是单个的体积
# f[j] 表示面额为 j 时候总的方案数
def change(self, amount: int, coins: List[int]) -> int:
f =[0] * (amount +1)
f[0] =1
for c in coins:
for j in range(c, amount+1):
f[j] += f[j -c]
return f[amount]
|
当二分排序时候，数组本身就完成了排序，所以直接返回数组就行，不必使用在 quick_sort 的时候返回结果。
时间复杂度是 $O(n)$，证明很繁琐。具体证明可以参考《算法导论》第 9 章第 2 小节。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
class Solution:
def quick_sort(self,arr, l, r):
key = arr[l]
left, right =l, r
while l<r:
while l <r and arr[r] >=key:
r -= 1
arr[l] = arr[r]
while l <r and arr[l] <=key:
l +=1
arr[r] = arr[l]
arr[l] =key
return l
def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
l, r =0, len(arr) -1
while l <r:
index =self.quick_sort(arr, l, r)
if index ==k:
break
elif index <k:
l = index +1
else:
r =index
return arr[:k]
|
还有一种思路：堆。 这个是 $nlogn$ 的算法，可以优化成 $nlogk$ 的时间复杂度。
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution:
def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
# 时间复杂度是 nlogk ，
import heapq
lst =[]
for num in arr:
heapq.heappush(lst, num)
res =[]
while k:
res.append(heapq.heappop(lst))
k -=1
return res
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
square = [num* num for num in nums]
if nums[0] >=0: return square
if nums[-1] <0: return square[::-1]
index =0
for (ind, num) in enumerate(nums):
if num >=0:
index =ind
break
res =[]
i =index
j =index -1
while j >=0 and i <= len(nums) -1:
if square[j] <= square[i]:
res.append(square[j])
j -=1
else:
res.append(square[i])
i +=1
while j >=0:
res.append(square[j])
j -=1
while i <= len(nums) -1:
res.append(square[i])
i +=1
return res
|
首先需要找到分界点，按照平方进行排序，[0, ind] 是逆序，[ind, n] 是顺序。只要找到临界点就行。同时学习一下更加简洁的去书写 归并排序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
# 首先找到第一个数值为正的数字
n =len(nums)
ind =n
for i in range(n):
if nums[i] >=0:
ind = i
break
else:
nums[i] = -nums[i]
# ind 是正序和逆序的分割点
i, j = ind -1, ind
res =[]
while i >=0 or j < n:
if i<0 :
res.append(nums[j])
j +=1
elif j == n:
res.append(nums[i])
i -=1
else:
if nums[i] < nums[j]:
res.append(nums[i])
i -=1
else:
res.append(nums[j])
j +=1
return [ x*x for x in res]
|
c++ 代码。当指数是偶数时候，不断整除 2 最后是1，使用 res= res*p 可以得到最后的结果；是一个快速幂的 结果。注意 c++ 中定义别名 #define LL long long 最后是没有分号的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
public:
#define LL long long
double myPow(double x, int n) {
double res =1, p =x;
LL t =abs(n);
while(t)
{
if(t&1 ==1)
res =res * p;
p = p *p;
t >>= 1;
}
return n>0? res: 1.0/res;
}
};
|
python 代码
1
2
3
4
5
6
7
8
9
10
|
class Solution:
def myPow(self, x: float, n: int) -> float:
res =1
p , t =x, abs(n)
while t:
if t&1 ==1: res =res *p
p = p *p
t >>= 1
return res if n >0 else 1.0/ res
|
二分算法有两个版本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
// 一般使用的是 l =mid + 1 这个版本
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid; // check()判断mid是否满足性质
else l = mid + 1;
}
return l;
}
// 在求解平方根的函数中也可以使用 这个版本
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
|
判断是否是一个平衡二叉树。
python 版本，根据定义去书写，dfs 的思路，如果左右子树有不符合条件的，那么 return 为 -1。否则整个树的高度是当前左右子树高度 +1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
def height(root):
if not root: return 0
h_left = height(root.left)
h_right= height(root.right)
if h_left ==-1 or h_right == -1 or abs(h_left -h_right) >1:
return -1
else:
return max(h_right, h_left) +1
return height(root) >= 0
|
c++ 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int dfs(TreeNode* root)
{
if(root ==nullptr) return 0;
int h_left = dfs(root -> left), h_right = dfs(root ->right);
if(h_left == -1 || h_right ==-1 || abs(h_right - h_left) >1)
return -1;
return max(h_left, h_right) +1;
}
bool isBalanced(TreeNode* root) {
return dfs(root) >=0;
}
};
|
大数相乘，求解的时候，需要先求余数，然后取整数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
class Solution:
def addStrings(self, a: str, b: str) -> str:
aa =list(a)[::-1]
bb = list(b)[::-1]
len1, len2 =len(aa), len(bb)
i,j =0, 0
t=0
res =[]
while i <len1 and j < len2:
t = int(aa[i]) + int(bb[j]) +t
r = t%10 # 这两个步骤不能颠倒
t = t//10
res.append(r)
i +=1
j +=1
while i <len1:
t = int(aa[i]) +t
r = t %10
t = t//10
res.append(r)
i += 1
while j <len2:
t = int(bb[j]) +t
r = t %10
t = t//10
res.append(r)
j += 1
if t >0: res.append(t)
res = res[::-1]
res =[str(item) for item in res]
return ''.join(res)
|
- 1486. XOR Operation in an Array
$O(n)$ 的时间复杂度，如果考察异或操作，那么多和二进制有关。因为数据范围是$10^3$，所以直接暴力求解就ok了。
（也可以归结为模拟题）
python解法
1
2
3
4
5
6
7
|
class Solution:
def xorOperation(self, n: int, start: int) -> int:
res =0
for i in range(n):
t = start + 2*i
res =res ^ (t)
return res
|
c++ 解法
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution {
public:
int xorOperation(int n, int start) {
int res =0;
for(int i =0; i< n; i++)
{
int t =i *2 + start;
res = res^ t;
}
return res;
}
};
|
- 1487. Making File Names Unique
数据范围 $5*10^4$，这意味着需要是$O(n)$ 的做法。使用dictionary
题解：
For while 是非常常见的结构，for 是有序循环，while 是条件循环。
暴力求解（c++）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class Solution {
public:
vector<string> getFolderNames(vector<string>& names) {
unordered_set<string> dict;
vector<string> res;
for(auto name: names)
{
int i =0;
string suf;
while(dict.count(name+suf))
{
i ++;
suf ='('+to_string(i) +')';
}
dict.insert(name+suf);
res.push_back(name+suf);
}
return res;
}
};
|
时间复杂度分析：$N \times 5\times 10^4$ ，$N$ 是很大的常数，所以可能 time out。
优化的点： 对于同一个文件名，如果之前已经查找过，那么不必从头开始查找。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
class Solution {
public:
vector<string> getFolderNames(vector<string>& names) {
unordered_set<string> dict;
unordered_map<string, int> cnt;
vector<string> res;
for(auto name: names)
{
int i =0;
string suf;
if (cnt[name] ) i =cnt[name];
# 这里能够减少时间复杂度
while(dict.count(name+suf))
{
i ++;
suf ='('+to_string(i) +')';
}
cnt[name] =i;
dict.insert(name+suf);
res.push_back(name+suf);
}
return res;
}
};
|
python 版本的code （不仅是算法思路，还需要算法的实现）
下面的解法是正确的，但是 time out （暴力解法）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution:
def getFolderNames(self, names: List[str]) -> List[str]:
from collections import Counter
dic =Counter()
dic_ =Counter()
res =[]
for name in names:
i = 0
suf =""
# 这里的 dic 更像是一种 set() 判别是否存在，而非真正dictionary 的功能
# 每次i 的变化都是从0开始 +1，实际上可以使用dic 保存一个最大值
while dic.get(name+suf, 0):
i +=1
suf ="({})".format(i)
dic[name+suf] =1
res.append(name+suf)
return res
|
经过上述思路优化的做法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class Solution:
def getFolderNames(self, names: List[str]) -> List[str]:
from collections import Counter
dic =Counter()
dic_ =Counter()
res =[]
for name in names:
i = 0
suf =""
# 这里的 dic 更像是一种 set() 判别是否存在，而非真正dictionary 的功能
# 每次i 的变化都是从0开始 +1，实际上可以使用dic 保存一个最大值
if dic_.get(name, 0):i =dic_.get(name)
while dic.get(name+suf, 0):
i +=1
suf ="({})".format(i)
dic[name+suf] =1
dic_[name] =i
res.append(name+suf)
return res
|
将暴力解法写出来，然后去优化，也是一种很基本的解题思路。
1475. Final Prices With a Special Discount in a Shop
时间复杂度是$O(n^2)$
c++ 解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution {
public:
// 能想到的算法是 $O(n^2)$，
// n =500,所以暴力求解不是最优的，但是能过的
vector<int> finalPrices(vector<int>& prices) {
int n =prices.size();
vector<int> res(n, 0);
int j ;
for(int i =0; i<n-1;i ++ )
{
j =i +1;
while(j <n && prices[j] > prices[i])
j ++;
if (j !=n) res[i] =prices[i] -prices[j];
else
res[i] =prices[i];
}
res[n-1] =prices[n-1];
return res;
}
};
|
python解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution:
def finalPrices(self, prices: List[int]) -> List[int]:
# 暴力求解一波
res =[]
n =len(prices)
for i in range(0, n-1):
j =i +1
while j < n and prices[j] > prices[i]:
j +=1
if j !=n:
res.append(prices[i] -prices[j])
else:
res.append(prices[i])
res.append(prices[-1])
return res
|
优化时间复杂度
寻找最近一个比他小的数字，使用单调栈的思想。
c++ 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution {
public:
// 寻找距离最近的比当前数小的数字
vector<int> finalPrices(vector<int>& prices) {
stack<int> stk;
vector<int> res;
int n =prices.size();
for(int i =n-1; i>=0; i--)
{
int t =prices[i];
while(stk.size() && t < stk.top()) stk.pop();
if(stk.size() && stk.top() <= t) res.push_back(t -stk.top());
else
res.push_back(t);
while(stk.size() && t ==stk.top()) stk.pop();
stk.push(t);
}
return vector<int>{res.rbegin(), res.rend()};
}
};
|
python 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution:
# 距离最近的小数，单调栈思想，最后的时间复杂度是$O(n)$
def finalPrices(self, prices: List[int]) -> List[int]:
res =[]
stk =[]
n =len(prices)
for i in range(n-1, -1, -1):
t =prices[i]
while stk and stk[-1] > t:
stk.pop()
if stk and stk[-1] <= t:
res.append(t-stk[-1])
else:
res.append(t)
stk.append(t)
return res[::-1]
|
1476. Subrectangle Queries
因为数据范围是 $n=100$，那么使用暴力求解就能解决问题。
思路一
python实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class SubrectangleQueries:
def __init__(self, rectangle: List[List[int]]):
self.query =rectangle
def updateSubrectangle(self, row1: int, col1: int, row2: int, col2: int, newValue: int) -> None:
for i in range(row1, row2+1):
for j in range(col1, col2+1):
self.query[i][j] =newValue
def getValue(self, row: int, col: int) -> int:
return self.query[row][col]
# Your SubrectangleQueries object will be instantiated and called as such:
# obj = SubrectangleQueries(rectangle)
# obj.updateSubrectangle(row1,col1,row2,col2,newValue)
# param_2 = obj.getValue(row,col)
|
c++ 实现
多注意一下c++ 中双重数组的声明和初始化。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class SubrectangleQueries {
public:
vector<vector<int>> rect;
SubrectangleQueries(vector<vector<int>>& rectangle) {
rect =rectangle;
}
void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
for(int i =row1; i<= row2; i ++)
for(int j =col1; j<= col2; j++)
rect[i][j] =newValue;
}
int getValue(int row, int col) {
return rect[row][col];
}
};
|
思路一在 updateSubrectangle 比较耗时。还有一种思路：维护一个更新表，将用户的操作以key-value 的方式保存起来。
python实现代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class SubrectangleQueries:
# 第二种思路：记录update过程，注意 stk中存储的 [(), ()]修改记录，如果修改记录中没有，那么从原来的rectangle中找找
# python 中如果不再修改，那么是() 要不 [] 更优化
def __init__(self, rectangle: List[List[int]]):
self.update = []
self.query =rectangle
def updateSubrectangle(self, row1: int, col1: int, row2: int, col2: int, newValue: int) -> None:
self.stk.update((row1, col1, row2, col2, newValue))
def getValue(self, row: int, col: int) -> int:
n =len(self.update)
for i in range(n-1, -1, -1):
if row >= self.update[i][0] and row <= self.update[i][2] and col >= self.update[i][1] and col<= self.update[i][3]:
return self.update[i][-1]
return self.query[row][col]
|
更加简洁的写法
优化了判断函数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class SubrectangleQueries:
# 第二种思路：记录update过程
def __init__(self, rectangle: List[List[int]]):
self.update = []
self.query =rectangle
def updateSubrectangle(self, row1: int, col1: int, row2: int, col2: int, newValue: int) -> None:
self.update.append((row1, col1, row2, col2, newValue))
def getValue(self, row: int, col: int) -> int:
n =len(self.update)
def inside(x, y, R):
return R[0] <=x <= R[2] and R[1] <= y<=R[3]
for i in range(len(self.update) -1, -1, -1):
if inside(row, col, self.update[i][:4]):
return self.update[i][-1]
return self.query[row][col]
|
c++ 实现上述思路
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class SubrectangleQueries {
public:
vector<vector<int>> query;
//stack<int> stk; // 需要使用二维列表实现
vector<vector<int>> update;
SubrectangleQueries(vector<vector<int>>& rectangle) {
query =rectangle;
}
void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
update.push_back({row1, col1, row2, col2, newValue}); // c++ 中这属于简化之后的构造函数
}
int getValue(int row, int col) {
for(int i =update.size()-1; i >=0 ; i--)
{
if (row >= update[i][0] && row <= update[i][2] && col >= update[i][1] && col<= update[i][3])
return udpate[i][4];
}
return query[row][col];
}
};
|
- Path Crossing
判断路线是否相交
分析：数据范围是$10^4$，那么应该是$nlogn$的做法（最多是$n^2$） 的做法？属于模拟题？
正确的解法： 使用dictionary 保存走过的点的坐标，如果发现已经走过，那么 return true否则 return false
c++ 解答
注意set.find() 和set.count() 对应的判断条件。使用set 就可以表示无修改的dictionary。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution {
public:
bool isPathCrossing(string path) {
unordered_set<string> dict;
dict.insert("00");
int x=0, y=0;
for(auto ch: path)
{
if (ch=='N') y +=1;
else if (ch =='E') x +=1;
else if (ch =='S') y -=1;
else if (ch =='W') x -=1;
string t =to_string(x)+to_string(y);
if (dict.count(t) ) return true;
//if (dict.find(t) != dict.end()) return true;
dict.insert(t);
}
return false;
}
};
|
python 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution:
def isPathCrossing(self, path: str) -> bool:
dic =set()
dic.add("00")
x, y =0, 0
for ch in path:
if ch =='N': y +=1
elif ch =='E': x +=1
elif ch =='S': y -=1
elif ch =='W': x -=1
t =str(x)+str(y)
if t in dic: return True
dic.add(t)
return False
|
1497. Check If Array Pairs Are Divisible by k
解题思路：数学题。数字是否可以被k 整除转换为余数问题。如果余数为0，那么可以被其整除；如果两个数字之和可以被整除，那么余数之和相加为k。
c++ 解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution {
public:
bool canArrange(vector<int>& arr, int k) {
vector<int> r(k, 0);
for(auto num: arr)
r[(num%k +k)%k] +=1;
if(r[0] %2 ==1) return false;
for(int i =1; i<k ;i++)
if(r[i] != r[k-i]) return false;
return true;
}
};
|
最后的for 循环还可以优化成双指针的形式。
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 {
public:
bool canArrange(vector<int>& arr, int k) {
vector<int> r(k, 0);
for(auto num: arr)
r[(num%k +k)%k] +=1;
if(r[0] %2 ==1) return false;
for(int i =1, j =k-1; i<j; i++, j --)
if(i ==j)
{
if(r[i] %2 !=0) return false;
}
else
{
if(r[i] != r[j] ) return false;
}
return true;
}
};
|
python 解法 （按照第二种写法）
1
2
3
4
5
6
7
8
|
class Solution:
def canArrange(self, arr: List[int], k: int) -> bool:
r = [0] *k
for num in arr:
r[(num%k +k) %k] +=1
return r[0]%2 ==0 and all( r[i] ==r[k-i] for i in range(1,k//2+1))
|
1498. Number of Subsequences That Satisfy the Given Sum Condition
主要是思路问题，查看最后给出的例子可以发现，当序列中任一两数之和满足条件，那么是可以使用数学公式的。所以可以先排序，然后使用二分去查找合适的区间。最后的时间复杂度是 $O(nlogn)$。
任意序列（sequence） 和任意区间的区别：前者可以是非连续，后者是连续的。
python 求解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution:
def numSubseq(self, nums: List[int], target: int) -> int:
# 如果是 subarry 可以使用预处理找到每个区间的 最大最小值？ 但是这个是 subsequence，没有什么思路
# n =10^5，算法复杂度一般在nlogn 或者 O(n) ，但还是没有思路
MOD = 1000000000 +7
nums.sort()
res =0
l, r = 0, len(nums) -1
while l <= r:
if nums[l] +nums[r] > target: r -=1
else:
res =(res+ pow(2, r-l, MOD) ) % MOD
l +=1
return res
|
python 中的一个函数 pow(x, y, z)，其中 x is the base, y is the exponent, z (optional) is used for modulus.
(x**y) % z
c++解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
class Solution {
public:
int numSubseq(vector<int>& nums, int target) {
int res =0, n =nums.size();
vector<int> pow(n,1); // 这个就是一个预处理
int MOD =1000000000 +7;
for(int i =1; i <n; i++)
pow[i] =(pow[i-1] *2) %MOD;
int l =0, r =n-1;
sort(nums.begin(), nums.end());
while (l <= r)
{
if ( nums[l] + nums[r] > target)
r -=1;
else
{
res =( res + pow[r-l] %MOD )% MOD;
l +=1;
}
}
return res;
}
};
|
1491. Average Salary Excluding the Minimum and Maximum Salary
题目很简单，简单的遍历一下就可以
c++ 实现代码
（需要记住的是INT_MAX和 INT_MIN 两个常量）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution {
public:
double average(vector<int>& salary) {
double res =0.0;
int min_v =INT_MAX, max_v =INT_MIN;
for(auto num : salary)
{
res += num;
min_v = min(min_v, num);
max_v =max(max_v, num);
}
return (res -min_v -max_v )/(salary.size() -2);
}
};
|
python实现代码
1
2
3
4
5
6
7
8
9
10
|
class Solution:
def average(self, salary: List[int]) -> float:
min_v, max_v = float("inf"), -float("inf")
res =0
for num in salary:
res += num
min_v =min(min_v, num)
max_v =max(max_v, num)
return (res -min_v -max_v)*1.0/(len(salary) -2)
|
1492. The kth Factor of n
数据量是 1000，那么使用暴力枚举就可以： 先找出所有的除数，然后得到。时间复杂度是$O(n)$。
python 解法
1
2
3
4
5
6
7
8
9
10
|
class Solution:
def kthFactor(self, n: int, k: int) -> int:
res=[]
for i in range(1, n+1):
if n%i ==0:
res.append(i)
if k <= len(res):
return res[k-1];
else:
return -1
|
c++ 解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution {
public:
int kthFactor(int n, int k) {
vector<int> res;
for(int i =1; i<=n; i++)
{
if( n%i ==0) res.push_back(i);
}
if (res.size() >=k)
return res[k-1];
else
return -1;
}
};
|
上述解法并没有利用到左右两个数字是“对称”的信息。所以可以从枚举每个数字到枚举每个整除数。优化一下时间复杂度 $O(\sqrt(n))$。
c++ 解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
class Solution {
public:
int kthFactor(int n, int k) {
vector<int> beg, end;
int i =1;
while (i *i <=n)
{
if (n%i ==0)
{
beg.push_back(i);
if (i *i !=n)
end.push_back(n/i);
}
i +=1;
}
if (k <= beg.size())
return beg[k-1];
else if ( k<= beg.size() +end.size())
return end[end.size() +beg.size() -k];
return -1;
}
};
|
python 解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution:
# 数据量是 1000，那么使用暴力枚举就可以
# 先找出所有的除数，然后得到
def kthFactor(self, n: int, k: int) -> int:
beg, end =[], []
i =1
while i *i <= n:
if n%i ==0:
beg.append(i)
if i *i != n:
end.append(n//i)
i +=1
if k <= len(beg):
return beg[k-1]
elif k <= len(beg) +len(end):
return end[len(beg) +len(end) -k]
return -1
|
1503. Last Moment Before All Ants Fall Out of a Plank
python 实现
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution:
# 这个比较难的抽象出来模型，没有什么思路
# 是模拟题。对于向左走的 ant，所需要的时间是其初始位置；对于向右走的ant，所需要的时间是其当前的位置。然后求解所有可能的最大值
# 算法时间复杂度是 O(n)
def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:
res = -1
for item in left:
res =max(res, item)
for item in right:
res =max(res, n -item)
return res
|
c++ 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution {
public:
int getLastMoment(int n, vector<int>& left, vector<int>& right) {
int res =-1;
for(auto item: left)
res =max(res, item);
for(auto item: right)
res =max(res, n -item);
return res;
}
};
|
1504. Count Submatrices With All Ones
因为数据范围是 150，那么可以使用 $n^3$ 的做法；当然是可以使用单调栈进行优化，然后时间复杂度是 $n^2$。判断是否可以使用单调栈，问题中是否包含这寻找左侧最近的最小元素（左侧意味着已经处理过，遍历过）。
以下是单调栈优化过的。
c++ 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
class Solution {
public:
int numSubmat(vector<vector<int>>& mat) {
int rows =mat.size(), cols =mat[0].size();
// 二维vector 的书写
vector<vector<int>> f(rows, vector<int>(cols));
for(int i =0; i< rows; i++)
for(int j =0; j< cols; j++)
if(mat[i][j])
{
f[i][j] =1;
if(i) f[i][j] += f[i-1][j];
}
else
f[i][j] =0;
int res =0;
for(int i =0; i < rows; i++)
{
stack<pair<int, int>> stk;
for(int j =0; j< cols; j++)
{
int s =0;
while(stk.size() && f[i][stk.top().first] >= f[i][j]) stk.pop();
if(stk.size())
{
s += stk.top().second;
s += f[i][j] *(j - stk.top().first);
}
else
s += f[i][j] *(j+1);
stk.push({j, s});
res += s;
}
}
return res;
}
};
|
python 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
class Solution:
def numSubmat(self, mat: List[List[int]]) -> int:
res =0
rows, cols =len(mat), len(mat[0])
f = [ [0] * cols for _ in range(rows)]
for i in range(rows):
for j in range(cols):
if mat[i][j]:
f[i][j] =1
if i : f[i][j] += f[i-1][j]
for i in range(rows):
stk =[]
for j in range(cols):
s =0
while stk and f[i][stk[-1][0]] >= f[i][j]: stk.pop()
if stk:
s += stk[-1][1] # 累加之前的结果
s += (j- stk[-1][0]) * f[i][j]
else:
s += (j+1) *f[i][j]
stk.append([j, s])
res +=s
return res
|
可以写得更加紧凑
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
class Solution:
def numSubmat(self, mat: List[List[int]]) -> int:
res =0
rows, cols =len(mat), len(mat[0])
f = [ [0] * cols for _ in range(rows)]
for i in range(rows):
stk =[]
for j in range(cols):
if mat[i][j]:
f[i][j] =1
if i : f[i][j] += f[i-1][j]
s =0
while stk and f[i][stk[-1][0]] >= f[i][j]: stk.pop()
if stk:
s += stk[-1][1] # 累加之前的结果
s += (j- stk[-1][0]) * f[i][j]
else:
s += (j+1) *f[i][j]
stk.append([j, s])
res +=s
return res
|
1507. Reformat Date
python 比较擅长字符串处理，下面的解法的缺点是使用了int() 转换函数；优点 是使用$ a<= char <= z$ 进行字符的判断和处理。
python解法
（下面是使用了一种更加优化的方法，没有调用python 自带的int 函数）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution:
def reformatDate(self, date: str) -> str:
mon_dic={"Jan":"01",
"Feb": "02",
"Mar": "03",
"Apr":"04",
"May" :"05",
"Jun": "06",
"Jul" : "07",
"Aug" :"08",
"Sep" : "09",
"Oct" :"10",
"Nov" : "11",
"Dec" :"12"}
# 因为字符串是符合某种规范，所以按照长度分为两类
if len(date) ==13:
return date[-4:] + '-' + mon_dic[date[-8:-5]] + '-' + date[:2]
else:
return date[-4:] + '-' +mon_dic[date[-8:-5]] + '-0'+date[0]
|
c++ 实现的时候，多使用substr() 函数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
class Solution {
public:
// c++ 中处理字符串： 合理使用substr
string reformatDate(string date) {
unordered_map<string, string> mp;
mp["Jan"] ="01";
mp["Feb"] ="02";
mp["Mar"] ="03";
mp["Apr"] ="04";
mp["May"] ="05" ;
mp["Jun"] ="06";
mp["Jul"] ="07";
mp["Aug"] ="08";
mp["Sep"] ="09";
mp["Oct"] ="10";
mp["Nov"] ="11";
mp["Dec"] ="12";
string day;
int offset ;
if(isdigit(date[1]))
{
day = date.substr(0, 2);
offset =1;
}
else
{
day = '0' +date.substr(0, 1);
offset =0;
}
string month =mp[date.substr(offset+4, 3)];
string year = date.substr(8+offset);
return year+"-" +month +"-" +day;
}
};
|
- 1508. Range Sum of Sorted Subarray Sums
python 实现（这种方式会timeout），尽管分析是可以在 $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:
# 暴力求解：1. 得到 subarry sum (n^2) 2. sort() nlogn 3. 选择 [left, right]，是O(n) 算法。 N =10^3 ，所以是可以满足条件的。
def sum_with_modu(self, arr: List[int], MOD :int) -> int:
res =0
for item in arr:
res += (item %MOD)
return res
def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
MOD =1000000000 +7
sub_sum =[]
n =len(nums)
for i in range(n+1):
for j in range(i+1, n+1):
tmp =nums[i:j]
sub_sum.append(self.sum_with_modu(tmp, MOD))
sub_sum.sort()
#print(sub_sum)
res =0
for i in range(left-1, right):
res += (sub_sum[i] %MOD)
return res
|
不要使用内置的 sum() 去计算，使用以下的代码是可以通过的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution:
def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
MOD =1000000000 +7
sums =[]
n =len(nums)
for i in range(n):
s =0
for j in range(i, n):
s += nums[j]
sums.append(s)
sums.sort()
#print(sums)
ans =0
for i in range(left-1, right):
ans += sums[i]
return ans %MOD;
|
c++ 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
class Solution {
public:
int rangeSum(vector<int>& nums, int n, int left, int right) {
const int mode =1000000007;
vector<int> sums;
for(int i =0; i< n; i ++)
{
int t =0;
for(int j =i ; j< n; j++)
{
t += nums[j];
sums.push_back(t);
}
}
sort(sums.begin(), sums.end());
long long res =0;
for(int i =left -1 ; i <= right -1; i ++)
{
res += sums[i];
}
return res %mode;
}
};
|
1509. Minimum Difference Between Largest and Smallest Value in Three Moves
其实可以在线性时间内解决，分别找出一个list 中最大的三个数字和最小的三个数字，但实现起来很复杂。
c++ 实现
1
2
3
4
5
6
7
8
9
10
11
|
class Solution {
public:
// 时间复杂度 nlogn，使用排序。求解最大数和最小数之间的最小差值。一般来说可以按照贪心的思路求解，修改最大或者最小的三个数字。
// 那么有四种组合：修改最大的三个数字，修改最大两个和最小的一个，修改最大一个 和最小两个，修改最小三个，然后比较四种方案的最小值
int minDifference(vector<int>& nums) {
if (nums.size() <=4 ) return 0;
int n =nums.size();
sort(nums.begin(), nums.end());
return min( min(nums[n-4] -nums[0], nums[n-3] -nums[1]), min(nums[n-2] -nums[2], nums[n-1] -nums[3]));
}
};
|
python 实现（可以简化min 函数的书写）
1
2
3
4
5
6
|
class Solution:
def minDifference(self, nums: List[int]) -> int:
if len(nums) <= 4: return 0
n =len(nums)
nums.sort()
return min( nums[n-4] -nums[0], nums[n-3] -nums[1], nums[n-2] -nums[2], nums[n-1] -nums[3])
|
1510. Stone Game IV
LeetCode 最后一题一般都是一个模板题。（所以多积累一些）
经典的博弈论问题。必胜或者必败，不存在平局。
必胜态：能走到某一个必败态；必败态：只能走到必胜态。定义 f[i] 的状态，可能是必胜态也可能是必败态。
c++实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
public:
bool winnerSquareGame(int n) {
vector<bool> st(n+1);
st[0] =false;
for(int i =1; i<=n ; i++)
for(int j=1; j *j <=i; j++)
if ( st[i -j *j] ==false)
{
st[i] =true;
break;
}
return st[n];
}
};
|
python 实现
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution:
def winnerSquareGame(self, n: int) -> bool:
st =[ False] *(n +1)
for i in range(1,n+1):
j =1
while j *j <=i:
if st[i -j *j] == False:
st[i] =True
break
j +=1
return st[n]
|
1512. Number of Good Pairs
数据范围是 100，那么暴力求解就行。那么便是 $n^2$ 的时间复杂度。
python 解法
1
2
3
4
5
6
7
8
9
10
11
|
class Solution:
def numIdenticalPairs(self, nums: List[int]) -> int:
res =0
n =len(nums)
for i in range(0, n):
j =i +1
while j < n:
if nums[i] ==nums[j]:
res +=1
j +=1
return res
|
优化成 $nlogn$ 时间复杂度 （python 实现）
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution:
def numIdenticalPairs(self, nums: List[int]) -> int:
# 先排序，然后双指针。最后的时间复杂是 nlogn
nums.sort()
res =0
n =len(nums)
for i in range(n):
j =i +1
while j < n and nums[i] ==nums[j]:
res +=1
j += 1
return res
|
c++ 实现第二种算法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution {
public:
int numIdenticalPairs(vector<int>& nums) {
int res =0;
sort(nums.begin(), nums.end());
for(int i =0; i< nums.size(); i++)
{
int j =i +1;
while (j < nums.size() && nums[i] ==nums[j])
{
res +=1;
j ++;
}
}
return res;
}
};
|
1513. Number of Substrings With Only 1s
数据量 $O(10^5)$ ，所以可以确定是 $O(n)$ 或者 $nlogn$ 的算法。根据最后一个case 可以知道如果都是1，那么可以使用数学的方式处理，所以就是一个 for-while 循环。空间上可以不必要使用 list 保存。
python解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution:
def numSub(self, s: str) -> int:
i =0
substr =[]
MOD =1000000007
while i < len(s):
if s[i] =='1':
j =i
while j < len(s) and s[j] =='1':
j +=1
substr.append(s[i:j])
i =j+1
else:
i +=1
res =0
for sub in substr:
len_s =len(sub)
res +=( (1 +len_s) *len_s //2 %MOD )
return res
|
c++ 写法
（在Python中的 substring 也是没有必要的，因为最后参与计算的是 len(substr)）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution {
public:
// 将string 分割成单个的 substring，这些 substring全部都是1
int numSub(string s) {
const int MOD =1000000007;
int res =0;
for(int i =0; i< s.size(); i ++)
{
if (s[i] =='1')
{
int j =i ;
while (j< s.size() & s[j]=='1') j +=1;
long long n =j -i;
res +=( (n +1)* n/2 %MOD );
i =j;
}
}
return res;
}
};
|
1518. Water Bottles
模拟题的思路，需要使用到取整和取余两个知识点。
c++ 解法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution {
public:
// 这个是模拟题，每次都是取其商，然后余数是累加到下一次的结果中
int numWaterBottles(int numBottles, int numExchange) {
int res =0;
int t1, t2;
res += numBottles;
while (numBottles >= numExchange)
{
t1= (numBottles / numExchange);
t2 = numBottles % numExchange;
res += t1;
numBottles =t1 + t2;
//cout << t1<< " "<< t2<<" " << numBottles<< endl;
}
return res;
}
};
|
python 解法
(相同的思路，使用python 进行实现)
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution:
def numWaterBottles(self, numBottles: int, numExchange: int) -> int:
res =0
res += numBottles
while numBottles >= numExchange:
res += (numBottles // numExchange)
numBottles = (numBottles // numExchange) + (numBottles % numExchange)
return res
|
1519. Number of Nodes in the Sub-Tree With the Same Label
1
2
3
4
5
6
7
8
9
10
11
|
class Solution {
public:
// 数据范围是 10^5, 所以最好是 O(n) 或者 O(nlogn) 的做法
// 可以在O(n) 时间内完成，从底部开始层序遍历
// 可以复习一下 树的遍历（dfs，bfs 和层序遍历）
// 从上到下的层序遍历 可以使用 stack 实现；但是从下往上的层序遍历不会写 （这道题目并不是按照指针的方式给出了 树，而是给出了边，无向图的思路）
// 树形dp 问题
vector<int> countSubTrees(int n, vector<vector<int>>& edges, string labels) {
}
};
|
视频讲解：https://www.acwing.com/video/1507/
c++ 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
class Solution {
private:
vector<vector<int>> f;
void dfs(int u, int fa, vector<vector<int>> &g)
{
for(auto v: g[u])
{
if (v!= fa)
{
dfs(v, u, g);
for(int i =0 ; i< 26; i++)
f[u][i] += f[v][i];
}
}
}
public:
// 这个是树形dp 问题
vector<int> countSubTrees(int n, vector<vector<int>>& edges, string labels) {
vector<vector<int>> g(n);
for(const auto e: edges)
{
int a =e[0], b =e[1];
g[a].push_back(b), g[b].push_back(a);
}
f.resize(n, vector<int>(26, 0));
// 状态表示需要初始化
for(int i =0; i< n; i++)
f[i][labels[i]-'a'] ++;
dfs(0, -1, g);
vector<int> res(n);
for(int i =0 ; i< n; i++)
res[i] += f[i][labels[i] -'a'];
return res;
}
};
|
python 实现, python 中使用嵌套函数（inner function） 是很好用的，直接共享了变量。ord() 小函数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
class Solution:
# python 实现的时候有 嵌套函数的概念，所以可以好好利用一下
def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:
g =defaultdict(list)
for e in edges:
a, b =e[0], e[1]
g[a].append(b)
g[b].append(a)
# 状态转移的表示
f =[[0] *26 for _ in range(n)]
for i in range(n):
f[i][ord(labels[i]) -97] +=1
def dfs(cur, pa):
for v in g[cur]:
if v != pa:
dfs(v, cur)
for i in range(26):
f[cur][i] += f[v][i]
dfs(0, -1)
res =[0] *n
for i in range(n):
res[i] = f[i][ord(labels[i]) -97]
return res
|
中轴值 pivot
时间复杂度
递归时，每层时间复杂度为 O(n)
，但并不是都进入左右两部分递归。
仅进入一侧递归在平均情况下数组长度会减半，故时间复杂度为 n+n/2+n/4+…+1=O(n)
注意的点：
partition 函数名； r =ind -1 这个边界值是需要注意的。k 值和 index 之间 相差1. 都是细节。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
class Solution:
def partition(self,arr, l, r):
if l >r: return
key = arr[r]
while l <r:
while l <r and arr[l] >= key: l +=1
arr[r] = arr[l]
while l < r and arr[r] <= key: r -=1
arr[l] = arr[r]
arr[r] =key
return l
def findKthLargest(self, nums: List[int], k: int) -> int:
if not nums: return
l, r = 0, len(nums) -1
while l <r:
ind = self.partition(nums, l, r)
if ind < k-1:
l =ind +1
elif ind ==k-1:
break
else:
r =ind -1
return nums[k-1]
|
如果处理的是字符串问题，并且出现至少 关键词，那么可以考虑 滑动窗口。 cnt 表示满足出现数量为 k 的字母的个数， dif_cnt 不同字母出现的个数。基本的思路：枚举字符串中出现不同字母的个数，时间复杂度是$26n$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
class Solution:
def longestSubstring(self, s: str, k: int) -> int:
res =0
for i in range(1, len(set(s)) +1):
l =r = cnt = dif_cnt =0
times =[0] *26
while r < len(s):
ind = ord(s[r]) - ord('a')
times[ind] +=1
if times[ind] ==1:
dif_cnt +=1
if times[ind] ==k:
cnt +=1
r += 1
while l <r and dif_cnt >i:
ind = ord(s[l]) - ord('a')
if times[ind] ==1:
dif_cnt -= 1
if times[ind] ==k:
cnt -=1
times[ind] -=1
l +=1
if i ==dif_cnt ==cnt:
res =max(res, r -l)
return res
|