🎨自動填補 迴旋矩陣IV_Spiral Matrix IV_Leetcode 2326

閱讀時間約 1 分鐘

題目敘述 2326. Spiral Matrix IV


題目給定一個Linked list和對應的矩陣高度m、寬度n。

依照順時針的拜訪順序,
從左上角出發,依照次序把Linked List的內容填到矩陣裡。

如果有剩餘不足的空位,就填補-1


最後將填補好的矩陣返回作為答案。


測試範例

Example 1:

raw-image
Input: m = 3, n = 5, head = [3,0,2,6,8,1,7,9,4,2,5,5,0]
Output: [[3,0,2,6,8],[5,0,-1,-1,1],[5,2,4,9,7]]
Explanation: The diagram above shows how the values are printed in the matrix.
Note that the remaining spaces in the matrix are filled with -1.


Example 2:

raw-image
Input: m = 1, n = 4, head = [0,1,2]
Output: [[0,1,2,-1]]
Explanation: The diagram above shows how the values are printed from left to right in the matrix.
The last space in the matrix is set to -1.

約束條件

Constraints:

  • 1 <= m, n <= 10^5

高度、寬度都介於1~十萬之間。

  • 1 <= m * n <= 10^5

格子點總數介於1~十萬之間。

  • The number of nodes in the list is in the range [1, m * n].

Linked list長度介於 1~格子點總數之間。

  • 0 <= Node.val <= 1000

所有節點值都介於0~1000之間。


演算法 模擬順時針迴旋路徑


先建立一個高度m 寬度n的二維陣列,陣列元素值都初始化成-1。


接著,依照題意進行順時針迴旋路徑的模擬,

依照順序把Linked List的內容填到對應的陣列位置上。


最後,回傳二維陣列作為答案即可。


Python程式碼 模擬順時針迴旋路徑

class Solution:
def spiralMatrix(self, m: int, n: int, head: "ListNode") -> List[List[int]]:
# Store the east, south, west, north movements in a matrix.
x, y = 0, 0

# Go east on starting point
direction = 0

# Direction vector:
# Easr , South , West , North
vector = [[1, 0], [0, 1], [-1, 0], [0, -1]]
res = [[-1 for _ in range(n)] for _ in range(m)]

# Keep filling array cell one by one on spiral path
while head is not None:
res[y][x] = head.val

newx = x + vector[direction][0]
newy = y + vector[direction][1]

# If we meet an edge or an already filled cell, change the direction clockwise.
if ( newy < 0 or newx < 0 or newy >= m or newx >= n or res[newy][newx] != -1):
direction = (direction + 1) % 4

x += vector[direction][0]
y += vector[direction][1]

head = head.next

return res

Go程式碼 模擬順時針迴旋路徑


func spiralMatrix(m int, n int, head *ListNode) [][]int {

result := make( [][]int, m)

// Create 2D Array with height m * width n
for y := 0 ; y < m ; y++{
result[y] = make( []int, n)

for x := 0 ; x < n ; x++{
result[y][x] = -1
}
}

// Moving Vector
// East , South , West , North
vector := [][]int{ {1, 0}, {0, 1}, {-1, 0}, {0, -1}}

// Direction
direction := 0

// Starting point
x, y := 0, 0

// Keep moving in spiral path, filling with node value in linked list
for head != nil{

result[y][x] = head.Val

// Turn right if next position is edge or out of boundary.
nx, ny := x + vector[direction][0], y + vector[direction][1]

if (nx >= n) || (nx < 0) || (ny >= m) || (ny < 0) || ( result[ny][nx] != -1 ) {
direction = (direction + 1) % 4
}

// Go to next array cell in spiral path
x, y = x + vector[direction][0], y + vector[direction][1]

// Go to next node of linked list
head = head.Next
}

// Return 2D Array
return result
}

複雜度分析

時間複雜度 O(mn)

建立二維陣列,依序拜訪每個格子點一次,總共耗時O(m * n)


空間複雜度 O(mn)

建立二維陣列,總共所需空間為O(m * n)


Reference

[1] Spiral Matrix IV - LeetCode

83會員
424內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
發表第一個留言支持創作者!
Walking Robot Simulation 機器人在一個無限大小的 X-Y 2D平面上行走,從點 (0, 0) 開始出發,一開始面向北方。 機器人可以接收以下三種類型的命令 -2 :向左轉 90 度 -1 :向右轉 90 度 1 <= x <= 9 :向前移動 x步
Leetcode #1945. Sum of Digits of String After Convert 給定一個由小寫字母組成的字串 s ,以及一個整數 k 。 首先,用英文字母順序的位置替換每個字母,將 s 轉換 為整數 並且計算digits sum,反覆迭代k次。
 Binary Tree Inorder Traversal 題目給定一個二元樹的根結點。 請輸出中序拜訪(In-order traversal)的拜訪序列。 中序拜訪的定義: 1.拜訪左子樹。 2.拜訪目前的節點。 3.拜訪右子樹。
