อภิปรายปัญหาที่เราได้รับเลขไบนารี เราต้องลบ bit หนึ่งออกจากมัน เพื่อให้ตัวเลขที่เหลือควรเป็นค่าสูงสุดของตัวเลือกอื่นๆ ตัวอย่างเช่น:
Input : N = 1011 Output: 111 คำอธิบาย: เราต้องลบ bit หนึ่ง ดังนั้นการลบ bit 0 จะให้ตัวเลขสูงสุดมากกว่าการลบ bit 1 ใดๆ 111 > 101, 011 Input: 111 Output: 11 คำอธิบาย: เนื่องจากทุก bit เป็น 1 ดังนั้นเราสามารถลบ bit ใดๆ ได้
วิธีการหาคำตอบ
วิธี Brute-Force
การนำ Brute force ไปใช้จะให้ตัวเลขผลลัพธ์สูงสุด คือ โดยการลบแต่ละ bit ทีละตัว เปรียบเทียบผลลัพธ์ที่แตกต่างกัน และได้ผลลัพธ์สูงสุด
แต่มี วิธีที่มีประสิทธิภาพ (Efficient approach) หนึ่งที่สามารถใช้ได้ คือ ถ้าเราลบ bit ที่ซ้ำกันน้อยที่สุด (least redundant bit)
วิธีที่มีประสิทธิภาพ (Efficient Approach)
วิธีที่มีประสิทธิภาพจะส่งผลต่อตัวเลขผลลัพธ์น้อยที่สุด
- ก่อนอื่น เดินทางผ่าน bit จากด้านขวา
- ค้นหา 0 และข้ามมันในครั้งแรกที่พบ
- ถ้าไม่พบ 0 ให้ลบ bit ใดๆ หนึ่งตัว
ตัวอย่าง
โค้ด C++ สำหรับวิธีที่มีประสิทธิภาพ
#include <bits/stdc++.h>
using namespace std;
int main(){
string str = "1011";
bool flag = false;
int n = str.length();
// เริ่มต้นอาร์เรย์ใหม่สำหรับ
char res[n - 1];
int j = 0;
// เดินทางผ่านเลขไบนารีจากขวา
for (int i = 0; j < n - 1; i++) {
// ถ้าพบ 0 ให้ข้ามมัน
if (str[i] == '0' && flag == false) {
flag = true;
continue;
}
else
res[j++] = str[i];
}
// พิมพ์สตริงผลลัพธ์
cout << "Maximum number: " << res;
return 0;
}ผลลัพธ์
Maximum number: 111
คำอธิบายโค้ด
- ตัวแปร flag ใช้เพื่อให้ลบ 0 เพียงตัวเดียวเท่านั้น
- อาร์เรย์ตัวอักษร res ถูกเริ่มต้นเพื่อเก็บตัวเลขผลลัพธ์
- ลูปจะทำงานจนถึง n-1 เพราะเราต้องเก็บองค์ประกอบน้อยกว่าตัวเลขเดิมหนึ่งตัว
สรุป
ในบทช่วยสอนนี้ เราอภิปรายการหาตัวเลขสูงสุดหลังจากลบหนึ่ง bit ออกจากมัน เราอภิปรายสองวิธีในการแก้ปัญหานี้
เรายังเขียนโค้ด C++ สำหรับปัญหานี้ ซึ่งเราสามารถเขียนในภาษาอื่นๆ เช่น C, Java, Python ฯลฯ ได้ เราหวังว่าบทช่วยสอนนี้จะเป็นประโยชน์
