653. Two Sum IV - Input is a BST
Given the root of a Binary Search Tree and a target number k, return true if there exist two elements in the BST such that their sum is equal to the given target.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def findTarget(self, root: TreeNode, k: int) -> bool:
def func(root):
if root is None:
return
self.arr.append(root.val)
func(root.left)
func(root.right)
self.arr = []
func(root)
for i in range(len(self.arr)):
if k - self.arr[i] != self.arr[i] and k - self.arr[i] in self.arr:
return True
return False재귀로 어떻게 풀어보려했는데... 안돼서 그냥 값들을 list 에 담고 TwoSum 해줌^^
Solution 1: Accepted (Runtime: 76 ms - 80.53% / Memory Usage: 16.3 MB - 95.46%)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def findTarget(self, root: TreeNode, k: int) -> bool:
if not root:
return False
bfs, s = [root], set()
for i in bfs:
if k - i.val in s:
return True
s.add(i.val)
if i.left:
bfs.append(i.left)
if i.right:
bfs.append(i.right)
return False그냥 루트부터 트리를 보면서 s 에 value 값을 넣어주고
k - i.val 가 s 에 있으면 두개의 합을 찾은 거니까 return True
첨에 풀었던 재귀 함수 =
def func(root, target, two)
(two = 두개를 더했는지 여부)=>
target값 하나만 쓰지 말고s같은 리스트나 셋을 하나 추가했으면 풀렸을 듯...
이렇게 간단했다니...^^
1071. Greatest Common Divisor of Strings
For two strings s and t, we say "t divides s" if and only if s = t + ... + t (t concatenated with itself 1 or more times)
Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2.
My Answer 1: Accepted (Runtime: 132 ms - 9.25% / Memory Usage: 14.4 MB - 28.49%)
class Solution:
def gcdOfStrings(self, str1: str, str2: str) -> str:
# 겹치는 부분이 없는 경우
if len(str1) > len(str2):
a = str1
b = str2
else:
a = str2
b = str1
if b not in a:
return ""
result = ""
common = ""
for i in range(len(b)):
tmp1 = a
common += b[i]
tmp1 = a.replace(common, "")
tmp2 = b.replace(common, "")
if tmp1 == "" and tmp2 == "":
result = common
return result우선 더 긴 문자열을 a 로, 짧은 걸 b 로 잡아주고
b 가 a 에 포함되지 않으면 common 이 없으므로 빈 문자열 return
b 를 하나씩 common 에 넣어주면서 a, b 에서 common 을 제거해주고
a, b 모두 빈 문자열인지 확인 => 나누어 떨어지는지 확인
나누어 떨어지면 result update
- largest string 을 찾아야하므로 나누어 떨어지는 걸 찾았다고 바로 return 하면 안됨
My Answer 2: Accepted (Runtime: 40 ms - 22.92% / Memory Usage: 14.4 MB - 28.49%)
class Solution:
def gcdOfStrings(self, str1: str, str2: str) -> str:
# 겹치는 부분이 없는 경우
if len(str1) > len(str2):
a = str1
b = str2
else:
a = str2
b = str1
if b not in a:
return ""
result = ""
common = ""
for i in range(len(b)):
tmp = a
common += b[i]
if a.count(common) * len(common) == len(a) and b.count(common) * len(common) == len(b):
result = common
return result첫번째랑 비슷한데 이건 길이로 판단
a.count(common) * len(common) == len(a) => a가 common 으로 나눠떨어진다
b 도 마찬가지로 처리해주고 a, b 모두 나눠떨어지면 result update
replace 하는 것보다 좀 더 빠름!!
Solution 1: Accepted (Runtime: 20 ms - 99.40% / Memory Usage: 14.3 MB - 56.17%)
def gcdOfStrings(self, str1: str, str2: str) -> str:
if not str1 or not str2:
return str1 if str1 else str2
elif len(str1) < len(str2):
return self.gcdOfStrings(str2, str1)
elif str1[: len(str2)] == str2:
return self.gcdOfStrings(str1[len(str2) :], str2)
else:
return ''더 긴 문자열을 str1 자리로, 짧은 건 str2 자리로 옮겨주면서 재귀 돌림
재귀로 공통된 부분을 지워가게 되므로 최종적으로 남는 게 (str1 or str2) common 이 된다
빠르다~~
GCD(최대공약수) 알고리즘 = 유클리드 호제법
0개의 댓글
