그냥 코딩하는 사람의 블로그

https://leetcode.com/problems/longest-palindromic-substring/submissions/

풀이 과정

1. DP로 풀이하는게 정석이라고 하지만 문자열 최대 길이가 1000이므로 브루트포스로 풀수 있을것이라고 생각함.
2. 현재 위치가 i라고 하면, i 기준으로 문자를 하나씩 늘려가면서 펠린드롬이라면 문자열을 갱신하는 방식으로 코드 작성
   1. 시간 초과가 발생. 시간을 조금 절약하기 위해 정답 문자열의 길이 + 1부터 문자를 하나씩 늘려가도록 변경
   2. 위 방식으로 코드를 작성하니 시간 초과가 해결됨. 

소스 코드

class Solution:
    def longestPalindrome(self, s: str) -> str:
        answer = ""
        def checkPalindrome(s):
            return s == s[::-1]
        
        for i in range(len(s)):
            for j in range(len(answer)+1, len(s)-i+1):
                if checkPalindrome(s[i:i+j]):
                    answer = s[i:i+j] if len(answer) < j else answer
                    
        return answer

문제 설명

Given two sorted arraysnums1andnums2of sizemandnrespectively, returnthe medianof the two sorted arrays.

The overall run time complexity should beO(log (m+n)).

Example 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Example 3:

Input: nums1 = [0,0], nums2 = [0,0]
Output: 0.00000

Example 4:

Input: nums1 = [], nums2 = [1]
Output: 1.00000

Example 5:

Input: nums1 = [2], nums2 = []
Output: 2.00000

Constraints:

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -106<= nums1[i], nums2[i] <= 106

풀이 과정

• 두개 합쳐서 정렬해서 풀 수도 있지만 오래 걸림.

