- Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.
- This article also participated in the “Digitalstar Project” to win a creative gift package and creative incentive money.
Thank you very much for reading this article. Welcome [👍 like] [⭐ collect] [📝 comment] ~ Give up is not difficult, But insists it must be very cool ~ hope we all can be a little bit of progress every day ~ in this paper, from two headed white hat original ~ https://juejin.cn/user/2771185768884824/posts blog
1476. Subrectangle query:
You implement a class SubrectangleQueries, whose constructor takes a rectangle of Rows x cols (represented here as an integer matrix), and supports the following two operations:
- updateSubrectangle(int row1, int col1, int row2, int col2, int newValue)
- Update the subrectangle with (Row1,col1) as the upper left corner and (Row2,col2) as the lower right corner with newValue.
- getValue(int row, int col)
- Returns the current value of the coordinate (row,col) in the rectangle.
Sample 1
Input: ["SubrectangleQueries","getValue","updateSubrectangle","getValue","getValue","updateSubrectangle","getValue","getValue" ] [[[[1, 2, 1], and 4 [4], [3, 2, 1], [1,1,1]]], [0, 2], [0,0,3,2,5], [0, 2], [3, 1], [3,0,3,2,10], [3, 1], [0, 2]] output: [null, 1, null, 5, 5, null, 10, 5) : Rectanglequeries = new rectanglequeries ([1,2,1],[4,3,4],[3,2,1],[1,1,1]]); / / initial (4 x3) rectangle is as follows: / / 1 1/2/4, 3, 4, / / 1/2/3 1 1 1 subrectangleQueries getValue (0, 2); / / return 1 subrectangleQueries. UpdateSubrectangle (0, 0, 3, 2, 5); / / the updated rectangle into: / / 5 5 5 / / / / 5 5 5 / / 5 subrectangleQueries. GetValue (0, 2); / / return 5 subrectangleQueries. GetValue (3, 1); / / return 5 subrectangleQueries. UpdateSubrectangle (3, 0, 3, 2, 10); / / rectangle into: after this update may / / / / 5 5 5 5 5 / / / / 10 10. 10 subrectangleQueries getValue (3, 1); / / return 10 subrectangleQueries getValue (0, 2); / / return 5Copy the codeThe sample 2
Input: ["SubrectangleQueries","getValue","updateSubrectangle","getValue","getValue","updateSubrectangle","getValue"] ,1,1 [[[[1], [2,2,2], [3 filling]]], [0, 0], [0,0,2,2,100], [0, 0], [2],,1,2,2,20 [1], [2]] output: [null, 1, null, 100100, null, 20] explanation: Rectanglequeries SubrectangleQueries = new rectanglequeries ([1,1,1],[2,2,2],[3,3]]); subrectangleQueries.getValue(0, 0); / / return 1 subrectangleQueries. UpdateSubrectangle (0, 0, 2, 2, 100); subrectangleQueries.getValue(0, 0); / / return 100 subrectangleQueries getValue (2, 2); / / return 100 subrectangleQueries. UpdateSubrectangle (1, 1, 2, 2, 20). subrectangleQueries.getValue(2, 2); / / return 20Copy the codeprompt
- There are up to 500 updateSubrectangle and getValue operations.
- 1 <= rows, cols <= 100
- rows == rectangle.length
- cols == rectangle[i].length
- 0 <= row1 <= row2 < rows
- 0 <= col1 <= col2 < cols
- 1 <= newValue, rectangle[i][j] <= 10^9
- 0 <= row < rows
- 0 <= col < cols
Analysis of the
- The initial value of the rectangle must be saved.
- And the most intuitive way to do that is to update the rectangle every time and just return the value.
- According to the prompt, we can know that the rectangle is 100 * 100, namely each update values most likely need to update the 10000 values, but number of updates will have 500 times, so we can record each update operation, when the values we pour the search history operation, if the point had not been updated, the original value. Thus, the time complexity of the update operation is only O(1), and the value operation is at most 500 cycles to find the history.
- Which way is not absolute, we can depend on the actual situation, in this case, there are more values than operations, so we don’t do updates, but we save the history operations.
Answer key
java
class SubrectangleQueries {
private final int[][] rectangle;
private List<int[]> history = new ArrayList<>();
public SubrectangleQueries(int[][] rectangle) {
this.rectangle = rectangle;
}
public void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
history.add(new int[]{row1, col1, row2, col2, newValue});
}
public int getValue(int row, int col) {
for (int i = history.size() - 1; i >= 0; --i) {
int[] h = history.get(i);
if (row >= h[0] && row <= h[2]
&& col >= h[1] && col <= h[3]) {
return h[4]; }}returnrectangle[row][col]; }}/** * Your SubrectangleQueries object will be instantiated and called as such: * SubrectangleQueries obj = new SubrectangleQueries(rectangle); * obj.updateSubrectangle(row1,col1,row2,col2,newValue); * int param_2 = obj.getValue(row,col); * /
Copy the codec
typedef struct {
int value[100] [100];
int history[500] [5];
int history_size;
} SubrectangleQueries;
SubrectangleQueries *subrectangleQueriesCreate(int **rectangle, int rectangleSize, int *rectangleColSize) {
SubrectangleQueries *obj = NULL;
obj = (SubrectangleQueries *) malloc(sizeof(SubrectangleQueries));
if (obj == NULL) {
return NULL;
}
for (int i = 0; i < rectangleSize; ++i) {
for (int j = 0; j < rectangleColSize[i]; ++j) { obj->value[i][j] = rectangle[i][j]; }}return obj;
}
void
subrectangleQueriesUpdateSubrectangle(SubrectangleQueries *obj, int row1, int col1, int row2, int col2, int newValue) {
int *h = obj->history[obj->history_size++];
h[0] = row1;
h[1] = col1;
h[2] = row2;
h[3] = col2;
h[4] = newValue;
}
int subrectangleQueriesGetValue(SubrectangleQueries *obj, int row, int col) {
for (int i = obj->history_size - 1; i >= 0; --i) {
int *h = obj->history[i];
if (row >= h[0] && row <= h[2]
&& col >= h[1] && col <= h[3]) {
return h[4]; }}return obj->value[row][col];
}
void subrectangleQueriesFree(SubrectangleQueries *obj) {
free(obj);
}
/** * Your SubrectangleQueries struct will be instantiated and called as such: * SubrectangleQueries* obj = subrectangleQueriesCreate(rectangle, rectangleSize, rectangleColSize); * subrectangleQueriesUpdateSubrectangle(obj, row1, col1, row2, col2, newValue); * int param_2 = subrectangleQueriesGetValue(obj, row, col); * subrectangleQueriesFree(obj); * /
Copy the codec++
class SubrectangleQueries {
private:
vector<vector<int>> rectangle;
vector<vector<int>> history;
public:
SubrectangleQueries(vector<vector<int>>& rectangle) : rectangle(rectangle) {
}
void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
history.push_back({row1, col1, row2, col2, newValue});
}
int getValue(int row, int col) {
for (int i = history.size() - 1; i >= 0; --i) {
vector<int> h = history[i];
if (row >= h[0] && row <= h[2]
&& col >= h[1] && col <= h[3]) {
return h[4]; }}returnrectangle[row][col]; }};/** * Your SubrectangleQueries object will be instantiated and called as such: * SubrectangleQueries* obj = new SubrectangleQueries(rectangle); * obj->updateSubrectangle(row1,col1,row2,col2,newValue); * int param_2 = obj->getValue(row,col); * /
Copy the codepython
class SubrectangleQueries:
def __init__(self, rectangle: List[List[int]]) :
self.rectangle = rectangle
self.history = []
def updateSubrectangle(self, row1: int, col1: int, row2: int, col2: int, newValue: int) - >None:
self.history.append((row1, col1, row2, col2, newValue))
def getValue(self, row: int, col: int) - >int:
for i in range(len(self.history) - 1, -1, -1):
row1, col1, row2, col2, val = self.history[i]
if row1 <= row <= row2 and col1 <= col <= col2:
return val
return self.rectangle[row][col]
# Your SubrectangleQueries object will be instantiated and called as such:
# obj = SubrectangleQueries(rectangle)
# obj.updateSubrectangle(row1,col1,row2,col2,newValue)
# param_2 = obj.getValue(row,col)
Copy the codego
type SubrectangleQueries struct {
rectangle [][]int
history [][]int
}
func Constructor(rectangle [][]int) SubrectangleQueries {
return SubrectangleQueries{rectangle: rectangle}
}
func (this *SubrectangleQueries) UpdateSubrectangle(row1 int, col1 int, row2 int, col2 int, newValue int) {
this.history = append(this.history, []int{row1, col1, row2, col2, newValue})
}
func (this *SubrectangleQueries) GetValue(row int, col int) int {
for i := len(this.history) - 1; i >= 0; i-- {
h := this.history[i]
if h[0] <= row && row <= h[2] && h[1] <= col && col <= h[3] {
return h[4]}}return this.rectangle[row][col]
}
/** * Your SubrectangleQueries object will be instantiated and called as such: * obj := Constructor(rectangle); * obj.UpdateSubrectangle(row1,col1,row2,col2,newValue); * param_2 := obj.GetValue(row,col); * /
Copy the coderust
struct SubrectangleQueries {
rectangle: Vec<Vec<i32>>,
history: Vec< (i32.i32.i32.i32.i32) >}/** * `&self` means the method takes an immutable reference. * If you need a mutable reference, change it to `&mut self` instead. */
impl SubrectangleQueries {
fn new(rectangle: Vec<Vec<i32- > > >)Self {
Self {rectangle, history: vec![]}}fn update_subrectangle(&mut self, row1: i32, col1: i32, row2: i32, col2: i32, new_value: i32) {
self.history.push((row1, col1, row2, col2, new_value));
}
fn get_value(&self, row: i32, col: i32) - >i32 {
for &(r1, c1, r2, c2, val) in self.history.iter().rev() {
if r1 <= row && row <= r2 && c1 <= col && col <= c2 {
return val
}
}
self.rectangle[row as usize][col as usize]}}/** * Your SubrectangleQueries object will be instantiated and called as such: * let obj = SubrectangleQueries::new(rectangle); * obj.update_subrectangle(row1, col1, row2, col2, newValue); * let ret_2: i32 = obj.get_value(row, col); * /
Copy the code