눈가락★

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree

주어진 리스트는 정렬되어있기 때문에, 정중앙값이 무조건 root 가 된다.

따라서 리스트의 중앙값을 찾아서 TreeNode의 val 로 설정하고,

중앙값의 왼쪽 리스트를 TreeNode 의 left 로 설정하고,

중앙값의 오른쪽 리스트를 TreeNode 의 right 로 설정하면 된다.

리스트가 None 이거나, 리스트의 길이가 1개 이하일때는, 그 자체로 완성된 BST 이므로 리스트를 TreeNode 로 그대로 반환한다.

python 은 간단하게 리스트를 자르는 방법을 제공하므로 이 방법을 이용하면 직관적인 코드를 작성할 수 있다.

리스트를 자르는 행위는 O(n) 시간을 소모하므로 효율적이지 못하다.

따라서 리스트를 실제로 자르지 않고, 인덱스를 사용하여 논리적으로 잘라 판단한다.

# 리스트를 실제로 잘라서 사용
class Solution:
    def func(self, nums: List[int], mid: int) -> Optional[TreeNode]:
        if(not nums or len(nums)==0): return None
        if(len(nums)==1): return TreeNode(nums[0])
        tree = TreeNode(nums[mid])
        left = nums[0:mid]
        right = nums[mid+1:len(nums)]
        tree.left = self.func(left, len(left)//2)
        tree.right = self.func(right, len(right)//2)
        return tree

    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        return self.func(nums, len(nums)//2)

# 인덱스를 이용하여 리스트를 구분
class Solution:
    def func(self, nums: List[int], li: int, ri: int) -> Optional[TreeNode]:
        if(not nums or li>=ri): return None
        if(li==ri+1): return TreeNode(nums[0])
        mid = (li+ri)//2
        tree = TreeNode(nums[mid])
        tree.left = self.func(nums, li, mid)
        tree.right = self.func(nums, mid+1, ri)
        return tree

    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        return self.func(nums, 0, len(nums))

< English (feedback by ChatGPT) >

The given list is already sorted, so the middle value in the list becomes a root without a reason.

(The given list is already sorted, so the middle value will always be the root of the BST.)

So, we can find the middle value in the list and set it as a TreeNode's 'val',

(We find the middle value and assign it as the val of a TreeNode.)

set the left part of the list from the middle value as a TreeNode's 'left',

set the right part of the list from the middle value as a TreeNode's 'right'.

(Then we recursively assign the left part of the list (before the middle) as the left child,

and the right part (after the middle) as the right child.)

If the list is None or the length of the list is less than 1, it means the list is already complete BST,

so just we can retrun the list itself as a TreeNode.
(If the list is None or its length is 1 or less, it is already a complete BST,

so we can directly return it as a TreeNode.)

Python supports an easy way to chop a list, so we can use the way to write some intuitive codes.

(Python provides a convenient way to slice lists, which allows us to write intuitive code.)

Chopping a list needs O(n) time complexity, and it is not efficient.

(However, slicing a list takes O(n) time, which is not efficient.)

So we can use indexes to seperate the list rather than chopping.

(To improve performance, we can avoid slicing and instead use index boundaries to simulate the splits logically.)

주어진 두 개의 트리를 같은 순서대로 동시에 순회한다.

순회하면서 두 트리 노드 값이 같은지 확인한다.

두 트리 노드 값이 None 이면 같다고 처리한다.

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if(p is None and q is None): return True
        if(p is None or q is None or p.val != q.val): return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

< English (feedback by ChatGPT) >

We Iterate through the two given trees simultaneously as a same step.

(We iterate through the two given trees simultaneously in the same order.)

While iteration, we can check whether the two nodes of each trees have the same values.

(During the traversal, we check whether the corresponding nodes in each tree have the same values.)

It's the same when the both of two tree node values are None.

(If both nodes are None, we consider them equal.)

다이나믹 프로그래밍 문제 푸는 방법은 https://eyeballs.tistory.com/179 참고

길이가 n 인 계단을 오르는 방법의 수를 구하면 된다.

오르는 방법은 두 가지, 한 계단을 오르는 방법과 두 계단을 오르는 방법.

한 계단을 오르면 길이가 1 만큼 줄어들기 때문에, 길이가 n-1인 계단을 오르는 방법의 수를 구하면 된다.

두 계단을 오르면 길이가 2 만큼 줄어들기 때문에, 길이가 n-2인 계단을 오르는 방법의 수를 구하면 된다.

이 두 케이스를 합친 점화식은 d(n) = d(n-1) + d(n-2) 가 된다.

베이스 케이스는 간단하다.
계단이 하나뿐인 계단(d(1))을 오르는 방법은 1이고

계단이 두 개인 계단(d(2))을 오르는 방법은 2이다.

계단이 세 개인 계단(d(3))은 점화식으로 구할 수 있다.

class Solution:
    def climbStairs(self, n: int) -> int:
        d = dict()
        for i in range(1, n+1):
            if(i<3) : d[i]=i
            else : d[i] = d[i-1] + d[i-2]
        return d[n]

< English (feedback by ChatGPT) >

The task is to get how many steps we need to go upstair with the n length of the stair.

(The task is to find the number of ways to climb a staircase with n steps.)

There are two ways to go upstair, one step at once and two step at once.

(There are two possible moves: climbing one step at a time or two steps at a time.)

When go upstair with one step, length is decreased by 1, then we will get how many steps we need to go upstair with n-1 length of the stair.

(If you take one step, the remaining length becomes n-1, so the number of ways to climb is the same as for a staircase of length n-1.)

When go upstair with two steps, length is decreased by 2, then we will get how many steps we need to go upstair with n-2 length of the stair.

(If you take two steps, the remaining length becomes n-2, so the number of ways is the same as for a staircase of length n-2.)

The recurrence formula with the two cases is d(n) = d(n-1) + d(n-2)

(Combining these two cases gives the recurrence formula: d(n) = d(n-1) + d(n-2).)

The base case is simple.

(The base cases are simple:)

It's 1 way to go upstair with the 1 length of the stair.

(There is only 1 way to climb a staircase with 1 step,)

It's 2 ways to go upstair with the 2 length of the stair.

(and 2 ways to climb a staircase with 2 steps.)

The steps to go upstair with the 3 length of the stair could be calculated by the recurrence formula.

(For 3 steps, we can calculate the number of ways using the recurrence formula.)

주어진 list1, list2 의 값들을 앞에서부터 차례대로 비교한다.

두 값 중 더 작은 값을 ListNode 에 넣고, 작은 값이 넣어진 list 를 next 로 옮긴다.

두 list 중 하나라도 None 인 경우, 비교를 위한 반복문이 멈춘다.

반복문을 빠져나온 후에도 아직 값이 남아있는 list 가 있다면, 반환할 ListNode 뒤에 남은 list 를 모두 덧붙여준다.

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if(list1 is None): return list2

        l1 = list1
        l2 = list2
        result = ml = ListNode()
        while(l1 is not None and l2 is not None):
            if(l1.val < l2.val):
                ml.val = l1.val
                l1 = l1.next
            else:
                ml.val = l2.val
                l2 = l2.next
            ml.next = ListNode()
            ml = ml.next
        if(l1 is not None):
            ml.val = l1.val
            ml.next = l1.next
        if(l2 is not None):
            ml.val = l2.val
            ml.next = l2.next
        return result

< English (feedback by ChatGPT) >

We will compare the two values of the given list1, list2 from the beginning.

(We compare the values of list1 and list2 one by one from the beginning.)

Assign the smaller value between them into ListNode, and move its next of the list which is assigned.

(At each step, we insert the smaller value into a new ListNode, and move forward in the list from which the smaller value was taken.)

If one of the two lists is equals to None, the while loop for comparison is stopped.

(The loop continues until one of the lists becomes None.)

After loop is stopped, if one of the two lists has values left, append all the left to ListNode which will be returned.

(After the loop ends, if any elements remain in either list, we append the remaining nodes to the end of the result ListNode.)

https://leetcode.com/problems/remove-duplicates-from-sorted-array

in-place 알고리즘을 사용하여, 주어진 리스트 내의 중복값을 없애는 문제이다.

중복을 없앤 숫자값들을 리스트의 가장 앞에 배치하면 된다.

간단하게 두 개의 포인터를 사용하여 구현할 수 있다.

r 포인터는 리스트를 처음부터 끝까지 순회한다.

l 포인터와 r 포인터가 가리키는 값이 서로 다르면, l 포인터 위치를 하나 증가시키고 l 포인터 자리에 r 포인터 값을 넣는다.

l 포인터가 리스트를 벗어날까봐 걱정할 필요는 없다.

r 포인터가 항상 l 포인터보다 크기 때문에, l 포인터의 최댓값은 r 포인터의 값이 된다.

그리고 r 포인터는 리스트의 range 를 넘기지 않는다.

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

< English (feedback by ChatGPT) >

This is the problem to remove the duplicates in the given list using the in-place algorithm.

(This problem requires removing duplicates from a given list using an in-place algorithm.)

The digit values after removing the duplicates should be placed at the front of the list.

(The unique values should be placed at the beginning of the list.)

I simply implemented using two pointers.

(I implemented this simply using two pointers.)

'r pointer' iterates through the list.

(The r pointer iterates through the list.)

If the values at 'l pointer' and 'r pointer' are not matched, increase 'l pointer' by 1 and put 'r pointer' value into 'l pointer' value.

(If the values at the l and r pointers are different, we increment the l pointer by one and assign the value at r to the new l position.)

We don't need to worry if 'l pointer' exceeds the range of the list.

(We don’t need to worry about the l pointer exceeding the list’s range,)

'r pointer' is always bigger than 'l pointer' so the biggest index of 'l pointer' is the same with 'r pointer'

(because the r pointer is always ahead of the l pointer, so the maximum index l can reach is equal to that of r.)

and 'r pointer' never exceed the range of the list.

(Also, the r pointer never goes beyond the list’s range.)