雲林SONG

發表文章

目前顯示的是 2024的文章

Sorting Algorithm 排序演算法介紹

- 6月 25, 2024

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。 If you like this post, please click the ads on the blog or buy me a coffee . Thank you very much. 在本部落格的文章： Python 排序演算法範例 ( Sorting Algorithms in Python ) 有介紹一些常見的四種排序演算法：插入排序、選擇排序、合併排序、氣泡排序。除了這四種之外還有其他的嗎？當然有！！！例如：謝耳排序、快速排序、堆積排序、基數排序、雞尾酒排序等。那排序演算法到底在做什麼？！又為什麼會有這麼多種的演算法呢？！排序是要將東西依照某種規則放置，例如將一個數列由小排到大，或是將容器依照體積由大排到小。在電腦科學裡，排序是將元素依照數值大小或是字典順序來排列。但因為考量到排序的速度(計算量)，於是科學家們想出了各式各樣的排序演算法，有些排序演算法適用於資料量小的情境，有些排序演算法適用於資料量大的情境。對於排序演算法的選擇可從排序方法是用比較式的、還是非比較式的，以及時間複雜度與實際資料分布的狀況來選擇。在 https://github.com/TheAlgorithms 上有以不同的程式語言實作各式各樣的演算法，例如 Python 排序演算法、 Java排序演算法、 C語言排序演算法、等。此外若想看一些常見演算法的動畫，可參考【會動的演算法】一書的動畫網址： https://www.flag.com.tw/activity/F2708/exercise/books/

LeetCode 解題練習：Plus One

- 2月 23, 2024

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。 If you like this post, please click the ads on the blog or buy me a coffee . Thank you very much. 題目原文描述 https://leetcode.com/problems/plus-one/ 中文描述給定一個用陣列 digits 表示大整數 large integer，digits[i] 代表大整數的第 i 位數之值。例如 12345 會以 digits = [1, 2, 3, 4, 5] 來表示。請將 digits 的數值加一。範例一：輸入 digits = [9,9,9,9] 輸出 [1, 0, 0, 0, 0] 說明：整數 9999 加一後為 10000。範例二：輸入 digits = [2, 2, 3, 4, 5] 輸出 [2, 2, 3, 4, 6] 說明：整數 22345 加一後為 22346。解法：若目前 digits[i] 為 9 ，將 digits[i] 設定為 0；否則 digits[i] 加一並回傳 digits。若每位數都是9，在最左邊補1。 Python Code class Solution : def plusOne ( self , digits : List[ int ]) -> List[ int ]: for i in range ( len (digits) - 1 , - 1 , - 1 ): # 從最右邊位置開始判斷 if digits[i] == 9 : # digits[i]為9，要進位 digits[i] = 0 else : ...

LeetCode 解題練習：Largest Number At Least Twice of Others

- 2月 22, 2024

題目原文描述 https://leetcode.com/problems/largest-number-at-least-twice-of-others/ 中文描述給定一個有唯一最大值的整數陣列 nums ，請判斷此最大值元素是否為其他陣列元素值的兩倍以上，若有成立，請回傳此最大值在陣列中的索引位置。範例一：輸入 nums = [1, 2, 3, 6, 2, 3, 1] 輸出 3 因為 6 是最大值，且都為其他陣列元素[1, 2, 3]的兩倍以上。範例二：輸入 nums = [1, 2, 3, 4, 6] 輸出 -1 因為 6 是最大值，但 6 不是 4 的兩倍以上。解法一： Two Pass。先找出最大值 largestNum 與索引位置 largestIdx。判斷陣列中所有非最大值之元素是否有 largestNum 小於 nums[i] * 2，若有，回傳 -1。 Python Code class Solution : def dominantIndex ( self , nums : List[ int ]) -> int : largestNum = - 1 # 最大值 largestIdx = - 1 # 最大值位置 # 找最大值與索引位置 for i in range ( len (nums)): if nums[i] > largestNum: largestNum = nums[i] largestIdx = i ...

LeetCode 解題：Find Pivot Index

- 2月 21, 2024

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。 If you like this post, please click the ads on the blog or buy me a coffee . Thank you very much. 題目原文描述 https://leetcode.com/problems/find-pivot-index/ 中文描述給定一個整數陣列 nums ，找出某目標索引位置 Pivot Index，讓目標索引位置的左邊元素陣列元素總和等於目標索引位置的右邊陣列元素總和，總和不包含目標索引位置之值。範例一：輸入 nums = [1, 2, 3, 4, 2, 2, 2] 輸出 3 因為 [1, 2, 3] 總和等於 6 等於 [2, 2, 2]總和範例二：輸入 nums = [3, -3, 3] 輸出 0 因為 [] 總和等於 0 等於 [-3, 3] 總和解法一：暴力法。對每一個索引位置算出左邊元素陣列元素總和 leftSum 與右邊元素陣列元素總和 rightSum 是否相等。 Python Code class Solution : def pivotIndex ( self , nums : List[ int ]) -> int : total = sum (nums) # 陣列總和 leftSum = 0 # 左邊總和 for i in range ( len (nums)): # 從左邊索引0開始找起 rightSum = sum (nums[i+ 1 :]) # 右邊總和 leftSum = total - rightSum - nums[i] # 左邊總和 ...

