นับจุดที่แตกต่างที่เยี่ยมชมบนเส้นจำนวนใน C++

เราได้รับลำดับเลขฐานสองของ 0 และ 1 ยังถือว่าบุคคลกำลังนั่งอยู่ที่ตำแหน่งหรือจุดที่เก็บไว้ใน current_pos ตอนนี้เริ่มต้นจาก current_pos หากลำดับไบนารีมี 0 แล้ว hemove เหลือขั้นตอนเดียว ( 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) รับตำแหน่งปัจจุบันและอินพุตพาธและส่งกลับจำนวนตำแหน่ง/จุดที่แตกต่างกัน

• เลนตัวแปรเก็บความยาวของเส้นทาง

• ความถี่อาร์เรย์[21] ใช้เพื่อเก็บความถี่สำหรับจำนวนครั้งที่เข้าชมจุด ดัชนีแสดงถึงจุด รวม 0-20.

• เริ่มสำรวจเส้นทางสตริง

• หากค่าปัจจุบันเป็น 0 ให้เลื่อนไปทางซ้าย ( current_pos -1 ) อัปเดตความถี่ของ pointfrequency นี้[current_pos]++.

• ค่าปัจจุบันอื่นคือ 1 เลื่อนไปทางขวา ( current_pos +1 ) อัปเดตความถี่ของ pointfrequency นี้[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