我们给定了一个二进制的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
说明-从路径[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)将当前位置和路径作为输入,并返回不同位置/点的计数。
变量len存储路径的长度。
数组频率[21]用于存储该点被访问的次数。索引代表要点。总计0-20。
开始遍历路径字符串。
如果当前值为0,则向左移动(current_pos -1)。更新该点频率[current_pos] ++的频率。
其他当前值为1,向右移动(current_pos +1)。更新该点频率[current_pos] ++的频率。
现在遍历频率数组,并遍历每个非零值。增加数量。
计数包含不同的访问点。
返回计数为所需结果。
#include <bits/stdc++.h> using namespace std; //在0到20之间访问的离散点 int getDistinctPoints(int current_pos, string path){ //路径长度 int len = path.length(); int count=0; //数组来存储访问点的次数 int frequency[21]={0}; //对于路径中的所有方向 for (int i = 0; i < len; i++) { //对于左方向 if (path[i] == '0') { current_pos--; frequency[current_pos]++; //increase visit count } //如果方向正确 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