레이블이 알고리즘인 게시물을 표시합니다. 모든 게시물 표시
레이블이 알고리즘인 게시물을 표시합니다. 모든 게시물 표시

2019년 5월 29일 수요일

[leetcode] 118. Pascal's Triangle

원문)
Given a non-negative integer numRows, generate the first numRows of Pascal's triangle.

 번역)
양수 숫자열이 주어졌을때, 파스칼 삼각형을 처음 열부터 만들어라.


예제)

In Pascal's triangle, each number is the sum of the two numbers directly above it.
Example:
Input: 5
Output:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

문제접근)

우선 첫번째는 넣어두고
그 다음부터는 이전 배열저장된것을 가져와서 각각 더해주고 넣어준다.
그리고 양끝에 1을 넣어준다.


코드)

 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        answer = []
        
        for i in range(numRows):
            if i == 0:
                answer.append([1])
            else:
                tmp = [1]
                prev = answer[i - 1]
                l = len(prev)
                if l > 1:
                    for i in range(1, l):
                        tmp.append(prev[i-1] + prev[i])
                tmp.append(1)
                answer.append(tmp)
        return answer


Read more ...
작성자: 시간: 댓글 없음:
라벨: , ,

[leetcode] 54. Spiral Matrix

원문)
Given a matrix of m x n elements (m rows, n columns),
return all elements of the matrix in spiral order.

번역)
행렬(행 M, 열 N)주어졌을때,
나선의 모든 요소들을 반환하라.


예제)
Example 1:
Input:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]
Example 2:
Input:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]
문제접근)

총 4개의 방향을 잡고 각 방향 별로 쪼개서 각 기능을 하도록 구현하였다.
반영 -> 체크 -> 움직임 으로 순서를 잡고 했다.


코드)

 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        answer = []
        
        m = len(matrix)
        if m == 0:
            return []
        n = len(matrix[0])
        
        left = 0
        bottom = m - 1
        right = n - 1
        top = 1
        
        row = 0
        y = 0
        col = 0
        x = 1
        state = 0
        
        while len(answer) < m * n:
            # add
            answer.append(matrix[row][col])
            
            # check
            if state == 0:
                # check
                if col == right:
                    right -= 1
                    state = 1
                    # dir
                    x = 0
                    y = 1
            elif state == 1:
                # check
                if row == bottom:
                    bottom -= 1
                    state = 2
                    # dir
                    x = -1
                    y = 0
            elif state == 2:
                # check
                if col == left:
                    left += 1
                    state = 3
                    # dir
                    x = 0
                    y = -1
            else:
                # check
                if row == top:
                    top += 1
                    state = 0
                    # dir
                    x = 1
                    y = 0
                    
            # move
            row += y
            col += x
        
        return answer


Read more ...
작성자: 시간: 댓글 없음:
라벨: , ,

[leetcode] 498. Diagonal Traverse

원문)
Given a matrix of M x N elements (M rows, N columns),
return all elements of the matrix in diagonal order as shown in the below image.

번역)
행렬(행 M, 열 N)주어졌을때,
다음 그림에서 처럼 모든 요소들을 반환하라.


예제)
Example 1:
Input:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

Output:  [1,2,4,7,5,3,6,8,9]

Explanation:









Note:



The total number of elements of the given matrix will not exceed 10,000.

문제접근)

우선 쪼개서 생각해 보려고한다.

(row, col)으로 자리를 변환시켜 보면 다음과 같다.

r을 변경해보자.

변경해서 앞자리 수만 확인해보면
"00" "01" "02" "12" "22"
col 증가하다가 다 지나가면 row을 증가하는 규칙성을 확인할 수 있다.



1개는 하나이니까 2개 이상부터 보면
"01 10" "02 11 20"
이 내용도 확인해보면 row는 증가 col는 감소하는 것을 알 수 있다.
주의사항은 r인경우는 실제값은 reverse해야한다.

해당 2가지 규칙을 각각 구별하여 구분하면 구현할 수 있다.


4 X 4를 한번 보자.



해당 내용도 위의 규칙이 적용되는것을 확인하였다.



