🏅環環相扣 插入GCD到鏈結串列中_Insert GCD in Linked List_Leetcode #2807

閱讀時間約 1 分鐘

題目敘述 Insert Greatest Common Divisors in Linked List


題目給定一個鏈結串列,
請在兩兩節點之間加入一個新節點,新節點的值為兩者之間的最大公因數。

最後返回新串列的head node作為答案。


測試範例

Example 1:

raw-image


Input: head = [18,6,10,3]
Output: [18,6,6,2,10,1,3]
Explanation: The 1st diagram denotes the initial linked list and the 2nd diagram denotes the linked list after inserting the new nodes (nodes in blue are the inserted nodes).
- We insert the greatest common divisor of 18 and 6 = 6 between the 1st and the 2nd nodes.
- We insert the greatest common divisor of 6 and 10 = 2 between the 2nd and the 3rd nodes.
- We insert the greatest common divisor of 10 and 3 = 1 between the 3rd and the 4th nodes.
There are no more adjacent nodes, so we return the linked list.

Example 2:

raw-image


Input: head = [7]
Output: [7]
Explanation: The 1st diagram denotes the initial linked list and the 2nd diagram denotes the linked list after inserting the new nodes.
There are no pairs of adjacent nodes, so we return the initial linked list.

約束條件

Constraints:

  • The number of nodes in the list is in the range [1, 5000].

節點總數介於1~5000之間。

  • 1 <= Node.val <= 1000

節點值都介於1~1000之間。


演算法 兩兩一組為單元操作。


兩兩一組為單元操作。

先計算相鄰兩節點之間的最大公因數GCD,

接著在中間插入新結點。

接著移動到下一個位置,如此反覆操作,直到串列尾端為止。


Python 程式碼 兩兩一組為單元操作

class Solution:
def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:

## Base case
# Empty list or only one node
if not head or not head.next:
return head

## General cases
# Locate next node
next_hop = head.next

# Compute gcd between next node and current node
_gcd = math.gcd(head.val, next_hop.val)

# Insert node with GCD value
head.next = ListNode( _gcd, next_hop)

# Go to original next node
self.insertGreatestCommonDivisors(next_hop)
return head

Go 程式碼 兩兩一組為單元操作


func getGCD(a, b int) int{

// Euclid algorithm to find GCD
for b != 0{
a, b = b, a % b
}

return a
}

func insertGreatestCommonDivisors(head *ListNode) *ListNode {

// Base Case
if head == nil || head.Next == nil{
return head
}

// General case
// Locate original next node
nextHop := head.Next

// Compute GCD between current node and next node
_gcd := getGCD(head.Val, nextHop.Val)

// Insert node of GCD
head.Next = &ListNode{Val: _gcd, Next: nextHop}

// Going to original next node
insertGreatestCommonDivisors(nextHop)

return head
}

複雜度分析

時間複雜度: O(n)

從頭到尾拜訪每個節點,總共耗時為O(n)

空間複雜度: O(n)

從頭到尾拜訪每個節點,遞迴深度 = run time call stack深度 = O(n)


Reference

[1] Insert Greatest Common Divisors in Linked List - LeetCode



83會員
424內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
發表第一個留言支持創作者!
2326. Spiral Matrix IV 題目給定一個Linked list和對應的矩陣高度m、寬度n。 請依照順時針的拜訪順序, 從左上角出發,依照次序把Linked List的內容填到矩陣裡。 如果有剩餘不足的空位,就填補-1。 最後將填補好的矩陣返回作為答案。
 Binary Tree Inorder Traversal 題目給定一個二元樹的根結點。 請輸出中序拜訪(In-order traversal)的拜訪序列。 中序拜訪的定義: 1.拜訪左子樹。 2.拜訪目前的節點。 3.拜訪右子樹。
