C++の数直線上で訪問した個別のポイントをカウントします

0と1のバイナリシーケンスが与えられます。また、current_posに保存されている位置またはポイントに人が座っていると仮定します。ここで、current_posから開始し、バイナリシーケンスの値が0の場合、残りの1ステップ（current_pos-1）になります。 1の場合、彼は1ステップ右に移動します（current_pos + 1）。目標は、バイナリシーケンス全体が完了した後、彼が訪れた明確な位置またはポイントを見つけることです。

ポイントが訪問された回数を使用してこれを解決します。頻度がゼロ以外の場合は、個別のポイントの数を増やします。

入力

Path[]= “001100” current_pos=3

出力

Distinct points visited on number line: 3

説明 −パス[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

説明 −パス[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の文字列がパスに格納されます。

• Current_posは開始点を格納します。

• 関数getDistinctPoints（int current_pos、string path）は、現在の位置とpathas入力を受け取り、個別の位置/ポイントの数を返します。

• 変数lenは、パスの長さを格納します。

• 配列頻度[21]は、ポイントが訪問された回数の頻度を格納するために使用されます。インデックスはポイントを表します。合計0〜20。

• パス文字列のトラバースを開始します。

• 現在の値が0の場合は、左に移動します（current_pos -1）。このポイント頻度[current_pos]++の頻度を更新します。

• それ以外の場合、現在の値は1で、右に移動します（current_pos +1）。このポイント頻度[current_pos]++の頻度を更新します。

• 次に、周波数配列をトラバースし、ゼロ以外の値ごとにトラバースします。カウントを増やします。

• カウントには、個別の訪問ポイントが含まれます。

• 希望する結果としてカウントを返します。

例

#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