資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學科
時尚研究
法律研究C++中的範圍加法
假設我們有一個大小為 n 的陣列，該陣列初始化為 0，我們還有一個值 k，我們將執行 k 次更新操作。每個操作將表示為三元組： [startIndex, endIndex, inc]，其中 inc 將子陣列 A[startIndex ... endIndex]（包括 startIndex 和 endIndex）的每個元素遞增。我們必須找出在執行所有 k 次操作後修改後的陣列。
因此，如果輸入類似於 length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]，那麼輸出將為 [- 2,0,3,5,3]
為了解決這個問題，我們將遵循以下步驟 -
定義大小為 n 的陣列 ret
對於初始化 i := 0，當 i < a 的大小，更新（增加 i 1），操作 -
l := a[i, 0]
r := a[i, 1] + 1
ret[l] := ret[l] + a[i, 2]
如果 r < n，那麼 -
ret[r] := ret[r] - a[i, 2]
對於初始化 i := 1，當 i < n，更新（增加 i 1），操作 -
ret[i] := ret[i] + ret[i - 1]
返回 ret
示例
讓我們看看以下實現以更好地理解 -
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto< v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int< getModifiedArray(int n, vector& a) {
vector<int< ret(n);
for (int i = 0; i < a.size(); i++) {
int l = a[i][0];
int r = a[i][1] + 1;
ret[l] += a[i][2];
if (r < n) {
ret[r] -= a[i][2];
}
}
for (int i = 1; i < n; i++) {
ret[i] += ret[i - 1];
}
return ret;
}
};
main(){
Solution ob;
vector<vector<int<> v = {{1,3,2},{2,4,3},{0,2,-2}};
print_vector(ob.getModifiedArray(5,v));
}輸入
5, {{1,3,2},{2,4,3},{0,2,-2}}輸出
[-2, 0, 3, 5, 3, ]
更新於： 2020 年 11 月 19 日
178 次瀏覽
廣告