資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究給定從路徑中 C++ 中停止的最小數量
問題陳述
- 在二維空間中有許多點需要按特定順序訪問。
- 從一點到另一點的路徑始終選擇為最短路徑，並且路徑段始終與網格線對齊。
- 我們得到了為訪問點而選擇的路徑。我們需要告訴生成給定路徑所需的最少點。
演算法
1. We can solve this problem by observing the pattern of movement when visiting the stop 2. If we want to take the shortest path from one point to another point, then we will move in either one or max two directions
示例
#include <bits/stdc++.h>
using namespace std;
int getMinStops(string path) {
int n = path.length();
map<char, int> directionMap;
int stops = 1;
for (int i = 0; i < n; ++i) {
char direction = path[i];
directionMap[direction] = 1;
if ((directionMap['L'] && directionMap['R']) ||
(directionMap['U'] && directionMap['D'])) {
directionMap.clear();
++stops;
directionMap[direction] = 1;
}
}
return stops + 1;
}
int main() {
string path = "LLUUULLDD";
cout << "Minimum stops = " << getMinStops(path) << endl;
return 0;
}當您編譯並執行上面的程式時，它會生成以下輸出
輸出
Minimum stops = 3
更新於： 23-Dec-2019
115次瀏覽
廣告