力扣第446場周賽

?有事沒趕上, 賽后模擬了一下, 分享一下我的解題思路和做題感受??

1.執行指令后的得分

題目鏈接如下：力扣

給你兩個數組：instructions?和?values，數組的長度均為?n。

你需要根據以下規則模擬一個過程：

從下標?i = 0?的第一個指令開始，初始得分為 0。
如果?instructions[i]?是?"add"：
將?values[i]?加到你的得分中。
移動到下一個指令?(i + 1)。

如果?instructions[i]?是?"jump"：
移動到下標為?(i + values[i])?的指令，但不修改你的得分。

當以下任一情況發生時，過程會終止：

越界（即?i < 0?或?i >= n），或
嘗試再次執行已經執行過的指令。被重復訪問的指令不會再次執行。

返回過程結束時的得分。

示例 1：

輸入：?instructions = ["jump","add","add","jump","add","jump"], values = [2,1,3,1,-2,-3]

輸出：?1

解釋：

從下標?0 開始模擬過程：

下標 0：指令是?"jump"，移動到下標?0 + 2 = 2。
下標 2：指令是?"add"，將?values[2] = 3?加到得分中，移動到下標?3。得分變為 3。
下標 3：指令是?"jump"，移動到下標?3 + 1 = 4。
下標 4：指令是?"add"，將?values[4] = -2?加到得分中，移動到下標?5。得分變為 1。
下標 5：指令是?"jump"，移動到下標?5 + (-3) = 2。
下標 2：已經訪問過。過程結束。

示例 2：

輸入：?instructions = ["jump","add","add"], values = [3,1,1]

輸出：?0

解釋：

從下標?0 開始模擬過程：

下標 0：指令是?"jump"，移動到下標?0 + 3 = 3。
下標 3：越界。過程結束。

示例 3：

輸入：?instructions = ["jump"], values = [0]

輸出：?0

解釋：

從下標?0 開始模擬過程：

下標 0：指令是?"jump"，移動到下標?0 + 0 = 0。
下標 0：已經訪問過。過程結束。

提示：

n == instructions.length == values.length
1 <= n <= 10^5
instructions[i]?只能是?"add"?或?"jump"。
-105?<= values[i] <= 10^5

解題思路：模擬的時候wa了好幾次，注意不要越界

