資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究查詢“X”形圖案的總數
在這個問題中，我們需要找到給定矩陣中“X”形圖案的總數。我們可以使用一個或多個相鄰的“X”元素來構造單個“X”形圖案。
我們可以使用 DFS（深度優先搜尋）技術來解決這個問題。對於每個“X”元素，我們可以使用 DFS 找到所有相鄰元素，並將其計為一個“X”形圖案。如果我們找到一個新的“X”，我們將再次找到其相鄰元素。
這裡，我們將使用迭代和遞迴 DFS 來找到“X”形圖案的總數。
問題陳述 - 我們給定一個大小為 N*M 的矩陣[]，其中包含“X”和“O”字元。我們需要找到給定矩陣中“X”形圖案的總數。一個“X”形圖案包含一個或多個垂直和水平相鄰的“X”元素。
示例
輸入
matrix = {{'O', 'O', 'X'}, {'O', 'X', 'X'}, {'X', 'X', 'X'}}
輸出
1
解釋 - 這裡，所有 X 都是相鄰的。因此，我們只能建立一個形狀。
O O X O X X O X X
輸入
matrix = {{'X', 'O', 'X'}, {'O', 'O', 'X'}, {'X', 'X', 'X'}}
輸出
2
解釋
The first shape is :- X O O O - - - - - The second shape is :- - O X O O X X X X
方法 1
在這種方法中，我們將使用遞迴 DFS 技術來找到給定矩陣中“X”形圖案的總數。
演算法
步驟 1 - 將“cnt”初始化為 0，以儲存“X”形圖案總數。
步驟 2 - 使用兩個巢狀迴圈開始遍歷矩陣。
步驟 3 - 如果當前元素是“X”，則將“cnt”加 1，並執行 performDFS() 函式以將所有相鄰的“X”替換為“O”。
步驟 4 - 定義 performDFS() 函式。
步驟 4.1 - 如果索引 p 小於 0，q 小於 0，p 大於矩陣的總行數，或 q 大於矩陣的總行數，則執行 return 語句。
步驟 4.2 - 如果 matrix[p][q] 是“X”，則將其更新為“O”。
步驟 4.3 - 對所有 4 個方向進行遞迴呼叫，以訪問相鄰的“X”元素。
步驟 5 - 返回“cnt”值。
示例
#include <bits/stdc++.h>
using namespace std;
void performDFS(vector<vector<char>> &matrix, int p, int q) {
if (p < 0 || q < 0 || p >= matrix.size() || matrix[p].size() <= q) {
return;
}
if (matrix[p][q] == 'X') {
// Update element with 'O'
matrix[p][q] = 'O';
// Recursively call DFS in all 4 directions
performDFS(matrix, p + 1, q);
performDFS(matrix, p, q + 1);
performDFS(matrix, p - 1, q);
performDFS(matrix, p, q - 1);
}
}
int findXShape(vector<vector<char>> &matrix) {
int rows = matrix.size();
int cols = matrix[0].size();
int cnt = 0;
for (int p = 0; p < matrix.size(); p++) {
for (int q = 0; q < matrix[p].size(); q++) {
// performing DFS on each element having a value 'X'
if (matrix[p][q] == 'X') {
cnt++;
performDFS(matrix, p, q);
}
}
}
return cnt;
}
int main() {
vector<vector<char>> matrix = {{'O', 'O', 'X'},
{'O', 'X', 'X'},
{'X', 'X', 'X'}};
cout << "The total number of X shape in the given matrix is " << findXShape(matrix) << endl;
return 0;
}
輸出
The total number of X shape in the given matrix is 1
時間複雜度 - O(N*M*N*M)，其中 (N*M) 用於矩陣遍歷，O(N*M) 用於執行 DFS。
空間複雜度 - O(1)，因為我們沒有使用任何額外的空間。
方法 2
在這種方法中，我們將使用“while”迴圈執行深度優先搜尋。此外，我們將使用堆疊資料結構來跟蹤最後訪問的陣列元素。
演算法
步驟 1 - 將“cnt”初始化為 0，並使用兩個巢狀迴圈遍歷給定矩陣。
步驟 2 - 如果當前元素是“X”，則將“cnt”值加 1，並執行 performDFS() 函式。
步驟 3.1 - 在 performDFS() 函式中，定義“pairSt”堆疊並將 {0, 0} 推入堆疊。
步驟 3.2 - 遍歷堆疊，直到其變為空。
步驟 3.3 - 從堆疊中彈出頂部元素，並將它的第一個和第二個元素分別儲存到“x”和“y”變數中。
步驟 3.4 - 如果當前元素是“X”，則將其更新為“O”。
步驟 3.5 - 如果存在任何相鄰的“X”元素，則將索引推入堆疊。
步驟 4 - 返回“cnt”值。
示例
#include <bits/stdc++.h>
using namespace std;
int subArrSum(int nums[], int len, int k){
int totalSum = 0;
// Deques to store indices of the current window in increasing and decreasing order, respectively;
deque<int> inc(k), dec(k);
// Handling the first window
int p = 0;
for (p = 0; p < k; p++){
// Remove elements which are greater than the current element
while ((!inc.empty()) && nums[inc.back()] >= nums[p])
inc.pop_back();
// Remove elements from dec deque which are smaller than the current element
while ((!dec.empty()) && nums[dec.back()] <= nums[p])
dec.pop_back(); // Remove from rear
// Add the nums[p] at last
inc.push_back(p);
dec.push_back(p);
}
// Hanlding other windows
for (; p < len; p++){
// get the first element from both the queues, and add them
totalSum += nums[inc.front()] + nums[dec.front()];
// Removing elements of the previous window
while (!inc.empty() && inc.front() <= p - k)
inc.pop_front();
while (!dec.empty() && dec.front() <= p - k)
dec.pop_front();
while ((!inc.empty()) && nums[inc.back()] >= nums[p])
inc.pop_back();
while ((!dec.empty()) && nums[dec.back()] <= nums[p])
dec.pop_back();
inc.push_back(p);
dec.push_back(p);
}
// Last window sum
totalSum += nums[inc.front()] + nums[dec.front()];
return totalSum;
}
int main() {
int nums[] = {3, 5, -2, 6, 4, 8, -9, 10, -5};
int len = sizeof(nums) / sizeof(nums[0]);
int K = 4;
cout << "The ans of minimum and maximum elements of all subarrays of size K is " << subArrSum(nums, len, K);
return 0;
}
輸出
The ans of minimum and maximum elements of all subarrays of size K is 15
時間複雜度 - O(N*M*N*M)，其中 (N*M) 用於遍歷矩陣，O(N*M) 用於執行 DFS。
空間複雜度 - O(N*M)，用於在矩陣中儲存索引對。
我們學習瞭如何在矩陣中實現迭代和遞迴 DFS。有時，在矩陣中實現 DFS 來解決與矩陣相關的複雜問題也很有用。
110 次瀏覽
