Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/631.html
631. Design Excel Sum Formula
Level
Hard
Description
Your task is to design the basic function of Excel and implement the function of sum formula. Specifically, you need to implement the following functions:
Excel(int H, char W): This is the constructor. The inputs represents the height and width of the Excel form. H is a positive integer, range from 1 to 26. It represents the height. W is a character range from ‘A’ to ‘Z’. It represents that the width is the number of characters from ‘A’ to W. The Excel form content is represented by a height * width 2D integer array C, it should be initialized to zero. You should assume that the first row of C starts from 1, and the first column of C starts from ‘A’.
void Set(int row, char column, int val): Change the value at C(row, column) to be val.
int Get(int row, char column): Return the value at C(row, column).
int Sum(int row, char column, List of Strings : numbers): This function calculate and set the value at C(row, column), where the value should be the sum of cells represented by numbers. This function return the sum result at C(row, column). This sum formula should exist until this cell is overlapped by another value or another sum formula.
numbers is a list of strings that each string represent a cell or a range of cells. If the string represent a single cell, then it has the following format: ColRow. For example, “F7” represents the cell at (7, F).
If the string represent a range of cells, then it has the following format: ColRow1:ColRow2. The range will always be a rectangle, and ColRow1 represent the position of the top-left cell, and ColRow2 represents the position of the bottom-right cell.
Example 1:
Excel(3,"C");
// construct a 3*3 2D array with all zero.
// A B C
// 1 0 0 0
// 2 0 0 0
// 3 0 0 0
Set(1, "A", 2);
// set C(1,"A") to be 2.
// A B C
// 1 2 0 0
// 2 0 0 0
// 3 0 0 0
Sum(3, "C", ["A1", "A1:B2"]);
// set C(3,"C") to be the sum of value at C(1,"A") and the values sum of the rectangle range whose top-left cell is C(1,"A") and bottom-right cell is C(2,"B"). Return 4.
// A B C
// 1 2 0 0
// 2 0 0 0
// 3 0 0 4
Set(2, "B", 2);
// set C(2,"B") to be 2. Note C(3, "C") should also be changed.
// A B C
// 1 2 0 0
// 2 0 2 0
// 3 0 0 6
Note:
- You could assume that there won’t be any circular sum reference. For example, A1 = sum(B1) and B1 = sum(A1).
- The test cases are using double-quotes to represent a character.
- Please remember to RESET your class variables declared in class Excel, as static/class variables are persisted across multiple test cases. Please see here for more details.
Solution
In class Excel, maintain the number of rows and the number of columns, the cells, and two maps that stores each cell and the sum cells relevant to the cell and stores each sum cell and the cells relevant to the sum cell, respectively.
For the constructor, initialize the number of rows to H + 1 and the number of columns to W - 'A' + 1, initialize the cells with the rows and the columns, and initialize the two maps.
For method set, set the given cell’s value to v, remove the relations in the two maps between the current cell and other cells where the current cell is a sum cell (which means the current cell’s value equals the sum of one or several other cells), and update the cells’ values that are directly or indirectly affected by the current cell.
For method get, simply get the value of the given cell and return.
For method sum, first obtain the given cell’s value and call method set to remove the relations of the previous sum formula (if it exists), then update the two maps and calculate the sum of the current cell, and finally update the cells’ values that are directly or indirectly affected by the current cell, which is the same as the last step in method set.
-
class Excel { int rows; int columns; int[][] cells; Map<String, Map<String, Integer>> cellSumMap; Map<String, Map<String, Integer>> sumCellMap; public Excel(int H, char W) { rows = H + 1; columns = W - 'A' + 1; cells = new int[rows][columns]; cellSumMap = new HashMap<String, Map<String, Integer>>(); sumCellMap = new HashMap<String, Map<String, Integer>>(); } public void set(int r, char c, int v) { int prevValue = cells[r][c - 'A']; int difference = v - prevValue; String cellName = String.valueOf(c) + r; Map<String, Integer> cellMap = sumCellMap.getOrDefault(cellName, new HashMap<String, Integer>()); sumCellMap.remove(cellName); Set<String> cellSet = cellMap.keySet(); for (String cell : cellSet) { Map<String, Integer> sumMap = cellSumMap.getOrDefault(cell, new HashMap<String, Integer>()); sumMap.remove(cellName); cellSumMap.put(cell, sumMap); } updateRelevantCells(cellName, difference); } public int get(int r, char c) { return cells[r][c - 'A']; } public int sum(int r, char c, String[] strs) { int sum = 0; int prevValue = cells[r][c - 'A']; set(r, c, prevValue); String sumCellName = String.valueOf(c) + r; for (String str : strs) { if (str.indexOf(':') >= 0) { String[] array = str.split(":"); String start = array[0], end = array[1]; char startColumn = start.charAt(0), endColumn = end.charAt(0); int startRow = Integer.parseInt(start.substring(1)), endRow = Integer.parseInt(end.substring(1)); for (int i = startRow; i <= endRow; i++) { for (char j = startColumn; j <= endColumn; j++) { String cellName = String.valueOf(j) + i; Map<String, Integer> sumMap = cellSumMap.getOrDefault(cellName, new HashMap<String, Integer>()); int sumCount = sumMap.getOrDefault(sumCellName, 0) + 1; sumMap.put(sumCellName, sumCount); cellSumMap.put(cellName, sumMap); Map<String, Integer> cellMap = sumCellMap.getOrDefault(sumCellName, new HashMap<String, Integer>()); int cellCount = cellMap.getOrDefault(cellName, 0) + 1; cellMap.put(cellName, cellCount); sumCellMap.put(sumCellName, cellMap); sum += cells[i][j - 'A']; } } } else { Map<String, Integer> sumMap = cellSumMap.getOrDefault(str, new HashMap<String, Integer>()); int sumCount = sumMap.getOrDefault(sumCellName, 0) + 1; sumMap.put(sumCellName, sumCount); cellSumMap.put(str, sumMap); Map<String, Integer> cellMap = sumCellMap.getOrDefault(sumCellName, new HashMap<String, Integer>()); int cellCount = cellMap.getOrDefault(str, 0) + 1; cellMap.put(str, cellCount); sumCellMap.put(sumCellName, cellMap); char cellColumn = str.charAt(0); int cellRow = Integer.parseInt(str.substring(1)); sum += cells[cellRow][cellColumn - 'A']; } } int difference = sum - prevValue; updateRelevantCells(sumCellName, difference); return cells[r][c - 'A']; } private void updateRelevantCells(String cellName, int difference) { Queue<String> cellQueue = new LinkedList<String>(); Queue<Integer> differenceQueue = new LinkedList<Integer>(); cellQueue.offer(cellName); differenceQueue.offer(difference); while (!cellQueue.isEmpty()) { String cell = cellQueue.poll(); int curDifference = differenceQueue.poll(); char column = cell.charAt(0); int row = Integer.parseInt(cell.substring(1)); cells[row][column - 'A'] += curDifference; Map<String, Integer> map = cellSumMap.getOrDefault(cell, new HashMap<String, Integer>()); Set<String> set = map.keySet(); for (String nextCell : set) { int count = map.get(nextCell); cellQueue.offer(nextCell); differenceQueue.offer(curDifference * count); } } } } /** * Your Excel object will be instantiated and called as such: * Excel obj = new Excel(H, W); * obj.set(r,c,v); * int param_2 = obj.get(r,c); * int param_3 = obj.sum(r,c,strs); */ -
class Excel: def __init__(self, H: int, W: str): self.grid = [[0] * (ord(W) - 64) for _ in range(H)] self.formula = {} def set(self, r: int, c: str, v: int) -> None: self.formula[(r, ord(c) - 64)] = [v, None] def get(self, r: int, c: str) -> int: if (r, ord(c) - 64) in self.formula: return self.evaluate(r, ord(c) - 64, self.formula[(r, ord(c) - 64)][0]) return self.grid[r-1][ord(c)-65] def sum(self, r: int, c: str, strs: List[str]) -> int: cells = [] for s in strs: if ':' not in s: cells.append((int(s[1:]), ord(s[0]) - 64)) else: start, end = s.split(':') r1, c1 = int(start[1:]), ord(start[0]) - 64 r2, c2 = int(end[1:]), ord(end[0]) - 64 cells += [(r, c) for r in range(r1, r2+1) for c in range(c1, c2+1)] value = sum(self.get(r, chr(c+64)) for r, c in cells) self.formula[(r, ord(c) - 64)] = [value, cells] return value def evaluate(self, r: int, c: int, formula: Union[int, List]): if isinstance(formula, int): return formula value, cells = formula if not cells: return value value = sum(self.evaluate(r, c, self.formula[(r, c)][0]) for r, c in cells) self.formula[(r, c)] = [value, None] return value ############## class Excel(object): def __init__(self, H, W): """ :type H: int :type W: str """ H, W = self.decodeCoord(H, W) self.data = [[0] * (W + 1) for _ in range(H + 1)] self.formulas = {} def decodeCoord(self, r, c): return int(r) - 1, ord(c) - ord("A") + 1 def set(self, r, c, v): """ :type r: int :type c: str :type v: int :rtype: void """ r, c = self.decodeCoord(r, c) if (r, c) in self.formulas: del self.formulas[(r, c)] self.data[r][c] = v def get(self, r, c): """ :type r: int :type c: str :rtype: int """ r, c = self.decodeCoord(r, c) if (r, c) in self.formulas: return self.computeFormula(self.formulas[(r, c)]) return self.data[r][c] def computeFormula(self, strs): ans = 0 for s in strs: startI, startJ, endI, endJ = self.parseRange(s) for i in range(startI, endI + 1): for j in range(startJ, endJ + 1): if (i, j) in self.formulas: ans += self.computeFormula(self.formulas[(i, j)]) else: ans += self.data[i][j] return ans def parseRange(self, s): start = end = s if ":" in s: start, end = s.split(":") startI, startJ = self.decodeCoord(start[1:], start[0]) endI, endJ = self.decodeCoord(end[1:], end[0]) return (startI, startJ, endI, endJ) def sum(self, r, c, strs): """ :type r: int :type c: str :type strs: List[str] :rtype: int """ r, c = self.decodeCoord(r, c) self.formulas[(r, c)] = strs return self.computeFormula(strs) # Your Excel object will be instantiated and called as such: # obj = Excel(H, W) # obj.set(r,c,v) # param_2 = obj.get(r,c) # param_3 = obj.sum(r,c,strs)