class Solution {
public:long long calculateScore(vector<string>& a, vector<int>& b) {unordered_map<int,int> mp;int i=0; long long score=0;while(i<a.size()){if(a[i]=="jump"){if(mp[i]) break;mp[i]=1;i=i+b[i];if (i >= a.size() || i < 0) { break;}}if(a[i]=="add"){if(mp[i]) break;mp[i]=1;score+=b[i];// cout<<score<<endl;i++;}}return score;}
};

2.非遞減數組的最大長度?

題目鏈接如下：力扣

給你一個整數數組 nums。在一次操作中，你可以選擇一個子數組，并將其替換為一個等于該子數組最大值的單個元素。

返回經過零次或多次操作后，數組仍為非遞減的情況下，數組可能的最大長度。

子數組是數組中一個連續、非空的元素序列。

示例 1：

輸入： nums = [4,2,5,3,5]

輸出： 3

解釋：

實現最大長度的一種方法是：

將子數組 nums[1..2] = [2, 5] 替換為 5 → [4, 5, 3, 5]。
將子數組 nums[2..3] = [3, 5] 替換為 5 → [4, 5, 5]。
最終數組 [4, 5, 5] 是非遞減的，長度為 3。

示例 2：

輸入： nums = [1,2,3]

輸出： 3

解釋：

無需任何操作，因為數組 [1,2,3] 已經是非遞減的。

提示：

1 <= nums.length <= 2 * 10^5
1 <= nums[i] <= 2 * 10^5

解題思路：?題意是, 找到遞減的子數組, 然后將該子數組用子數組中的最大值進行替換，保證剩余數組的長度盡可能長

class Solution {
public:int maximumPossibleSize(vector<int>& nums) {int n = nums.size();int count = 0;int preMax = 0;int i = 0;while (i < n) {if (nums[i] >= preMax) {preMax = nums[i];count++;i++;}else {int curNum = nums[i];int j = i + 1;while (j < n && curNum < preMax) {curNum = max(curNum, nums[j]);j++;}if (curNum < preMax) {break;}preMax = curNum;count++;i = j;}}return count;}
};

?3.?求出數組的 X 值 I

題目鏈接如下：力扣

給你一個由?正?整數組成的數組?nums，以及一個?正?整數?k。

你可以對?nums?執行?一次?操作，該操作中可以移除任意?不重疊?的前綴和后綴，使得?nums?仍然?非空?。

你需要找出?nums?的?x 值，即在執行操作后，剩余元素的?乘積?除以?k?后的?余數?為?x?的操作數量。

返回一個大小為?k?的數組?result，其中?result[x]?表示對于?0 <= x <= k - 1，nums?的?x 值。

數組的?前綴?指從數組起始位置開始到數組中任意位置的一段連續子數組。

數組的?后綴?是指從數組中任意位置開始到數組末尾的一段連續子數組。

子數組?是數組中一段連續的元素序列。

注意，在操作中選擇的前綴和后綴可以是?空的?。

示例 1：

輸入：?nums = [1,2,3,4,5], k = 3

輸出：?[9,2,4]

解釋：

對于?x = 0，可行的操作包括所有不會移除?nums[2] == 3?的前后綴移除方式。
對于?x = 1，可行操作包括：
移除空前綴和后綴?[2, 3, 4, 5]，nums?變為?[1]。
移除前綴?[1, 2, 3]?和后綴?[5]，nums?變為?[4]。

對于?x = 2，可行操作包括：
移除空前綴和后綴?[3, 4, 5]，nums?變為?[1, 2]。
移除前綴?[1]?和后綴?[3, 4, 5]，nums?變為?[2]。
移除前綴?[1, 2, 3]?和空后綴，nums?變為?[4, 5]。
移除前綴?[1, 2, 3, 4]?和空后綴，nums?變為?[5]。

示例 2：

輸入：?nums = [1,2,4,8,16,32], k = 4

輸出：?[18,1,2,0]

解釋：

對于?x = 0，唯一?不?得到?x = 0?的操作有：
移除空前綴和后綴?[4, 8, 16, 32]，nums?變為?[1, 2]。
移除空前綴和后綴?[2, 4, 8, 16, 32]，nums?變為?[1]。
移除前綴?[1]?和后綴?[4, 8, 16, 32]，nums?變為?[2]。

對于?x = 1，唯一的操作是：
移除空前綴和后綴?[2, 4, 8, 16, 32]，nums?變為?[1]。

對于?x = 2，可行操作包括：
移除空前綴和后綴?[4, 8, 16, 32]，nums?變為?[1, 2]。
移除前綴?[1]?和后綴?[4, 8, 16, 32]，nums?變為?[2]。

對于?x = 3，沒有可行的操作。

示例 3：

輸入：?nums = [1,1,2,1,1], k = 2

輸出：?[9,6]

提示：

1 <= nums[i] <= 10^9
1 <= nums.length <= 10^5
1 <= k <= 5?

?解題思路：看不懂題的可以直接看我下面提供的圖片

1. 簡單來說就是刪除一個前綴/后綴后的子數組中元素的乘積除以?k?的余數?x，并返回一個數組 result，其中?result[x]?表示余數為?x?的子數組數量

2. 因為可以刪除0個元素, 1個元素, 2個元素, .... , 多個前綴/后綴, 統計刪除后的子數組，其實就是在統計所有的子數組。

3. 將數組分兩類，一種是不包含nums[i]%k==0, 另一種是包含nums[i]%k==0, 因為是求子數組的乘積%k, 所以只要包含nums[i]%k==0, 它的余數肯定是0, 其他不包含 nums[i]%k==0的子數組的乘積的余數就可能是1,2,3,...,k-1。所以我們就以nums[i]%k==0為分割點分開進行統計(詳細在下面代碼中), 在每個不包含 nums[i]%k==0的子數組中, 采用動態規劃進行統計, 其中pre[x]表示以?nums[i-1]?結尾的子數組，乘積余數為 x?的數量,? cur[x]：表示以?nums[i]?結尾的子數組，乘積余數為x的數量。dp_counts[x]：最終統計所有子數組的乘積余數 x?的總數

4. 補充解釋一下,?int a=nums[i]%k;? int b=(i*a)%k; 當前元素為nums[i], %k的余數為 a, 其實我們只需要將 a和pre數組中的余數進行想乘即可，也就是 b= (i%a)%k, 看新子數組是否能產生新的余數, eg: 5%3=2, 再加nums[i]=2, 原本需要計算 5*2%3=1, 其實現在只需計算? 2*2%3=1即可

5. 數學：計算某一數組中子數組的個數 n*(n+1)/2;?

? ?eg: nums=[1,2,3] 子數組：[1], [2], [3], [1,2], [1,2,3] ,[2,3], total_sub=3*4/2=6?

class Solution {
public:vector<long long> resultArray(vector<int>& nums, int k) {int n=nums.size(); long long Total_Sub=(long long)n*(n+1)/2;//1. 找到以nums[i]%k==0為分界點的子區間vector<pair<int,int>> sub_interval;int start=0;for(int i=0;i<=n;i++){if(i==n||nums[i]%k==0){if(start<i){sub_interval.emplace_back(start,i-1);}start=i+1;}}//2. 統計各個子數組中余數的相關信息long long total_none_sub=0;vector<long long> dp_counts(k,0);for(auto& x:sub_interval){int l=x.first,r=x.second;int len=r-l+1;total_none_sub+=(long long)len*(len+1)/2;vector<long long> pre(k,0);for(int i=l;i<=r;i++){int a=nums[i]%k;vector<long long> cur(k,0);for(int i=0;i<k;i++){if(pre[i]==0) continue;int b=(i*a)%k;cur[b]+=pre[i];}cur[a]+=1;for(int i=0;i<k;i++){dp_counts[i]+=cur[i];}pre.swap(cur);}}// 3. 至少包含一個nums[i]%k=0 的子數組的數量long long zero_sub=Total_Sub-total_none_sub;// 4. 統計結果vector<long long> result(k,0);result[0]=dp_counts[0]+zero_sub;for(int i=1;i<k;i++){result[i]=dp_counts[i];}return result;}
};

4.?求出數組的 X 值 II?

題目鏈接如下：3525. 求出數組的 X 值 II - 力扣（LeetCode）

給你一個由?正整數?組成的數組?nums?和一個?正整數?k。同時給你一個二維數組?queries，其中?queries[i] = [indexi, valuei, starti, xi]。

你可以對?nums?執行?一次?操作，移除?nums?的任意?后綴?，使得?nums?仍然非空。

給定一個?x，nums?的?x值?定義為執行以上操作后剩余元素的?乘積?除以?k?的?余數?為?x?的方案數。

對于?queries?中的每個查詢，你需要執行以下操作，然后確定?xi?對應的?nums?的?x值：

將?nums[indexi]?更新為?valuei。僅這個更改在接下來的所有查詢中保留。
移除?前綴?nums[0..(starti?- 1)]（nums[0..(-1)]?表示?空前綴?）。

返回一個長度為?queries.length?的數組?result，其中?result[i]?是第?i?個查詢的答案。

數組的一個?前綴?是從數組開始位置到任意位置的子數組。

數組的一個?后綴?是從數組中任意位置開始直到結束的子數組。

子數組?是數組中一段連續的元素序列。

注意：操作中所選的前綴或后綴可以是?空的?。

注意：x值在本題中與問題 I 有不同的定義。

示例 1：

輸入：?nums = [1,2,3,4,5], k = 3, queries = [[2,2,0,2],[3,3,3,0],[0,1,0,1]]

輸出：?[2,2,2]

解釋：

對于查詢 0，nums?變為?[1, 2, 2, 4, 5]?。移除空前綴后，可選操作包括：
移除后綴?[2, 4, 5]?，nums?變為?[1, 2]。
不移除任何后綴。nums?保持為?[1, 2, 2, 4, 5]，乘積為 80，對 3 取余為 2。

對于查詢 1，nums?變為?[1, 2, 2, 3, 5]?。移除前綴?[1, 2, 2]?后，可選操作包括：
不移除任何后綴，nums?為?[3, 5]。
移除后綴?[5]?，nums?為?[3]。

對于查詢 2，nums?保持為?[1, 2, 2, 3, 5]?。移除空前綴后。可選操作包括：
移除后綴?[2, 2, 3, 5]。nums?為?[1]。
移除后綴?[3, 5]。nums?為?[1, 2, 2]。

示例 2：

輸入：?nums = [1,2,4,8,16,32], k = 4, queries = [[0,2,0,2],[0,2,0,1]]

輸出：?[1,0]

解釋：

對于查詢 0，nums?變為?[2, 2, 4, 8, 16, 32]。唯一可行的操作是：
移除后綴?[2, 4, 8, 16, 32]。

對于查詢 1，nums?仍為?[2, 2, 4, 8, 16, 32]。沒有任何操作能使余數為 1。

示例 3：

輸入：?nums = [1,1,2,1,1], k = 2, queries = [[2,1,0,1]]

輸出：?[5]

提示：

1 <= nums[i] <= 10^9
1 <= nums.length <= 10^5
1 <= k <= 5
1 <= queries.length <= 2 * 10^4
queries[i] == [indexi, valuei, starti, xi]
0 <= indexi?<= nums.length - 1
1 <= valuei?<= 10^9
0 <= starti?<= nums.length - 1
0 <= xi?<= k - 1

解題思路：這道題，群里有人調了一個多小時，才寫出來

1. 題意就是, 計算左端點為start, 右端點為start, start+1,....,n-1, 這一共有n-start個子數組, 元素乘積模k為x的子數組的個數

2. 分治計算 [l,r], 也就是左端點為l, 右端點為l, l+1, ... , r 的子數組的個數, 滿足元素乘積取模k為x

3. 題目中既有查詢, 合并又有修改，類似于前面那道題, M=(l+r)/2, 將右側的對應的余數的個數合并到左側

4. 下面代碼中的線段樹板子是抄的大佬的, 具體修改的部分已經在代碼中指出。

class SegmentTree {int n; int k; using T = pair<int, array<int, 5>>;vector<T> tree;//1. 修改T merge_val(T a, T b) const {auto [x,cnt]=a;for(int i=0;i<k;i++){cnt[x*i%k]+=b.second[i];}return {x*b.first%k,cnt};}//2. 修改T new_val(int val) const {int x = val % k;array<int, 5> cnt{};cnt[x]=1;return {x, cnt};}void maintain(int node) {tree[node] = merge_val(tree[node * 2], tree[node * 2 + 1]);}void build(const vector<int>& a, int node, int l, int r) {if (l == r) { tree[node] = new_val(a[l]);return;}int m = (l + r) / 2;build(a, node * 2, l, m); build(a, node * 2 + 1, m + 1, r); maintain(node);}void update(int node, int l, int r, int i, int val) {if (l == r) { tree[node] = new_val(val);return;}int m = (l + r) / 2;if (i <= m) {update(node * 2, l, m, i, val);} else {  update(node * 2 + 1, m + 1, r, i, val);}maintain(node);}T query(int node, int l, int r, int ql, int qr) const {if (ql <= l && r <= qr) { return tree[node];}int m = (l + r) / 2;if (qr <= m) {  return query(node * 2, l, m, ql, qr);}if (ql > m) {  return query(node * 2 + 1, m + 1, r, ql, qr);}T l_res = query(node * 2, l, m, ql, qr);T r_res = query(node * 2 + 1, m + 1, r, ql, qr);return merge_val(l_res, r_res);}
public:// SegmentTree(int n, T init_val) : SegmentTree(vector<T>(n, init_val)) {}SegmentTree(const vector<int>& a, int k) : k(k), n(a.size()), tree(2 << bit_width(a.size() - 1)) {build(a, 1, 0, n - 1);}void update(int i, int val) {update(1, 0, n - 1, i, val);}T query(int ql, int qr) const {return query(1, 0, n - 1, ql, qr);}T get(int i) const {return query(1, 0, n - 1, i, i);}
};
class Solution {
public:vector<int> resultArray(vector<int>& nums, int k, vector<vector<int>>& queries) {SegmentTree t(nums,k);int n=nums.size();vector<int> ans;for(auto& it:queries){//1. 按題意先修改t.update(it[0],it[1]);//2. 刪除前綴和后auto [x,cnt]=t.query(it[2],n-1);ans.push_back(cnt[it[3]]);}return ans;}
};
// queries[i] = [indexi, valuei, starti, xi]