[leetcode] 1476. Subrectangle Queries

[leetcode] 1476. Subrectangle Queries

Description

Implement the class SubrectangleQueries which receives a rows x cols rectangle as a matrix of integers in the constructor and supports two methods:

updateSubrectangle(int row1, int col1, int row2, int col2, int newValue)

Updates all values with newValue in the subrectangle whose upper left coordinate is (row1,col1) and bottom right coordinate is (row2,col2).

getValue(int row, int col)

Returns the current value of the coordinate (row,col) from the rectangle.

Example 1:

Input["SubrectangleQueries","getValue","updateSubrectangle","getValue","getValue","updateSubrectangle","getValue","getValue"][[[[1,2,1],[4,3,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]ExplanationSubrectangleQueries subrectangleQueries = new SubrectangleQueries([[1,2,1],[4,3,4],[3,2,1],[1,1,1]]); // The initial rectangle (4x3) looks like:// 1 2 1// 4 3 4// 3 2 1// 1 1 1subrectangleQueries.getValue(0, 2); // return 1subrectangleQueries.updateSubrectangle(0, 0, 3, 2, 5);// After this update the rectangle looks like:// 5 5 5// 5 5 5// 5 5 5// 5 5 5 subrectangleQueries.getValue(0, 2); // return 5subrectangleQueries.getValue(3, 1); // return 5subrectangleQueries.updateSubrectangle(3, 0, 3, 2, 10);// After this update the rectangle looks like:// 5 5 5// 5 5 5// 5 5 5// 10 10 10 subrectangleQueries.getValue(3, 1); // return 10subrectangleQueries.getValue(0, 2); // return 5

Example 2:

Input["SubrectangleQueries","getValue","updateSubrectangle","getValue","getValue","updateSubrectangle","getValue"][[[[1,1,1],[2,2,2],[3,3,3]]],[0,0],[0,0,2,2,100],[0,0],[2,2],[1,1,2,2,20],[2,2]]Output[null,1,null,100,100,null,20]ExplanationSubrectangleQueries subrectangleQueries = new SubrectangleQueries([[1,1,1],[2,2,2],[3,3,3]]);subrectangleQueries.getValue(0, 0); // return 1subrectangleQueries.updateSubrectangle(0, 0, 2, 2, 100);subrectangleQueries.getValue(0, 0); // return 100subrectangleQueries.getValue(2, 2); // return 100subrectangleQueries.updateSubrectangle(1, 1, 2, 2, 20);subrectangleQueries.getValue(2, 2); // return 20

Constraints:

There will be at most 500 operations considering both methods: updateSubrectangle and getValue.1 <= rows, cols <= 100rows == rectangle.lengthcols == rectangle[i].length0 <= row1 <= row2 < rows0 <= col1 <= col2 < cols1 <= newValue, rectangle[i][j] <= 10^90 <= row < rows0 <= col < cols

分析

题目的意思是：给定一个矩阵，实现矩阵的update和get操作，如果按照题目暴力破解的话，肯定会超时。仔细分析才发现，可以先在update的时候把坐标和值存起来，然后在get的时候判断坐标是否落入该区间，如果没有则返回rectangle相应位置的值，有则返回该区间所对应的值。

代码

class SubrectangleQueries: def __init__(self, rectangle: List[List[int]]): self.rectangle=rectangle self.pos=[] def updateSubrectangle(self, row1: int, col1: int, row2: int, col2: int, newValue: int) -> None: self.pos.append([row1,col1,row2,col2,newValue]) def getValue(self, row: int, col: int) -> int: if(len(self.pos)==0): return self.rectangle[row][col] else: t=-1 for p in self.pos: row1,col1,row2,col2,val=p if((row>=row1 and row<=row2) and (col>=col1 and col<=col2)): t=val if(t==-1): return self.rectangle[row][col] return t # 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)

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。