LeetCode day2

4 minutes read
LeetCode
#LeetCode
views 844 words

20. Valid Parentheses

Topic: String, Stack

Given a string containing just the characters ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets
  2. Open brackets must be closed in the correct order

Note that an empty string is also considered valid.

Example 1:

Input: "()"
Output: true

Example 2:

Input: "()[]{}"
Output: true

Example 3:

Input: "(]"
Output: false

Example 4:

Input: "([)]"
Output: false

Example 5:

Input: "{[]}"
Output: true

Approach1

def isValid(self, s: str) -> bool:
    dic = {'{': '}',  '[': ']', '(': ')', '?': '?'}
    stack = ['?']
    for c in s:
        if c in dic: stack.append(c)
        elif dic[stack.pop()] != c: return False 
    return len(stack) == 1

Approach2

slow runtime, but code is neat

def isValid(self, s):
    while "()" in s or "{}" in s or '[]' in s:
        s = s.replace("()", "").replace('{}', "").replace('[]', "")
    return s == ''

21. Merge Two Sorted Lists

Topic: Linked List

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

Approach1

iteratively(24ms):

    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = cur = ListNode(0)
        while l1 and l2:
            if l1.val < l2.val:
                cur.next = l1
                l1 = l1.next
            else:
                cur.next = l2
                l2 = l2.next
            cur = cur.next
        cur.next = l1 or l2
        return dummy.next

Approach2

recursively(48ms):

def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
    if l1 and l2:
		# keep l1 always point to the smallest node
        if l1.val > l2.val:
            l1, l2 = l2, l1
		# so each step, connect the current smallest node to the already linked list
        l1.next = self.mergeTwoLists(l1.next, l2)
	# short-circuit evaluation, if l1 not None, return l1, else, return l2
    return l1 or l2

26. Remove Duplicates from Sorted Array

Topic: Array, Two Pointers

Given a sorted array nums, remove the duplicates in-place(原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度) (an in-place algorithm is an algorithm which transforms input using no auxiliary data structure.) such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place (原地修改输入数组) with O(1) extra memory.

Example 1:

Given nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.

It doesn't matter what you leave beyond the returned length.

Example 2:

Given nums = [0,0,1,1,1,2,2,3,3,4],

Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.

It doesn't matter what values are set beyond the returned length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

Approach1

def removeDuplicates(self, nums: List[int]) -> int:
    len_ = 1
    if len(nums)==0:
        return 0
    for i in range(1,len(nums)):
        if nums[i] != nums[i-1]:
            nums[len_] = nums[i]
            len_ +=1
    print(len_,nums)
    return len_

Approach2

Same as approach1 but neat

def removeDuplicates(nums):
    if not nums: return 0
    i = 0
    for j in range(1, len(nums)):
        if nums[i] != nums[j]:
            i += 1
            nums[i] = nums[j]
            print(nums,i,j)
            '''
            [0, 1, 1, 1, 1, 2, 2, 3, 3, 4] 1 2
            [0, 1, 2, 1, 1, 2, 2, 3, 3, 4] 2 5
            [0, 1, 2, 3, 1, 2, 2, 3, 3, 4] 3 7
            [0, 1, 2, 3, 4, 2, 2, 3, 3, 4] 4 9
            '''
    return i + 1

28. Implement strStr()

Topic: String, Two Pointers

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = "hello", needle = "ll"
Output: 2

Example 2:

Input: haystack = "aaaaa", needle = "bba"
Output: -1

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C’s strstr() and Java’s indexOf().

Approach1

def strStr(self, haystack: str, needle: str) -> int:
    if needle == '':
        return 0
    return haystack.find(needle)

Approach2

def strStr(self, haystack: str, needle: str) -> int:
    if needle == '':
        return 0
    for i in range(0, len(haystack) - len(needle) + 1):
        if haystack[i:i+len(needle)] == needle:
            return i
    
    return -1