發表文章

Reshape the Matrix[LeetCode/Python3/Easy]

圖片
  題目 在 MATLAB 中有一個方便的函數叫作 reshape ，可以將一個 m x n 的矩陣轉換為一個新的矩陣，大小為 r x c ，並保留其原始數據。 給定一个由二维数组表示的矩阵 mat ，以及两个正整数 r 和 c ，分别表示想要的矩阵的行數和列數。 将矩阵以相同的行遍历顺序重新排列成一个新的矩阵。如果所需大小为给定矩阵大小的子矩阵，则可以进行重塑操作。 如果重新调整大小操作具有合法性，并且可以按照所需大小重塑矩阵，则输出新的重新调整大小后的矩阵；否则，输出原始矩阵。 示例 1: 输入：mat = [[1,2],[3,4]], r = 1, c = 4 输出：[[1,2,3,4]] 示例 2: 输入：mat = [[1,2],[3,4]], r = 2, c = 4 输出：[[1,2],[3,4]] 提示: m == mat.length n == mat[i].length 1 <= m, n <= 100 1000 <= mat[i][j] <= 1000 1 <= r, c <= 300 我的答案 直覺解答 class Solution: def matrixReshape(self, mat: List[List[int]], r: int, c: int) -> List[List[int]]: m = len(mat) n = len(mat[0]) if m*n != r*c: return mat re_mat=[] rr=0 cc=0 for i in range(m): for j in range(n): if cc ==0: re_mat.append([mat[i][j]]) cc+=1 elif cc == c: re_mat.append([mat[i][j]])
張貼留言
閱讀完整內容

Best Time to Buy and Sell Stock[LeetCode/Python3/Easy]

圖片
  題目 給定一個數組  prices ，它的第  i 個元素  prices[i]  表示一支給定股票在第 i 天的價格。 你要買入一支股票一次，並在未來某个时间卖出它。此次交易所能获得的最大利润是多少？如果你不能获得任何利润，返回 0。 示例 1: 输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。 示例 2: 输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。 提示: 1 <= prices.length <= 105 0 <= prices[i] <= 104 我的答案 class Solution: def maxProfit(self, prices: List[int]) -> int: if len(prices)<2: return 0 max_profit=0 Buy=0 for i in range(1,len(prices)): if prices[i] < prices[Buy]: Buy=i if prices[i] - prices[Buy] > max_profit: max_profit = prices[i] - prices[Buy] return max_profit
張貼留言
閱讀完整內容

Merged Sorted Array[LeetCode/Python3/Easy]

圖片
  題目 給定兩個非遞減排序的整數數組nums1和nums2，以及兩個整數m和n，分別表示nums1和nums2中的元素數量。 將nums2合併到nums1中，並且是按照非遞減排序的方式。 最終排序好的數組不應該由函數返回，而應該是被存儲在nums1中。為了實現這一點，nums1的長度為m + n，其中前m個元素表示應該合併的元素，而最後n個元素則設置為0，並且應該被忽略。nums2的長度為n。 範例1: 輸入: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 輸出: [1,2,2,3,5,6] 解釋：我們要合併的數組是[1,2,3]和[2,5,6]。合併的結果是[1,2,2,3,5,6]，其中下劃線的元素來自nums1。 範例2: 輸入: nums1 = [1], m = 1, nums2 = [], n = 0 輸出: [1] 解釋：我們要合併的數組是[1]和[]。合併的結果是[1]。 範例3: 輸入: nums1 = [0], m = 0, nums2 = [1], n = 1 輸出: [1] 解釋：我們要合併的數組是[]和[1]。合併的結果是[1]。 請注意，由於m = 0，nums1中沒有元素。 0只是為了確保合併結果可以放入nums1中。 限制: nums1.length == m + n nums2.length == n 0 <= m, n <= 200 1 <= m + n <= 200 109 <= nums1[i], nums2[j] <= 109 *跟進問題：**能否設計一個時間複雜度為O(m+n)的算法？ 我的答案 直覺答案 class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: """ Do not return anything, modify nums1 in-place instead. """ j=0 i=0
張貼留言
閱讀完整內容

Maximum Subarray[LeetCode/Python3/Medium]

