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?

## 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.

## 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

## 328. Odd Even 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:
return head