LeetCode周赛题，日常刷题笔记。
十月第二周（完成三道）
第一道完成的位于上一个文件中。
- 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
|