🔥博客主页： A_SHOWY
🎥系列专栏：力扣刷题总结录 数据结构 云计算 数字图像处理 力扣每日一题_
【1.4】2397.被列覆盖的最多行数
2397. 被列覆盖的最多行数
https://leetcode.cn/problems/maximum-rows-covered-by-columns/
这个题目真的太巧妙了，运用这种位运算来模拟这个数组，然后，将数组用位运算以后的二进制和存储，然后，用位运算设置limit，给while循环，1个数不够的还得continue了，最后按位与，整体结构都非常巧妙。
- 第一部分，存储每一行的二进制表示位，用一个数组把一个转为二进制存起来。
vector<int> mask(m,0); //存储每一行的二进制表示位 for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ mask[i] += matrix[i][j] << (n - j -1); } } - 在判断的时候，用limit卡住界限，维护列变换的区间
while((++cur) < limit){ if(__builtin_popcount(cur) != numSelect) { continue; } - 用了一个内置函数关于一个二进制中1 的个数的函数，还有0的个数的函数
__builtin_popcount(cur) //1的个数 __builtin_ctz(cur) //0的个数，count trailing zero - 最后把每一行遍历一遍，与变换后的列的第一行按位与，看看能不能覆盖这一行的所有1
class Solution {
public:
int maximumRows(vector<vector<int>>& matrix, int numSelect) {
if(numSelect >= matrix[0].size()) return matrix.size();
int m = matrix.size();
int n = matrix[0].size();
vector<int> mask(m,0);
//存储每一行的二进制表示位
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
mask[i] += matrix[i][j] << (n - j -1);
}
}
int res = 0;//记录最大行数
int cur = 0;//最大列数
int limit = (1 << n);
while((++cur) < limit){
if(__builtin_popcount(cur) != numSelect) {
continue;
}
int t = 0;
for(int j = 0; j < m; j++){//遍历一遍按位与
if((mask[j] & cur) == mask[j]){
t++;
}
}
res = max(res,t);
}
return res;
}
};【1.14】83.删除排序链表中的重复元素
83. 删除排序链表中的重复元素https://leetcode.cn/problems/remove-duplicates-from-sorted-list/
很久没有做到链表题目，但是这道确实简单，只需要注意一下while循环中除了cur非空，还要兼顾cur -> next非空。重复时，就让指针指向next -> next
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode* cur = head;
while(cur != NULL && cur ->next != NULL)
{
if(cur -> val == cur -> next -> val) {
cur -> next = cur -> next -> next;
}
else cur = cur -> next;
}
return head;
}
};【1.15】82.删除排序链表中的重复Ⅱ
82. 删除排序链表中的重复元素 IIhttps://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/
与83题删除排序链表中元素的主要区别为此题要求将出现过的重复元素的所有元素均删除例如1，2，2，2将所有的2删除。需要引入头结点，因为头部可能也会被删除，统一操作。
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode* dummyhead = new ListNode(0);
dummyhead -> next =head;
ListNode* cur = dummyhead;
while(cur -> next && cur-> next -> next){
if(cur -> next-> val == cur -> next -> next -> val)
{
int x = cur -> next -> val;
while(cur -> next && cur -> next -> val == x){//直到cur -> next 为空节点或者cur -> next 不为x
cur -> next = cur -> next -> next;
}
}
else cur = cur -> next;
}
head = dummyhead -> next;
delete dummyhead;
return head;
}
};那么本题的总体思路也是比较简单，先设置一个虚拟头结点dummyhead，其具体步骤为
ListNode* dummyhead = new ListNode(0);
dummyhead -> next =head;
ListNode* cur = dummyhead; 如果节点的下一个等于其下一个的下一个，就说明重复，把重复的数字记下来，统一删除。while中判定条件是删除直到cur的下一个是空节点或者粗人的下一个的值不是x。最后再删除头结点。
【1.17】2744.最大字符串配对数目
2744. 最大字符串配对数目https://leetcode.cn/problems/find-maximum-number-of-string-pairs/
该题目如果暴力做，二重循环思路比较简单，但是也可以用哈希法解决。
法一：暴力
class Solution {
public:
int maximumNumberOfStringPairs(vector<string>& words) {
int ans = 0;
for(int i = 0; i < words.size();++i){
for(int j = i + 1; j < words.size(); ++j){
if(words[i][0] == words[j][1] && words[i][1] == words[j][0]) ans++;
}
}
return ans;
}
};法二：哈希
1.set.count 表示统计元素出现的次数不为0
2.用哈希值来存，题目限制是一个两位的字符串，同时都是小写字母，所以可以用第一位*100+第二位作为哈希值来存，两位互不影响。
class Solution {
public:
int maximumNumberOfStringPairs(vector<string>& words) {
unordered_set<int> set;
int ans = 0;
for(int i = 0; i < words.size(); i++){
if(set.count(words[i][1] * 100 + words[i][0])) ans++;
set.insert(words[i][0] * 100 + words[i][1]);
}
return ans;
}
};如果把后边两部反过来会出现一些问题，先插入后判定，那么比如cc、aa、bb这种重叠的字符串就会被多算一次产生错误
for(int i = 0; i < words.size(); i++){
set.insert(words[i][0] * 100 + words[i][1]);
if(set.count(words[i][1] * 100 + words[i][0])) ans++;
}
【1.18】2171.拿出最少数目的魔法豆
2171. 拿出最少数目的魔法豆https://leetcode.cn/problems/removing-minimum-number-of-magic-beans/
这道题目其实暴力做法非常容易，但是不通过，数据集太大了。如果想减少复杂度的话，可以先排序分段进行处理，也就是用排序+前缀和来解决
方法一：暴力（不通过）
class Solution {
public:
long long minimumRemoval(vector<int>& beans) {
vector<long long> res(beans.size(),0);
for(int i = 0; i < beans.size(); i++){
for(int j = 0; j < beans.size(); j++){
if(beans[j] >= beans[i]){
res[i] += beans[j] - beans[i];
}
else{
res[i] += beans[j];
}
}
}
long long ans = 9999999999;
for(int i =0; i < beans.size();++i){
if(res[i] < ans){
ans = res[i];
}
}
return ans;
}
};暴力两个for直接不通过
方法二：排序 + 前缀和
//排序 + 前缀和
class Solution {
public:
long long minimumRemoval(vector<int>& beans) {
sort(beans.begin(),beans.end());
//前缀和
vector<long long> sum(beans.size() + 1,0);//让sum【0】 = 0
for(int i = 0; i < beans.size(); i++){
sum[i + 1] = sum[i] + beans[i];
}
long long res = LLONG_MAX/2;
int n = beans.size();
for(int i = 0; i < n; i++){
res = min(res,sum[i] + sum[n] - sum[i + 1] - (n -1L -i) * beans[i]);
}
return res;
}
};先排序以后，创建一个数组储存前缀和，这时候要注意新数组的个数是size + 1,然后循环迭代赋值。
在后边的时候，设置res为LLONG_MAX/2,然后看图按照逻辑操作就行，比i这个地方的值小的一律置为0，比它大的置为beans【i】
【1.20】2788.按分隔符拆分字符串
2788. 按分隔符拆分字符串https://leetcode.cn/problems/split-strings-by-separator/
该题目是一个比较简单的模拟题，主要是积累getline函数的使用方法
1.getline(ss, sub, separator) 的作用是从 std::stringstream 对象 ss 中读取一行（以 separator 为分隔符），并将结果存储在字符串 sub 中。istream& getline(istream& is, string& str, char delim);is: 输入流，str: 存储读取的行的字符串。delim: 指定的分隔符，getline 会根据这个分隔符进行拆分。
class Solution {
public:
vector<string> splitWordsBySeparator(vector<string>& words, char separator) {
vector<string> res;
for(string &word : words){//遍历输入的字符串数组
stringstream ss(word);//使用字符串流 stringstream 对每个字符串进行处理，后边要用getline
string str;
while(getline(ss,str,separator)){
if(!str.empty()) {res.push_back(str);}
}
}
return res;
}
};2.记住&在这里是引用的意思，函数可以直接调用或者修改传递的字符串，而不是对其副本进行操作增加效率。
【1.21】410.分割数组的最大值
410. 分割数组的最大值https://leetcode.cn/problems/split-array-largest-sum/
本题是一个hard题，分析题目，要求 最大值最小，确定思路不是二分就是dp，本题我们用二分求解。
先分析 每段和越小——》分出的段越多 ，
假设我分了 一个段落和最大值为sum 对应的段落为——》k1>k
代表着 段落分多了，减少分的段，就要每段和大一点。 所以小于等于sum那一部分就可以删掉了（因为要减少段，要每段和大一点）
这里的k个可以理解为至多。
class Solution {
public:
int splitArray(vector<int>& nums, int k) {
auto maxElement = max_element(nums.begin(), nums.end());
int l = *maxElement;
int sum = 0;
for(int i = 0; i< nums.size(); i++){
sum += nums[i];
}
int r = sum;
while(l <= r){
int mid = l + ((r-l) / 2);
if(check(nums,mid,k)) r = mid - 1;//如果能够分到k段，sum给大了
else l = mid + 1;
}
return l;//当最后l，r，mid指向同一个点的时候，假如满足就是l，假如不满足，l=mid + 1，所以最后返回l
}
bool check(vector<int>& nums, int m, int k){
int cnt = 1;//段数
int s = 0;
for(int i = 0; i < nums.size(); i++){
if(nums[i] + s <= m) s += nums[i];
else{
if(cnt++ == k) return false;
else s = nums[i];
}
}
return true;
}
};这里面有很多值得注意的点，第一个是设置l和r，在设置r的时候就是最少的分段是一整个，所以直接求和，在左边的时候，最多的分段就是每个一段，所以直接找最大值，最大值的时候用一个迭代器，然后不要忘了求迭代器指向的具体值。
在二分法的时候，到了l，r，mid三个指向同一个点时候，考虑，假如这时候满足了，那么这三个点都能表示满足的最大值，如果不满足，那么l要mid+1，最后满足的还是l，所以要返回l。
在check函数中，注意先循环一手，如果小于这个值，就加进去s，如果不满足，先判断段落是不是够k了，如果够了直接false，否则新加一个cnt
【1.22】670.最大交换
670. 最大交换https://leetcode.cn/problems/maximum-swap/
该题目主要考察灵活运用to_string 和stoi和swap函数，进行一次遍历。看题解以后，还有一种贪心的算法可以借鉴
方法一：遍历
class Solution {
public:
int maximumSwap(int num) {
string stringNum = to_string(num);//to_string转成字符串
int maxnum = num;
int n = stringNum.size();
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
swap(stringNum[i],stringNum[j]);
maxnum = max(maxnum , stoi(stringNum));//stoi字符串转成int
swap(stringNum[i],stringNum[j]);
}
}
return maxnum;
}
};先把给的num转化成string形式，然后对字符串每一个字符进行两两交换，取最大值，在每一次循环中，交换过了要记得交换回来。
方法二：贪心
只要让靠近右边的最大的数的索引和左边的比这个数小的数的索引交换位置就能保证换完的数是一个最大。先遍历一遍，找到最大的数，然后从右到左看数字是否比这个最大的数大。
但是注意保证在求maxId时候，尽量保证其靠近右侧。
class Solution {
public:
int maximumSwap(int num) {
string stringnum = to_string(num);
int n = stringnum.size();
int maxId = n - 1;
int idx1 = -1;
int idx2 = -1;
for(int i = n - 1; i >= 0; i--){
if(stringnum[i] > stringnum[maxId]){
maxId = i;
}
else if (stringnum[i] < stringnum[maxId]){
idx1 = i;
idx2 = maxId;
}
}
if(idx1 >= 0){
swap(stringnum[idx1],stringnum[idx2]);
return stoi(stringnum);
}
else return num;
}
};【1.23】2765.最长交替子数组
2765. 最长交替子数组https://leetcode.cn/problems/longest-alternating-subarray/
这道题目第一思路就是双重循环，类似于双指针，让后边的指针指向的数减去前面的数根据奇数偶数分为0和1即可。看题解以后，发现其实可以降低复杂度为o（n）
方法一： 双重循环
class Solution {
public:
int alternatingSubarray(vector<int>& nums) {
int res = -1;
for(int i = 0; i < nums.size(); i++){
for(int j = i + 1; j < nums.size();j++){
int length = j - i + 1;
if(nums[j] - nums[i] == (length + 1) % 2){
res = max(res,length);
}
else {
break;
}
}
}
return res;
}
};方法二： 单重循环
考虑到当内层循环在第i个不满足条件时，不需要从初始+1外层循环继续开始，因为如果从初始 +1开始，到第i个一定会断，而且长度要比原来的要小。
所以可以直接从i+1继续遍历，但是要注意第i个断了以后，要考虑假如第i个减第i-1个正好是1的时候需要给在新的数组中算上。
class Solution {
public:
int alternatingSubarray(vector<int>& nums) {
int res = -1;
int j = 0;//前指针
for(int i = 1; i < nums.size(); i++){
int length = i -j +1;
if(nums[i] - nums[j] == (length + 1) % 2){
res = max(res,length);
}
else {
if(nums[i] - nums[i-1] == 1){
j = i-1;
res = max(res,2);
}
else{
j = i;
}
}
}
return res;
}
};【1.24】2865.美丽塔
【1.24】2866.美丽塔Ⅱ
2865. 美丽塔 Ihttps://leetcode.cn/problems/beautiful-towers-i/
本题可以直接暴力求解，外层遍历让每一个值都当做峰值，内层循环从中间向两边都递减。 同时补充了一道美丽塔Ⅱ
方法一：暴力枚举
class Solution {
public:
long long maximumSumOfHeights(vector<int>& maxHeights) {
long long res = 0;
int n = maxHeights.size();
for(int i = 0; i < n; i++){//外层分别设为峰顶
int pre = maxHeights[i];
long long sum = pre;
for(int j = i - 1 ;j >= 0; j--){
pre = min(pre,maxHeights[j]);
sum += pre;
}
int suf = maxHeights[i];
for(int j = i + 1; j < n; j++){
suf = min(suf,maxHeights[j]);
sum += suf;
}
res = max(res,sum);
}
return res;
}
};值得注意的点数据类型要匹配，在函数种定义的maxheights 的值都是int类型，在比较min的过程中，要求两个数的定义都是int类型，而函数返回的是long long，所以定义的sum值是longlong类型。
整体思路是设置每一个值为峰值，然后都向左向右递减用最小值。然后对sum求最大值即可。
补充题目：2866.美丽塔22866. 美丽塔 IIhttps://leetcode.cn/problems/beautiful-towers-ii/ 题目一模一样，唯一的区别就是数据量大，不让用枚举了。
这时候就用到第二个方法，单调栈。
方法二：单调栈
由于题目要求一个峰值，然后两边都是单调的，而且两边逻辑一样，所以我们可以考虑一边，每一边都使用单调栈，对单调栈的操作，首先要进行一个while的pop，因为我们要求栈内元素单调递增的，当出现下边这种情况的时候，为了迁就后边的元素，前面的要弹出（但是要注意我们栈里存储的是下标index），弹出以后，如果这个栈是空的，就让i以前的数都等于maxHeights【i】即可，如果有元素，那么把以前的元素加着pre【top -1】，让后边的都等于maxHeights【i】即可。最后别忘了把下标push进去。然后右边是同理的，最后别忘了峰顶算了两次，减去一次。
class Solution {//单调栈解法，时间复杂度o（n）
public:
long long maximumSumOfHeights(vector<int>& maxHeights) {
int n = maxHeights.size();
long long res = 0;
vector<long long>pre(n), suf(n);
stack<int> stk1,stk2;//两个栈存放当前峰值左/右构造的最大值
for(int i = 0; i < n; ++i){
while(!stk1.empty() && maxHeights[stk1.top()] > maxHeights[i]){ stk1.pop();}
if(stk1.empty()){pre[i] = (long long )(i + 1) * maxHeights[i];}
else{
pre[i] = pre[stk1.top()] + (long long )(i - stk1.top()) * maxHeights[i];
}
stk1.push(i);//把下标push进去
}
for(int i = n -1; i >= 0; --i){
while(!stk2.empty() && maxHeights[stk2.top()] > maxHeights[i]){stk2.pop();}
if(stk2.empty()) {suf[i] = (long long )(n - i) * maxHeights[i];}
else{
suf[i] = suf[stk2.top()] + ((long long)(stk2.top() - i)) * maxHeights[i];
}
stk2.push(i);
res = max(res,suf[i] + pre[i] - maxHeights[i]);//maxHeights[i]算了两遍
}
return res;
}
};【1.25】2859.计算k置下标对应元素的和
2859. 计算 K 置位下标对应元素的和https://leetcode.cn/problems/sum-of-values-at-indices-with-k-set-bits/
本题其实就是一个求二进制的简单题目，大概率会想到用位运算解决
在c++中&表示的是按位与运算。当计算二进制中有多少个1的时候，可以配合位元算
num & (1 << i);//统计每一位上有1的数
sum++;//配合sum++可以统计二进制中是1的位的个数注意一点这个循环的大小，因为是int类型，最高就是32位，直接小于32就行
class Solution {
public:
int sumIndicesWithKSetBits(vector<int>& nums, int k) {
int res = 0;
for(int i = 0; i< nums.size();i++){
if(count(i) == k){
res+= nums[i];
}
}
return res;
}
int count(int num){
int sum = 0;
for(int i = 0; i < 32; i++){
if(num & (1 << i)){
sum++;
}
}
return sum;
}
};除了位元算，还有一种可以求一个数二进制的置为1的个数方法
int count(int num){
int sum = 0;
while(num){
sum += (num % 2);
num /= 2;
}
return sum;
}【1.26】2846.边权重均等查询
2846. 边权重均等查询https://leetcode.cn/problems/minimum-edge-weight-equilibrium-queries-in-a-tree/
2500+分hard题，超出水平范围太多，暂时跳过。
【1.27】2861.最大合金数
2861. 最大合金数https://leetcode.cn/problems/maximum-number-of-alloys/
看题目“所有合金都需要由同一台机器制造。”又给了个最大值budget，让求取得的最大合金数，也满足二段性，那就是二分法求解了，因为设置这个mid，当我们最大数设置为mid，那么比mid小的数就都不能取了。
1.设置这个二分，第一个点就是最大值可以稍微的小一点，我们可以设置为budget/1（单价最小就是1）+ 库存的最大量（其实根据木桶效应，应该是库存的最小量）
2.先置为false，遍历每一个机器的花费，再内层遍历每一个零件，求出每个零件加起来总共的spend，再和budget比对，如果比这个小，那么这个mid可以取，就进行变换，置为true，如果不行，再改right
3.在内层遍历的时候，要考虑if(composition[i][j] * (long)mid - stock[j] > 0)，这个很关键，库存够了就置为0，不能是负数，我一直卡在这。
//花费小于budget，求能创造合金的最大值，二分
class Solution {
public:
int maxNumberOfAlloys(int n, int k, int budget, vector<vector<int>>& composition, vector<int>& stock, vector<int>& cost) {
int left = 0;
//右侧值不用设置太大，考虑最大值
auto max = max_element(stock.begin(),stock.end());
int right = *max + budget;
int ans = 0;
while(left <= right){
int mid = left + ((right -left) / 2);//设置的最大值，当这个满足的时候，比他小的都不合适
bool flag = false;//如果可以制造出就用true
//遍历一遍每台机器花费
for(int i = 0; i < k; i++){
long spend = 0;
for(int j = 0; j < n; j++){
if(composition[i][j] * (long)mid - stock[j] > 0){
spend += (composition[i][j] * (long)mid - stock[j]) * cost[j];}
}
if(budget >= spend){
flag = true;
break;//第i类就能搞定了
}
}
if(flag){
ans = mid;
left = mid + 1;
}
else{
right = mid -1;
}
}
return ans;
}
};【1.28】365.水壶问题
365. 水壶问题https://leetcode.cn/problems/water-and-jug-problem/
这个问题除了用深度优先搜索（也是刚会用的），还可以用数学方法更好操作，贝祖定理解决，但是需要考虑的问题比较多。
1.先分析一下，这些操作的实质其实这个水的总量变化只能是x或者是y，因为首先操作的结果至少有一个桶是空的有一个是满的（把一个倒掉，或者加满），假如说把一个半满的水加满或者倒掉是没有意义的，因为等价于一开始就把它置为0或者加满。
2.所以我们的目标变成了找到一堆数组a和b来满足ax + by = z，那么只需满足z <= x + y的情况下， 如果a > 0,b > 0一定ok，如果a < 0，操作就是先给b加满，把b到给a，a倒掉，再把b剩下的到给a，如此反复。如果是b < 0 ，把操作反过来就行。
3.贝祖定理表示，如果要实现ax + by = z，只需要z整除x和y的最大公约数即可。
class Solution {
public:
bool canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
if(jug1Capacity + jug2Capacity < targetCapacity){
return false;
}
//这里贝组定理用之前考虑x或者y万一是0没有最大公约数
if(jug1Capacity == 0 ||jug2Capacity ==0){
return targetCapacity == 0 || jug1Capacity + jug2Capacity == targetCapacity;
}
else{
return targetCapacity % gcd(jug1Capacity,jug2Capacity) == 0;
}
}
};【1.29】514.自由之路
514. 自由之路https://leetcode.cn/problems/freedom-trail/
这是一道困难题，思路能想到是用dp来解，但是解法还是有一定难度的。分为几个步骤，逻辑要清晰。
- 代码主要分为几个步骤，首先是对king进行字母到位置的映射，然后创建dp初始化，然后dp函数的实现。
- 创建位置索引的时候，这种映射的构建是为了在后续动态规划的过程中更方便地获取每个字符在环形拨盘上的位置信息。
-
dp初始化初始值给个最大值
-
动态规划转移要分类，在i==0的时候第一个字符，不需要考虑前一个字符的位置，所以分开，对于不是第一个字符要进行一遍循环（对上一个字符的位置循环），进行dp函数的编写，最后输出dp最后一行的最小值
-
对于这种环形的可以顺时针逆时针转动的函数求最小值，这个函数值得记一下，加一个len就能完美解决负数问题。
class Solution { public: int getMin(int len,int a, int b){ return min((len + a - b) % len ,(len + b - a) % len); } int findRotateSteps(string ring, string key) { //第一步先建立ring中字母的位置索引 vector<int> pos[26]; for(int i = 0; i < ring.size(); i++){ pos[ring[i] - 'a'].push_back(i); } //第二步，创建dp初始化 vector<vector<int>> dp(key.size(),vector<int>(ring.size(),INT_MAX)); //第三步 动态规划状态转移 for(int i = 0; i < key.size(); i++){//遍历key的每个字符 for(auto j : pos[key[i] - 'a']){//遍历key【i】在圆盘出现的每个位置 if(i == 0){ dp[i][j] = min(dp[i][j],0 + getMin(ring.size(),0,j) + 1); continue; } //如果不是第一个，遍历前一个的字符的位置状态 for(auto k : pos[key[i - 1] - 'a']){ dp[i][j] = min(dp[i][j],dp[i - 1][k] + getMin(ring.size(),k,j) + 1); } } } return *min_element(dp.back().begin(),dp.back().end()); } };
【1.30】2808.使循环数组所有元素相等的最少秒数
2808. 使循环数组所有元素相等的最少秒数https://leetcode.cn/problems/minimum-seconds-to-equalize-a-circular-array/
1900分左右的题目，用哈希表解决，思路不算难，主要是昨天的题给了思路，一看题目就知道是一个圆环形状的，左右都能走。哈希表存一下出现的元素的索引i用数组存，因为可能有多个。按照圆环找mx/2的最小值就行。
- 先搞个哈希表，每个nums【i】对应的i值存到数组里，为了后续遍历的时候用
- 按照圆的方案去找相邻最远的值，求每个nums【i】的数值里距离最远的值，然后找最小值求出来即可。
- 在找个遍历中，先+n为了找圆环情况两个的距离，后边遍历的是相邻的。
class Solution {
public:
int minimumSeconds(vector<int>& nums) {
unordered_map<int,vector<int>> map;
int res = nums.size();
//先搞个哈希表，每个nums【i】对应的i值存到数组里
for(int i = 0; i < nums.size(); i++){
map[nums[i]].push_back(i);
}
//不要忘了找圈
for(auto& s : map){
int mx = s.second[0] + nums.size() - s.second.back();
for(int i = 1; i < s.second.size(); i++){
mx = max(mx, s.second[i] - s.second[i - 1]);
}
res = min(res, mx/2);
}
return res;
}
};【1.31】2760.找出不同元素数目差数组
2670. 找出不同元素数目差数组https://leetcode.cn/problems/find-the-distinct-difference-array/
哈希表，难点在于建立数组的时候的范围还有，运用哈希表去统计“从第i个数到最后一个数不同的数的数量”和“从第一个数到第i个数不同数的数量”
class Solution {
public:
vector<int> distinctDifferenceArray(vector<int>& nums) {
int n = nums.size();
vector<int> res;
unordered_set<int> st;
vector<int> suf(n + 1);//为了满足后边运算的时候suf(n -1)
for(int i = n - 1; i > 0; i--){
st.insert(nums[i]);
suf[i] = st.size();//从第i开始到结尾不同值的数量
}
st.clear();
for(int i = 0; i < n; i++){
st.insert(nums[i]);//从第一个数开始到第i个数不同值的数量
res.push_back(st.size() -suf[i + 1]);
}
return res;
}
};创建suf数组大小是n+1的时候，是为了后边满足运算的时候suf（n - 1）.
