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