付費限定

字典應用: 計算相同的column row pairs_Leetcode 精選75題解析

更新於 發佈於 閱讀時間約 6 分鐘

題目敘述

題目會給定我們一個二維陣列,要求我們計算內部元素相同的column row pairs總共有多少條?

註: pair的定義就是row i 和 column j 彼此內部元素值都相同,這樣就算一條pair。


題目的原文敘述


測試範例

Example 1:

raw-image
Input: grid = [[3,2,1],[1,7,6],[2,7,7]]
Output: 1
Explanation: There is 1 equal row and column pair:
- (Row 2, Column 1): [2,7,7]

Example 2:

raw-image
Input: grid = [[3,1,2,2],[1,4,4,5],[2,4,2,2],[2,4,2,2]]
Output: 3
Explanation: There are 3 equal row and column pairs:
- (Row 0, Column 0): [3,1,2,2]
- (Row 2, Column 2): [2,4,2,2]
- (Row 3, Column 2): [2,4,2,2]

約束條件

Constraints:

  • n == grid.length == grid[i].length

輸入陣列一定是方陣。

  • 1 <= n <= 200

方陣的邊長介於1 ~ 200之間。

  • 1 <= grid[i][j] <= 10^5

元素值都介於1 ~ 10^5 之間。


演算法

這題的關鍵在於把每條row和每條column都轉換為可hash的對象,並且儲存在字典裏面,統計出現次數。


又因為記憶體排列是row-major的關係,在讀取某個column j的時候,會先把矩陣grid作轉秩grid T,再讀取grid T的row j,會比較方便。

在python,有一個很實用的語法,可以很簡潔的實現矩陣轉秩的功能。

