853. Car Fleet

Medium

N cars are going to the same destination along a one lane road. The destination is target miles away.

Each car i has a constant speed speed[i] (in miles per hour), and initial position position[i] miles towards the target along the road.

A car can never pass another car ahead of it, but it can catch up to it, and drive bumper to bumper at the same speed.

The distance between these two cars is ignored - they are assumed to have the same position.

A car fleet is some non-empty set of cars driving at the same position and same speed. Note that a single car is also a car fleet.

If a car catches up to a car fleet right at the destination point, it will still be considered as one car fleet.

How many car fleets will arrive at the destination?

題目大意：高速公路上有一系列車從不同的位置出發(fā)拓春，它們各自的速度不同，從同一個方向前往同一個終點五芝，它們不能超車痘儡，一旦遇上只能前后排成一個car fleet辕万，問到達終點時有多少個car fleet枢步。

解題思路：計算每輛車到終點需要的時間，時間長的一定會被時間短的擋住渐尿，成為一個car fleet醉途。下面嘗試用python解題。

class Solution:
    def carFleet(self, target: int, pos: List[int], speed: List[int]) -> int:
        #corner case handle
        if len(pos) != len(speed) or len(pos) == 0 :
            return 0

        cars = []
        #car position, time to reach target
        for i in range(len(pos)):
            cars.append((pos[i], 1.0*(target - pos[i])/speed[i]))

        #sort in reverse order
        cars.sort(key=lambda tup: tup[0], reverse=True)
        car_fleet = 0
        max_time = 0
        for _, t in cars:
            #max_time record the time for prev car fleet, if the next car
            # need less time to reach target, it would be blocked and join
            # the prev car fleet
            if t > max_time:
                #new car fleet exist if need to take event more to reach
                #   the final target
                max_time = t
                car_fleet += 1
        return car_fleet
        

在線測試一下

Success
[Details]
Runtime: 76 ms, faster than 93.20% of Python3 online submissions for Car Fleet.
Memory Usage: 15.3 MB, less than 59.78% of Python3 online submissions for Car Fleet.

976. Largest Perimeter Triangle

Easy

Given an array A of positive lengths, return the largest perimeter of a triangle with non-zero area, formed from 3 of these lengths.

If it is impossible to form any triangle of non-zero area, return 0.

Example 1:

Input: [2,1,2]
Output: 5

Example 2:

Input: [1,2,1]
Output: 0

Example 3:

Input: [3,2,3,4]
Output: 10

Example 4:

Input: [3,6,2,3]
Output: 8

Note:

3 <= A.length <= 10000
1 <= A[i] <= 10^6

題目大意：給一組數(shù)砖茸，找出三個數(shù)組成三角形隘擎，要求其周長最長。

解題思路：要組成三角形凉夯，要求兩短邊之和大于第三邊货葬，除此之外采幌，選的三邊越長，周長也越長震桶。

class Solution:
    def largestPerimeter(self, nums: List[int]) -> int:
        nums.sort(reverse=True) #sort in reverse order
        for i in range(len(nums) - 2):
            if nums[i] < nums[i+1] + nums[i+2]:
                return nums[i] + nums[i+1] + nums[i+2]
        return 0        

測試一下休傍，

Success
[Details]
Runtime: 72 ms, faster than 90.14% of Python3 online submissions for Largest Perimeter Triangle.
Memory Usage: 13.9 MB, less than 62.16% of Python3 online submissions for Largest Perimeter Triangle.

945. Minimum Increment to Make Array Unique

Medium

Given an array of integers A, a move consists of choosing any A[i], and incrementing it by 1.

Return the least number of moves to make every value in A unique.

Example 1:

Input: [1,2,2]
Output: 1
Explanation: After 1 move, the array could be [1, 2, 3].

Example 2:

Input: [3,2,1,2,1,7]
Output: 6
Explanation: After 6 moves, the array could be [3, 4, 1, 2, 5, 7].
It can be shown with 5 or less moves that it is impossible for the array to have all unique values.

Note:
0 <= A.length <= 40000
0 <= A[i] < 40000

題目大意：給一組數(shù)據(jù)，數(shù)據(jù)中存在重復(fù)蹲姐，要求以最小的改動磨取，使得數(shù)據(jù)中的元素都是唯一的。

解題思路：從最小的元素開始柴墩，依次修改重復(fù)元素忙厌。

    def minIncrementForUnique(self, nums: List[int]) -> int:
        nums.sort(reverse=False)
        ans = 0
        cnt = {}
        for n in nums:
            cnt[n] = 1

        #1  1        2    2     3     7
        #0 +1(2)  +1(3)  +2(4)  +2(5) 
        for i in range(1, len(nums)):
            if nums[i] > nums[i-1]:
                continue
            #calculate distance between two adjecent num
            ans += nums[i-1] - nums[i] + 1
            #make following num one more than previous one to
            #   make it unique
            nums[i] = nums[i-1] + 1

        return ans 

測試一下

Success
[Details]
Runtime: 168 ms, faster than 42.89% of Python3 online submissions for Minimum Increment to Make Array Unique.
Memory Usage: 19 MB, less than 7.08% of Python3 online submissions for Minimum Increment to Make Array Unique.

