본문 바로가기

leetcode

 (9)
[leetcode] 28. Implement strStr() (easy) class Solution: def strStr(self, haystack: str, needle: str) -> int: if not needle: return 0 needle_len = len(needle) haystack_len = len(haystack) for i in range(haystack_len-needle_len+1): temp = haystack[i:i+needle_len] if temp == needle: return i return -1 [문제] 주어진 haystack 스트링 안에서 needle 스트링을 찾는 문제이다 Input: haystack = "hello", needle = "ll" Output: 2 [풀이] hatstack 스트링 안에서 인덱스를 하나씩 이동하며, need..
[leetcode] 21. Merge Two Sorted Lists [easy] # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: ans = ListNode(None) temp = ans node1 = l1 node2 = l2 v1, v2 = -1, -1 while node1 != None: # set values v1 = node1.val if node2 != None: v2 = node2.val if v1 2->4, 1->3->4 Output: 1->1->2->3->4->4 [풀이] 하..
[leetcode] 26. Remove Duplicates from Sorted Array class Solution: def removeDuplicates(self, nums: List[int]) -> int: ans = 0 nums_new = sorted(set(nums)) for i, v in enumerate(nums_new): ans = ans + 1 nums[i] = v del nums[ans:] return ans [문제] 정렬된 배열이 input으로 들어오고, 중복된 숫자를 제거해서 전체 갯수를 리턴한다. 단, nums도 직접 수정을 해야 한다. 아래와 같이 사용하기 위해서 // nums is passed in by reference. (i.e., without making a copy) int len = removeDuplicates(nums); // any modificati..
[leetcode] 20. Valid Parentheses (easy) class Solution: def isValid(self, s: str) -> bool: dic = {'(':')', '{':'}', '[':']'} stack = [] for c in s: # print ('c is', c) if c in ['(','{','[']: stack.append(c) else: if len(stack) == 0: return False pop = stack.pop() if dic[pop] == c: continue else: return False if len(stack) > 0: return False return True [문제] 규칙에 맞게 괄호 여닫는게 제대로 되어 있는 지 확인하는 문제 [풀이] stack을 이용해서 해결 - 여는 괄호가 나오면 push - 닫는 괄..
[leetcode] 14. Longest Common Prefix (easy) class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: ans = '' for chars in zip(*strs): print(chars) char = set(chars) if len(char) != 1: break else: ans = ans + chars[0] return ans [문제] Input: ["flower","flow","flight"] Output: "fl" 스트링 배열로 들어오는 스트링 간에 공통적인 앞글자들을 찾는 문제임 [풀이] 파이썬3에서 제공하는 * (unzip 기능)과 zip 내장함수를 이용하여 해결 - 먼저 스트링 배열을 * 를 통해 배열을 제거한다. zip 함수를 사용하기 위해서... : flower f..
[leetcode] 13. Roman to Integer (easy) class Solution: def romanToInt(self, s: str) -> int: dict = {'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000} ans = 0 size = len(s) for i in range(size): if i I 1, V 5, X 10, L 50, C 100, D 500, M 1000 [풀이] 4, 9, 40, 90, 400, 9..
[leetcode] 9. Palindrome Number (easy) class Solution: def isPalindrome(self, x: int) -> bool: if x 321-) 숫자를 문자열로 변환하고, for loop를 돌면서, 양 끝 캐릭터가 다른 지 여부를 판별한다. 다른 캐릭터가 발견되면 False, 발견되지 않으면 True 난이도가 Easy여서 별로 어렵진 않았음
팰린드롬 Palindrome 문제 풀기 - Manacher 알고리즘(Manacher's Algorithm) Manacher's algorithm 을 이용해서 해결한다. Brute-Force 알고리즘을 사용하면 O(n^2) 시간 복잡도가 걸린다. 맨체스터 알고리즘 사용 시, O(n) 시간 복잡도가 걸린다.

티스토리툴바