transpose = list( zip( *grid ) )
以行動支持創作者!付費即可解鎖
本篇內容共 2412 字、1 則留言,僅發佈於Leetcode精選75題 解析+統整你目前無法檢視以下內容,可能因為尚未登入,或沒有該房間的查看權限。
留言
avatar-img
留言分享你的想法!
小松鼠-avatar-img
發文者
2024/05/29
Leetcode 精選75題 題目與題解 熱門考點 目錄 (持續更新中)提及了這篇文章,趕快過去看看吧!
avatar-img
小松鼠的演算法樂園
96會員
427內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
2024/05/29
Leetcode 精選75題 題目與題解 熱門考點 目錄 (持續更新中) 建議從左側目錄 或者 按Ctrl+F輸入關鍵字進行搜尋
Thumbnail
2024/05/29
Leetcode 精選75題 題目與題解 熱門考點 目錄 (持續更新中) 建議從左側目錄 或者 按Ctrl+F輸入關鍵字進行搜尋
Thumbnail
2024/05/24
知道如何從一組給定的英文字母和單字庫中的單字拼出最高分的單字組合。使用DFS + 回溯法 + 剪枝優化的演算法,詳細分析瞭如何展開所有可能的路徑,並且找出符合條件的狀態,協助讀者理解演算法背後的思維和方法。
Thumbnail
2024/05/24
知道如何從一組給定的英文字母和單字庫中的單字拼出最高分的單字組合。使用DFS + 回溯法 + 剪枝優化的演算法,詳細分析瞭如何展開所有可能的路徑,並且找出符合條件的狀態,協助讀者理解演算法背後的思維和方法。
Thumbnail
2024/05/21
子集合生成是一道經典的組合類上機考和面試題目。本篇文章介紹多個不同的解決方案,以及相關演算法框架。主要目標是給定n個相異的元素,產生所有的子集合。
Thumbnail
2024/05/21
子集合生成是一道經典的組合類上機考和面試題目。本篇文章介紹多個不同的解決方案,以及相關演算法框架。主要目標是給定n個相異的元素,產生所有的子集合。
Thumbnail
看更多
你可能也想看
Thumbnail
孩子寫功課時瞇眼?小心近視!這款喜光全光譜TIONE⁺光健康智慧檯燈,獲眼科院長推薦,網路好評不斷!全光譜LED、180cm大照明範圍、5段亮度及色溫調整、350度萬向旋轉,讓孩子學習更舒適、保護眼睛!
Thumbnail
孩子寫功課時瞇眼?小心近視!這款喜光全光譜TIONE⁺光健康智慧檯燈,獲眼科院長推薦,網路好評不斷!全光譜LED、180cm大照明範圍、5段亮度及色溫調整、350度萬向旋轉,讓孩子學習更舒適、保護眼睛!
Thumbnail
創作者營運專員/經理(Operations Specialist/Manager)將負責對平台成長及收入至關重要的 Partnership 夥伴創作者開發及營運。你將發揮對知識與內容變現、影響力變現的精準判斷力,找到你心中的潛力新星或有聲量的中大型創作者加入 vocus。
Thumbnail
創作者營運專員/經理(Operations Specialist/Manager)將負責對平台成長及收入至關重要的 Partnership 夥伴創作者開發及營運。你將發揮對知識與內容變現、影響力變現的精準判斷力,找到你心中的潛力新星或有聲量的中大型創作者加入 vocus。
Thumbnail
題目敘述 Intersection of Two Arrays II 給定兩個輸入陣列,請找出兩個陣列交集的元素,並且依照出現次數輸出。 測試範例 Example 1: Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2,2] 交集元素
Thumbnail
題目敘述 Intersection of Two Arrays II 給定兩個輸入陣列,請找出兩個陣列交集的元素,並且依照出現次數輸出。 測試範例 Example 1: Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2,2] 交集元素
Thumbnail
題目敘述 題目會給定我們一個二維陣列,要求我們計算內部元素相同的column row pairs總共有多少條? 註: pair的定義就是row i 和 column j 彼此內部元素值都相同,這樣就算一條pair。 題目的原文敘述 測試範例 Example 1: Input: gr
Thumbnail
題目敘述 題目會給定我們一個二維陣列,要求我們計算內部元素相同的column row pairs總共有多少條? 註: pair的定義就是row i 和 column j 彼此內部元素值都相同,這樣就算一條pair。 題目的原文敘述 測試範例 Example 1: Input: gr
Thumbnail
題目敘述 題目會給定我們兩個整數陣列作為輸入nums1, nums2,要求我們找出兩個陣列的差異值。 找出在nums1但是不在nums2的元素,以陣列的形式放在answer[0]輸出。 找出在nums2但是不在nums1的元素,以陣列的形式放在answer[1]輸出。 題目的原文敘述
Thumbnail
題目敘述 題目會給定我們兩個整數陣列作為輸入nums1, nums2,要求我們找出兩個陣列的差異值。 找出在nums1但是不在nums2的元素,以陣列的形式放在answer[0]輸出。 找出在nums2但是不在nums1的元素,以陣列的形式放在answer[1]輸出。 題目的原文敘述
Thumbnail
題目敘述 題目會給定一個整數陣列arr,要求我們判斷是否每個元素的出現次數都不同? 題目的原文敘述 測試範例 Example 1: Input: arr = [1,2,2,1,1,3] Output: true Explanation: The value 1 has 3 occurre
Thumbnail
題目敘述 題目會給定一個整數陣列arr,要求我們判斷是否每個元素的出現次數都不同? 題目的原文敘述 測試範例 Example 1: Input: arr = [1,2,2,1,1,3] Output: true Explanation: The value 1 has 3 occurre
Thumbnail
題目敘述 題目會給定我們一個二元矩陣grid,要求我們計算這個矩陣的Difference值,並且以矩陣的形式返回答案。 對於grid[i][j] 的Difference值定義 = 同一個row i裡面 1的數目 + 同一個column j裡面 1的數目 - 同一個row i裡面 0的數目
Thumbnail
題目敘述 題目會給定我們一個二元矩陣grid,要求我們計算這個矩陣的Difference值,並且以矩陣的形式返回答案。 對於grid[i][j] 的Difference值定義 = 同一個row i裡面 1的數目 + 同一個column j裡面 1的數目 - 同一個row i裡面 0的數目
Thumbnail
題目敘述 題目會給我們一個陣列,要求我們返回 兩數之和=target所在的陣列索引值。 題目還額外保證,一定剛好有一組解。 測試範例 Example 1: Input: nums = [2,7,11,15], target = 9 Output: [0,1]
Thumbnail
題目敘述 題目會給我們一個陣列,要求我們返回 兩數之和=target所在的陣列索引值。 題目還額外保證,一定剛好有一組解。 測試範例 Example 1: Input: nums = [2,7,11,15], target = 9 Output: [0,1]
Thumbnail
題目會給我們一個方陣,要求我們計算兩條對角線的元素總和。
Thumbnail
題目會給我們一個方陣,要求我們計算兩條對角線的元素總和。
Thumbnail
題目會給我們一個pair陣列,裡面都是原本陣列相鄰元素形成的pair,順序已經被打散。 要求我們從pair陣列重建出原本的陣列。 答案可能有不只一組,任選一組回傳即可。
Thumbnail
題目會給我們一個pair陣列,裡面都是原本陣列相鄰元素形成的pair,順序已經被打散。 要求我們從pair陣列重建出原本的陣列。 答案可能有不只一組,任選一組回傳即可。
Thumbnail
題目會給定一組輸入陣列,裡面每個參數分別代表矩陣的寬和高。 如果有兩個矩陣的寬/高的比例是相同的,代表這兩個矩陣是等比例的。 要求我們計算,等比例的矩陣pair總共有多少個?
Thumbnail
題目會給定一組輸入陣列,裡面每個參數分別代表矩陣的寬和高。 如果有兩個矩陣的寬/高的比例是相同的,代表這兩個矩陣是等比例的。 要求我們計算,等比例的矩陣pair總共有多少個?
Thumbnail
題目會給定我們一個輸入陣列,要求我們計算好配對的數目有多少個? 好配對的定義: 兩個數字相同,但是陣列索引一個在前,一個在後。 nums[i] == nums[j] and i < j. 這樣 (i, j) 就稱為一組好配對。
Thumbnail
題目會給定我們一個輸入陣列,要求我們計算好配對的數目有多少個? 好配對的定義: 兩個數字相同,但是陣列索引一個在前,一個在後。 nums[i] == nums[j] and i < j. 這樣 (i, j) 就稱為一組好配對。
追蹤感興趣的內容從 Google News 追蹤更多 vocus 的最新精選內容追蹤 Google News