238. Product of Array Except Self
https://leetcode.com/problems/product-of-array-except-self/
My Answer 1: Accepted (Runtime: 268 ms - 18.59% / Memory Usage: 21.3 MB - 43.51%)
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
ans = []
p = 1
zero = 0
for i in range(len(nums)):
if nums[i] != 0:
p *= nums[i]
else:
zero += 1
for i in range(len(nums)):
if nums[i] == 0 and zero == 1:
ans.append(p)
elif zero == 0:
ans.append(p//nums[i])
else:
ans.append(0)
return ans먼저 p, zero 를 구함
p: 0 을 제외한 전체 곱
zero: 0 의 개수
다시 nums 를 보면서
0 이 한개일 때는 0 을 제외한 나머지 위치는 모두 0 이고 0 의 위치만 p 를 가짐
0 이 없으면 p // nums[i] 로 자기 자신 제외한 곱
0 이 많을 때는 전부 다 0 으로
Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)
만족한다!!
Solution 1: Accepted (Runtime: 240 ms - 57.91% / Memory Usage: 20.9 MB - 81.82%)
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
result = [1] * len(nums)
for i in range(1, len(nums)):
result[i] = nums[i-1] * result[i-1]
right_prod = 1
for i in range(len(nums)-1, -1, -1):
result[i] *= right_prod
right_prod *= nums[i]
return result자신을 제외한 모든 숫자를 곱해야 한다는 점에서
처음 for 문에서는 자신 기준 모든 왼쪽 값을 곱하고
두번째 for 문에서는 자신 기준 모든 오른쪽 값을 곱해주는 것
왼쪽 -> 오른쪽 방향으로의 누적곱을 result 에 저장
오른쪽 -> 왼쪽 방향으로의 누적곱을 result 에 저장
240. Search a 2D Matrix II
https://leetcode.com/problems/search-a-2d-matrix-ii/
My Answer 1: Accepted (Runtime: 424 ms - 5.01% / Memory Usage: 21.2 MB - 5.53%)
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
dp = [[-1] * len(matrix[0]) for _ in range(len(matrix))]
def func(i, j):
if dp[i][j] != -1:
return dp[i][j]
if matrix[i][j] == target:
dp[i][j] = 1
return True
if matrix[i][j] > target:
dp[i][j] = 0
return False
if i+1 < len(matrix) and matrix[i+1][j] <= target:
if func(i+1, j):
dp[i][j] = 1
return True
if j+1 < len(matrix[0]) and matrix[i][j+1] <= target:
if func(i, j+1):
dp[i][j] = 1
return True
dp[i][j] = 0
return False
return func(0, 0)matrix 와 같은 크기의 dp 를 만들어서 모두 -1 로 초기화
(0, 0) 부터 재귀 돌려서 target 찾기
func)
현재 좌표가 dp 값을 갖고 있으면 그대로 dp return
target 을 찾았으면 dp = 1 & return True
target 보다 크면 이 이후는 가망이 없으니까 dp = 0 & return False
나머지는 i+1, j+1 을 하면서 target 을 찾아감
=> 찾으면 맞물린 (i, j) 의 dp 도 1 로
dp 가 없으면 Time Limit 걸려서 더 빠르게 재귀를 빠져나가기 위해 사용
Solution 1: Accepted (Runtime: 160 ms - 84.41% / Memory Usage: 20.7 MB - 31.15%)
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
## RC ##
## APPROACH : GREEDY ##
## Similar to Leetcode: 74. Search A 2D Matrix ##
# 1. First, we initialize a (row, col) pointer to the bottom-left of the matrix.
# 2. If the currently-pointed-to value is larger than target we can move one row "up".
# 3. Otherwise, if the currently-pointed-to value is smaller than target, we can move one column "right".
## TIME COMPLEXITY : O(N + M) ##
## SPACE COMPLEXITY : O(1) ##
i, j = len(matrix) - 1, 0
while(i >= 0 and i < len(matrix) and j >=0 and j < len(matrix[0])):
if(matrix[i][j] == target): return True
if(matrix[i][j] > target): i -= 1
if(matrix[i][j] < target): j += 1
return False재귀 쓸 필요 없이 Greedy 쓰면 간단히 풀린다
i 를 len(matrix) - 1 부터 시작한다는 것이 중요!!
알아두기~~
251. Flatten 2D Vector
https://leetcode.com/problems/flatten-2d-vector/
https://www.lintcode.com/problem/601/
My Answer 1: Accepted (Runtime: 1973 ms / Memory Usage: 29.11 MB) - 57.20 %
class Vector2D(object):
# @param vec2d {List[List[int]]}
def __init__(self, vec2d):
# Initialize your data structure here
self.vec = vec2d
self.idx = 0
i = 0
while i < len(self.vec):
if len(self.vec[i]) == 0:
self.vec.pop(i)
continue
i += 1
if len(self.vec) == 0:
self.idx = -1
# @return {int} a next element
def next(self):
# Write your code here
if self.idx != -1 and self.vec[self.idx]:
a = self.vec[self.idx].pop(0)
if len(self.vec[self.idx]) == 0 and self.idx < len(self.vec)-1:
self.idx += 1
return a
# @return {boolean} true if it has next element
# or false
def hasNext(self):
# Write your code here
if self.idx != -1 and len(self.vec[self.idx]) != 0:
return True
return False
# Your Vector2D object will be instantiated and called as such:
# i, v = Vector2D(vec2d), []
# while i.hasNext(): v.append(i.next())init)
self.vec: vec2d 그대로 저장
self.idx: 존재하는 숫자가 들어있는 리스트의 index 를 가리키도록
비어있는 리스트들은 모두 없애줌
self.vec 이 아예 비어있는 상태면 self.idx 도 -1 로 없다는 것을 알려줌
next)
self.vec 에 남아있는 숫자가 있을때만 pop 해서 return
현재 self.idx 가 가리키는 리스트가 비어있으면 다음 인덱스를 가리키도록 처리
hasNext)
self.idx 가 가리키는 값이 존재하는지 여부 return
Solution 1: Accepted (Runtime: 76 ms - 87.54% / Memory Usage: 20 MB - 62.32%)
class Vector2D:
def __init__(self, v: List[List[int]]):
self.data = []
for i in range(len(v)):
for j in range(len(v[i])):
self.data.append(v[i][j])
self.pointer = 0
def next(self) -> int:
if self.pointer < len(self.data):
self.pointer += 1
return self.data[self.pointer-1]
def hasNext(self) -> bool:
if self.pointer < len(self.data):
return True
else:
return False
# Your Vector2D object will be instantiated and called as such:
# obj = Vector2D(v)
# param_1 = obj.next()
# param_2 = obj.hasNext()저번에 내가 풀었던 방식
그냥.. self.data 에 순서대로 저장하고 pointer 로 next 를 가리키도록
if self.pointer < len(self.data): 면 더이상 next 가 없다는 의미
포인터 없이 pop 만 하면 Time Limit 걸린다..