LeetCode 解題練習：Find All Numbers Disappeared in an Array

- 2月 20, 2024

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。 If you like this post, please click the ads on the blog or buy me a coffee . Thank you very much. 題目原文描述 https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/ 中文描述給定一個含有[1, n] 之間的n個元素之整數陣列 nums (陣列長度為 n)，找出[1, n] 之間沒有出現在陣列 nums 元素中的整數。範例一：輸入 nums = [2, 2] 輸出 [1] 範例二：輸入 nums = [1, 2, 2] 輸出 [3] 範例三：輸入 nums = [1, 2, 1, 2, 1, 3, 4] 輸出 [5, 6, 7] 解法一：使用計數的方式記錄[1,n]每一個數字出現在 nums 的次數，再統計出現次數為0的數字有哪些。 Python Code class Solution : def findDisappearedNumbers ( self , nums : List[ int ]) -> List[ int ]: n = len (nums) counts = [ 0 ] * n # 計算 [1,n] 數字出現的次數 for i in nums: counts[i - 1 ] += 1 # 出現一次就增加1 missingNumbers = [] # 沒出現在 nums 的數字 ...

LeetCode 解題練習：Height Checker

- 2月 19, 2024

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。 If you like this post, please click the ads on the blog or buy me a coffee . Thank you very much. 題目原文描述 https://leetcode.com/problems/height-checker/ 中文描述給定一個整數陣列 heights ，請算出 heights 中沒有依照由小到大之順序的元素個數。範例一：輸入 heights = [3, 1, 2] 輸出 3 因為依照小到大的陣列為 [1, 2, 3] ，heights 每個元素皆不再所屬的排序位置上。範例二：輸入 heights = [1, 3, 2] 輸出 2 因為依照小到大的陣列為 [1, 2, 3] ，heights[0]有在排序的位置上，其餘元素皆不在所屬的排序位置上。範例三：輸入 heights = [1, 2, 3] 輸出 0 因為依照小到大的陣列為 [1, 2, 3] ，heights所有元素皆在所屬的排序位置上。解法：先用內建排序函式產生由小排到大的 expected 陣列，依照索引位置 i 算出 heights[i] != expected[i] 有多少個。 Python Code class Solution : def heightChecker ( self , heights : List[ int ]) -> int : expected = sorted (heights) notMatch = 0 for i in range ( len (heights)): if heights[i] != expected[i]: not...

LeetCode 解題練習：Sort Array By Parity

- 2月 18, 2024

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。 If you like this post, please click the ads on the blog or buy me a coffee . Thank you very much. 題目原文描述 https://leetcode.com/problems/sort-array-by-parity/ 中文描述給定一個整數陣列 nums ，產生一個陣列將nums中所有偶數放在陣列開頭，放完偶數後再放奇數。範例一：輸入 nums = [5, 2, 4, 1] 輸出 [2, 4, 5, 1] 或 [4, 2, 1, 5] 或 [2, 4, 1, 5] 或 [4, 2, 5, 1] 皆可為答案範例二：輸入 nums = [5, 2, 1] 輸出 [2, 5, 1] 或 [2, 1, 5] 皆可為答案解法一：建立一個陣列 parityArr ，迴圈走訪 nums 陣列，若 nums[i] 為偶數，加到 parityArr 最前面；若 nums[i] 為奇數，加到 parityArr 最後面。 Python Code class Solution : def sortArrayByParity ( self , nums : List[ int ]) -> List[ int ]: parityArr = [] for n in nums: if n % 2 == 0 : parityArr.insert( 0 , n) # 偶數加到parityArr最前面 else : ...

LeetCode 解題練習：Move Zeroes

