力扣周赛（节选）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 == 21 <= startX <= targetX <= 1e51 <= startY <= targetY <= 1e51 <= specialRoads.length <= 200specialRoads[i].length == 5startX <= x1i, x2i <= targetXstartY <= y1i, y2i <= targetY1 <= 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 <= 1e54 <= k <= 26s 是一个漂亮字符串问题剖析
长度为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)