leetcode weekly contest 记录
leetcode第194场周赛
1486. XOR Operation in an Array
python 实现，时间和空间复杂度都是 $O(n)$, $n$ 是数组的长度
1
2
3
4
5
6
7
8
9
|
class Solution:
def xorOperation(self, n: int, start: int) -> int:
arr =[]
for i in range(n):
arr.append(start + 2*i)
res =0
for num in arr:
res ^= num
return res
|
python 实现，时间复杂度是 $O(n)$， 空间复杂度是 $O(1)$。
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 ^= t
return res
|
c++ 实现，时间复杂度是 $O(n)$ 空间复杂度是$O(1)$
1
2
3
4
5
6
7
8
9
|
class Solution {
public:
int xorOperation(int n, int start) {
int res =0;
for(int i =0; i<n; i++)
res ^= start+ i*2;
return res;
}
};
|
1487. Making File Names Unique
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 {
public:
// 思路：暴力求解。每次判断一下当前的已经新建的文件名，如果有那么进行某种操作，否则直接新建
// 这种操作 k+=1
vector<string> getFolderNames(vector<string>& names) {
unordered_set<string> hash;
vector<string> res;
for(auto name :names)
{
int k =0;
string suf;
while(hash.count(name+suf))
{
k ++;
suf ="(" +to_string(k) +")";
}
hash.insert(name+ suf);
res.push_back(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
23
24
25
26
27
28
29
|
class Solution {
public:
// 时间复杂度主要在for while 循环，那么减少while循环次数，如果之前已经枚举过，那么直接枚举下一个
// cnt map中存储的是当前已经枚举到的最大的值
vector<string> getFolderNames(vector<string>& names) {
unordered_map<string, int> cnt;
unordered_set<string> hash;
vector<string> res;
for(auto name :names)
{
int k =0;
string suf;
if(cnt[name]) k =cnt[name];
while(hash.count(name+suf))
{
k ++;
suf ="(" +to_string(k) +")";
}
cnt[name] =k;
hash.insert(name+ suf);
res.push_back(name+suf);
}
return res;
}
};
|
leetcode第28场双周赛
1475. Final Prices With a Special Discount in a Shop
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:
// 通过查看数据范围，那么是可以通过暴力的方式求解的， n^2 的时间复杂度
// 找到最近一个比他小的数字，可以使用单调栈的思路解题，这个是一个模板题， 时间复杂 O(n)
// 单调栈，栈顶元素是比后面的元素要大，建立的过程是从后往前遍历的
vector<int> finalPrices(vector<int>& prices) {
vector<int> res;
stack<int> stk;
for(int i =prices.size() -1; i >=0; i--)
{
int t =prices[i];
while(stk.size() && stk.top() > t) stk.pop();
if(stk.size() ) res.push_back(t - stk.top());
else res.push_back(t);
while(stk.size() && stk.top() ==t) stk.pop();
stk.push(t);
}
return vector<int>{res.rbegin(), res.rend()};
}
};
|
python 解法： 比较完全还原上面 c++ 的算法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution(object):
def finalPrices(self, prices):
"""
:type prices: List[int]
:rtype: List[int]
"""
# reverse for easier processing
prices = prices[::-1]
stk =[]
res =[0] *len(prices)
for (index, p) in enumerate(prices):
while stk and stk[-1] > p: stk.pop()
if stk:
res[index] = p- stk[-1]
else:
res[index] =p
stk.append(p)
return res[::-1]
|
1476. 子矩形查询
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 SubrectangleQueries {
// 一定要从解决当前问题的角度出发，当前的数据范围 500 100 100 这样是500 w，那么暴力解法是可以接受的
public:
vector<vector<int>> q;
SubrectangleQueries(vector<vector<int>>& rectangle) {
q =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++)
q[i][j] =newValue;
}
int getValue(int row, int col) {
return q[row][col];
}
};
/**
* Your SubrectangleQueries object will be instantiated and called as such:
* SubrectangleQueries* obj = new SubrectangleQueries(rectangle);
* obj->updateSubrectangle(row1,col1,row2,col2,newValue);
* int param_2 = obj->getValue(row,col);
*/
|
思路二
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 SubrectangleQueries {
public:
// 还有一种思路：维护修改记录
// 这个表示的是二维数组
vector<vector<int>> q;
vector<vector<int>> updates;
SubrectangleQueries(vector<vector<int>>& rectangle) {
q =rectangle;
}
void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
// 给出的是 某个范围的 newValue
// 这个是无脑的加入，最后会使 updates 越来越大。
updates.push_back({row1, col1, row2, col2, newValue});
}
int getValue(int row, int col) {
// 记录表 越往后面越是新的数据, 所以从后往前进行遍历
for(int i =updates.size() -1; i >=0 ; i--)
{
if (row >= updates[i][0] && row <= updates[i][2] && col >= updates[i][1] && col<= updates[i][3])
return updates[i][4];
}
return q[row][col];
}
};
/**
* Your SubrectangleQueries object will be instantiated and called as such:
* SubrectangleQueries* obj = new SubrectangleQueries(rectangle);
* obj->updateSubrectangle(row1,col1,row2,col2,newValue);
* int param_2 = obj->getValue(row,col);
*/
|
python 实现的代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class SubrectangleQueries:
def __init__(self, rectangle: List[List[int]]):
self.q =rectangle
self.updates =[]
def updateSubrectangle(self, row1: int, col1: int, row2: int, col2: int, newValue: int) -> None:
self.updates.append([row1, col1, row2, col2, newValue])
def getValue(self, row: int, col: int) -> int:
size =len(self.updates) if self.updates else 0
for i in range(size -1, -1, -1):
if row>= self.updates[i][0] and row <= self.updates[i][2] and col >= self.updates[i][1] and col <=self.updates[i][3]:
return self.updates[i][4]
return self.q[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)
|
leetcode第195场周赛
1496. Path Crossing
主要的问题：没有思路
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:
// 使用hash 表存储走过的路径，如果发现当前遍历的点在 hash表中，那么就return false。
bool isPathCrossing(string path) {
unordered_set<string> hash;
hash.insert("0.0");
int row =0, col =0;
for (char ch : path)
{
if (ch =='N') row +=1;
else if (ch =='E') col +=1;
else if(ch =='S') row -=1;
else if (ch =='W') col -=1;
string t =to_string(row) +"."+to_string(col);
if(hash.find(t) != hash.end()) return true;
hash.insert(t);
}
return false;
}
};
|
python 解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class Solution(object):
def isPathCrossing(self, path):
"""
:type path: str
:rtype: bool
"""
points =[]
points.append("00")
row, col =0, 0
for ch in path:
if ch =='N':
row +=1
elif ch =='E': col +=1
elif ch =='S': row -=1
elif ch =='W': col -=1
t =str(row)+ str(col)
if t in points:
return True
points.append(t)
return False
|
上述算法时间复杂度 $O(n)$，空间复杂度$O(n)$
1497. 检查数组对是否可以被 k 整除
自己的想法：首先需要枚举各种组合的数组对，然后判断各个数组对是否能被 k整除。
更好的想法： 整除转换为余数，如果余数为0，那么就可以被整除。
题意： 判断一个数组中的数组对是否可以被 k 整除。可以任意组成一个数组对。
思路： 整除问题转换成余数问题，如果余数为0，那么可以被整除。如果两个数字组成的和可以被整除，那么这两个数的余数是$i$ 和$k-i$，其中$k$ 是这数字.
Note: the elements in arr can be negative, therefore in Java the remainder may be negative too; In order to get positive remainder for any element a, use (a % k + k) % k;
如果一个数组中可能含有负数，那么使用 (a%k +k )%k 是可以得到余数的结果
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:
bool canArrange(vector<int>& arr, int k) {
vector<int> r(k, 0);
for(int a: arr)
r[ (a%k +k) %k] +=1;
if(r[0] %2 != 0) return false; // 这个是偶数个直接能被整除，不是说非要等于0
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
9
10
11
|
class Solution(object):
def canArrange(self, arr, k):
"""
:type arr: List[int]
:type k: int
:rtype: 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))
|
python 可以使用更加简洁的语句，all 中所有的判断，如果全部符合条件，那么return True，只有有一个False 那么return False
LeetCode 1498. 满足条件的子序列数目
分析：自己能够想到的是先排序，然后就没有思路了。忘记了不去重的进行排列组合的数学公式，hhh。
比如这里例子中：
1
2
3
4
|
Input: nums = [2,3,3,4,6,7], target = 12
Output: 61
Explanation: There are 63 non-empty subsequences, two of them don't satisfy the condition ([6,7], [7]).
Number of valid subsequences (63 - 2 = 61).
|
解题思路：
- 排序
- 双指针算法找出 两个满足 target 的两个元素，根据index 计算结果
编程 tips： 对于去余，那么凡是相加的情况下都是要取余。
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
|
class Solution {
public:
//
int numSubseq(vector<int>& nums, int target) {
const int mod =1000000007;
int n =nums.size();
sort(nums.begin(), nums.end());
vector<int> power(n);
power[0] =1;
for(int i =1; i< n; i++)
power[i] = power[i -1] * 2 %mod;
int l =0, r =n-1;
int ans =0;
while(l <=r)
{
if( nums[l] +nums[r] <= target)
{
ans = (ans + power[r-l]) %mod;
l +=1;
}
else
r -=1;
}
return ans;
}
};
|
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
|
class Solution(object):
def numSubseq(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
mod = 1000000007
nums.sort()
n =len(nums)
power =[1] * n
for i in range(1,n):
power[i] =power[i-1] * 2 % mod;
l, r =0, n-1
res =0
while l<=r:
if nums[l] +nums[r] <= target:
res = (res +power[r -l]) %mod
l +=1
else:
r -=1
return res
|
leetcode第29场双周赛
1491. Average Salary Excluding the Minimum and Maximum Salary
python 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution(object):
def average(self, salary):
"""
:type salary: List[int]
:rtype: float
"""
# python 中初始化最大和最小值
#min_s, max_s, sum_s = max(salary), min(salary), 0
min_s, max_s, sum_s =float('inf'), -float('inf'), 0
for item in salary:
if item < min_s: min_s =item
if item > max_s: max_s =item
sum_s += item
return (sum_s -min_s- max_s)*1.0/(len(salary) -2)
|
无论是在python2 还是在python3 中，都是可以使用 float('inf') 进行初始化最值的。
c++ 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution {
public:
double average(vector<int>& salary) {
int max_s =INT_MIN, min_s =INT_MAX, sum =0;
for(auto s: salary)
{
if(s > max_s) max_s =s;
if( s< min_s) min_s =s;
sum += s;
}
return (sum -max_s -min_s)*1.0 /( salary.size() -2);
}
};
|
1492. The kth Factor of n
难点：
求解数字的因数（这个应该是基本功），然后排序，找到第 k 个。
c++ 解法一： 时间复杂度大概是 $nlog(n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution {
public:
// 计算因数的时间复杂度是 O(sqrt(n)) ，这个是常识
int kthFactor(int n, int k) {
vector<int> res;
for(int i =1; i*i <=n; i++)
if( n %i ==0)
{
res.push_back(i) ;// 这个是符合因数的定义的
if( i *i != n) res.push_back(n /i); //一对因数中相对比较大的数字
}
sort(res.begin(), res.end());
if(k <= res.size()) return res[k-1];
return -1;
}
};
|
c++ 解法二： 时间复杂度是 $O(\sqrt(n))$。注意 beg 和 end 的数字 push_back 和获取的方式还是很精妙的，好好体会。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution {
public:
int kthFactor(int n, int k) {
vector<int> beg, end;
for(int i =1; i*i <= n; i++)
if( n %i ==0)
{
beg.push_back(i);
if (i *i != n) end.push_back(n/i);
}
if(k <= beg.size()) return beg[k -1];
if(k <= beg.size() + end.size()) return end[ beg.size() + end.size() -k];
return -1;
}
};
|
python 解法 (基本上就是按照 c++ 解法二进行的复写)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution:
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];
if k <= len(beg) +len(end): return end[len(beg) +len(end) -k];
return -1
|
leetcode第29场双周赛
1493. Longest Subarray of 1’s After Deleting One Element
没有思路，知道和最长子序列有关。最长子序列一般和双指针有关。
给定的是二进制数组 binary array
思路： 可以使用双指针求解，也可以使用动态规划求解（需要两个函数 $f$ 和$g$），相对来说双指针算法比较难想，比较好写。问题可以转换成最多包含一个0的最长的1的序列 。每个数字最多被访问两次，所以时间复杂度是 $O(n)$
滑动窗口是一种特殊的双指针算法
难点： 将问题转换成双指针算法。
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 longestSubarray(vector<int>& nums) {
int res =0;
int zeros =0;
for(int i =0, j =0; j < nums.size(); j++)
{
if(nums[j] ==0) zeros ++;
// [i,j] 闭区间中 0 的个数最多1
while( zeros >1 && i<= j)
{
if(nums[i] ==0) zeros -=1;
i ++;
}
res =max(res, j -i +1 -1);
}
return res;
}
};
|
python 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution:
def longestSubarray(self, nums: List[int]) -> int:
# 双指针算法，[i,j] 闭区间0的个数最多为1
res =0
n =len(nums)
i =0
zeros =0
for j in range(n):
if nums[j] ==0: zeros +=1
while i<=j and zeros >1:
if nums[i] ==0: zeros -=1
i +=1
res =max(res, j -i)
return res
|
leetcode第196场周赛
1502. Can Make Arithmetic Progression From Sequence
（看题目的时候，可以看看数据范围，根据数据范围，也能大概猜出使用什么算法是ok的）
python 解法
1
2
3
4
5
6
7
8
9
10
|
class Solution:
def canMakeArithmeticProgression(self, arr: List[int]) -> bool:
# 从数据范围可以知道，时间复杂度是$O(n^2)$或者 $O(nlogn)$ 做法
# 所以可以使用先排序，然后再判断
arr.sort()
diff =arr[0] -arr[1]
for i in range(1, len(arr)-1):
if diff != arr[i] -arr[i+1]:
return False
return True
|
c++ 解法
1
2
3
4
5
6
7
8
9
10
11
|
class Solution {
public:
bool canMakeArithmeticProgression(vector<int>& arr) {
sort(arr.begin(), arr.end());
int diff =arr[0] -arr[1];
for(int i =1; i< arr.size()-1; i++)
if (diff !=arr[i] -arr[i+1])
return false;
return true;
}
};
|
1492. The kth Factor of n
leetcode第29场双周赛 （复习）
以 $n *n $作为中点，能够被整除的数字是左右各有一个的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution:
# sqrt(n) 的时间复杂度在于，左右两个值是比较对称的
# 使用 beg 和end 两个就不用重新排序，因为是有序的
def kthFactor(self, n: int, k: int) -> int:
i =1
beg, end =[], []
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]
if k <= len(beg) +len(end):
return end[len(beg)+len(end) -k] # 在end中数字越大，但index 越小
return -1
|
1503. Last Moment Before All Ants Fall Out of a Plank
leetcode第196场周赛
模拟题。时间复杂度是 $O(n)$
c++解题思路。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution {
public:
// 场景很丰富，是一道模拟题
// 两个方向相反的蚂蚁相遇之后，方向转变，不会花销时间，如果不考虑编号实际上是没有交换（求解max 时间也是不用考虑编号的）
// 向左做的时间是 index，向右走的时间是 len -index
int getLastMoment(int n, vector<int>& left, vector<int>& right) {
int res =0;
for(auto num : left)
res =max(res, num);
for(auto num :right)
res =max(res, n-num);
return res;
}
};
|
python 解题思路
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution(object):
def getLastMoment(self, n, left, right):
"""
:type n: int
:type left: List[int]
:type right: List[int]
:rtype: int
"""
res =0
for num in left:
res =max(res, num)
for num in right:
res =max(res, n-num)
return res
|
1504. Count Submatrices With All Ones
从数据范围，可以看出 是$O(n^3)$ 做法
属于技术性问题（枚举），一定要保证不重复。
枚举的顺序：以当前的格子作为右下角进行枚举，先往左枚举宽度，同时向上枚举高度，所以是三重循环。
每个格子往上数 1 的个数，需要进行预处理得到，是$O(n^2)$ 的过程。
找到左边第一个比他小的数字：单调栈类型的模板
c++ 实现
还是看不懂呀，这个是需要多看几遍视频才能弄懂。
统计全 1 子矩形 视频教程
leetcode第30场双周赛
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
43
44
45
|
class Solution {
public:
int numSubmat(vector<vector<int>>& mat) {
int n =mat.size(), m =mat[0].size();
vector<vector<int>> f(n, vector<int>(m) );
// 预处理，f(i,j) 表示该点上面有几个连续的1
for(int i =0; i<n; i++)
for(int j =0; j< m; j++)
if(mat[i][j])
{
f[i][j] =1;
if(i ) f[i][j] += f[i-1][j];
}
int res =0;
for(int i =0; i<n; i++)
{
// 单调栈, 找到左边第一个比当前数小的数字，这个是模板题目
stack<pair<int, int>> stk; // 不仅存储index 还要存储总和
for(int j =0; j< m; j++)
{
// 如果发现栈顶元素比较大，那么就弹出
while( stk.size() && f[i][stk.top().first] >= f[i][j]) stk.pop();
// 找到了第一个比当前元素小的元素
int s =0;
if(stk.size())
{
s += stk.top().second;
s += (j -stk.top().first) * f[i][j];
}
else
s += (j +1) * f[i][j];
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
|
class Solution(object):
def numSubmat(self, dp):
"""
:type mat: List[List[int]]
:rtype: int
"""
sums, n, m = 0, len(dp), len(dp[0])
cnt = [[0]*m for _ in range(n)]
sts = [[] for _ in range(m)]
for i in range(n):
for j in range(m):
dp[i][j] += dp[i][j-1]*dp[i][j] if j > 0 else 0
while sts[j] and dp[sts[j][-1]][j] >= dp[i][j]:
sts[j].pop()
pre, precnt = -1, 0
if sts[j]:
pre, precnt = sts[j][-1], cnt[sts[j][-1]][j]
cnt[i][j] += precnt + (i-pre)*dp[i][j]
sums += cnt[i][j]
sts[j].append(i)
return sums
|
1507. 转变日期格式
字符串类的问题，使用Python 处理比 c++ 更容易一些。
python 解法
1
2
3
4
5
6
7
8
9
10
|
class Solution:
def reformatDate(self, date: str) -> str:
date =date.split()
months =["Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"]
day =int(date[0][:-2])
month =months.index(date[1]) +1
year =int(date[2])
return '{:04d}-{:02d}-{:02d}'.format(year, month, day)
|
还需要学习一下 format 的使用。（注意需要写的 int类型）
c++ 处理字符串感觉有点复杂，暂时没有写。
1508. Range Sum of Sorted Subarray Sums
c++实现。暴力枚举的方式。时间复杂度是$O(n^2 logn)$
共有 $n^2$ 个区间，所以排序的时间复杂度是 $n^2 log n^2$ ，即 $n^2 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
|
class Solution {
public:
// 先写个基本的解法，即暴力搜索
int rangeSum(vector<int>& nums, int n, int left, int right) {
const int mod =1000000007;
vector<int> sums ;
for(int i =0; i< nums.size() ; i ++)
{
int s =0;
for(int j =i ; j< nums.size() ; j++)
{
s += nums[j];
sums.push_back(s);
}
}
sort(sums.begin(), sums.end());
int res =0;
for(int i =left-1 ; i< right; i++)
res += sums[i];
return res%mod;
}
};
|
c++ 解法
时间复杂度是 $O(nlog M)$ 其中 $M$ 是一个很大的数字，但是这个时间复杂度大概还是 $nlogn$ 的。主要的思路就是 二分+ 前缀和。
将[a, b] 区间和转换成求解 [1, b] 和[1, a] 区间和的差值。
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
typedef long long LL;
typedef pair<int, LL> PIL;
const int MOD =1e9+7;
class Solution {
public:
vector<LL> s, ss;
int n ;
PIL get(LL mid)
{
int cnt =0;
LL sum =0;
for(int i =1, j =0; i<=n ; i++)
{
while(s[i] - s[j] > mid) j ++;
if( j< i)
{
cnt += i -j;
sum += s[i] * (i -j) -ss[i-1];
if(j) sum += ss[j-1];
}
}
return {cnt, sum};
}
LL f(int m)
{
LL l =0, r =ss.back();
while(l <r)
{
LL mid = l +r >> 1;
auto t =get(mid);
if(t.first >=m) r =mid;
else l =mid +1;
}
auto t =get(r);
return t.second - (t.first -m) * r;
}
int rangeSum(vector<int>& nums, int _n, int left, int right) {
n =_n ;
s.resize(n +1), ss.resize(n +1);
for(int i =1; i<=n; i++)
{
s[i] =s[i-1] + nums[i-1];
ss[i] =ss[i-1] +s[i];
}
return (f(right) -f(left -1))% MOD;
}
};
|
leetcode第30场双周赛
1509. Minimum Difference Between Largest and Smallest Value in Three Moves
c++ 解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution {
public:
// 这道题是非常具有技巧性的：通过移动三次，寻找最大和最小数字之间的差值。 最大的三个数字和最小的三个数字相互差值的最小值。
//数据范围是 10^5 那麼使用sort 函數，nlogn 的時間複雜度就是可以接受的
// 貪心的做法：從直觀上講，我們會修改最大的若干數字或者最小的若干數字
// 當修改三個數字時候，有四種選擇：最小的三个；最小的两个+最大的一个； 最小的一个+最大的两个；最大的三个
int minDifference(vector<int>& nums) {
int n =nums.size();
if(n<4) return 0;
sort(nums.begin(), nums.end() );
return min(min(nums[n-1]-nums[3], nums[n-2] -nums[2]), min(nums[n-3]-nums[1], nums[n-4]-nums[0]));
}
};
|
python 解法
1
2
3
4
5
6
7
|
class Solution:
def minDifference(self, nums: List[int]) -> int:
if len(nums) <4: return 0
n =len(nums)
nums.sort()
return min( nums[n-1] -nums[3], nums[n-2]-nums[2], nums[n-3]-nums[1], nums[n-4] -nums[0])
|
1510. Stone Game IV
python 解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution:
# 两个人都采取最优策略：这个是不太能理解的。
# 解法：如果一方拿走stone 之后，剩下的个使得对方没有办法走下去，那么这个就是最优的策略。使用动态规划的思想 f[i] 表示剩下 i个元素 是否可以达成最优策略
# 转移方程 j =1 开始枚举， j^2<= i, 如果 f[j] ==false，那么f[i] =True
# 时间复杂度 n\sqrt(n)
def winnerSquareGame(self, n: int) -> bool:
f =[False] *(n+1)
for i in range(1, n+1):
j =1
while j*j <=i:
if f[i-j*j] ==False:
f[i] = True
break
j +=1
return f[n]
|
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:
bool winnerSquareGame(int n) {
vector<bool> f(n+1);
f[0] =false;
for(int i =1; i<n+1; i++)
{
f[i] =false; //在这里进行初始化，非常nice
for(int j =1; j *j<= i; j++)
{
if(!f[i-j *j])
{
f[i] =true;
break;
}
}
}
return f[n];
}
};
|
LeetCode第197场周赛
1512. Number of Good Pairs
题解： 从数据范围中可以知道，使用 $n^2$ 的算法是没有问题的，所以可以直接暴力求解。
c++ 解法。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution {
public:
int numIdenticalPairs(vector<int>& nums) {
int n =nums.size();
int cnt =0;
for(int i =0; i<n; i++)
for(int j =i +1 ; j< n; j++)
if (nums[i] ==nums[j])
cnt +=1;
return cnt;
}
};
|
但还有更优的做法，可以实现 $O(n)$ 的算法复杂度。 思路：使用字典维护数字出现的频率，每次重复出现一次就在之前的基础上 +1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution {
public:
int numIdenticalPairs(vector<int>& nums) {
unordered_map<int, int> dict ;
int cnt =0;
for(auto num : nums)
{
cnt += dict[num];
dict[num] +=1;
}
return cnt;
}
};
|
python 解法, 使用第二种思路，时间复杂度是$O(n)$ 空间复杂度是$O(n)$
1
2
3
4
5
6
7
8
9
10
11
|
class Solution:
def numIdenticalPairs(self, nums: List[int]) -> int:
dic ={}
cnt =0
for num in nums:
if num in dic:
cnt += dic[num]
dic[num] +=1
else:
dic[num] =1
return cnt
|
LeetCode 1513. Number of Substrings With Only 1s
除了使用count 函数之外，没有其他的想法。从数据范围上看，应该是 $nlogn$ 或者 $n^2$ 的时间复杂度。
正确的思路是这样的： [i, j] 表示区间是连续的1，那么所有字符为 1 的子字符串的书目录是 (c =j-i +1)
1
2
|
c +c -1 + ... +1 = c (c+1)/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
|
class Solution {
public:
int numSub(string s) {
int MOD =1000000000 +7;
cout << MOD << endl;
int res =0;
for(int i =0; i< s.size() ; i++)
{
if(s[i] =='1')
{
int j =i +1;
while(s[j] =='1' && j < s.size())
{
j ++;
}
int c =j -i ;
res = (res + c *(c+1ll)/2 ) %MOD;
i =j -1;
}
}
return res;
}
};
|
python 解法
下面的解法是错误的，在python 中 range() 函数中的i 会一直从 1, 2, 3 这样进行遍历。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution:
def numSub(self, s: str) -> int:
res =0
for i in range(len(s)):
if (s[i] =='1'):
j =i
while j < len(s) and s[j] =='1':
j +=1
c =j -i +1
print(c)
res = (res + c *(c+1)) % 1000000007
i =j -1
return res
|
正确的 python代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution:
def numSub(self, s: str) -> int:
res =0
len_ =len(s)
i =0
while i < len_ :
if s[i] =='1':
j =i +1
while j < len_ and s[j] =='1':
j +=1
c =j -i
#print(c)
res += (c *(c+1)/2) % (1000000007)
i =j +1
else:
i +=1
return int(res)
|
LeetCode第198场周赛
1518. Water Bottles
知道这个题目是数学题（模拟题），考察的是取余和整除，但是没有写出来，多练呀。
python 解法
1
2
3
4
5
6
7
8
|
class Solution:
def numWaterBottles(self, numBottles: int, numExchange: int) -> int:
res =numBottles
while numBottles >= numExchange:
res += numBottles // numExchange
numBottles = numBottles // numExchange + numBottles % numExchange
return res
|
c++ 解法
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution {
public:
int numWaterBottles(int numBottles, int numExchange) {
int res =numBottles;
while (numBottles >= numExchange)
{
res += numBottles / numExchange;
numBottles = numBottles/numExchange +numBottles% numExchange;
}
return res;
}
};
|
LeetCode 1519. Number of Nodes in the Sub-Tree With the Same Label
能够在 $O(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
26
27
28
29
30
31
32
33
34
35
|
class Solution {
public:
vector<vector<int>> f;
vector<vector<int>> g;
string w;
vector<int> countSubTrees(int n, vector<vector<int>>& edges, string labels) {
w =labels;
g.resize(n);
f =vector<vector<int>>(n, vector<int>(26));
// 保存邻接表
for(auto & e: edges)
{
int a =e[0], b =e[1];
g[a].push_back(b);
g[b].push_back(a);
}
dfs(0, -1);
vector<int> res(n);
for(int i =0; i< n; i++) res[i] =f[i][w[i] -'a'];
return res;
}
void dfs(int u, int father)
{
f[u][w[u] -'a'] =1;
for(auto son: g[u]){
if(son ==father) continue;
dfs(son, u);
for(int j =0; j< 26; j++)
f[u][j] += f[son][j];
}
}
};
|
leetcode第 204场周赛
LeetCode 1566. Detect Pattern of Length M Repeated K or More Times
没有什么思路。（至少暴力枚举是应该能够想到的）
c++ 解法，时间复杂度是 $O(n^2)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
public:
bool containsPattern(vector<int>& arr, int m, int k) {
// 暴力枚举
int n =arr.size();
// 开始枚举起点 i
for(int i =0; i +m*k <=n; i++)
{
bool flag =true;
for(int j =i; j< i +m *k ; j++)
if(arr[j] != arr[i + (j -i) %m])
{
flag =false;
break;
}
if (flag) return true; // 存在性质，如果有一个，那么就可以return true
}
return false;
}
};
|
python 解法
以下的解法，简直把 python 对于切片特性的应用简直是非常到位。
1
2
3
4
5
6
7
8
9
10
11
|
class Solution:
def containsPattern(self, arr: List[int], m: int, k: int) -> bool:
# 双重枚举
# python 中切片的用法，简直了
i =0
while i <= len(arr) -1:
subset= arr[i: i+m]
if subset *k == arr[i: i +m *k]:
return True
i += 1
return False
|
c++ 解法，时间复杂度 $O(n)$
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 ;
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;
}
};
|
python 复现上述的解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution:
def containsPattern(self, arr: List[int], m: int, k: int) -> bool:
n =len(arr)
i =0
counter =0
while i +m< n:
if arr[i] == arr[i+m]:
counter +=1
else:
counter =0
if counter == m*(k-1):
return True;
i += 1
return False
|
1567. Maximum Length of Subarray With Positive Product
暴力求解：先求解出子数组，然后根据乘积是正数和最大长度选择最后的数组。时间复杂度是 $O(n^2)$，这里给出的数据范围是$O(n)$，那么时间复杂度最好是 $O(n)$ 或者 $O(nlogn)$ 。
dp 或者双指针，这两种方法的适用场景。
数列问题且数据范围是 $10^5$，那么多半是递推。
递推就是一种特殊的dp。使用 $f(i)$ 和$g(i)$ 分别表示以 $arr[i]$ 为结尾的乘积为正和乘积为负的最大长度。
然后根据 $arr[i]$ 和 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
|
class Solution {
public:
int getMaxLen(vector<int>& nums) {
int n =nums.size();
vector<int> f(n), g(n);
if(nums[0] >0) f[0] =1;
else if (nums[0] <0) g[0] =1;
int res =f[0];
for(int i =1; i< n; i++)
{
if(nums[i] >0)
{
f[i] =f[i-1] +1;
if (g[i-1]) g[i] =g[i-1] +1;
}
else if (nums[i] <0)
{
if(g[i-1]) f[i] =g[i-1] +1;
g[i] =f[i-1] +1;
}
res =max(res, f[i]);
}
return res;
}
};
|
python 解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution:
def getMaxLen(self, nums: List[int]) -> int:
# 使用递推（一种特殊的dp） 进行求解
n =len(nums)
f =[0] * n
g =[0] *n
if nums[0]>0: f[0] =1
elif nums[0] <0: g[0] =1
res =f[0]
for i in range(1,n):
if nums[i] >0:
f[i] =f[i-1] +1
if(g[i-1]): g[i] =g[i-1] +1
elif nums[i] <0:
if g[i-1]: f[i] = g[i-1] +1
g[i] = f[i-1] +1
res =max(res, f[i])
return res
|
LeetCode第205场周赛
1576. Replace All ?’s to Avoid Consecutive Repeating Characters
对于每个字母遍历的是字母表，有限个，并且最多遍历两次就找到了，所以时间复杂度是$O(n)$。
c++ 解法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
public:
// 自己不太熟悉的点：遍历一个数组的左右相邻的元素
string modifyString(string s) {
int n =s.size();
for(int i =0; i<n; i++)
{
char ch =s[i];
if (ch !='?')
continue;
for(char j ='a'; j <= 'z'; j ++)
{
if(i > 0 && s[i-1] ==j) continue;
if (i< n-1 && s[i+1] ==j ) continue;
s[i] =j;
}
}
return s;
}
};
|
将 string 可以直接转换成list
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution:
def modifyString(self, s: str) -> str:
# 对于顺序 index 访问，python语言很吃亏呀
# python 中string 是无法进行index 操作的
res =""
s =list(s)
alpha ="abcdefghijklmnopqrstuvwxyz"
for ind, val in enumerate(s):
print(val)
if val != '?':
res += val
continue
for ch in alpha:
if ind>0 and s[ind-1] ==ch: continue
if ind < len(s)-1 and s[ind +1] ==ch: continue
s[ind] =ch
break
return ''.join(s)
|
- LeetCode 1577. 数的平方等于两数乘积的方法数
这里是暴力求解，时间复杂度是$n^3$，n 的范围是 $10^3$，所以基本上是不可行的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution:
# 我能想到的是暴力枚举，时间复杂度是$(n^3)$， n =10^3，所以是可解的方案; 所以时间范围一定要控制在 $n^2$ 时间复杂度
def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
res =0
for num in nums1:
n =len(nums2)
for i in range(n):
for j in range(i+1, n):
if nums2[i] * nums2[j] ==num *num:
res +=1
for num in nums2:
n =len(nums1)
for i in range(n):
for j in range(i+1, n):
if nums1[i] * nums1[j] == num *num:
res +=1
return res
|
优化一下，需要保持在 $n^2$ 时间复杂度上。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
typedef long long LL;
class Solution {
public:
int work(vector<int> &a, vector<int>& b)
{
int res =0;
unordered_map<LL, int> hash;
// 保存了 a中元素平方值出现的个数
for(int x: a) hash[(LL) x*x] ++;
for(int j =0; j< b.size(); j++)
for(int k =j +1; k < b.size(); k ++)
res += hash[(LL)b[j] *b[k]];
return res;
}
int numTriplets(vector<int>& nums1, vector<int>& nums2) {
return work(nums1, nums2) + work(nums2, nums1);
}
};
|
python 代码
时间复杂度是$O(n^2)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution:
def work(self, nums1, nums2):
res =0
dic ={}
for num in nums1:
if num*num in dic:
dic[num*num] +=1
else:
dic[num*num] =1
n =len(nums2)
for i in range(n):
for j in range(i+1, n):
if nums2[i] * nums2[j] in dic:
res += dic[nums2[i] * nums2[j]]
return res
def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
return self.work(nums1, nums2) + self.work(nums2, nums1);
|
LeetCode 1578. 避免重复字母的最小删除成本
看看人家的思维方式
数据范围是 $10^5$，那么算法复杂度一般是 $O(n)$或者$O(nlogn)$。对于每个字母都是有删掉 和保留两种选择，所以相当于从$2^n$ (n 是字符串的长度)的解空间中寻找一个最优解。那么这类问题 $70%$ 是dp求解，$10%$ 是贪心问题，还有$20%$ 是暴搜问题。
dp 可以分成状态表示和状态转移两个步骤。
其中 $f[i, j]$ 表示前 $i$ 个字母，以字符$j$ 结尾的最小的代价。（这种思路比较难理解，可以参考另外一种思路）
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
|
//1e9 = 10^9 ，是一种简写形式
class Solution {
public:
int minCost(string s, vector<int>& cost) {
const int n =s.size(), m =26;
vector<vector<int>> f(n+1, vector<int>(m, INT_MAX));
for(int j =0; j< m; j++)
f[0][j] =0;
for(int i =1; i<=n; i ++)
for( int j =0; j< m; j++)
{
f[i][j] =min( f[i][j], f[i-1][j] +cost[i-1]);
int k =s[i-1] - 'a';
if(j != k)
f[i][k] =min(f[i][k], f[i-1][j]);
}
int ans =INT_MAX;
for(int j =0; j< m; j++)
ans =min(ans, f[n][j]);
return ans;
}
};
|
思路二：
- 只是需要将每一段连续出现的字符删除到只剩下1个。
- 维度
sum 和m，分别表示当前连续字符的总代价和其中最大的代价
- 删除连续的一段时，需要保留代价最大的，故答案累加
sum-m
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:
int minCost(string s, vector<int>& cost) {
const int n =s.size();
int ans =0;
int sum =0, m =0;
for(int i =0; i< n; i++)
{
if(i ==0 || s[i-1] != s[i])
{
ans += sum -m;
sum =m =cost[i];
}
else
{
sum += cost[i];
m =max(m, cost[i]);
}
}
ans += sum -m;
return ans;
}
};
|
python 实现
时间复杂度是$O(n)$ 空间复杂度是$O(1)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution:
def minCost(self, s: str, cost: List[int]) -> int:
res =0
sum_ , m =0, 0
# 对于每一段连续的字母，留下 cost 最大的字母；使用sum 和m 分别表示连续字符串中cost总和 和最大的代价
# res 是上述过程的累加和
n =len(s)
for i in range(n):
if i==0 or s[i-1] != s[i]:
res += (sum_ -m)
sum_ , m =cost[i], cost[i]
else:
sum_ += cost[i]
m =max(m, cost[i])
res += (sum_ -m) # 最后再进行一次相加其实是不太清楚的
return res
|
leetcode第206场周赛
1582. Special Positions in a Binary Matrix
从数据范围上看 rows, cols 最大是100，暴力求解是可行的，那么就是 $O(n^3)$ 的做法。但是仍然是有更加简洁的做法，时间复杂度是$O(mn)$， 其中 $m,n$ 分别对应是矩阵的长和宽。
特殊的位置的定义，如果 $mat[i, j] =1$ 并且改行该列的其他元素都是0，那么该位置就是特殊位置。
算法思路：求解每行每列的综合，如果某个元素 $mat[,j] = row[i] =col[j] =1$ 那么该位置就是特殊位置。
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 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
16
17
18
19
|
class Solution:
def numSpecial(self, mat: List[List[int]]) -> int:
rows, cols = len(mat), len(mat[0])
a =[0] *rows
b =[0] *cols
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 a[i] ==1 and b[j] ==1:
res +=1
return res
|