코드)


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution:
    def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]:
        m = len(matrix)
        if m == 0:
            return []
        n = len(matrix[0])
        
        ans = []
        row = 0
        col = 0
        order = 1
        
        while True:
            order *= -1
            ans += self.traverse(col, row, matrix)[::order]
            if col < n - 1:
                col += 1
            elif row < m - 1:
                row += 1
            else:
                break
        return ans
    
    def traverse(self, col, row, matrix) -> List[int]:
        ret = []

        max_m = len(matrix) - 1
        max_n = len(matrix[0]) - 1

        while col >=0 and row <= max_m:
            ret.append(matrix[row][col])
            col -= 1
            row += 1
        return ret

Read more ...
작성자: 시간: 댓글 없음:
라벨: , ,

2019년 5월 25일 토요일

[leetcode] 66. Plus One

원문)
Given a non-empty array of digits representing a non-negative integer, plus one to the integer.
The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.
You may assume the integer does not contain any leading zero, except the number 0 itself.

번역)
양수의 값이 있는 배열이 주어졌을때 +1을 하라.
최상위 숫자가 리스트의 첫째자리에 있고 각 요소들은 한자리씩 들어가 있다.
숫자 0을 제외하고 나머지 최상위 자리에는 0이 들어갈 수 없다고 가정하라.


예제)
Example 1:
Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Example 2:
Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.
문제접근)
각 요소는 한자리 숫자만 들어갈 수 있다.
만약 10이면 1, 0 이렇게 2자리로 들어가야 한다.
우선 최하위 부터 자릿수 이동이 일어나야 하므로 기존 리스트를 뒤집어주고
10이 넘어가면 carry를 올려줘서
최종적으로 carry가 있을경우는 자릿수를 하나 더 올려준다.

코드)


class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        digits = digits[::-1]
        digits[0] += 1
        carry = 0

        for i in range(len(digits)):
            if carry:
                digits[i] += 1
                carry = 0
                
            carry = digits[i] // 10
            digits[i] = digits[i] % 10
        
        if carry:
            digits.append(1)
        return digits[::-1]

Read more ...
작성자: 시간: 댓글 없음:
라벨: , ,

[leetcode] 747. Largest Number At Least Twice of Others

원문)
In a given integer array nums, there is always exactly one largest element.
Find whether the largest element in the array is at least twice as much as
every other number in the array.
If it is, return the index of the largest element, otherwise return -1.

번역)
정수 배열이 주어지고, 그곳에는 가장 큰 요소가 있다.
해당 가장 큰 요소는 그 다음 큰 수의 두배가 넘어야 한다.
만약 있다면 그 해당 index를 반환하고 아니라면 -1를 반환하라.


예제)
Example 1:
Input: nums = [3, 6, 1, 0]
Output: 1
Explanation: 6 is the largest integer, and for every other number in the array x,
6 is more than twice as big as x.  The index of value 6 is 1, so we return 1.

Example 2:
Input: nums = [1, 2, 3, 4]
Output: -1
Explanation: 4 isn't at least as big as twice the value of 3, so we return -1.

Note:
  1. nums will have a length in the range [1, 50].
  2. Every nums[i] will be an integer in the range [0, 99].

문제접근)

  1. 리스트를 하나 복사해두고 max하나 최대값 빼고 다음 max값구해서
    m1, m2를 구하고 원본 리스트에서 index를 구하여 계산한다.
  2. 리스트를 복사하는것이 마음에 걸려서 조금더 찾아보니
    최대값을 구해두고 그 값을 이용하여 index를 구하고 나머지들끼리 max를 구한다.


코드)

1. 접근

class Solution:
    def dominantIndex(self, nums: List[int]) -> int:
        if len(nums) < 2:
            return 0
        tmp = nums.copy()
        m1 = max(tmp)
        tmp.remove(m1)
        m2 = max(tmp)
        index = nums.index(m1)
        
        if m1 >= m2 * 2:
            return index
        else:
            return -1

2. 접근


class Solution:
    def dominantIndex(self, nums: List[int]) -> int:
        m1 = max(nums)
        m2 = 0
        
        index = -1
        l = len(nums)
        for i in range(l):
            if nums[i] == m1:
                index = i
            else:
                m2 = max(m2, nums[i])
                
        if m1 >= m2 * 2:
            return index
        else:
            return -1


Read more ...
작성자: 시간: 댓글 없음:
라벨: , ,

[leetcode] 724. Find Pivot Index

