資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學沿給定字串指定的路徑行走時，計算訪問過的點的數量
在這個問題中，我們給定一個表示移動方向和起始座標的字串。我們需要找到重複訪問的位置。
我們可以使用集合或對映資料結構來儲存之前訪問過的座標。如果我們在集合或對映中找到任何重複的座標對，我們可以說該位置被重複訪問。
問題陳述 – 我們給定一個長度為 N 的字串 str，其中包含字元 'L'、'R'、'U' 和 'D'。此外，我們還給定表示起始位置的整數 X 和 Y。我們需要找到按照以下條件遵循路徑時重複訪問的座標總數。
對於字元 'L'，向左移動，將 X 的值減 1。
對於字元 'R'，向右移動，將 X 的值加 1。
對於字元 'U'，向上移動，將 Y 的值加 1。
對於字元 'D'，向下移動，將 Y 的值減 1。
示例
輸入 – str = "DDRULRD", X = 0, Y = 0
輸出 – 2
解釋 – 讓我們根據給定的字串跟蹤移動。
(0, -1) -> (0, -2) -> (1, -2) -> (1, -1) -> (0, -1) ->(1, -1) -> (1, 0).
上面的路徑顯示 (0, -1) 和 (1, -1) 被重複訪問。
輸入 – str = "RLUDRDDUU", X = 3, Y = 5
輸出 – 5
解釋 – 路徑移動如下所示。
(4, 5) -> (3, 5) -> (3, 6) -> (3, 5) ->(4, 5) -> (4, 4) -> (4, 3) -> (4, 4) - > (4, 5).
在上述位置中，(4, 5) 重複出現兩次，(3, 5) 作為初始位置也重複出現兩次，(4, 4) 重複出現一次。
方法 1
在這種方法中，我們將使用集合資料結構來跟蹤移動。我們將根據當前字元向 X 或 Y 座標新增 +1 或 -1。更新位置後，如果我們發現該位置座標已存在於集合中，則可以說它被重複訪問。
演算法
用字串的長度初始化變數 'len'。
用零初始化變數 'x_pos' 和 'y_pos'。定義變數 'cnt' 來儲存重複位置的數量。
定義集合，並使用 insert() 方法插入初始座標對。
開始遍歷字串。在迴圈中，使用 if-else 語句根據當前字元更新位置。
如果當前字元是 'U'，則設定 y_pos = 1 且 x_pos = 0。對於字元 'D'，設定 y_pos = -1 且 x_pos = 0;
如果當前字元是 'R'，則設定 y_pos = 0 且 x_pos = 1。對於字元 'L'，設定 y_pos = 0 且 x_pos = -1;
將 x_pos 加到 X 和 y_pos 加到 Y。
使用 find() 方法檢查 X 和 Y 是否存在於集合中。如果是，則將 'cnt' 的值增加 1。否則，將該對插入集合。
返回 'cnt' 值。
示例
#include <bits/stdc++.h>
using namespace std;
// function to cnt the total number of revisited positions
int countRevisited(string str, int X, int Y) {
// Stores the length of the string
int len = str.length();
// to store the current position
int x_pos = 0, y_pos = 0;
// to store the count of revisited positions
int cnt = 0;
// Define a set to store the pairs of visited positions
set<pair<int, int>> pairs;
// Insert the starting coordinates
pairs.insert({X, Y});
// Traverse over the string
for (int i = 0; i < len; i++) {
// Modify the current position according to the given direction.
if (str[i] == 'U') {
y_pos = 1;
x_pos = 0;
} else if (str[i] == 'D') {
y_pos = -1;
x_pos = 0;
} else if (str[i] == 'R') {
x_pos = 1;
y_pos = 0;
} else {
x_pos = -1;
y_pos = 0;
}
X += x_pos;
Y += y_pos;
// If the current position is already visited, then increment cnt by 1
if (pairs.find({X , Y }) != pairs.end()) {
cnt++;
}
// else insert the current position in the set
else {
pairs.insert({X , Y });
}
}
return cnt;
}
int main(){
string str = "RLUDRDDUU";
int X = 3, Y = 5;
cout << "The numbers of revisited coordinates while following the given path are - " << countRevisited(str, X, Y);
return 0;
}
輸出
The numbers of revisited coordinates while following the given path are - 5
時間複雜度 – O(N * logN)，因為我們遍歷字串並在集合中搜索對。
空間複雜度 – O(N)，因為在最壞情況下我們需要儲存 N 個對。
方法 2
此方法將使用對映資料結構來儲存訪問過的對。此外，我們還將在 C++ 中使用 switch case 語句根據字串的字元更新當前位置。
演算法
定義變數 'len'、'x_pos'、'y_pos' 和 'cnt'。
定義對映名稱 'pairs' 並將初始位置新增到對映中。
開始遍歷字串。使用 switch() 語句根據第 i 個索引處的字元更新 x_pos 和 y_pos 變數的值。
將 x_pos 的值加到 X 和 y_pos 的值加到 Y。
從對映中訪問對 {X, Y} 的值。如果它大於 0，則該位置被重複訪問，'cnt' 的值增加 1。否則，為對映中的當前對設定 1。
示例
#include <bits/stdc++.h>
using namespace std;
// function to cnt the total number of revisited positions
int countRevisited(string str, int X, int Y) {
// Stores the length of the string
int len = str.length();
// to store the current position
int x_pos = 0, y_pos = 0;
// to store the count of revisited positions
int cnt = 0;
// Define a map to store the pairs of visited positions
map<pair<int, int>, int> pairs;
// Insert the starting coordinates
pairs[{X, Y}] = 1;
// Traverse over the string
for (int i = 0; i < len; i++) {
// Modify the current position, according to the given direction using the switch statement
switch (str[i]){
case 'U':
y_pos = 1;
x_pos = 0;
break;
case 'D':
y_pos = -1;
x_pos = 0;
break;
case 'L':
y_pos = 0;
x_pos = -1;
break;
case 'R':
y_pos = 0;
x_pos = 1;
break;
}
X += x_pos;
Y += y_pos;
// If the current position is already visited, then increment cnt by 1
if (pairs[{X, Y}] > 0) {
cnt++;
}
// else insert the current position in the set
else {
pairs[{ X, Y}] = 1;
}
}
return cnt;
}
int main(){
string str = "RLUDRDDUU";
int X = 3, Y = 5;
cout << "The numbers of revisited coordinates while following the given path are - " << countRevisited(str, X, Y);
return 0;
}
輸出
The numbers of revisited coordinates while following the given path are - 5
時間複雜度 – O(N*logN)，因為我們迭代字串並在對映中搜索對。
空間複雜度 – O(N)，因為我們使用對映。
46 次瀏覽
