力扣周赛320
T1. 数组中不等三元组的数目
暴力
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
public:
int unequalTriplets(vector<int>& nums) {
int n = (int)nums.size();
int ans = 0;
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
for(int k = j + 1; k < n; k++){
if(nums[i] != nums[j] && nums[j] != nums[k] && nums[i] != nums[k]){
++ans;
}
}
}
}
return ans;
}
};
T2. 二叉搜索树最近节点查询
题解：遍历完二叉树直接二分查找
代码：
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/**
* 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<vector<int>> closestNodes(TreeNode* root, vector<int>& queries) {
vector<int> all;
function<void(TreeNode *)> dfs = [&](TreeNode *rt){
if(rt == nullptr) return ;
all.push_back(rt->val);
dfs(rt->left);
dfs(rt->right);
};
dfs(root);
sort(all.begin(), all.end());
vector<vector<int>> ans;
for(int &v: queries){
vector<int> temp;
auto mini = upper_bound(all.begin(), all.end(), v);
if(mini == all.begin()){
temp.push_back(-1);
}else{
--mini;
temp.push_back(*mini);
}
auto maxx = lower_bound(all.begin(),all.end(), v);
if(maxx == all.end()){
temp.push_back(-1);
}else{
temp.push_back(*maxx);
}
ans.push_back(temp);
}
return ans;
}
};
T3. 到达首都的最少油耗
题面
给你一棵 n 个节点的树（一个无向、连通、无环图），每个节点表示一个城市，编号从 0 到 n - 1 ，且恰好有 n - 1 条路。0 是首都。给你一个二维整数数组 roads ，其中 roads[i] = [ai, bi] ，表示城市 ai 和 bi 之间有一条 双向路 。
每个城市里有一个代表，他们都要去首都参加一个会议。
每座城市里有一辆车。给你一个整数 seats 表示每辆车里面座位的数目。
城市里的代表可以选择乘坐所在城市的车，或者乘坐其他城市的车。相邻城市之间一辆车的油耗是一升汽油。
请你返回到达首都最少需要多少升汽油。
题解
- 考虑到达每个节点需要的最少车数
- 如果以$u$为根的子树大小为$siz$，则最少需要$\lceil\frac{siz}{seats} \rceil$辆车
- 根据当前车数确定是否要加一，如果车数加一，就要多消耗$dep[u]-1$的油量
- 在每个节点整合车数，减去可以省去的油量
- DFS即可
代码
1 | class Solution { |
T4. 完美分割的方案数
题面
给你一个字符串 s ，每个字符是数字 '1' 到 '9' ，再给你两个整数 k 和 minLength 。
如果对 s 的分割满足以下条件，那么我们认为它是一个 完美 分割：
s被分成k段互不相交的子字符串。- 每个子字符串长度都 至少 为
minLength。 - 每个子字符串的第一个字符都是一个 质数 数字，最后一个字符都是一个 非质数 数字。质数数字为
'2'，'3'，'5'和'7'，剩下的都是非质数数字。
请你返回 s 的 完美 分割数目。由于答案可能很大，请返回答案对 109 + 7 取余 后的结果。
一个 子字符串 是字符串中一段连续字符串序列。
题解
令$dp[i][k]$表示前$i$个元素分割成$k$段的方案数
考虑$O(n ^ 3)$的转移有：
其中$satisfy(s[jj])=True$表示$s[jj]$不是质数而$s[jj + 1]$是质数。
- 利用前缀和维护$dp[i][k]$，则复杂度可以降为$O(n ^ 2)$
代码
1 | const int mod = 1e9 + 7; |