力扣周赛(节选)2022-04-30
6404. 将数组清空
关键词:树状数组、找法则
题目起源:6404. 将数组清空 – 力扣(Leetcode)——力扣第 103 场双周赛第 4 题
题目形容
T 树状数组
T 找法则
给你一个蕴含若干 互不雷同 整数的数组 nums
,你须要执行以下操作 直到 数组为空:
- 如果数组中第一个元素是以后数组中的 最小值,则删除它。
- 否则,将第一个元素挪动到数组的 开端。
请你返回须要多少个操作使 nums
为空。
问题剖析
问题等价于:设一指针 p 初始指向 nums[0],指针 p 把一直从左往右扫描(扫描到开端则从头开始扫描),每扫描到以后数组的最小值,就将其标记为“删除”,而后持续扫描,直到数组所有元素均被标记为“删除”,求指针总共须要挪动多少步,标记为删除的地位在挪动时间接疏忽。
设上一个最小值的地位为 pre,也即上次标记为“删除”的地位为 pre,以后最小值的地位为 i。
先思考 i≥pre 的状况,则从 pre 挪动到 i 共需 i -pre 步。又因为
- 这个 i -pr 步中,有些地位曾经被删除,挪动时间接被疏忽,不记录到理论步数中;
- 将一个地位标记为“删除”,指针 p 便会顺移到下一个未被删除的地位,所以指针并不是从 pre 开始挪动的。
设理论须要挪动 k 步,则 k =(i-pre)-[pre+1..i]中被删除的地位 -1。
再思考 i <pre 的状况,则从 pre 挪动到 i 共需 (n-pre)+1+(i-1)。同样须要思考被删除的地位和指针的顺移,则理论挪动步数 k =(n-pre)+1+(i-1)-[pre+1..n] 被删除的地位 -[1..i]被删除的地位 -1。
以上只思考到挪动的次数,题目还需加上删除操作的次数,故答案最初须要 +n。
通过剖析发现,须要保护区间被删除的地位的个数,因此想到树状数组(或者线段树)。
代码实现
// 树状数组模板
const int N = 1e5 + 5;
int tr[N], n;
int lowbit(int x) {return x & -x;}
void add(int x) {for (int i = x; i <= n; i += lowbit(i))tr[i]++;
}
int query(int x) {
int res = 0;
for (int i = x; i; i -= lowbit(i))res += tr[i];
return res;
}
long long countOperationsToEmptyArray(vector<int> &nums) {n = nums.size();
int idx[n];
iota(idx, idx + n, 1); // 从 1 开始
sort(idx, idx + n, [&](int &i, int &j) {return nums[i - 1] < nums[j - 1];
});
long long res = n; // 删除操作执行 n 次
int pre = 0; // 上一个被删除的数的地位
for (int i: idx) {if (i >= pre) {
// 从 pre 挪动到 i,并且跳过已删除的数
res += (i - pre) - (query(i) - query(pre)) - 1;
} else {
// 从 pre 挪动到 n,从 1 挪动到 i,并且跳过已删除的数
res += (n - pre + i) - (query(n) - query(pre)) - (query(i)) - 1;
}
add(i), pre = i;
}
return res;
}
工夫复杂度:O(nlog(n))
空间复杂度:O(n)
6343. 返回指标的最小代价
关键词:单源最短路、深度优先
题目起源:6343. 返回指标的最小代价 – 力扣(Leetcode)——力扣第 343 场周赛第 3 题
题目形容
T 单源最短路
T 深度优先
给你一个数组 start
,其中 start = [startX, startY]
示意你的初始地位位于二维空间上的 (startX, startY)
。另给你一个数组 target
,其中 target = [targetX, targetY]
示意你的指标地位 (targetX, targetY)
。
从地位 (x1, y1)
到空间中任一其余地位 (x2, y2)
的代价是 |x2 - x1| + |y2 - y1|
。
给你一个二维数组 specialRoads
,示意空间中存在的一些非凡门路。其中 specialRoads[i] = [x1i, y1i, x2i, y2i, costi]
示意第 i
条非凡门路能够从 (x1i, y1i)
到 (x2i, y2i)
,但老本等于 costi
。你能够应用每条非凡门路任意次数。
返回从 (startX, startY)
到 (targetX, targetY)
所需的最小代价。
输出:start = [1,1], target = [4,5], specialRoads = [[1,2,3,3,2],[3,4,4,5,1]]
输入:5
输出:start = [3,2], target = [5,7], specialRoads = [[3,2,3,4,4],[3,3,5,5,5],[3,4,5,6,6]]
输入:7
数据范畴
start.length == target.length == 2
1 <= startX <= targetX <= 1e5
1 <= startY <= targetY <= 1e5
1 <= specialRoads.length <= 200
specialRoads[i].length == 5
startX <= x1i, x2i <= targetX
startY <= y1i, y2i <= targetY
1 <= costi <= 1e5
单源最短路
可能通过的点只有源点、起点和非凡门路上的点,故本题可转化为简略的单源最短路问题,因为是浓密图,故采纳奢侈 Dijkstra 算法即可。
int minimumCost(vector<int> &start, vector<int> &target, vector<vector<int>> &specialRoads) {
using ll = long long;
ll t = (ll) target[0] << 32 | target[1];
ll s = (ll) start[0] << 32 | start[1];
// 源点 s 到各点的最短距离
unordered_map<ll, int> dis = {{s, 0},
{t, INT_MAX}};
// 标记一个点是否被拜访
unordered_set<ll> vis;
while (true) {
// 找到间隔源点最近的点
ll p = -1;
for (auto &d: dis)
if (vis.find(d.first) == vis.end() &&
(p < 0 || d.second < dis[p]))
p = d.first;
// 起点的间隔曾经确定
if (p == t) return dis[t];
// 标记以后点的间隔被确定
vis.insert(p);
// 通过点 p 更新各点到源点的间隔
int tx = p >> 32, ty = p & UINT32_MAX;
dis[t] = min(dis[p] + target[0] - tx + target[1] - ty, dis[t]);
for (auto &r: specialRoads) {// 源点 s 到 (r[2],r[3]) 的间隔
// 要从 p 间接到(r[2],r[3]),要么从 p 通过非凡门路到(r[2],r[3])
int x = r[2], y = r[3];
int d = dis[p] +
min(abs(x - tx) + abs(y - ty),
abs(r[0] - tx) + abs(r[1] - ty) + r[4]
);
// 更新间隔
ll tp = (ll) x << 32 | y;
if (dis.find(tp) == dis.end() || d < dis[tp])dis[tp] = d;
}
}
}
工夫复杂度:O(n^2)。其中,n 指的是 specialRoads 的长度
空间复杂度:O(n)
深度优先
因为数据规模并不是很大,1 <= specialRoads.length <= 200
,故采纳深搜来枚举每种可能也能够通过大部分数据(1038 / 1040)。
进行深搜前能够将非凡门路按其终点与源点的间隔排序,从而放慢最小值的获取。
int minimumCost(vector<int> &start, vector<int> &target, vector<vector<int>> &specialRoads) {
auto &v = specialRoads;
int len = v.size();
// 终点间隔源点近的门路先枚举
sort(v.begin(), v.end(),
[&](const auto &v1, const auto &v2) {return abs(v1[0] - start[0]) + abs(v1[1] - start[1]) < abs(v2[0] - start[0]) + abs(v2[1] - start[1]);
}
);
// 标记门路是否被枚举(一条非凡门路不可能应用两次)bool f[len];
memset(f, 0, sizeof f);
// 不通过任何非凡门路
int minCost = abs(start[0] - target[0]) + abs(start[1] - target[1]);
// 枚举所有非凡门路的组合
function<void(int, int, int)> dfs = [&](int x, int y, int cst) {if (cst >= minCost)return;
minCost = min(cst + abs(target[0] - x) + abs(target[1] - y), minCost);
for (int i = 0; i < len; i++) {if (!f[i]) {f[i] = true;
dfs(v[i][2], v[i][3],
cst + abs(v[i][0] - x) + abs(v[i][1] - y) + v[i][4]
);
f[i] = false;
}
}
};
dfs(start[0], start[1], 0);
return minCost;
}
6344. 字典序最小的漂亮字符串
关键词:贪婪
题目起源:6344. 字典序最小的漂亮字符串 – 力扣(Leetcode)——力扣第 343 场周赛第 4 题
题目形容
T 贪婪
如果一个字符串满足以下条件,则称其为 漂亮字符串:
- 它由英语小写字母表的前
k
个字母组成。 - 它不蕴含任何长度为
2
或更长的回文子字符串。
给你一个长度为 n
的漂亮字符串 s
和一个正整数 k
。
请你找出并返回一个长度为 n
的漂亮字符串,该字符串还满足:在字典序大于 s
的所有漂亮字符串中字典序最小。如果不存在这样的字符串,则返回一个空字符串。
对于长度雷同的两个字符串 a
和 b
,如果字符串 a
在与字符串 b
不同的第一个地位上的字符字典序更大,则字符串 a
的字典序大于字符串 b
。
例如,"abcd"
的字典序比 "abcc"
更大,因为在不同的第一个地位(第四个字符)上 d
的字典序大于 c
。
输出:s = "abcz", k = 26
输入:"abda"
解释:字符串 "abda" 既是漂亮字符串,又满足字典序大于 "abcz"。能够证实不存在字符串同时满足字典序大于 "abcz"、漂亮字符串、字典序小于 "abda" 这三个条件。
输出:s = "dc", k = 4
输入:""解释:能够证实,不存在既是漂亮字符串,又字典序大于"dc" 的字符串。
数据范畴
1 <= n == s.length <= 1e5
4 <= k <= 26
s 是一个漂亮字符串
问题剖析
长度为 m 的回文串必然蕴含一个长度为 m - 2 的字符串,又字符串 s 本就不含回文串,故只须要保障批改字符后不会呈现长度为 2 或 3 的回文串,则字符串中就肯定不含回文串。
题目要求字典序最小,故一直对字符串 s 进行 +1,每次 +1,查看是否呈现回文串,若不呈现回文串,阐明找到符合要求的串。
代码实现
string smallestBeautifulString(string s, int k) {int n = s.size(), i = n - 1;
k += 'a', s[i]++;
while (i < n) {
// 越界(需进位)if (s[i] == k) {if (i == 0)return ""; // 不存在符合条件的串
s[i] = 'a', s[--i]++;
}
// 是否和后面字符形成回文串
else if (i && s[i] == s[i - 1] || i > 1 && s[i] == s[i - 2])s[i]++;
// 是否和前面字符形成回文串
else i++;
}
return s;
}
工夫复杂度:O(n)
空间复杂度:O(1)