啊啊學語

題目 Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears once or twice , return an array of all the integers that appears twice . You must write an algorithm that runs in  O(n)  time and uses only constant extra space. 直覺解 構想： 用 seen 把出現過的數字存起來。如果遇到已經在 seen 裡面的數字，那就是重複的（不符合 uses only constant extra space）。 python 3 實作： class Solution: def findDuplicates(self, nums: List[int]) -> List[int]: ans = [] seen = {} for num in nums: if num not in seen: seen[num] = True else: ans.append(num) return ans 效能： Runtime: 351 ms, faster than 76.63% of Python3 online submissions for Find All Duplicates in an Array. Memory Usage: 22.8 MB, less than 19.60% of Python3 online submissions for Find All Duplicates in an Array. 研究別人的解 來源：sample 308 ms submission 構想：List comprehension 和 set（不符合 uses only const...

題目 You are given an integer array prices where prices[i] is the price of a given stock on the i th day, and an integer k . Find the maximum profit you can achieve. You may complete at most k transactions. Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again). 直覺解 構想： 先找出所有可以低買高賣的時機，再從這些時機裡面挑出 k 個。挑選方式：while 迴圈，每圈會減少一個時機，減少方式有兩種，合併兩個相鄰的時機，或移除一個時機。 python 3 實作（失敗）： class Solution: def maxProfit(self, k: int, prices: List[int]) -> int: profit = 0 if len(prices) < 2 or k == 0: return profit # find all best time to buy and sell stock start = 0 intervals = [] while start < len(prices): interval = self.find_buy_sell_interval(start, prices) if interval['buy'] is None or interval['sell'] is None: break interval['subtotal'] = prices[interval[...

題目 Given an array nums and an integer target . Return the maximum number of non-empty non-overlapping subarrays such that the sum of values in each subarray is equal to target . 直覺解 構想： 我把 non-overlapping subarray 理解為「nums 中的每個成員，最多只能用在一個 subarray 裡」（後來才發現不是這個意思⋯⋯做白工啊做白工 orz） 先找出所有 subarray，再過濾出 sum 等於 target 的 non-empty subarray，為了加快查詢速度，把過濾出來的 subarray 轉為 dictionary，key 是數字，value 是數字出現幾次。用 recursion 嘗試所有可能的 non-overlapping subarray 組合，找出 maximum number。 python 3 實作（失敗）： class Solution: def maxNonOverlapping(self, nums: List[int], target: int) -> int: sum_eq_target = [] for array in self.get_subarrays(nums): if array and sum(array) == target: map = {} for item in array: map[item] = map.get(item, 0) + 1 sum_eq_target.append(map) if not sum_eq_target: return 0 nums_map = {} for n in nums: nums_map[n] = nums_map.g...

題目 There are n oranges in the kitchen and you decided to eat some of these oranges every day as follows: Eat one orange. If the number of remaining oranges ( n ) is divisible by 2 then you can eat n/2 oranges. If the number of remaining oranges ( n ) is divisible by 3 then you can eat 2*(n/3) oranges. You can only choose one of the actions per day. Return the minimum number of days to eat n oranges. 直覺解 構想： 每天，看哪個方式可以吃最多橘子，就用那個吃法。但是這題是 Hard，總覺得事情沒有這麼簡單⋯⋯ python 3 實作（失敗）： class Solution:     def minDays(self, n: int) -> int:         days = 0         while n > 0:             if n % 3 == 0:                 n = n // 3              elif n % 2 == 0:                 n = n >> 1             else:  ...

題目 A conveyor belt has packages that must be shipped from one port to another within days days. The i th package on the conveyor belt has a weight of weights[i] . Each day, we load the ship with packages on the conveyor belt (in the order given by weights ). We may not load more weight than the maximum weight capacity of the ship. Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within days days. 直覺解 構想： 先設定 capacity = max(weights) ，計算需要幾天。天數超過的話 capacity += 1。直到天數在許可範圍內為止。 python 3 實作（失敗）： class Solution:     def shipWithinDays(self, weights: List[int], days: int) -> int:         capacity = max(weights)         needed_days = 1         package_wieghts = 0         while True:             for weight in weights:                 if ne...