티스토리

My Software Engineering

검색하기

블로그 홈

My Software Engineering

leeter.tistory.com/m

Leeter 님의 블로그입니다.

구독자: 0

방명록 방문하기

주요 글 목록

300. Longest Increasing Subsequence Description: Given an integer array nums, return the length of the longest strictly increasing subsequence. A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7]. ''' [1] brute force) -idea:: when, cur_num==-float(inf), from idx==0 to .. 공감수 0 댓글수 0 2021. 11. 26.
435. Non-overlapping Intervals Description: Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping. ''' [1] sort and greedy) -idea:: sort intervals(key is interval[0]) then, keep end point(interval[0]) while comparing next interval with end, It is advantageous to remove longer interval (greedy approa.. 공감수 0 댓글수 0 2021. 11. 21.
57. Insert Interval Description: You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval. Insert newInterval into intervals such that intervals is still sorte.. 공감수 0 댓글수 0 2021. 11. 21.
106. Construct Binary Tree from Inorder and Postorder Traversal Description: Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree. # 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 ''' [1] divide and se.. 공감수 0 댓글수 0 2021. 11. 21.
540. Single Element in a Sorted Array Description: You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Return the single element that appears only once. Your solution must run in O(log n) time and O(1) space. ''' [1] binary search) idea:: set left and right. compare mid with both mid-1 and mid+1 code:: def singleNonDuplicate(self, nums.. 공감수 0 댓글수 0 2021. 11. 20.
208. Implement Trie (Prefix Tree) Description: A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker. Implement the Trie class: Trie() Initializes the trie object. void insert(String word) Inserts the string word into the trie. boolean search(String word).. 공감수 0 댓글수 0 2021. 11. 17.
235. Lowest Common Ancestor of a Binary Search Tree Description: Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST. According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).” # Definition for a binary tree node. # class TreeNod.. 공감수 0 댓글수 0 2021. 11. 17.
62. Unique Paths Description: A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below). How many possible unique paths are there? ''' [1] dp) idea:: paths[i][j]=path[i-1][j]+path[i][j-1] code:: def unique.. 공감수 0 댓글수 0 2021. 11. 17.
230. Kth Smallest Element in a BST Description: Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree. # 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 ''' [1] recursive) idea:: compare the number of nodes of left sub-tree (denot.. 공감수 0 댓글수 0 2021. 11. 16.
98. Validate Binary Search Tree Description: Given the root of 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 keys less than the node's key. The right subtree of a node contains only nodes with keys greater than the node's key. Both the left and right subtrees must also be binary search trees. # Definition for a binary t.. 공감수 0 댓글수 0 2021. 11. 16.
297. Serialize and Deserialize Binary Tree Description: Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment. Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deser.. 공감수 0 댓글수 0 2021. 11. 15.
124. Binary Tree Maximum Path Sum Description: A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root. The path sum of a path is the sum of the node's values in the path. Given the root of a binary tree, return the maximum path sum of any non-empty p.. 공감수 0 댓글수 0 2021. 11. 15.
105. Construct Binary Tree from Preorder and Inorder Traversal Description: Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree. # 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 ''' [1] divide and set) .. 공감수 0 댓글수 0 2021. 11. 15.
572. Subtree of Another Tree Description: Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise. A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree could also be considered as a subtree of itself. # Definition for a binary tree node. # class.. 공감수 0 댓글수 0 2021. 11. 15.
102. Binary Tree Level Order Traversal Description: Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level). # 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 ''' [1] using queue) code:: from collections import deque class Solution: def levelOrder(.. 공감수 0 댓글수 0 2021. 11. 14.
104. Maximum Depth of Binary Tree Description: Given the root of a binary tree, return its maximum depth. A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. # 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 ''' [1] bottom-up) code:: def maxDe.. 공감수 0 댓글수 0 2021. 11. 12.
100. Same Tree Description: Given the root of a binary tree, return its maximum depth. A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. # 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 ''' [1] top-down) idea:: check whet.. 공감수 0 댓글수 0 2021. 11. 12.
143. Reorder List Description: You are given the head of a singly linked-list. The list can be represented as: L0 → L1 → … → Ln - 1 → Ln Reorder the list to be on the following form: L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → … You may not modify the values in the list's nodes. Only nodes themselves may be changed. # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.va.. 공감수 0 댓글수 0 2021. 11. 12.
19. Remove Nth Node From End of List Description: Given the head of a linked list, remove the nth node from the end of the list and return its head. # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next ''' [1] two pass) idea:: 1. get the length of linked list, let it len 2. delete len-n+1 th node code:: def removeNthFromEnd(self, head: Optional[ListNode],.. 공감수 0 댓글수 0 2021. 11. 12.
367. Valid Perfect Square Description: Given a positive integer num, write a function which returns True if num is a perfect square else False. Follow up: Do not use any built-in library function such as sqrt. ''' [1] brute force) code:: def isPerfectSqurare(num): for i in range(1,num): if i*i==num: return True elif i*i>num: # optimization break return False -T/C: O(n) -S/C: O(1) ''' ''' [2] brute force - optimization) c.. 공감수 0 댓글수 0 2021. 11. 12.
203. Remove Linked List Elements Description: Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head. # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next ''' [1] two pointers - inplace) idea:: this problem can be solved using out-place. but, in-place also can be so.. 공감수 0 댓글수 0 2021. 11. 12.
1413. Minimum Value to Get Positive Step by Step Sum Description: Given an array of integers nums, you start with an initial positive value startValue. In each iteration, you calculate the step by step sum of startValue plus elements in nums (from left to right). Return the minimum positive value of startValue such that the step by step sum is never less than 1. ''' [1] prefix sum) code:: def minStartValue(self, nums: List[int]) -> int: prefix=cop.. 공감수 0 댓글수 0 2021. 11. 11.
23. Merge k Sorted Lists Description: You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it. # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next ''' [1] sort) idea:: 1. while traversing all linked list, append val to list 2. sort it 3.. 공감수 0 댓글수 0 2021. 11. 10.
122. Best Time to Buy and Sell Stock II Description: You are given an integer array prices where prices[i] is the price of a given stock on the ith day. On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day. Find and return the maximum profit you can achieve. ''' [1] brute force - recursive and calculate a.. 공감수 0 댓글수 0 2021. 11. 10.
21. Merge Two Sorted Lists Description: Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists. # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next ''' [1] linear-merge) code:: def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[.. 공감수 0 댓글수 0 2021. 11. 10.
438. Find All Anagrams in a String Description: Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order. An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once. ''' [1] sliding window and hashmap) # optimization required idea:: pMap contains every frequency of all .. 공감수 0 댓글수 0 2021. 11. 9.
141. Linked List Cycle Description: Given head, the head of a linked list, determine if the linked list has a cycle in it. There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter. Return true if the.. 공감수 0 댓글수 0 2021. 11. 9.
206. Reverse Linked List Description: Given the head of a singly linked list, reverse the list, and return the reversed list. # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next ''' [1] iterative) code:: def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: prev=None cur=head next=cur while cur: next=cur.next cur.next=prev pr.. 공감수 0 댓글수 0 2021. 11. 9.
5. Longest Palindromic Substring Description: Given a string s, return the longest palindromic substring in s. ''' [1] brute force) idea:: by using nested-loop. check substring is palindrome, if it is, longest substring. code:: def longestPalindrome(self, s: str) -> str: longest='' for i in range(len(s)): for j in range(i,len(s)): if self.isPalindrome(s[i:j+1]) and len(longest) str: # init dp=[[0 if i!=j else 1 for i in range(l.. 공감수 0 댓글수 0 2021. 11. 8.
96. Unique Binary Search Trees Description: Given an integer n, return the number of structurally unique BST's (binary search trees) which has exactly n nodes of unique values from 1 to n. ''' [1] recursive) idea:: when n=3, then 1 and 2 and 3 can be root node 1. when 1 is a root node, left-subTree will be None, right-subTree will be made by [2,3] 2. when 2 is a root node, left-subTree will be made by [1], right-subTree will .. 공감수 0 댓글수 0 2021. 11. 8.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.