MiMi’s learning notes - 生活/工作筆記

  題目 在 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]])

  題目 給定一個數組  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

  題目 給定兩個非遞減排序的整數數組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

  題目 給定一個整數數組 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 我的時間複雜度好爛喔ＱＱ 找時間再來思考有沒有比較好的方法

題目 給定一個整數陣列 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  

  題目 給定一個整數數組 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

  題目 給定一個數組 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

  題目 給定一個字符串 s ，找到不含重複字符的 最長子串 的長度。 例子 1: 輸入: s = "abcabcbb" 輸出: 3 解釋: 答案是 "abc"，長度為 3。 例子 2: 輸入: s = "bbbbb" 輸出: 1 解釋: 答案是 "b"，長度為 1。 例子 3: 輸入: s = "pwwkew" 輸出: 3 解釋: 答案是 "wke"，長度為 3。 注意答案必須是子串，"pwke" 是一個子序列而不是子串。 限制: 0 <= s.length <= 5 * 104 s  由英文字母、數字、符號和空格組成。 我的答案 class Solution: def lengthOfLongestSubstring(self, s: str) -> int: if not s: return 0 if len(s)==1: return 1 head=0 longest_s=0 for i in range(1,len(s)+1): sub_string=s[head:i] if i<len(s): while s[i] in s[head:i]: head+=1 if s[i]==s[head] and i-1 ==head: head=i if len(sub_string) > longest_s: longest_s=len(sub_string) return longest_s

  題目 給你兩個 非空 的鏈表，分別表示兩個非負整數。數字以 相反的順序 存儲，每個節點包含一個數字。將兩個數字相加並以鏈表形式返回其和。 你可以假設除了數字0本身，這兩個數字都不會以0開頭。 例子1: 輸入: l1 = [2,4,3], l2 = [5,6,4] 輸出: [7,0,8] 解釋: 342 + 465 = 807. 例子2: 輸入: l1 = [0], l2 = [0] 輸出: [0] 例子3: 輸入: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 輸出: [8,9,9,9,0,0,0,1] 限制: 鏈表中節點數目在範圍 [1, 100] 中。 0 <= Node.val <= 9 題目保證鏈表表示的數字不含前導零。 我的答案 # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]: Output_Node=ListNode() Output_currentNode=Output_Node value=0 while l1 and l2 : value += l1.val+l2.val Output_currentNode.val=value%10 value=value//10 l1=l1.next l2=l2.next if l1 and l2: Output_currentNode.next=ListNode()

  題目 在一個字串陣列中，找出最長的公共前綴字串。 如果沒有公共前綴，回傳空字串 ""。 範例1: 輸入: strs = ["flower","flow","flight"] 輸出: "fl" 範例2: 輸入: strs = ["dog","racecar","car"] 輸出: "" 說明: 輸入字串中沒有公共前綴。 限制條件： 1 <= strs.length <= 200 0 <= strs[i].length <= 200 strs[i] 僅包含小寫英文字母。 我的答案 直覺答案 class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: def text_length(text): return len(text) strs.sort(key=text_length) prefix='' for j in range(len(strs[0])): prefix=prefix+strs[0][j] for i in range(1,len(strs)): if prefix == strs[i][:j+1]: pass else: if prefix: return prefix[:len(prefix)-1] else: return "" return prefix 可憐的performance😂 改善後的解答 cl

  題目 羅馬數字由七個不同的符號表示： I ， V ， X ， L ， C ， D 和 M 。 符號值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000 例如， 2 用羅馬數字寫為 II ，只是兩個1相加。 12 寫為 XII ，這只是 X + II 。數字 27 寫為 XXVII ，這是 XX + V + II 。 羅馬數字通常從左到右按從大到小的順序書寫。但是，數字四的符號不是 IIII 。相反，數字四寫為 IV 。因為1在5之前，所以減去它使其成為4。相同的原則適用於數字9，它寫為 IX 。有六種情況使用減法： I 可以放在 V (5)和 X (10)之前，以形成4和9。 X 可以放在 L (50)和 C (100)之前，以形成40和90。 C 可以放在 D (500)和 M (1000)之前，以形成400和900。 給定一個羅馬數字，將其轉換為整數。 範例1： 輸入：s = "III" 輸出：3 解釋：III = 3。 範例2： 輸入：s = "LVIII" 輸出：58 解釋：L = 50，V= 5，III = 3。 範例3： 輸入：s = "MCMXCIV" 輸出：1994 解釋：M = 1000，CM = 900，XC = 90和IV = 4。 限制： 1 <= s.length <= 15 s 只包含字符 ('I', 'V', 'X', 'L', 'C', 'D', 'M') 。 保證 s 是 [1, 3999] 範圍內的有效羅馬數字。 我的答案 class Solution: def romanToInt(self, s: str) -> int: Symbol={'I':1, 'V':5, &#

  題目 給定一個整數 x ，如果 x 是 Palindrome Number ，則返回 true ，否則返回 false 。 Palindrome Number 是指正序（從左到右）和倒序（從右到左）讀都是一樣的整數。 例子 1： 輸入：x = 121 輸出：true 解釋：121從左到右和從右到左讀都是121。 例子 2： 輸入：x = -121 輸出：false 解釋：從左到右讀為-121。從右到左讀為121-。因此它不是回文數。 例子 3： 輸入：x = 10 輸出：false 解釋：從右到左讀為01。因此它不是回文數。 限制： 231 <= x <= 231 - 1 進一步挑戰： 你能不將整數轉為字串來解決這個問題嗎？ 我的答案 其實這是我第一個想到的答案 class Solution: def isPalindrome(self, x: int) -> bool: if x <0: return False String=str(x) if len(String)==1: return True for i in range(len(String)//2): if String[i] != String[-1-i]: return False return True 表現其實還不錯，打敗95.49%的人 這是我嘗試的第二種答案 class Solution: def isPalindrome(self, x: int) -> bool: if x <0: return False String=str(x) x_Reversed=int(String[::-1]) if x-x_Reversed == 0: return True else: return False 結果表現反而比較差😂 於是就是尋

題目 給定一個整數數組nums和一個整數target，返回兩個數字的索引，使它們相加等於target。 你可以假設每個輸入都只有一個解，並且你不能使用相同的元素兩次。 你可以以任何順序返回答案。 Example 1: Input: nums = [2,7,11,15], target = 9 Output: [0,1] Explanation: Because nums[0] + nums[1] == 9, we return [0, 1]. Example 2: Input: nums = [3,2,4], target = 6 Output: [1,2] Example 3: Input: nums = [3,3], target = 6 Output: [0,1] Constraints: 2 <= nums.length <= 104 109 <= nums[i] <= 109 109 <= target <= 109 只有一個有效答案存在。 我的解答 時間複雜度O(n^2) for i in range(len(nums)): for j in range(i+1, len(nums)): if nums[i]+nums[j] == target:      return [i,j] 時間複雜度O(n) for item in nums: if (target -item) in nums: if item == target-item and nums.count(item)>=2: return [nums.index(item), nums.index(target-item, nums.index(item)+1)] elif item != target-item: return [nums.index(item), nums.index(target-item)] else: pass