PY @yeahub_python_backend
Showing posts older than #90 · Back to latest
Input
["Excel", "set", "sum", "set", "get"]
[[3, "C"], [1, "A", 2], [3, "C", ["A1", "A1:B2"]], [2, "B", 2], [3, "C"]]
Output
[null, null, 4, null, 6]
class Excel:
def __init__(self, height: int, width: str):
self.mat = [[0] * (ord(width) - ord('A') + 1) for _ in range(height)]
self.formulas = {}
def set(self, row: int, column: str, val: int) -> None:
self.mat[row - 1][ord(column) - ord('A')] = val
self.formulas.pop((row, column), None)
def get(self, row: int, column: str) -> int:
if (row, column) in self.formulas:
return self._evaluate_formula(row, column)
return self.mat[row - 1][ord(column) - ord('A')]
def sum(self, row: int, column: str, numbers: List[str]) -> int:
self.formulas[(row, column)] = numbers
return self._evaluate_formula(row, column)
def _evaluate_formula(self, row: int, column: str) -> int:
total = 0
for number in self.formulas[(row, column)]:
if ':' in number:
start, end = number.split(':')
start_row, start_col = int(start[1:]), start[0]
end_row, end_col = int(end[1:]), end[0]
for r in range(start_row, end_row + 1):
for c in range(ord(start_col), ord(end_col) + 1):
total += self.get(r, chr(c))
else:
r, c = int(number[1:]), number[0]
total += self.get(r, c)
return total
Input: envelopes = [[5,4],[6,4],[6,7],[2,3]]
Output: 3
Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
dp = []
for num in nums:
i = bisect_left(dp, num)
if i < len(dp):
dp[i] = num
else:
dp.append(num)
return len(dp)
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
envelopes.sort(key=lambda x: (x[0], -x[1]))
second_dim = [e[1] for e in envelopes]
return self.lengthOfLIS(second_dim)