圖片
  題目 給定一個整數數組 nums ，找到具有最大和的子數組並返回 其和 。 示例 1: 輸入: nums = [-2,1,-3,4,-1,2,1,-5,4] 輸出: 6 解釋: 數組中具有最大和的子數組為 [4,-1,2,1]，其和為 6。 示例 2: 輸入: nums = [1] 輸出: 1 解釋: 數組中具有最大和的子數組為 [1]，其和為 1。 示例 3: 輸入: nums = [5,4,-1,7,8] 輸出: 23 解釋: 數組中具有最大和的子數組為 [5,4,-1,7,8]，其和為 23。 限制: 1 <= nums.length <= 105 104 <= nums[i] <= 104 進階:  如果你已經實現了$ O(n) $的解法，嘗試使用更為複雜的分治策略求解。 我的答案 class Solution: def maxSubArray(self, nums: List[int]) -> int: sum_list=[0]*len(nums) sum_list[0]=nums[0] max_sum=sum_list[0] for i in range(1, len(nums)): sum_list[i]=max(sum_list[i-1]+nums[i], nums[i]) max_sum=max(max_sum,sum_list[i]) print(sum_list) return max_sum 我的時間複雜度好爛喔ＱＱ 找時間再來思考有沒有比較好的方法
張貼留言
閱讀完整內容

Contains Duplicate[LeetCode/Python3/Easy]

圖片
題目 給定一個整數陣列 nums ，如果在陣列中有任何值出現 至少兩次 ，則返回 true ；如果每個元素都是唯一的，則返回 false 。 例 1: 輸入: nums = [1,2,3,1] 輸出: true 例 2: 輸入: nums = [1,2,3,4] 輸出: false 例 3: 輸入: nums = [1,1,1,3,3,4,3,2,4,2] 輸出: true 限制: 1 <= nums.length <= 105 109 <= nums[i] <= 109 我的答案 第一個答案 class Solution: def containsDuplicate(self, nums: List[int]) -> bool: appeared_element={} for item in nums: if item in appeared_element: return True else: appeared_element[item]=1 return False 原本一開始我還使用list來存出現過的數字，結果執行時間超過上限，後來改成用dictionary來存，就可以通過！因為dictionary的資料結構為hash table，在查詢上的速度會比list快上許多。 第二個答案 class Solution: def containsDuplicate(self, nums: List[int]) -> bool: if len(nums)>len(set(nums)): return True else: return False  
張貼留言
閱讀完整內容

Find Pivot Index[LeetCode/Python3/Easy]

圖片
  題目 給定一個整數數組 nums，計算這個數組中的「中心下標」。 中心下標的左邊所有數的和等於右邊所有數的和。 如果不存在中心下標，返回 -1。如果有多個中心下標，請返回最左邊那個。 範例 1： 輸入：nums = [1, 7, 3, 6, 5, 6] 輸出：3 解釋： 中心下標是 3 。 左邊數組的和為 nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 。 右邊數組的和為 nums[4] + nums[5] = 5 + 6 = 11 。 範例 2： 輸入：nums = [1, 2, 3] 輸出：-1 解釋： 這個數組中不存在中心下標。 範例 3： 輸入：nums = [2, 1, -1] 輸出：0 解釋： 中心下標是 0 。 左邊數組（加粗部分）的和為 0 。 右邊數組的和為 nums[1] + nums[2] = 1 + -1 = 0 。 提示： nums 的長度范圍为 [0, 10000]。 任何一个 nums[i] 将会是一个范围在 [-1000, 1000]的整数。 我的答案 直覺答案 class Solution: def pivotIndex(self, nums: List[int]) -> int: if len(nums)==1: return 0 for i in range(len(nums)): if sum(nums[:i]) == sum(nums[i+1:]): return i return -1 別人的答案 class Solution: def pivotIndex(self, nums: List[int]) -> int: """ :type nums: List[int] :rtype: int """ left_sum = 0 right_sum = sum(nums) for i in range(len
張貼留言
閱讀完整內容

Running Sum of 1d Array[LeetCode/Python3/Easy]

圖片
  題目 給定一個數組 nums ，我們定義一個數組的和值為 runningSum[i] = sum(nums[0]…nums[i]) 。 返回 nums 的和值。 範例1： 輸入：nums = [1,2,3,4] 輸出：[1,3,6,10] 說明：和值分別為：[1, 1+2, 1+2+3, 1+2+3+4]。 範例2： 輸入：nums = [1,1,1,1,1] 輸出：[1,2,3,4,5] 說明：和值分別為：[1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1]。 範例3： 輸入：nums = [3,1,2,10,1] 輸出：[3,4,6,16,17] 限制： 1 <= nums.length <= 1000 10^6 <= nums[i] <= 10^6 我的答案 class Solution: def runningSum(self, nums: List[int]) -> List[int]: running_sum=[] for item in nums: if len(running_sum) ==0: running_sum.append(item) else: running_sum.append(running_sum[-1]+item) return running_sum
張貼留言
閱讀完整內容