问题集

构造连续子序列问题

问题形如:现有整数数组num,取其中任意个数,和为sum,即记为可以取到sum.

现问最少添加几个数才能取到1到n的所有数

一图流

现在可以构造[0,m],想构造m+1时

假设现在得到了 [0,m] 内的所有整数，如果此时新发现了一个整数 s，那么把 s加到已得到的数字中，就得到了[s,m+s]内的所有整数。

(1) 如果能找到一个 小于或等于 m + 1 的数,可以直接合并,得到[0,m+s]

(2) 如果下一个数大于m+1后，就无法构造出m+1,那么就要把 m+1 加到数组中(贪心思想,最大范围嘛,如果加的比m+1小那有点亏),这样就可以得到[m+1,m+m+1]的所有数,合并之前的[0,m]即[0,m+m+1]所有数

力扣题目

https://leetcode.cn/problems/patching-array/description/

class Solution {
public:
    int minPatches(vector<int>& nums, int n) {
        long long m = 0;
        int ans = 0;
        int index = 0;
        while(m<n){
            if(index < nums.size() && nums[index] <= m + 1){
                m += nums[index];
                index++;
            }else{
                m += m +1;
                ans++;
            }
        }
        return ans;
    }
};

https://leetcode.cn/problems/maximum-number-of-consecutive-values-you-can-make/

class Solution {
public:
    int getMaximumConsecutive(vector<int>& coins) {
        sort(coins.begin(),coins.end());
        int m = 0;
        for(int i = 0; i < coins.size(); i++){
            if(coins[i] > m+1) break;
            m += coins[i];
        }
        return m+1;
    }
};

中位数贪心

https://leetcode.cn/problems/minimum-moves-to-equal-array-elements-ii/description/

给你一个长度为 n 的整数数组 nums ，返回使所有数组元素相等需要的最小操作数。在一次操作中，你可以使数组中的一个元素加 1 或者减 1 。

翻译一下就是让这数组里的所有元素都变为一个数,怎么最快.

直接给个结论,变成中位数最快

假如现在的数组是1,2,3,4,5手算一下,都变成2需要7步,如果都变成3需要6步

7是如何到6的呢

L代表左边有几个数,R代表右边有几个数

我们远离了1和2,所以1,2到我们的距离分别加一

我们接近了3,4,5所以3,4,5到我们的距离分别减一

+2-3=-1

所以7-1=6

假如再往右一步呢,远离1,2,3,接近4,5.总体距离加一变回了7

所以可以感觉出来中位数就是最小次数(没有严格证明,感受一下吧)

统计移除递增子数组的数目

https://leetcode.cn/problems/count-the-number-of-incremovable-subarrays-ii/

给你一个下标从 0 开始的 正 整数数组 nums 。

如果 nums 的一个子数组满足：移除这个子数组后剩余元素 严格递增 ，那么我们称这个子数组为 移除递增 子数组。比方说，[5, 3, 4, 6, 7] 中的 [3, 4] 是一个移除递增子数组，因为移除该子数组后，[5, 3, 4, 6, 7] 变为 [5, 6, 7] ，是严格递增的。

请你返回 nums 中 移除递增 子数组的总数目。

注意 ，剩余元素为空的数组也视为是递增的。

思路是:逆序部分必须去掉,留下左右两端的有序部分.枚举右边,然后看每次左边能接几个上去保持有序(即左边的最大要小于右边的最小)

class Solution {
public:
    long long incremovableSubarrayCount(vector<int>& nums) {
        int n = nums.size();
        int start = 0, end = 0;//分别为图中两个红色竖,即第一个逆序的起点和最后一个逆序的终点
        for(int i = 0; i < nums.size() - 1; i++){
            if(nums[i+1] <= nums[i]) {
                start = i + 1;
                break;
            }
        }
        for(int i = nums.size() - 1; i > 0; i--){
            if(nums[i-1] >= nums[i]) {
                end = i - 1;
                break;
            }
        }
        if(!start) return 1ll*n*(n+1)/2; //没有逆序

        long long ans = 0;
        for(int r = end; r < n-1; r++){ //枚举右边界(紫色)
            int l = start;
            while(l > 0 && nums[l-1] >= nums[r+1]) l--; //看看左边界第几个能接起来(蓝色)
            ans += l + 1; //几种情况
        }
        return ans + start + 1; //最后为空的时候,前面随便去几个,即start+1
    }                                                  
};

蓝桥取模

https://www.lanqiao.cn/problems/9989/learning/?contest_id=154

给A,B,low,high

请问[1,A]任取一个数对[1,B]任取一个数取模结果在[low,high]范围里的可能有几种

官解一图流

#include <iostream>
using namespace std;
typedef long long ll;

ll func(ll a, ll b, ll high) {
    if (high < 0) return 0; 
    ll ans = 0;
    for (ll i = 1; i <= b; i++) {
        ll n = a / i;
        ans += n * (min(high, i - 1) + 1);//处理前面几段
        ans += min(high, a % i) + 1;//处理最后一段
        ans--;
    } 
    return ans;
}

int main() {
    ll a, b, low, high;
    cin >> a >> b >> low >> high;
    cout << func(a, b, high) - func(a, b, low - 1) << endl;
    return 0;
}

转换字符串的最小成本(最短路问题)

https://leetcode.cn/problems/minimum-cost-to-convert-string-i/description/

主要想借这题复习一下最短路

还没写完~