922. Sort Array By Parity II

Easy

Given an array A of non-negative integers, half of the integers in A are odd, and half of the integers are even.

Sort the array so that whenever A[i] is odd, i is odd; and whenever A[i] is even, i is even.

You may return any answer array that satisfies this condition.

Example 1:

Input: [4,2,5,7]
Output: [4,5,2,7]
Explanation: [4,7,2,5], [2,5,4,7], [2,7,4,5] would also have been accepted.

Note:

2 <= A.length <= 20000
A.length % 2 == 0
0 <= A[i] <= 1000

題目大意：給定一個數(shù)組，要求調(diào)整元素順序江咳，使得奇數(shù)位的放的都是奇數(shù)逢净，偶數(shù)位放的是偶數(shù)。

解題思路：對數(shù)組進行依次掃描歼指，標(biāo)記需要調(diào)整位置的元素汹胃，第二次掃描時，交換需要調(diào)整的元素东臀。

class Solution:
    def sortArrayByParityII(self, nums: List[int]) -> List[int]:
        stat = {}
        is_even = lambda n : n%2 == 0
        is_odd = lambda n : n%2 == 1
        #mark the element with non-zero value if it needs to swap
        for i in range(len(nums)):
            if (is_even(nums[i]) and is_even(i)) or ((is_odd(nums[i])) and is_odd(i)):
                stat[i] = 0 #well aligned
            elif is_even(nums[i]):
                stat[i] = 1
            else:
                stat[i] = 2

        for i in range(len(nums)):
            if stat[i] == 0:
                continue
            else:
                #find the first valid element for swapping
                for j in range(i, len(nums)):
                    if stat[j] == 0 or stat[i] == stat[j]:
                        continue
                    nums[i], nums[j] = nums[j], nums[i]
                    stat[i] = 0 #reset stats
                    stat[j] = 0
                    break
        return nums

測試一下着饥，

Success
[Details]
Runtime: 352 ms, faster than 5.21% of Python3 online submissions for Sort Array By Parity II.
Memory Usage: 15.9 MB, less than 5.25% of Python3 online submissions for Sort Array By Parity II.

26. Remove Duplicates from Sorted Array

Easy

Given a sorted array nums, remove the duplicates in-place 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:

<pre>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.</pre>

Example 2:

<pre>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.
</pre>

題目大意：對于一個給定的數(shù)組，刪除所有重復(fù)的元素惰赋。

解題思路：維持一個索引宰掉，同時將所有不重復(fù)的元素前移，覆蓋重復(fù)的元素赁濒。最終的索引等于有效元素的長度轨奄。

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

        return idx

測試一下

Success
[Details]
Runtime: 56 ms, faster than 95.70% of Python3 online submissions for Remove Duplicates from Sorted Array.
Memory Usage: 15 MB, less than 11.86% of Python3 online submissions for Remove Duplicates from Sorted Array.

905. Sort Array By Parity

Easy

Given an array A of non-negative integers, return an array consisting of all the even elements of A, followed by all the odd elements of A.

You may return any answer array that satisfies this condition.

Example 1:

Input: [3,1,2,4]
Output: [2,4,3,1]
The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

題目大意：對給定的數(shù)組進行劃分排序，要求將偶數(shù)放到奇數(shù)之前拒炎。

解題思路：利用穩(wěn)定排序挪拟，將偶數(shù)移到奇數(shù)之前。

class Solution:
    def sortArrayByParity(self, nums: List[int]) -> List[int]:
        cmp = lambda a : a%2
        nums.sort(key=cmp)
        return nums   

測試一下

Success
[Details]
Runtime: 64 ms, faster than 97.07% of Python3 online submissions for Sort Array By Parity.
Memory Usage: 13.8 MB, less than 38.36% of Python3 online submissions for Sort Array By Parity.

899. Orderly Queue

Hard

A string S of lowercase letters is given. Then, we may make any number of moves.

In each move, we choose one of the first K letters (starting from the left), remove it, and place it at the end of the string.

Return the lexicographically smallest string we could have after any number of moves.

Example 1:

Input: S = "cba", K = 1
Output: "acb"
Explanation:
In the first move, we move the 1st character ("c") to the end, obtaining the string "bac".
In the second move, we move the 1st character ("b") to the end, obtaining the final result "acb".

題目大意：定義一次移動击你，將最左的K個字符放到字符串末尾玉组。利用有限次移動，將字符串排列丁侄。

解題思路：當(dāng)K>1惯雳，意味著可以利用選擇排序進行完全排序，否則鸿摇，嘗試以每個元素為中心進行翻折石景。

class Solution:
    def orderlyQueue(self, s: str, k: int) -> str:
        # sort or rotation
        if k > 1:
            return ''.join(sorted(s))
        ans = s
        for i in range(len(s)):
            ans = min(ans, s[i:] + s[:i]) #try every kind of break point in rotate
        return ans   

測試一下

Success
[Details]
Runtime: 40 ms, faster than 78.70% of Python3 online submissions for Orderly Queue.
Memory Usage: 13.2 MB, less than 57.14% of Python3 online submissions for Orderly Queue.