Most Stones Removed with Same Row or Column 給定一個2D平面,好幾顆石頭散布在不同的點座標。 輸入陣列代表每顆石頭所在的(x, y)座標。 如果某顆石頭的x座標或者y座標相同的軸線上,還有其他石頭, 則原本那顆石頭可以移除。 請問做多可已移除幾顆石頭?
給定兩個相同大小的二維陣列grid1, grid2。 格子點為0的地方代表海洋,格子點為1的地方代表陸地。 島嶼的定義是4連通(上、下、左、右)相鄰在一起的陸地。 如果有某個區域在grid2 是島嶼而且在grid1也是陸地, 那麼這些區域就稱為「子島嶼」。 請問grid2裡有多少座子島嶼?
題目敘述 N-ary Tree Postorder Traversal 題目給定一個n-ary(每個節點最多n個子樹)的樹根。 請返回後序拜訪這棵樹的軌跡。 推廣後的後序拜訪的定義: 1.從左到右依序拜訪所有子樹。 2.拜訪目前的節點。
題目敘述 145. Binary Tree Postorder Traversal 題目給定一個二元樹的根結點。 請輸出後序拜訪(Post-order traversal)的拜訪序列。 後序拜訪的定義: 1.拜訪左子樹。 2.拜訪右子樹。 3.拜訪目前的節點。
2326. Spiral Matrix IV 題目給定一個Linked list和對應的矩陣高度m、寬度n。 請依照順時針的拜訪順序, 從左上角出發,依照次序把Linked List的內容填到矩陣裡。 如果有剩餘不足的空位,就填補-1。 最後將填補好的矩陣返回作為答案。
 Binary Tree Inorder Traversal 題目給定一個二元樹的根結點。 請輸出中序拜訪(In-order traversal)的拜訪序列。 中序拜訪的定義: 1.拜訪左子樹。 2.拜訪目前的節點。 3.拜訪右子樹。