- 2月 17, 2024

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。 If you like this post, please click the ads on the blog or buy me a coffee . Thank you very much. 題目原文描述 https://leetcode.com/problems/move-zeroes/ 中文描述給定一個整數陣列 nums ，將所有的 0 移到陣列結尾處，並保持原先非零整數的順序。請修改原本陣列 nums 的內容來完成。範例一：輸入 nums = [0, 1, 0, 5, 0, 0, 3] 輸出 nums = [1, 5, 3, 0, 0, 0, 0] 範例二：輸入 nums = [0, 0, 1] 輸出 nums = [1, 0, 0] 範例三：輸入 nums = [1] 輸出 nums = [1] 範例四：輸入 nums = [0] 輸出 nums = [0] 解法一： left = 0，從左邊開始往右移動，如果陣列元素 nums[i] 不等於零，則將此元素複製到 nums[left]，再將 left 加 1。走訪完陣列後，left 為非零整數的數量，從left索引位置之後的元素通通設為零。 Python Code class Solution : def moveZeroes ( self , nums : List[ int ]) -> None : """ Do not return anything, modify nums in-place instead. """ left = 0 for i in range ( len (nums)): # 從左邊開始往右移動 if nums[i] != 0 : ...

LeetCode 解題練習：Replace Elements with Greatest Element on Right Side

- 2月 16, 2024

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。 If you like this post, please click the ads on the blog or buy me a coffee . Thank you very much. 題目原文描述 https://leetcode.com/problems/replace-elements-with-greatest-element-on-right-side/ 中文描述給定一個整數陣列 arr，將每個元素用該元素的右邊所有元素中之最大值來取代，並將最後一個元素用-1取代。範例一：輸入 arr = [45, 333, 2, 1, 9, 17] 輸出 [333, 17, 17, 17, 17, -1] 因為 45 右邊元素 [333, 2, 1, 9, 17] 最大值為 333。因為 333 右邊元素 [2, 1, 9, 17] 最大值為 17。因為 2 右邊元素 [1, 9, 17] 最大值為 17。因為 1 右邊元素 [9, 17] 最大值為 17。因為 9 右邊元素 [17] 最大值為 17。範例二：輸入 arr = [333] 輸出 [-1] 解法：以 curMax = -1 當目前最大值，t暫存目前陣列元素。從陣列的右邊開始以curMax替代，若 t 大於 curMax，則更新 curMax 為 t。可參考底下圖片動畫說明： Python Code class Solution : def replaceElements ( self , arr : List[ int ]) -> List[ int ]: curMax = - 1 # 目前最大值 for i in range ( len (arr)- 1 , - 1 , - 1 ): # 從右邊開始替代 t = arr[i] # 暫存目前陣列元素 ...

LeetCode 解題練習：Guess Number Higher or Lower

- 2月 15, 2024

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。 If you like this post, please click the ads on the blog or buy me a coffee . Thank you very much. 題目原文描述 https://leetcode.com/problems/guess-number-higher-or-lower/ 中文描述電腦從 1 到 n 選一個數字，當玩家猜數字時，電腦會給予太高或太低的提示。請使用以定義的函式 int guess(int num)，此函式回傳值得意義如下： -1 ，代表玩家猜的數字比電腦選的大。 1 ，代表玩家猜的數字比電腦選的小。 0 ，代表玩家猜中電腦選的數字。請輸出電腦所選的數字為何。範例一：輸入 n = 10, 電腦選 4 輸出 4 範例二：輸入 n = 100, 電腦選 93 輸出 93 解法：使用二分搜尋法 Binary Search 解即可。 Python Code # The guess API is already defined for you. # @param num, your guess # @return -1 if num is higher than the picked number # 1 if num is lower than the picked number # otherwise return 0 # def guess(num: int) -> int: class Solution : def guessNumber ( self , n : int ) -> int : l = 1 r = n g = (l + r) // 2 ans = guess(g) ...

LeetCode 解題練習：Valid Mountain Array

- 2月 14, 2024

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。 If you like this post, please click the ads on the blog or buy me a coffee . Thank you very much. 題目原文描述 https://leetcode.com/problems/valid-mountain-array/ 中文描述給定一個整數陣列 arr，檢查此陣列是否為一個合格的山脈陣列(Valid Mountain Array)。Valid Mountain Array 的定義如下：陣列長度大於等於3。存在一個整數 i ，且 0 < i < 陣列長度，使得底下條件成立： arr[0] < arr[1] < arr[2] < ... < arr[i-2] < arr[i-1] < arr[i] arr[arr.length - 1] < arr[arr.length - 2] < arr[arr.length - 3] < .... < arr[i + 2] < arr[i + 1] < arr[i] 範例一：輸入 arr = [1, 2] 輸出 false 因為陣列長度小於 3 範例二：輸入 arr = [1, 2, 1] 輸出 true 範例三：輸入 arr = [1, 2, 2, 3, 1] 輸出 false 因為 arr[1] = 2 = arr[2]，非嚴格遞增。範例四：輸入 arr = [1, 2, 3, 3, 2, 1] 輸出 false 因為 arr[2] = 3 = arr[3]，非嚴格遞減。解法一： left 從左邊開始往右找，找到非嚴格遞增的位置。 right = left + 1，繼續往右找，找到非嚴格遞減的位置。回傳 left != 0 and left < len (arr) - 1 and right == len (arr)。 Python Code class Solution : def validMountainArray ( self , ar...

