1480. Running Sum of 1d Array
Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]).
Return the running sum of nums.
My Answer 1: Accepted (Runtime: 40 ms - 64.89% / Memory Usage: 14.4 MB - 39.35%)
class Solution:
def runningSum(self, nums: List[int]) -> List[int]:
ans = []
tmp = 0
for i in range(len(nums)):
tmp += nums[i]
ans.append(tmp)
return ans문제 그대로 누적합을 ans 에 append
My Answer 2: Accepted (Runtime: 40 ms - 64.89% / Memory Usage: 14.5 MB - 39.35%)
class Solution:
def runningSum(self, nums: List[int]) -> List[int]:
for i in range(1, len(nums)):
nums[i] += nums[i-1]
return nums같은 건데 그냥 주어진 nums 에 누적해서 return
1297. Maximum Number of Occurrences of a Substring
Given a string s, return the maximum number of ocurrences of any substring under the following rules:
The number of unique characters in the substring must be less than or equal to maxLetters.
The substring size must be between minSize and maxSize inclusive.
My Answer 1: Accepted (Runtime: 4460 ms - 5.06% / Memory Usage: 183.5 MB - 5.56%)
class Solution:
def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
# sub: substring, cnt: letter 종류 개수
def func(s, sub, cnt):
# 조건에 해당하는 substring 은 self.dic 값 + 1
if cnt <= maxLetters and len(sub) >= minSize and len(sub) <= maxSize:
self.dic[sub] += 1
if cnt > maxLetters or len(s) == 0:
return
if s[0] not in sub:
func(s[1:], sub+s[0], cnt+1)
else:
func(s[1:], sub+s[0], cnt)
self.dic = collections.defaultdict(int)
for i in range(len(s)):
func(s[i:], "", 0)
# substring 이 없으면 return 0
if len(self.dic) == 0:
return 0
return max(self.dic.values())재귀로 모든 substring 의 경우를 보면서
minSize ~ maxSize 크기 & maxLetters 보다 적은 letter 인
substring 은 self.dic 에 개수와 함께 넣어줌
substring 이 없으면 return 0
있으면 value 값들 중 최댓값 return
빈도수를 기준으로 오름차순 정렬해서 가장 첫번째 value 값 return 도 가능
Solution 1: Accepted (Runtime: 88 ms - 99.35% / Memory Usage: 16.3 MB - 44.61%)
class Solution:
def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
count = collections.Counter(s[i:i + minSize] for i in range(len(s) - minSize + 1))
return max([count[w] for w in count if len(set(w)) <= maxLetters] + [0])minSize ~ maxSize 범위를 볼 필요가 없다고 하네요
무조건 minSize 크기의 substring 에서 답이 나옴
그래서 아예 minSize 의 substring 들의 개수를 세서 그 중 max 값만 return
훠얼씬 빠르다!!
1274. Number of Ships in a Rectangle
My Idea
우선 topRight 와 bottomLeft 범위 내의 모든 점들로 hasShips 돌려서
겹치는 부분 적절히 빼주면 되지 않나 싶었음
=> 최소 2중 for 문이 & more than 400 calls^^
두번째는 대각선으로 어떻게 비벼보기를 생각했는데
구체적으로 설계가 안됨...
이건 수학적으로 접근해야하지 않나싶은데...
머리 안돌아가서 모르겠음...^^
Solution 1: Accepted
# """
# This is Sea's API interface.
# You should not implement it, or speculate about its implementation
# """
#class Sea(object):
# def hasShips(self, topRight: 'Point', bottomLeft: 'Point') -> bool:
#
#class Point(object):
# def __init__(self, x: int, y: int):
# self.x = x
# self.y = y
class Solution(object):
def countShips(self, sea: 'Sea', topRight: 'Point', bottomLeft: 'Point') -> int:
def d_c(bottom, top):
if bottom.x>top.x or bottom.y>top.y:return 0
if (top.x, top.y) == (bottom.x, bottom.y):
return int(sea.hasShips(top, bottom))
else:
if not sea.hasShips(top, bottom):return 0
x0, y0 = bottom.x, bottom.y
x1, y1 = top.x, top.y
center_x, center_y = (x0+x1)//2, (y0+y1)//2
f1 = d_c(bottom, Point(center_x, center_y))
f2 = d_c(Point(center_x+1, center_y+1), top)
f3 = d_c(Point(x0, center_y+1), Point(center_x, y1))
f4 = d_c(Point(center_x+1, y0), Point(x1, center_y))
return f1+f2+f3+f4
return d_c(bottomLeft, topRight)핵심: Divide and Conquer
계속 4 등분 하기..
저 +1 이 중요한가보다
비슷한 풀이로 영상 설명도 있는데 이해는...
참고: https://www.youtube.com/watch?v=fZXyxGTqlgQ
0개의 댓글
