数据结构
网络
关系数据库管理系统 (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 次浏览
