1. Two Sum
Given an array of integers nums and and integer target, return the indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1]
Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]
문제 정의: nums 배열 내 두 정수가 더해졌을때, target이 되면 그 두 정수의 index를 반환
통과한 답 :
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
nums_map = {} #숫자라는 키가 들어가면 인덱스가 나오도록 딕셔너리를 만든다.
for i, nums in enumerate(nums):
if target - nums in nums_map: #target에서 현재 num를 뺀 것이 nums map의 key에 있으면
return[nums_map[target - nums], i] #현재의 num과 target에서 num을 뺀 배열을 return한다.
nums_map[nums] = i 20. Valid Parentheses
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
Example 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "()[]{}"
Output: trueExample 3:
Input: s = "(]"
Output: false
Solution:
class Solution:
def isValid(self, s: str) -> bool:
s_list = list(s)
answer = True
stack = []
for s in s_list:
if s == '[' or s == '(' or s == '{':
stack.append(s)
elif len(stack) != 0:
if (s == ']' and stack[-1] == '[') or (s == '}' and stack[-1] == '{') or (s == ')' and stack[-1] == '('):
stack.pop()
else:
answer = False
break
else:
answer = False
break
if len(stack) != 0:
answer = False
return answer
21. Merge Two Sorted Lists
Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.
Example:
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
문제 정의: 두 연결리스트 내 노드를 연결하여 병합된 새로운 리스트 반환
통과한 답 :
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if l1 is None : #l1이 없으면 l2 반환
return l2
if l2 is None : #l2이 없으면 l1 반환
return l1
if (l1.val > l2.val) : #l1의 val 가 l2의 val보다 크면
head = ListNode(l2.val) #head는 l2의 val (작은 순부터 head니까)
head.next = self.mergeTwoLists(l1, l2.next)
#head의 next는 l1과 l2의 next를 mergeTwoLists 함수에 적용해서 반환된 값
else : #l1의 val 가 l2의 val보다 작으면
head = ListNode(l1.val) #head는 l1의 val
head.next = self.mergeTwoLists(l1.next, l2)
#head의 next는 l1의 next와 l2를 mergeTwoLists 함수에 적용
#즉 작은 각 리스트의 값이 head이고 head의 next는 다음 작은 값이라는 함수 적용
return head
28. Implement strStr()
Implement strStr().
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Example 1:
Input: haystack = "hello", needle = "ll" Output: 2
Example 2:
Input: haystack = "aaaaa", needle = "bba" Output: -1
Solution:
class Solution(object):
def strStr(self, haystack, needle):
"""
:type haystack: str
:type needle: str
:rtype: int
"""
if haystack.find(needle) >= 0:
return haystack.find(needle)
else:
return -1
53. Maximum Subarray
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
Example :
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
문제 정의: 리스트 내 정수 중에 합계가 가장 정수들의 Subarry를 구하고 그 Subarry의 합계 값을 반환(Subarry는 정수 한 개 이상 포함)
통과한 답 :
- 동적 계획법 중 카데인 알고리즘 활용
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
for i in range(1, len(nums)): #1부터 nums내 원소 개수까지
if nums[i - 1] > 0: #i번째 원소의 앞 원소가 0보다 크면
nums[i] += nums[i - 1] #i번째 수와 i-1의 수를 더해서
return max(nums) #최댓값을 반환
class Solution(object):
def maxSubArray(self, nums):
for i in range(1,len(nums)): #1부터 nums내 원소 개수까지 i를 돌림
nums[i] = max(nums[i - 1] + nums[i], nums[i])
#nums의 i번째 수는 i-1번째 수+ i번째 수 부터 i번째 수까지 최대 값
return max(nums) #nums의 최대값 반환
70. Climbing Stairs
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Example 1:
Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Example 2:
Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
문제 정의:
계단을 한칸 혹은 두칸씩 올라갈 수 있다.
n번째 계단까지 올라가는 방법은 몇 번인지 반환하라.
통과한 답 :
def climbStairs(self, n):
a, b = 1, 1
for i in range(n):
a, b = b, a + b
return adef climbStairs1(self, n):
if n == 1:
return 1
if n == 2:
return 2
return self.climbStairs(n-1)+self.climbStairs(n-2)
101. Symmetric Tree
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree [1,2,2,3,4,4,3] is symmetric:
1
/ \
2 2
/ \ / \
3 4 4 3But the following [1,2,2,null,3,null,3] is not:
1
/ \
2 2
\ \
3 3
Solution : Recursive
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
if not root: #루트가 없으면 True 반환
return True
return self.check(root.left, root.right) #루트의 좌우 값 비교
def check(self, left, right):
if left is None and right is None: #좌우 둘다 없으면 True
return True
if left is None or right is None: #좌우 중 하나 없으면 False
return False
if left.val != right.val: #좌우 값이 다르면 False
return False
a = self.check(left.left, right.right) #좌의 좌 값, 우의 우 값 비교
b = self.check(left.right, right.left) #좌의 우값, 우의 좌 값 비교
return a and b
Solution : Iterative
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
if not root:
return True
stack = collections.deque([(root.left, root.right)])
while stack:
l, r = stack.pop()
if l is None and r is None:
continue
if l is None or r is None:
return False
if l.val != r.val:
return False
stack.append((l.left, r.right))
stack.append((l.right, r.left))
return True
104. Maximum Depth of Binary Tree
Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Note: A leaf is a node with no children.
Example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7return its depth = 3.
Solution 1 (Recursive) :
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if not root:
return 0
return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
Solution 2 (Recursive) :
class Solution:
def __init__(self):
self.max_depth = 0
def dfs(self, node: TreeNode, depth):
if not node:
return
if self.max_depth < depth:
self.max_depth = depth
if node.left:
self.dfs(node.left, depth + 1)
if node.right:
self.dfs(node.right, depth + 1)
def maxDepth(self, root: TreeNode) -> int:
if not root:
return 0
self.dfs(root, 1)
return self.max_depth
121. Best Time to Buy and Sell Stock
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Note that you cannot sell a stock before you buy one.
Example 1:
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Not 7-1 = 6, as selling price needs to be larger than buying price.
Example 2:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
Solution:
class Solution:
def maxProfit(self, prices: List[int]) -> int:
minPrice = float(inf) #임의의 가장 큰 수 inf
profit = 0
maxProfit = 0
for i in range(len(prices)):
minPrice = min(minPrice, prices[i])
maxProfit = max(maxProfit, prices[i] - minPrice)
return maxProfit
136. Single Numbe
Given a non-empty array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Example 1:
Input: [2,2,1]
Output: 1
Example 2:
Input: [4,1,2,1,2]
Output: 4
Solution 1 :
class Solution:
def singleNumber(self, nums: List[int]) -> int:
cnt_dict = Counter(nums)
items = cnt_dict.items()
for key, val in items:
if val == 1:
answer = key
break
return answerSolution 2 :
class Solution:
def singleNumber(self, nums: List[int]) -> int:
answer = 0
for i in nums:
answer = answer ^ i
return answer
155. Min Stack
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
- push(x) -- Push element x onto stack.
- pop() -- Removes the element on top of the stack.
- top() -- Get the top element.
- getMin() -- Retrieve the minimum element in the stack.
Constraints:
- Methods pop, top and getMin operations will always be called on non-empty stacks.
Example:
Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
Output
[null,null,null,null,-3,null,0,-2]
Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top(); // return 0
minStack.getMin(); // return -2
Solution:
class MinStack(object):
def __init__(self):
"""
initialize your data structure here.
"""
self.stack = []
self.minStack = []
def push(self, x):
"""
:type x: int
:rtype: nothing
"""
self.stack.append(x)
if not self.minStack or self.minStack[-1] >= x:
self.minStack.append(x)
def pop(self):
"""
:rtype: nothing
"""
tmp = self.stack.pop()
if tmp == self.minStack[-1]:
self.minStack.pop()
def top(self):
"""
:type x: int
"""
return self.stack[-1]
def getMin(self):
"""
:rtype: int
"""
return self.minStack[-1]
169. Majority Element
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.
Example 1:
Input: [3,2,3]
Output: 3
Example 2:
Input: [2,2,1,1,1,2,2]
Output: 2
Solution 1:
#Boyer–Moore majority vote algorithm 사용
class Solution:
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
count = 0
major = None
for n in nums:
if count == 0:
major = n
if n == major:
count += 1
else:
count -= 1
return majorSolution 2:
#most_common : collections 모듈 - Counter 중 하나
#most_common은 입력된 값의 요소들 중 빈도수(frequency)가 높은 순으로 상위 n개를 리스트(list) 안의 투플(tuple) 형태로 반환한다. n을 입력하지 않은 경우, 요소 전체를 [('값', 개수)]의 형태로 반환한다.
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
count = collections.Counter(nums)
return count.most_common(1)[0][0]
198. House Robber
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
Constraints:
- 0 <= nums.length <= 100
- 0 <= nums[i] <= 400
Example 1:
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
Example 2:
Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.
Solution 1:
class Solution:
def rob(self, nums: List[int]) -> int:
prev = 0
curr = 0
for i in nums:
prev, curr = curr, max(curr, prev + i)
return curr
Solution 2:
def rob(self, nums):
Rob = non_Rob = 0
for n in nums:
non_Rob, Rob = max(non_Rob, Rob), non_Rob + n
return max(Rob, non_Rob)
206. Reverse Linked List
Reverse a singly linked list.
Example:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULLSolution:
class Solution(object):
def reverseList(self, head):
prev = None
curr = head
while curr!= None:
tmp = curr.next
curr.next = prev
prev = curr
curr = tmp
return prev226. Invert Binary Tree
Invert a binary tree.
Example:
Input:
4
/ \
2 7
/ \ / \
1 3 6 9Output:
4
/ \
7 2
/ \ / \
9 6 3 1
Solution :
class Solution(object):
def invertTree(self, root):
stack = [root]
while stack:
node = stack.pop()
if node:
node.left, node.right = node.right, node.left
stack += node.left, node.right
return root
283. Move Zeroes
Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.
Example:
Input: [0,1,0,3,12]
Output: [1,3,12,0,0]
Solution :
#[::-1]는 처음부터 끝까지 -1칸 간격으로 ( == 역순으로)
#pop()는 리스트에서 주어진 위치에 있는 항목을 삭제하고, 그 항목을 돌려줌
class Solution:
def moveZeroes(self, nums):
for i in range(len(nums))[::-1]:
if nums[i] == 0:
nums.pop(i)
nums.append(0)
448. Find All Numbers Disappeared in an Array
Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements of [1, n] inclusive that do not appear in this array.
Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.
Example:
Input:
[4,3,2,7,8,2,3,1]
Output:
[5,6]
Solution 1:
class Solution(object):
def findDisappearedNumbers(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
return list(set(range(1, len(nums)+1)) - set(nums))
Solution 2:
class Solution:
def findDisappearedNumbers(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
for n in nums:
i = abs(n) - 1
nums[i] = -abs(nums[i])
return [i+1 for i, v in enumerate(nums) if v > 0]
Solution 3:
class Solution:
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
if len(nums) < 0:
answer = []
else:
max_num = len(nums)
answer = list(set(range(1,max_num + 1)) - set(nums))
return answer
543. Diameter of Binary Tree
Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
이진트리의 지름 구하기 즉 가장 긴 path의 '길이'를 구하면 된다.
이 때, 노드 사이의 길이란 노드 사이의 edge의 개수이다.
예를 들어 아래의 경우 path [4,2,1,3] 나 [5,2,1,3]가 가장 길기 때문에 3이 반환된다.
Example:
#Given a binary tree
1
/ \
2 3
/ \
4 5
#Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].
#Note: The length of path between two nodes is represented by the number of edges between them.
Solution 1:
class Solution(object):
def diameterOfBinaryTree(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.ans = 0
def depth(p):
if not p: return 0
left, right = depth(p.left), depth(p.right)
self.ans = max(self.ans, left+right)
return 1 + max(left, right)
depth(root)
return self.ans
Solution 2:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def diameterOfBinaryTree(self, root):
"""
:type root: TreeNode
:rtype: int
"""
def dfs(node):
if node is None:
return 0
left = dfs(node.left)
right = dfs(node.right)
self.ans = max(self.ans, left+right+1)
return max(left, right)+1
self.ans = 1
dfs(root)
return self.ans-1
617. Merge Two Binary Trees
Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.
You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.
Example 1:
Input:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
Output:
Merged tree:
3
/ \
4 5
/ \ \
5 4 7Note: The merging process must start from the root nodes of both trees.
Solution 1 (Recusive) :
class Solution:
def mergeTrees(self, t1, t2):
"""
:type t1: TreeNode
:type t2: TreeNode
:rtype: TreeNode
"""
if t1 is None:
return t2
if t2 is None:
return t1
t1.val = t1.val + t2.val
t1.left = self.mergeTrees(t1.left, t2.left)
t1.right = self.mergeTrees(t1.right, t2.right)
return t1
Solution 2 (Recusive) :
class Solution:
def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
if not t1 and not t2:
return None
if bool(t1) ^ bool(t2):
return t1 if t1 else t2
t1.val += t2.val
t1.left = self.mergeTrees(t1.left, t2.left)
t1.right = self.mergeTrees(t1.right, t2.right)
return t1
Solution 3 (Iterative) :
class Solution:
def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
if not t1 and not t2:
return None
if bool(t1) ^ bool(t2):
return t1 if t1 else t2
queue = deque([(t1, t2)])
while queue:
tree1, tree2 = queue.popleft()
tree1.val += tree2.val
if not tree1.left and tree2.left:
tree1.left = tree2.left
elif tree1.left and tree2.left:
queue.append((tree1.left, tree2.left))
if not tree1.right and tree2.right:
tree1.right = tree2.right
elif tree1.right and tree2.right:
queue.append((tree1.right, tree2.right))
return t1
'Python > PS in Python' 카테고리의 다른 글
| LeetCode160. Intersection of Two Linked Lists - Python (0) | 2020.09.16 |
|---|---|
| LeetCode 141. Linked List Cycle (0) | 2020.09.14 |
| LeetCode 198. House Robber - Python (0) | 2020.09.11 |
| LeetCode 155. Min Stack - Python (0) | 2020.09.09 |
| LeetCode 53. Maximum Subarray - Python (0) | 2020.09.07 |
댓글