Chúng tôi được cung cấp một chuỗi nhị phân của 0 và 1. Cũng giả sử một người đang ngồi tại vị trí hoặc điểm được lưu trữ trong current_pos. Bây giờ bắt đầu từ current_pos, nếu chuỗi nhị phân có 0 thì bước sang trái một bước (current_pos - 1). Nếu là 1, anh ấy di chuyển sang phải một bước (current_pos + 1). Thegoal là tìm các vị trí hoặc điểm riêng biệt mà anh ta đã truy cập sau khi toàn bộ chuỗi nhị phân được hoàn thành.
Chúng tôi sẽ giải quyết vấn đề này bằng cách sử dụng số lần một điểm được truy cập. Nếu tần số khác 0, hãy tăng số lượng các điểm riêng biệt.
Đầu vào
Path[]= “001100” current_pos=3
Đầu ra
Distinct points visited on number line: 3
Giải thích - bắt đầu từ đường dẫn [0] và vị trí 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
Tổng số vị trí phân biệt là 3, là 1,2,3
Đầu vào
Path[]= “010101” current_pos=5
Đầu ra
Distinct points visited on number line: 2
Giải thích - bắt đầu từ đường dẫn [0] và vị trí 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
Tổng số vị trí khác biệt là 2, là 4 và 5
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Chuỗi số 0 và số 1 được lưu trữ trong đường dẫn.
-
Điểm xuất phát của cửa hàng Current_pos.
-
Hàm getDistinctPoints (int current_pos, đường dẫn chuỗi) nhận vị trí hiện tại và đầu vào pathas và trả về số lượng các vị trí / điểm riêng biệt.
-
Biến len lưu trữ độ dài của đường dẫn.
-
Tần số mảng [21] được sử dụng để lưu trữ tần số cho số lần điểm được truy cập. Chỉ số đại diện cho điểm. Tổng số 0-20.
-
Bắt đầu duyệt qua chuỗi đường dẫn.
-
Nếu giá trị hiện tại là 0, di chuyển sang trái (current_pos -1). Cập nhật tần suất của tần suất điểm này [current_pos] ++.
-
Giá trị hiện tại khác là 1, di chuyển sang phải (current_pos +1). Cập nhật tần suất của tần suất điểm này [current_pos] ++.
-
Bây giờ duyệt qua mảng tần số và cho mỗi giá trị khác 0. Tăng số lượng.
-
Số lượng chứa các điểm đã truy cập riêng biệt.
- Số lượt trả về là kết quả mong muốn.
Ví dụ
#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;
} Đầu ra
Count of distinct points visited on the number line :5