給定一個長度為 n,而且索引從 0 開始的整數陣列 chalk 和參數 k 。一開始粉筆盒裡總共有 k 支粉筆。 當編號為 i 的學生回答問題時,會消耗 chalk[i] 支粉筆。 如果剩餘粉筆數量小於 chalk[i] ,那麼學生 i 需要 補充 粉筆。 請找出需要補充粉筆的學生的學生編號。
Convert 1D Array Into 2D Array 給定一個一維輸入陣列,請轉換成高度為m*寬度為n的二維陣列, 以二維陣列的形式輸出。 如果無法轉換,請輸出空陣列。
Most Stones Removed with Same Row or Column 給定一個2D平面,好幾顆石頭散布在不同的點座標。 輸入陣列代表每顆石頭所在的(x, y)座標。 如果某顆石頭的x座標或者y座標相同的軸線上,還有其他石頭, 則原本那顆石頭可以移除。 請問做多可已移除幾顆石頭?
Walking Robot Simulation 機器人在一個無限大小的 X-Y 2D平面上行走,從點 (0, 0) 開始出發,一開始面向北方。 機器人可以接收以下三種類型的命令 -2 :向左轉 90 度 -1 :向右轉 90 度 1 <= x <= 9 :向前移動 x步
Leetcode #1945. Sum of Digits of String After Convert 給定一個由小寫字母組成的字串 s ,以及一個整數 k 。 首先,用英文字母順序的位置替換每個字母,將 s 轉換 為整數 並且計算digits sum,反覆迭代k次。
 Binary Tree Inorder Traversal 題目給定一個二元樹的根結點。 請輸出中序拜訪(In-order traversal)的拜訪序列。 中序拜訪的定義: 1.拜訪左子樹。 2.拜訪目前的節點。 3.拜訪右子樹。
