資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++中計算數軸上訪問的不同點的個數
我們得到一個由0和1組成的二進位制序列。假設一個人坐在當前位置`current_pos`。從`current_pos`開始，如果二進位制序列是0，則他向左移動一步（`current_pos - 1`）。如果是1，則他向右移動一步（`current_pos + 1`）。目標是找到完成整個二進位制序列後他訪問過的不同位置或點。
我們將使用訪問點的次數來解決這個問題。如果頻率非零，則增加不同點的計數。
輸入
Path[]= “001100” current_pos=3
輸出
Distinct points visited on number line: 3
說明 − 從path[0]和位置3開始。
Path[0]: 0 → move left ...currpos=2 Path[1]: 0 → move left ...currpos=1 Path[2]: 1 → move right ...currpos=2 Path[3]: 1 → move left ...currpos=3 Path[4]: 0 → move left ...currpos=2 Path[5]: 0 → move left ...currpos=1
共有3個不同的位置，分別是1,2,3
輸入
Path[]= “010101” current_pos=5
輸出
Distinct points visited on number line: 2
說明 − 從path[0]和位置5開始。
Path[0]: 0 → move left ...currpos=4 Path[1]: 1 → move right ...currpos=5 Path[2]: 0 → move left ...currpos=4 Path[3]: 1 → move right ...currpos=5 Path[4]: 0 → move left ...currpos=4 Path[5]: 1 → move right ...currpos=5
共有2個不同的位置，分別是4和5
下面程式中使用的演算法如下
0和1的字串儲存在path中。
Current_pos儲存起始點。
函式`getDistinctPoints(int current_pos, string path)`以當前位置和路徑作為輸入，並返回不同位置/點的計數。
變數len儲存path的長度。
陣列frequency[21]用於儲存訪問點的頻率。索引表示點。總共0-20。
開始遍歷path字串。
如果當前值為0，則向左移動（`current_pos -1`）。更新此點的頻率`frequency[current_pos]++`。
否則當前值為1，則向右移動（`current_pos +1`）。更新此點的頻率`frequency[current_pos]++`。
現在遍歷frequency陣列，對於每個非零值，增加計數。
Count包含不同的已訪問點。
- 返回count作為期望結果。
示例
#include <bits/stdc++.h>
using namespace std;
//distict points visited between 0 to 20
int getDistinctPoints(int current_pos, string path){
// Length of path
int len = path.length();
int count=0;
// Array to store number of times a point is visited
int frequency[21]={0};
// For all the directions in path
for (int i = 0; i < len; i++) {
//for left direction
if (path[i] == '0') {
current_pos--;
frequency[current_pos]++; //increase visit count
}
// If the direction is right
else {
current_pos++;
frequency[current_pos]++; //increase visit count
}
}
for(int i=0;i<21;i++)
if(frequency[i]!=0) // if visted then frequency[i] is non zero
count++;
return count;
}
int main(){
int current_pos = 3;
string path = "011101100";
cout << "Count of distinct points visited on the number line:<<(getDistinctPoints(current_pos, path));
return 0;
}輸出
Count of distinct points visited on the number line :5
更新於：2020年8月3日
108次瀏覽
廣告