เราได้รับลำดับไบนารีของ 0 และ 1 สมมติว่ามีคนนั่งอยู่ที่ตำแหน่ง current_pos เริ่มจาก current_pos หากลำดับเป็น 0 ให้เดินซ้าย 1 ก้าว (current_pos - 1) หากเป็น 1 ให้เดินขวา 1 ก้าว (current_pos + 1) เป้าหมายคือหาจุดที่แตกต่างกัน (distinct positions) ที่เขาเยี่ยมชมหลังจบลำดับไบนารี
เราแก้ปัญหานี้โดยนับความถี่ของการเยี่ยมชมแต่ละจุด หากความถี่ไม่เป็นศูนย์ ให้นับเป็นจุดที่แตกต่างกัน
อินพุต
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
จุดที่แตกต่างกันคือ 1, 2, 3 รวม 3 จุด
อินพุต
Path[] = "010101" current_pos = 5
เอาต์พุต
Distinct points visited on number line: 2
คำอธิบาย − จุดที่แตกต่างกันคือ 4 และ 5 รวม 2 จุด
วิธีการที่ใช้ในโปรแกรมด้านล่าง
- เก็บสตริง 0 และ 1 ใน path
- current_pos เก็บจุดเริ่มต้น
- ฟังก์ชัน getDistinctPoints(int current_pos, string path) คืนค่าจำนวนจุดที่แตกต่างกัน
- len เก็บความยาว path
- อาเรย์ frequency[21] เก็บความถี่การเยี่ยมชมแต่ละจุด (index = จุด 0-20)
- ลูปผ่าน path string หากเป็น 0 current_pos-- และ frequency[current_pos]++ หากเป็น 1 current_pos++ และ frequency[current_pos]++
- ลูปผ่าน frequency array หากค่าไม่เป็น 0 ให้เพิ่ม count
- คืนค่า count
ตัวอย่างโค้ด
#include <bits/stdc++.h>
using namespace std;
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]++;
} else {
current_pos++;
frequency[current_pos]++;
}
}
for (int i = 0; i < 21; i++)
if (frequency[i] != 0)
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
