# 求出加密整数的和
给你一个整数数组 nums ，数组中的元素都是 正 整数。定义一个加密函数 encrypt ， encrypt(x) 将一个整数 x 中 每一个 数位都用 x 中的 最大 数位替换。比方说 encrypt(523) = 555 且 encrypt(213) = 333 。
请你返回数组中所有元素加密后的 和 。
示例 1：
输入： nums = [1,2,3]
输出： 6
解释： 加密后的元素位
[1,2,3]。加密元素的和为1 + 2 + 3 == 6。
示例 2：
** 输入：**nums = [10,21,31]
** 输出：**66
** 解释：** 加密后的元素为
[11,22,33]。加密元素的和为11 + 22 + 33 == 66。
数据范围：
1 <= nums.length <= 501 <= nums[i] <= 1000
思路： 遍历每个元素，计算最大位 maxv ，遍历的同时计算 111... 的值 base ，把 base * maxv 即为转化后的值
class Solution { | |
public: | |
int deal(int x){ | |
int base = 0, maxv = 0; | |
while(x){ | |
base = base * 10 + 1; | |
maxv = max(maxv, x % 10); | |
x /= 10; | |
} | |
return base * maxv; | |
} | |
int sumOfEncryptedInt(vector<int>& nums) { | |
int res = 0; | |
for(auto &x : nums) res += deal(x); | |
return res; | |
} | |
}; |
复杂度分析
- 时间复杂度：，其中
n为nums的长度，U=max(nums) - 空间复杂度：
# 执行操作标记数组中的元素
给你一个长度为 n 下标从 0 开始的正整数数组 nums 。
同时给你一个长度为 m 的二维操作数组 queries ，其中 queries[i] = [indexi, ki] 。
一开始，数组中的所有元素都 未标记 。
你需要依次对数组执行 m 次操作，第 i 次操作中，你需要执行：
- 如果下标
indexi对应的元素还没标记，那么标记这个元素。 - 然后标记
ki个数组中还没有标记的 最小 元素。如果有元素的值相等，那么优先标记它们中下标较小的。如果少于ki个未标记元素存在，那么将它们全部标记。
请你返回一个长度为 m 的数组 answer ，其中 answer[i] 是第 i 次操作后数组中还没标记元素的 和 。
示例 1：
输入： nums = [1,2,2,1,2,3,1], queries = [[1,2],[3,3],[4,2]]
输出：[8,3,0]
解释：
我们依次对数组做以下操作：
- 标记下标为
1的元素，同时标记2个未标记的最小元素。标记完后数组为nums = [***1***,***2***,2,***1***,2,3,1]。未标记元素的和为2 + 2 + 3 + 1 = 8。- 标记下标为
3的元素，由于它已经被标记过了，所以我们忽略这次标记，同时标记最靠前的3个未标记的最小元素。标记完后数组为 nums = [1,2,2,1,2,3,1] 。未标记元素的和为3。- 标记下标为
4的元素，由于它已经被标记过了，所以我们忽略这次标记，同时标记最靠前的2个未标记的最小元素。标记完后数组为 nums = [1,2,2,1,2,3,1] 。未标记元素的和为0。
示例 2：
** 输入：**nums = [1,4,2,3], queries = [[0,1]]
输出：[7]
** 解释：** 我们执行一次操作，将下标为
0处的元素标记，并且标记最靠前的1个未标记的最小元素。标记完后数组为nums = [***1***,4,***2***,3]。未标记元素的和为4 + 3 = 7。
数据范围：
n == nums.lengthm == queries.length1 <= m <= n <= 1051 <= n <= 105queries[i].length == 20 <= indexi, ki <= n - 1
思路： 由于需要从小到大标记，首先对元素进行排序，第一排序关键字为 nums[i] 的大小，第二关键字为下标 index 。使用一个哈希表来存储未标记的元素集合。每次操作，首先检查从哈希表中检查 query[i][0] 是否存在，存在说明未标记，并从哈希表中移除。其次从排序队列中选取 query[i][1] 个有效的元素并从哈希表中删除.
class Solution { | |
public: | |
typedef long long ll; | |
typedef pair<int, int> pii; | |
vector<long long> unmarkedSumArray(vector<int>& nums, vector<vector<int>>& queries) { | |
unordered_set<int> S; | |
int n = nums.size(); | |
vector<pii> tp(n); | |
ll sum = 0; | |
for(int i = 0; i < n; i ++ ) S.insert(i), tp[i] = {nums[i], i}, sum = sum + nums[i]; | |
sort(tp.begin(), tp.end()); | |
int m = queries.size(); | |
vector<ll> res(m, 0); | |
int k = 0; | |
for(int i = 0; i < m; i ++ ){ | |
auto item = queries[i]; | |
int index = item[0]; | |
int cnt = item[1]; | |
if(S.find(index) != S.end()) S.erase(index), sum = sum - nums[index]; | |
while(k < n && cnt > 0){ | |
pii cur = tp[k ++ ]; | |
if(S.find(cur.second) == S.end()) continue; | |
sum = sum - cur.first; | |
S.erase(cur.second); | |
cnt -- ; | |
} | |
res[i] = sum; | |
} | |
return res; | |
} | |
}; |
复杂度分析
- 时间复杂度：，其中
n为nums的长度 - 空间复杂度：
# 替换字符串中的问号使分数最小
给你一个字符串 s 。 s[i] 要么是小写英文字母，要么是问号 '?' 。
对于长度为 m 且 只 含有小写英文字母的字符串 t ，我们定义函数 cost(i) 为下标 i 之前（也就是范围 [0, i - 1] 中）出现过与 t[i] 相同 字符出现的次数。
字符串 t 的 分数 为所有下标 i 的 cost(i) 之 和 。
比方说，字符串 t = "aab" ：
cost(0) = 0cost(1) = 1cost(2) = 0- 所以，字符串
"aab"的分数为0 + 1 + 0 = 1。
你的任务是用小写英文字母 替换 s 中 所有 问号，使 s 的 分数 **** 最小 。
请你返回替换所有问号 '?' 之后且分数最小的字符串。如果有多个字符串的 分数最小 ，那么返回字典序最小的一个。
示例 1：
** 输入：**s = "???"
输出： "abc"
** 解释：** 这个例子中，我们将
s中的问号'?'替换得到"abc"。对于字符串
"abc"，cost(0) = 0，cost(1) = 0和cost(2) = 0。
"abc"的分数为0。其他修改
s得到分数0的字符串为"cba"，"abz"和"hey"。这些字符串中，我们返回字典序最小的。
示例 2：
输入： s = "a?a?"
输出： "abac"
** 解释：** 这个例子中，我们将
s中的问号'?'替换得到"abac"。对于字符串
"abac"，cost(0) = 0，cost(1) = 0，cost(2) = 1和cost(3) = 0。
"abac"的分数为1。
