LeetCode day29

3 minutes read
LeetCode
#LeetCode
views 628 words

Diffculty: Medium

300. Longest Increasing Subsequence

Topic: DP, Binary Search

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Note:

  • There may be more than one LIS combination, it is only necessary for you to return the length.
  • Your algorithm should run in O(n^2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

Approach1

Approach2

322. Coin Change

Topic: DP

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:

Input: coins = [1, 2, 5], amount = 11
Output: 3 
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

Note: You may assume that you have an infinite number of each kind of coin.

Approach1

Approach2

324. Wiggle Sort II

Topic: Sort

Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]….

Example 1:

Input: nums = [1, 5, 1, 1, 6, 4]
Output: One possible answer is [1, 4, 1, 5, 1, 6].

Example 2:

Input: nums = [1, 3, 2, 2, 3, 1]
Output: One possible answer is [2, 3, 1, 3, 1, 2].

Note: You may assume all input has valid answer.

Follow Up: Can you do it in O(n) time and/or in-place with O(1) extra space?

Approach1

my

def wiggleSort(nums: List[int]) -> None:
    """
    Do not return anything, modify nums in-place instead.
    """
    nums.sort()
    mid = len(nums) //2
    nums[0::2],nums[1::2] = nums[:mid], nums[mid:]
    # print(nums)

Approach2

荷兰旗

def wiggleSort(nums: List[int]) -> None:
    """
    Do not return anything, modify nums in-place instead.
    """
    n = len(nums)
    if n < 2:return nums
    mid = (0 + n-1) // 2 # 中位数索引
    

    # 快速排序中的一次划分
    def partition(begin,end):
        left,right = begin,end
        while left < right:
            while left < right and nums[left] < nums[right]:right -= 1
            if left < right:
                nums[left],nums[right] = nums[right],nums[left]
                left += 1
            while left < right and nums[left] < nums[right]: left += 1
            if left < right:
                nums[left],nums[right] = nums[right],nums[left]
                right -= 1
        return left

    # 找到中位数对应的数值
    left,right = 0, n-1
    while True:
        pivot = partition(left,right)
        if pivot == mid:break
        elif pivot > mid:right = pivot - 1
        else:left = pivot + 1

    # 三路划分(荷兰旗)
    midNum = nums[mid]
    left,curr,right = 0, 0, n-1
    while curr < right:
        if nums[curr] < midNum:
            nums[left],nums[curr] = nums[curr],nums[left]
            left += 1
            curr += 1
        elif nums[curr] > midNum:
            nums[curr],nums[right] = nums[right],nums[curr]
            right -= 1
        else:
            curr += 1

    # 交叉合并
    small,big ,_nums = mid,n-1,nums[:]
    for i in range(n):
        if i%2 == 0:
            nums[i] = _nums[small]
            small -= 1
        else:#big
            nums[i] = _nums[big]
            big -= 1

理论上时间复杂度是O(N),空间复杂度是O（1），但其实比较慢，只能击败15%左右

328. Odd Even Linked List

Topic: Linked list

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

Example 1:

Input: 1->2->3->4->5->NULL
Output: 1->3->5->2->4->NULL

Example 2:

Input: 2->1->3->5->6->4->7->NULL
Output: 2->3->6->7->1->5->4->NULL

Note:

  • The relative order inside both the even and odd groups should remain as it was in the input.
  • The first node is considered odd, the second node even and so on …

Approach1

def oddEvenList(head: ListNode) -> ListNode:
    if not head:return head
    odd = head
    even_head = even = head.next
    while odd.next and even.next:
        odd.next = odd.next.next
        even.next = even.next.next
        odd,even = odd.next,even.next
    odd.next = even_head
    return head

Approach2