Most Stones Removed with Same Row or Column 給定一個2D平面,好幾顆石頭散布在不同的點座標。 輸入陣列代表每顆石頭所在的(x, y)座標。 如果某顆石頭的x座標或者y座標相同的軸線上,還有其他石頭, 則原本那顆石頭可以移除。 請問做多可已移除幾顆石頭?
給定兩個相同大小的二維陣列grid1, grid2。 格子點為0的地方代表海洋,格子點為1的地方代表陸地。 島嶼的定義是4連通(上、下、左、右)相鄰在一起的陸地。 如果有某個區域在grid2 是島嶼而且在grid1也是陸地, 那麼這些區域就稱為「子島嶼」。 請問grid2裡有多少座子島嶼?
題目敘述 N-ary Tree Postorder Traversal 題目給定一個n-ary(每個節點最多n個子樹)的樹根。 請返回後序拜訪這棵樹的軌跡。 推廣後的後序拜訪的定義: 1.從左到右依序拜訪所有子樹。 2.拜訪目前的節點。
題目敘述 145. Binary Tree Postorder Traversal 題目給定一個二元樹的根結點。 請輸出後序拜訪(Post-order traversal)的拜訪序列。 後序拜訪的定義: 1.拜訪左子樹。 2.拜訪右子樹。 3.拜訪目前的節點。
你可能也想看
Google News 追蹤
Thumbnail
本專欄將提供給您最新的市場資訊、產業研究、交易心法、精選公司介紹,以上內容並非個股分析,還請各位依據自身狀況作出交易決策。歡迎訂閱支持我,獲得相關內容,也祝您的投資之路順遂! 每年 $990 訂閱方案👉 https://reurl.cc/VNYVxZ 每月 $99 訂閱方案👉https://re
Thumbnail
題目敘述 Combination Sum II_Leetcode #40 給定一個整數陣列candidates 和 目標值target。 每個陣列元素只能選擇一次,請問有多少種組合方法,可以使得組合數總和 = target? 請把滿足組合數總和 = target的組合方法以陣列的形式返回答案
Thumbnail
給定一個輸入陣列,每一個tuple代表節點之間了從屬關係。 請從從屬關係重建整顆二元樹,並且返回整顆二元樹的根結點。
Thumbnail
題目敘述 Merge Nodes in Between Zeros 給定一個鏈結串列,合併非零區間的節點(以加總的方式合併),輸出合併後的鏈結串列。
Thumbnail
題目敘述 Longest Arithmetic Subsequence of Given Difference 給定一個整數陣列nums,請找出給定公差difference的最長的等差數列的長度是多少?
Thumbnail
給定兩個輸入整數陣列, 若在兩個陣列遇到相同的數字可以連成一線, 但是有規定連線不可和別的連線有交叉, 請問最多可以形成幾條連線? 解答中探討了演算法化簡的技巧和DP模型, 可以透過演算法化簡的技巧, 把這題映射到原本已經學會的Longest Common Subsequence的DP模型來解開。
Thumbnail
給定一個字串陣列,請把它們所共有的字元伴隨著出現次數輸出。這篇文章介紹如何使用字典統計出現次數,和字典取交集的方法來解決此問題。並提供了複雜度分析和關鍵知識點。
Thumbnail
Append Characters to String to Make Subsequence 給定兩個字串s和字串t。 請計算最少的字元串接數量是多少,串接在s的尾端,使得t是s的子序列。 測試範例 Example 1: Input: s = "coaching", t =
Thumbnail
這題也是滿經典的DP動態規劃教學案例和題目,就順便複習一下吧。 題目敘述 題目會給我們兩個字串text1, text2。 要求我們找出兩個字串的最長共同子序列,並且返回最長共同子序列的長度。 如果彼此沒有共同子序列,則返回0。 題目的原文敘述 測試範例 Example 1: In
Thumbnail
題目敘述 題目會給定我們兩個字串word1 和 word2。 允許我們不限制次數進行下列兩種操作: 任意調換其中兩個字元的位置。 把字串中的某個字元全部置換成另一個字元,同時把另一個字元同時置換成某個字元。(例如把字串中原本的a都換成b,把原本的b都換成a) 問我們能不能通過上述兩項操作,
Thumbnail
本專欄將提供給您最新的市場資訊、產業研究、交易心法、精選公司介紹,以上內容並非個股分析,還請各位依據自身狀況作出交易決策。歡迎訂閱支持我,獲得相關內容,也祝您的投資之路順遂! 每年 $990 訂閱方案👉 https://reurl.cc/VNYVxZ 每月 $99 訂閱方案👉https://re
Thumbnail
題目敘述 Combination Sum II_Leetcode #40 給定一個整數陣列candidates 和 目標值target。 每個陣列元素只能選擇一次,請問有多少種組合方法,可以使得組合數總和 = target? 請把滿足組合數總和 = target的組合方法以陣列的形式返回答案
Thumbnail
給定一個輸入陣列,每一個tuple代表節點之間了從屬關係。 請從從屬關係重建整顆二元樹,並且返回整顆二元樹的根結點。
Thumbnail
題目敘述 Merge Nodes in Between Zeros 給定一個鏈結串列,合併非零區間的節點(以加總的方式合併),輸出合併後的鏈結串列。
Thumbnail
題目敘述 Longest Arithmetic Subsequence of Given Difference 給定一個整數陣列nums,請找出給定公差difference的最長的等差數列的長度是多少?
Thumbnail
給定兩個輸入整數陣列, 若在兩個陣列遇到相同的數字可以連成一線, 但是有規定連線不可和別的連線有交叉, 請問最多可以形成幾條連線? 解答中探討了演算法化簡的技巧和DP模型, 可以透過演算法化簡的技巧, 把這題映射到原本已經學會的Longest Common Subsequence的DP模型來解開。
Thumbnail
給定一個字串陣列,請把它們所共有的字元伴隨著出現次數輸出。這篇文章介紹如何使用字典統計出現次數,和字典取交集的方法來解決此問題。並提供了複雜度分析和關鍵知識點。
Thumbnail
Append Characters to String to Make Subsequence 給定兩個字串s和字串t。 請計算最少的字元串接數量是多少,串接在s的尾端,使得t是s的子序列。 測試範例 Example 1: Input: s = "coaching", t =
Thumbnail
這題也是滿經典的DP動態規劃教學案例和題目,就順便複習一下吧。 題目敘述 題目會給我們兩個字串text1, text2。 要求我們找出兩個字串的最長共同子序列,並且返回最長共同子序列的長度。 如果彼此沒有共同子序列,則返回0。 題目的原文敘述 測試範例 Example 1: In
Thumbnail
題目敘述 題目會給定我們兩個字串word1 和 word2。 允許我們不限制次數進行下列兩種操作: 任意調換其中兩個字元的位置。 把字串中的某個字元全部置換成另一個字元,同時把另一個字元同時置換成某個字元。(例如把字串中原本的a都換成b,把原本的b都換成a) 問我們能不能通過上述兩項操作,