LeetCode 解題練習：Check If N and Its Double Exist

- 2月 13, 2024

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。 If you like this post, please click the ads on the blog or buy me a coffee . Thank you very much. 題目原文描述 https://leetcode.com/problems/check-if-n-and-its-double-exist/ 中文描述給定一個整數陣列 arr，找出陣列中兩個不一樣位置的元素是不是符合 arr[i] * 2 = arr[j]，其中 i != j。範例一：輸入 arr = [-1, 8, 2, 1, 4] 輸出 true 因為元素 4 是元素 2 * 2。範例一：輸入 arr = [-1, 8, 3, 1, 4] 輸出 false 因為沒有任一兩個元素符合 arr[i] * 2 = arr[j]，其中 i != j。解法一：先排序，在用二分搜尋法找有沒有目前陣列元素兩倍的數字出現在不同的索引位置。 Python Code class Solution : def checkIfExist ( self , arr : List[ int ]) -> bool : arr.sort() count = len (arr) for i in range (count): pro = arr[i] * 2 left = 0 right = len (arr) - 1 while left <= right: ...

LeetCode 解題練習：Binary Search

- 2月 12, 2024

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。 If you like this post, please click the ads on the blog or buy me a coffee . Thank you very much. 題目原文描述 https://leetcode.com/problems/binary-search/ 中文描述給定一個由小排到大的整數陣列 nums ，與一個整數 target，請在陣列中尋找 target 所在的索引位置。若找不到，請傳回 -1。必須用演算法時間複雜度為 O(log n) 的方法來解。範例一：輸入 nums = [1, 2, 3, 4, 5, 6, 7], target = 5 輸出 4 因為 5 在陣列 nums 索引位置 4。範例二：輸入 nums = [1, 2, 3, 4, 5, 6, 7], target = 8 輸出 -1 因為 8 不在陣列 nums 裡。解法一：二分搜尋法的演算法如下：設定 left = 0, right = 陣列長度 - 1。當 left <= right 時 middle = (left + right) / 2。判斷 target 與 nums[middle] 的大小關係。若相等，回傳 middle。若 nums[middle] 大於 target，right = middle - 1。若 nums[middle] 小於 target，left = middle + 1。若 left > right 結束迴圈時，回傳 -1。可參考下圖動畫說明： Python Code class Solution : def search ( self , nums : List[ int ], target : int ) -> int : left = 0 right = len (nums) - 1 while left <= right: ...

LeetCode 解題練習：Sqrt(x)

- 2月 10, 2024

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。 If you like this post, please click the ads on the blog or buy me a coffee . Thank you very much. 題目原文描述 https://leetcode.com/problems/sqrtx/ 中文描述給一個非負整數 x ，求出最接近但不大於 x 平方根的整數。注意，不能使用內建函式。範例一：輸入 x = 9 輸出 3 範例二：輸入 x = 22 輸出 4 因為 x 的平方根為 4.69041575982，取整數部分為 4 。解法一：線性搜尋 r = 1 開始判斷到 r * r <= x，傳回 r - 1。 Python Code class Solution : def mySqrt ( self , x : int ) -> int : r = 1 while r * r <= x: r += 1 return r - 1 解法二：二分搜尋此部分可參考此教學影片的說明 https://www.youtube.com/watch?v=1_4xlky3Y2Y Python Code class Solution : def mySqrt ( self , x : int ) -> int : left = 1 right = x while left <= right: mid...

LeetCode 解題練習：Remove Duplicates from Sorted Array

- 2月 08, 2024

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。 If you like this post, please click the ads on the blog or buy me a coffee . Thank you very much. 題目原文描述 https://leetcode.com/problems/remove-duplicates-from-sorted-array/ 中文描述給定一個由小排到大的整數陣列 nums ，將陣列中重複的數字給刪除，並回傳不重複的元素個數k值。範例一：輸入 nums = [1, 1, 1, 2, 2, 3, 3] 輸出 k = 3, nums = [1, 2, 3, x, x, x, x] 因為 nums 有 3 個不重複的數字 [1, 2, 3] 解法：設定兩個變數 left = 0 與 right = 0，從陣列左邊開始判斷，若 nums[left] != nums[right] 時，將 left 加 1 ，並將 nums[left] 設為 nums[right]。請參考底下圖片： Python Code class Solution : def removeDuplicates ( self , nums : List[ int ]) -> int : left = 0 for right in range ( len (nums)): if nums[left] != nums[right]: left += 1 nums[left] = nums[right] return...

搜尋此網誌