給定一個長度為 n,而且索引從 0 開始的整數陣列 chalk 和參數 k 。一開始粉筆盒裡總共有 k 支粉筆。 當編號為 i 的學生回答問題時,會消耗 chalk[i] 支粉筆。 如果剩餘粉筆數量小於 chalk[i] ,那麼學生 i 需要 補充 粉筆。 請找出需要補充粉筆的學生的學生編號。
Convert 1D Array Into 2D Array 給定一個一維輸入陣列,請轉換成高度為m*寬度為n的二維陣列, 以二維陣列的形式輸出。 如果無法轉換,請輸出空陣列。
Most Stones Removed with Same Row or Column 給定一個2D平面,好幾顆石頭散布在不同的點座標。 輸入陣列代表每顆石頭所在的(x, y)座標。 如果某顆石頭的x座標或者y座標相同的軸線上,還有其他石頭, 則原本那顆石頭可以移除。 請問做多可已移除幾顆石頭?
你可能也想看
Google News 追蹤
Thumbnail
本專欄將提供給您最新的市場資訊、產業研究、交易心法、精選公司介紹,以上內容並非個股分析,還請各位依據自身狀況作出交易決策。歡迎訂閱支持我,獲得相關內容,也祝您的投資之路順遂! 每年 $990 訂閱方案👉 https://reurl.cc/VNYVxZ 每月 $99 訂閱方案👉https://re
Thumbnail
題目敘述 Combination Sum II_Leetcode #40 給定一個整數陣列candidates 和 目標值target。 每個陣列元素只能選擇一次,請問有多少種組合方法,可以使得組合數總和 = target? 請把滿足組合數總和 = target的組合方法以陣列的形式返回答案
Thumbnail
題目敘述: 給定一個二維陣列的高與寬,並且給定起點位置座標。 請從起點位置開始順時針拜訪陣列元素,並且把沿路走過的座標記錄下來。 以陣列的形式返回答案。
Thumbnail
給定一個輸入陣列,每一個tuple代表節點之間了從屬關係。 請從從屬關係重建整顆二元樹,並且返回整顆二元樹的根結點。
Thumbnail
題目敘述 Merge Nodes in Between Zeros 給定一個鏈結串列,合併非零區間的節點(以加總的方式合併),輸出合併後的鏈結串列。
Thumbnail
題目敘述 Intersection of Two Arrays II 給定兩個輸入陣列,請找出兩個陣列交集的元素,並且依照出現次數輸出。 測試範例 Example 1: Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2,2] 交集元素
Thumbnail
題目敘述 Combination Sum IV 給定一個輸入陣列nums,和目標值target,從nums裡面挑數字去湊出總和 = target,數字可以重複挑選。 請問有多少排列數可以湊出target? 註: 排列數的意思就是位置不同代表兩種不同的方法數。
Thumbnail
題目敘述 題目會給我們一個輸入陣列arr,起始點固定在索引為0的位置, 終點固定在索引為n-1的位置。 假設當下所在的索引位置為i,那麼每次移動的時候,可以跳到i-1,i+1,或者其他和我有相同元素值的位置arr[j], where arr[j] = arr[i]。 例如: 假設當下在i=3
Thumbnail
題目敘述 題目會給我們一個輸入陣列nums,和一個指定的k值。 請問,在輸入陣列nums中,有幾個子陣列的元素總合恰好為k ? 例如: nums = [1,2,3], k = 3 則有兩個子陣列的元素總合為3,分別是[1,2] 和 [3] 如果是第一次聽到或接觸前綴和prefix的同學
Thumbnail
題目敘述 題目會給我們一個輸入陣列nums,每個元素值代表那個格子點可以左右位移的固定長度。 例如,假設 nums[i] = 3,那麼下一步可以移動到nums[i-3] 或 nums[i+3]這兩個格子點。 題目​會給定一個起始點start索引位置,請問我們能不能走到內部數值為0的格子點?
Thumbnail
題目敘述 題目會給我們一顆二元樹的根結點,請我們列出每一層最右邊的節點值,以陣列的形式返回答案。 題目的原文敘述 測試範例 Example 1: Input: root = [1,2,3,null,5,null,4] Output: [1,3,4] 每一層最右邊的節點值分別是1, 3,
Thumbnail
本專欄將提供給您最新的市場資訊、產業研究、交易心法、精選公司介紹,以上內容並非個股分析,還請各位依據自身狀況作出交易決策。歡迎訂閱支持我,獲得相關內容,也祝您的投資之路順遂! 每年 $990 訂閱方案👉 https://reurl.cc/VNYVxZ 每月 $99 訂閱方案👉https://re
Thumbnail
題目敘述 Combination Sum II_Leetcode #40 給定一個整數陣列candidates 和 目標值target。 每個陣列元素只能選擇一次,請問有多少種組合方法,可以使得組合數總和 = target? 請把滿足組合數總和 = target的組合方法以陣列的形式返回答案
Thumbnail
題目敘述: 給定一個二維陣列的高與寬,並且給定起點位置座標。 請從起點位置開始順時針拜訪陣列元素,並且把沿路走過的座標記錄下來。 以陣列的形式返回答案。
Thumbnail
給定一個輸入陣列,每一個tuple代表節點之間了從屬關係。 請從從屬關係重建整顆二元樹,並且返回整顆二元樹的根結點。
Thumbnail
題目敘述 Merge Nodes in Between Zeros 給定一個鏈結串列,合併非零區間的節點(以加總的方式合併),輸出合併後的鏈結串列。
Thumbnail
題目敘述 Intersection of Two Arrays II 給定兩個輸入陣列,請找出兩個陣列交集的元素,並且依照出現次數輸出。 測試範例 Example 1: Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2,2] 交集元素
Thumbnail
題目敘述 Combination Sum IV 給定一個輸入陣列nums,和目標值target,從nums裡面挑數字去湊出總和 = target,數字可以重複挑選。 請問有多少排列數可以湊出target? 註: 排列數的意思就是位置不同代表兩種不同的方法數。
Thumbnail
題目敘述 題目會給我們一個輸入陣列arr,起始點固定在索引為0的位置, 終點固定在索引為n-1的位置。 假設當下所在的索引位置為i,那麼每次移動的時候,可以跳到i-1,i+1,或者其他和我有相同元素值的位置arr[j], where arr[j] = arr[i]。 例如: 假設當下在i=3
Thumbnail
題目敘述 題目會給我們一個輸入陣列nums,和一個指定的k值。 請問,在輸入陣列nums中,有幾個子陣列的元素總合恰好為k ? 例如: nums = [1,2,3], k = 3 則有兩個子陣列的元素總合為3,分別是[1,2] 和 [3] 如果是第一次聽到或接觸前綴和prefix的同學
Thumbnail
題目敘述 題目會給我們一個輸入陣列nums,每個元素值代表那個格子點可以左右位移的固定長度。 例如,假設 nums[i] = 3,那麼下一步可以移動到nums[i-3] 或 nums[i+3]這兩個格子點。 題目​會給定一個起始點start索引位置,請問我們能不能走到內部數值為0的格子點?
Thumbnail
題目敘述 題目會給我們一顆二元樹的根結點,請我們列出每一層最右邊的節點值,以陣列的形式返回答案。 題目的原文敘述 測試範例 Example 1: Input: root = [1,2,3,null,5,null,4] Output: [1,3,4] 每一層最右邊的節點值分別是1, 3,