1. 따라서, 우선 두개의 리스트를 queue로 바꾼다.
2. 전체 개수가 홀수일때, 짝수일때 중간값의 위치가 다르다.
   • 홀수일 때 : (두개의 리스트의 길이의 합 // 2)
   • 짝수일 때 : (두개의 리스트의 길이의 합 // 2) - 1, (두개의 리스트의 길이의 합 // 2)
     • 두개를 뽑고 2로 나누어준 값이 중간값
3. 따라서 홀수일 때는 (두개의 리스트의 길이의 합 // 2) - 1개만큼 뽑아주고, 짝수일 때는 (두개의 리스트의 길이의 합 // 2) - 2개만큼 뽑아준다.
   • 이 다음에 홀수일때는 한개 뽑고, 짝수일때는 두개 뽑아서 중간값 구해주면 됨.
4. 뽑아줄 때는 두개의 큐의 가장 왼쪽에서 값을 비교하며 하나씩 뽑아준다.
   • 한쪽이 큰 경우 다른쪽에서 뽑아줌.
   • 이 때, 한쪽 큐가 비는 경우 다른쪽 큐에서만 뽑아주면 된다.

소스 코드

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        from collections import deque

        q1 = deque(nums1)
        q2 = deque(nums2)

        total_length = len(nums1) + len(nums2)
        even = False

        def next_pop(q1, q2):
            temp = 0
            if q1 and q2:
                if q1[0] > q2[0]:
                    temp = q2.popleft()
                else:
                    temp = q1.popleft()
            elif q1:
                temp = q1.popleft()
            elif q2:
                temp = q2.popleft()
            return temp


        if total_length % 2 == 0:
            even = True
            median_idx = total_length // 2 
        else:
            median_idx = total_length // 2 + 1

        for i in range(median_idx-1):
            next_pop(q1, q2)

        answer = 0
        if even:
            answer = next_pop(q1, q2) + next_pop(q1, q2)
            answer = answer / 2
        else:
            answer = next_pop(q1, q2)

        answer = answer * 1.0

        return answer

문제 설명

You are given twonon-emptylinked lists representing two non-negative integers. The digits are stored inreverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Example 2:

Input: l1 = [0], l2 = [0]
Output: [0]

Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

Constraints:

• The number of nodes in each linked list is in the range[1, 100].
• 0 <= Node.val <= 9
• It is guaranteed that the list represents a number that does not have leading zeros.

풀이 과정

1. 먼저 입력받은 두개의 Linked-List를 따라 이동하면서 더해야 하는 수 a,b를 구한다.
   • idx를 10씩 곱해주면서 val * idx를 더해주면 된다.
2. a, b를 구해주었다면, 합계를 구한 다음 문자열로 바꾸고 뒤집는다.
3. 뒤집은 수 숫자 한자리씩 Linked-List를 구성하여 주면 된다.
   • 한자리씩 노드를 만들어서, 맨 마지막 노드에 붙여주면 된다.
   • 헤드 노드를 따로 만들어주어야 함 => 리턴할 때 사용
4. Linked-List의 헤드 노드를 리턴해주면 된다.

소스 코드

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        a = 0
        idx = 1
        temp = l1
        while temp:
            a += temp.val * idx
            idx *= 10
            temp = temp.next

        b = 0
        idx = 1
        temp = l2
        while temp:
            b += temp.val * idx
            idx *= 10
            temp = temp.next

        print(a, b)
        c = str(a + b)[::-1]

        head = None
        last = None
        for i in c:
            node = ListNode(val=int(i))
            if head is None:
                head = node

            if last is not None:
                last.next = node
                last = node
            else:
                last = node

        return head

문제 설명

You are given an array of k linked-listslists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

Input:

• lists = [[1,4,5],[1,3,4],[2,6]]

Output:

• [1,1,2,3,4,4,5,6]

Explanation:

• The linked-lists are: [ 1->4->5, 1->3->4, 2->6 ] merging them into one sorted list: 1->1->2->3->4->4->5->6

Example 2:

Input:

• lists = []

Output:

• []

Example 3:

Input:

• lists = [[]]

Output:

• []

Constraints:

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i]is sorted inascending order.
• The sum oflists[i].lengthwon't exceed10^4.

풀이 과정

• 문제는 k개의 linked-list가 주어질때, 모든 linked-list를 통합하여 하나의 리스트로 만듬(오름차순으로)

1. 리스트의 모든 요소들을 최소 히프에 넣는다
   • 히프의 특성에 의해 나중에 히프에서 빼줄때 정렬되어서 나올 예정
2. 히프에서 요소를 하나씩 꺼내서, 연결 그래프의 노드로 만들어준 다음 연결 그래프의 맨 마지막 노드의 링크에 넣어준다.
   • linked list 구성하기 위해 루트는 따로 저장해 두고, 맨 마지막을 가리키는 변수 따로 지정
3. 루트 노드를 리턴해주면 된다.

소스 코드

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
import heapq
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        heap = []
        answer = []

        for l in lists:
            temp = l
            while temp != None:
                heapq.heappush(heap, temp.val)
                temp = temp.next

        root = ListNode()
        prev = root

        while heap:
            t = heapq.heappop(heap)
            temp = ListNode(val=t, next=None)
            prev.next = temp
            prev = temp

        root = root.next

        return root

문제 설명

Given therootof a binary tree,determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

• The left subtree of a node contains only nodes with keysless thanthe node's key.
• The right subtree of a node contains only nodes with keysgreater thanthe node's key.
• Both the left and right subtrees must also be binary search trees.

Example 1:

Input: root = [2,1,3] Output: true

Example 2:

Input: root = [5,1,4,null,null,3,6] Output: false Explanation: The root node's value is 5 but its right child's value is 4.

Constraints:

• The number of nodes in the tree is in the range[1, 104].
• -231<= Node.val <= 231- 1

풀이 과정

1. 처음엔 부모 노드 기준으로 왼쪽, 오른쪽 노드의 값을 검사하는 방식으로만 진행
   • 트리의 깊이가 깊어지면 틀림.
   • 루트 노드 기준으로 .. 왼쪽 서브 트리의 모든 값은 루트 노드보다 작아야 되고, 오른쪽 서브 트리의 모든 값은 루트 노드보다 커야 함.
2. 따라서, 범위를 기준으로 Validate 진행
   • 초기 범위를 -2의 32승 ~ 2의 32승으로 두고
   • 현재 노드의 값이 범위 내에 들어있는지 검사(들어있지 않다면 False)
   • 현재 노드의 값이 범위 내에 들어있으면 자식 노드들 방문
     • 방문할 때, 범위 조절해주어야 함. 현재 범위가 (a ~ b)라면
     • 왼쪽 방문할 때는 (a ~ 현재 노드의 값)
     • 오른쪽 방문할 때는 (현재 노드의 값 ~ b)
3. 모든 노드들에 대해 조건 만족하는 경우 이진 트리이므로 True, 아니면 False 리턴

소스 코드

# 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 isValidBST(self, root: Optional[TreeNode]) -> bool:
        flag = False
        def validate(root, fr, to):
            if root == None:
                return True

            if fr < root.val and root.val < to:
                return validate(root.left, fr, root.val) and validate(root.right, root.val, to)
            else:
                return False

        return validate(root, -2**32, 2**32) 

문제 설명

3.Longest Substring Without Repeating Characters

Medium

Given a strings, find the length of the longest substring without repeating characters.

Example 1:
**Input:** s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Example 4:
Input: s = ""
Output: 0

Constraints:

• 0 <= s.length <= 5 * 10^4
• consists of English letters, digits, symbols and spaces.

풀이 과정

1. 현재 중복을 검사할 set과 Substring을 담을 queue를 구성한다.
2. 문자열을 왼쪽에서부터 오른쪽으로 문자 하나씩 진행한다
   • 문자 하나씩 반복문을 진행한다.
   • 만약 문자가 set 안에 있는 경우는, 기존 길이가 answer보다 길다면 저장한 다음, 해당 문자까지 queue와 set에서 빼주고 set하고 queue의 맨 마지막에 해당 문자를 다시 넣어준다.
   • 만약 문자가 set 안에 있지 않은 경우는 그대로 queue와 set에 넣어주면 된다.
3. 길이 최댓값을 리턴

소스 코드

from collections import deque

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        answer = 0
        length = 1
        if len(s) == 0:
            return 0
        check = set([s[0]])
        queue = deque([s[0]])
        for i in range(1, len(s)):
            if s[i] not in check:
                length += 1
                check.add(s[i])
                queue.append(s[i])
            else:
                answer = max(length, answer)
                while queue:
                    p = queue.popleft()
                    check.remove(p)
                    if p == s[i]:
                        break
                queue.append(s[i])
                check.add(s[i])
                length = len(check)

        answer = max(length, answer)
        return answer