원문)
Given an array of integers nums, write a method that returns the "pivot" index of this array.
We define the pivot index as the index where the sum of the numbers to the left of the index is equal to the sum of the numbers to the right of the index.
If no such index exists, we should return -1.
If there are multiple pivot indexes, you should return the left-most pivot index.

번역)
정수 숫자의 배열이 주어졌을때 배열의 "pivot" 인덱스를 구하라.
"pivot"은 인덱스의 왼쪽 숫자들의 합과 인덱스의 오른쪽 숫자들의 합이 동일한 index를
뜻한다.
만약 없다면 -1을 반환.
만약 여러개라면 가장 왼쪽의 pivot 인덱스를 반환.


예제)
Example 1:
Input: 
nums = [1, 7, 3, 6, 5, 6]
Output: 3
Explanation: 
The sum of the numbers to the left of index 3 (nums[3] = 6) is equal 
to the sum of numbers to the right of index 3.
Also, 3 is the first index where this occurs.

Example 2:
Input: 
nums = [1, 2, 3]
Output: -1
Explanation: 
There is no index that satisfies the conditions in the problem statement.

Note:
  • The length of nums will be in the range [0, 10000].
  • Each element nums[i] will be an integer in the range [-1000, 1000].

문제접근)
1. 접근
  • 다 되었다고 생각했는데, 느리다.
    왜 느리냐 생각해보니 sum을 계속한다 두번씩.
2. 접근

  • 왼쪽부터 더해주니까 그부분은 sum을 지웠다만 역시나 느린가 봄..
3. 접근

  • 총합을 구할 수 있다.
    그리고 접근 2의 l_sum을 가지고 있으니 r_sum도 구할 수 있다.


코드)

1. 접근

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        l = len(nums)
        
        if l == 0:
            return -1
        if 0 == sum(nums[1:]):
            return 0
        
        for i in range(1, l):
            l = nums[:i]
            r = nums[i+1:]
            if sum(l) == sum(r):
                return i
        return -1

2. 접근

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        l = len(nums)
        
        if l == 0:
            return -1
        if 0 == sum(nums[1:]):
            return 0
        
        l_sum = nums[0]
        for i in range(1, l):
            r = nums[i+1:]
            if l_sum == sum(r):
                return i
            l_sum += nums[i]
        return -1

3. 접근


class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        l = len(nums)
        t_sum = sum(nums)
        
        if l == 0:
            return -1
        if 0 == sum(nums[1:]):
            return 0
        
        l_sum = nums[0]
        for i in range(1, l):
            if l_sum == t_sum - l_sum - nums[i]:
                return i
            l_sum += nums[i]
        return -1

Read more ...
작성자: 시간: 댓글 1개:
라벨: , ,

[leetcode] 112. Path Sum

원문)
Given a binary tree and a sum,
determine if the tree has a root-to-leaf path such that
adding up all the values along the path equals the given sum.


번역)
이진트리와 합계가 주어졌을때,
root부터 leaf까지 경로의 값을 모두 더했을때 나오는 값과 주어진 합이 같을때의
경로가 있는지 구하라.


예제)
Given the below binary tree and sum = 22,
      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

문제접근)
1. 접근

  • 접근은 다 맞았는데 root is None check에서 고생했다.
    생각해보면 leaf노드만 체크해야한다.
    [1,2] 1의 경우를 생각해보면 된다.


코드)

1.접근

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        return self.top_down(root, sum)
    
    def top_down(self, root: TreeNode, sum: int) -> bool:
        if root is None:
            return False
        elif root.val == sum and root.left is None and root.right is None:
            return True

        sum -= root.val
        l = self.top_down(root.left, sum)
        r = self.top_down(root.right, sum)
        return l or r



# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        stack = [(root, sum)]
        
        while stack:
            cur, s = stack.pop()
            if cur:
                if cur.val == s and cur.left is None and cur.right is None:
                    return True
                
                s -= cur.val
                stack.append((cur.left, s))
                stack.append((cur.right, s))
        return False


Read more ...
작성자: 시간: 댓글 없음:
라벨: , ,

[leetcode] 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  3

But the following [1,2,2,null,3,null,3] is not:
    1
   / \
  2   2
   \   \
   3    3

문제접근)

 1. 접근
  • left자식노드와 right자식노드를 순회를 하는데
    right노드를 반대로 돌려서 순회하고 그 순회된 값을 가지고 비교
2. 접근
  • 1접근과 비슷하지만, rev가 필요없는 방안이다.
    비교자체를 밖과 안의 노드들끼리 비교한다.
    리프노드는 True, 값이 다르거나 level이 다르면 False.

코드)

1. 접근

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# 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 root is None:
            return True
        
        l = self.top_down(root.left, False)
        r = self.top_down(root.right, True)
        return l == r
    
    def top_down(self, root: TreeNode, rev: bool):
        if root is None:
            return [None]
        
        tmp = []
        tmp += [root.val]
        if rev:
            tmp += self.top_down(root.right, rev)
            tmp += self.top_down(root.left, rev)
        else:
            tmp += self.top_down(root.left, rev)
            tmp += self.top_down(root.right, rev)
        return tmp
        



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# 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 root is None:
            return True
        return self.traverse(root.left, False) == self.traverse(root.right, True)
    
    def traverse(self, root: TreeNode, rev: bool) -> List[int]:
        if root is None:
            return []
        
        answer = []
        stack = [root]
        
        while stack:
            cur = stack.pop()
            if cur:
                answer.append(cur.val)
                if rev:
                    stack.append(cur.left)
                    stack.append(cur.right)
                else:
                    stack.append(cur.right)
                    stack.append(cur.left)
            else:
                answer.append(cur)     
        return answer



2. 접근

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 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 root is None:
            return True
        return self.top_down(root.left, root.right)
    
    def top_down(self, left: TreeNode, right: TreeNode) -> bool:
        if left is None and right is None:
            return True
        elif left and right and left.val == right.val:
            _out = self.top_down(left.left, right.right)
            _in = self.top_down(left.right, right.left)
            return _in and _out
        else:
            return False
        




# 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 root is None:
            return True
        
        stack = [(root.left, root.right)]
        ret = True
        
        while stack:
            left, right = stack.pop()
            
            if left is None and right is None:
                continue
            elif left and right and left.val == right.val:
                stack.append((left.left, right.right))
                stack.append((left.right, right.left))
            else:
                return False
        return True




Read more ...
작성자: 시간: 댓글 없음:
라벨: , ,

[leetcode] 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.

번역)
이진트리가 주어졌을때, 최대 depth를 구하라.
최대 depth는 루트로드로부터 가장 먼곳에 있는 리프노드 까지의 경로를
추적한 노드의 숫자이다.


예제)
Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
return its depth = 3.

문제접근)
여러번 계속 recursive와 while문으로 풀어버릇하면 감이 오는것 같다.

코드)

1. top-down

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        return self.top_down(root, 0)

    def top_down(self, root: TreeNode, depth: int):
        if root is None:
            return depth
        
        l_m = self.top_down(root.left, depth+1)
        r_m = self.top_down(root.right, depth+1)
        return max(l_m, r_m)

2. bottom-up


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        stack = [(root, 1)]
        depth = 0
        
        while stack:
            cur, lv = stack.pop()
            if cur:
                stack.append((cur.left, lv + 1))
                stack.append((cur.right, lv + 1))
                depth = max(depth, lv)
        return depth


Read more ...
작성자: 시간: 댓글 없음:
라벨: , ,

[leetcode] 102. Binary Tree Level Order Traversal

원문)
Given a binary tree, return the level traversal of its nodes's values.

번역)
이진트리를 주어졌을때 그 노드값을 level 순회를 반환하라.


예제)
Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

 문제접근)
top-down은 레벨을 기록해서 같은 level만 따로 분류
bottom-up도 같은 동작방식으로

코드)

1.  top-down

 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        answer = []
        self.top_down(root, 0, answer)
        return answer
    
    def top_down(self, root: TreeNode, level: int, answer: List[List[int]]):
        if root is None:
            return
        
        if len(answer) == level:
            answer.append([])
            
        answer[level].append(root.val)
        self.top_down(root.left, level + 1, answer)
        self.top_down(root.right, level + 1, answer)


2. bottom-up

 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        answer = []
        stack = [(root, 0)]
        
        while stack:
            cur, level = stack.pop()
            if cur:
                if len(answer) == level:
                    answer.append([])
                    
                answer[level].append(cur.val)
                stack.append((cur.right, level + 1))
                stack.append((cur.left, level + 1))
            
        return answer


Read more ...
작성자: 시간: 댓글 없음:
라벨: , ,
피드 구독하기: 글 (Atom)