ผลต่างสูงสุดของเลขศูนย์และตัวในสตริงไบนารีใน C++

ภารกิจคือการค้นหาสตริงย่อยจากสตริงไบนารีที่กำหนด จากนั้นจึงหาค่าความแตกต่างสูงสุดระหว่างจำนวนศูนย์กับจำนวนนั้น

ตอนนี้มาทำความเข้าใจสิ่งที่เราต้องทำโดยใช้ตัวอย่าง -

อินพุต

str = “100100110”

ผลลัพธ์

2

คำอธิบาย

ในอาร์เรย์ย่อยจากตำแหน่ง 1 ถึง 5 (“00100”) ความแตกต่างระหว่างเลขศูนย์และอัน =4 – 1 =3 ซึ่งเป็นค่าสูงสุดที่หาได้

อินพุต

str = “00000”

ผลลัพธ์

5

แนวทางที่ใช้ในโปรแกรมด้านล่างดังนี้

• ในฟังก์ชัน main() สร้างสตริง str เพื่อเก็บสตริงไบนารี เริ่มต้นขนาด int ตัวแปรเพื่อเก็บ ขนาด ของสตริงและส่งผ่านทั้งคู่ไปยังฟังก์ชัน Max()

• ในฟังก์ชัน Max() ก่อนอื่นให้ตรวจสอบว่าองค์ประกอบทั้งหมดเป็น 1 หรือไม่โดยเรียกใช้ฟังก์ชัน One()

• สร้างฟังก์ชัน One() ของประเภท bool และภายในนั้นสร้างตัวแปร int O =0

• วนจาก i =0 จนถึง i

• นอกลูป ตรวจสอบว่า (O ==size) หากเป็นเช่นนั้น ให้คืนค่าเป็น จริง

• กลับไปที่ฟังก์ชัน Max() หากฟังก์ชัน One() คืนค่าเป็น true ให้คืนค่า -1 เป็นคำตอบ

• อย่างอื่นดำเนินการค้นหาความยาว เริ่มต้นอาร์เรย์ int a[100] ={ 0 }.

• วนจาก i =0 จนถึง i

• นอกลูป ให้เริ่มต้นอาร์เรย์อื่น int arr[100][3] และแทนที่องค์ประกอบทั้งหมดโดย -1 โดยใช้ memset(arr, -1, sizeof arr) และสุดท้ายเรียก Length(a, str, size, 0, 0, arr)

• ในฟังก์ชัน Length() ก่อนอื่นให้ตรวจสอบว่า (i>=size) ถ้าใช่ แสดงว่าสตริงนั้นโอเวอร์และคืนค่า 0

• จากนั้นตรวจสอบว่า (arr[i][s] !=-1) หากเป็นเช่นนั้น แสดงว่าสถานะได้รับการคำนวณแล้วและส่งคืน arr[i][s].

• จากนั้นตรวจสอบว่า (s ==0) ถ้าเป็นเช่นนั้น ให้คืนค่า arr[i][s] =max(a[i] + Length(a, str, size, i +1, 1, arr), Length(a, str, size, i + 1, 0 , arr));

• ผลตอบแทนอื่น arr[i][s] =max(a[i] + Length(a, str, size, i + 1, 1, arr), 0);

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
bool One(string str, int size){
   int O = 0;
   for (int i = 0; i < str.size(); i++)
      O += (str[i] == '1');
   return (O == size);
}
int Length(int a[], string str, int size,
int i, int s, int arr[][3]){
   // If string is over.
   if (i >= size)
      return 0;
      // If the already calculated.
   if (arr[i][s] != -1)
      return arr[i][s];
   if (s == 0)
      return arr[i][s] = max(a[i] +
      Length(a, str, size, i + 1, 1, arr),
      Length(a, str, size, i + 1, 0, arr));
   else
      return arr[i][s] = max(a[i] +
      Length(a, str, size, i + 1, 1, arr), 0);
}
int Max(string str, int size){
   // Checking if all elements are 1
   if (One(str, size))
      return -1;
      // Finding length
   int a[100] = { 0 };
   for (int i = 0; i < size; i++)
      a[i] = (str[i] == '0' ? 1 : -1);
      int arr[100][3];
      memset(arr, -1, sizeof arr);
   return Length(a, str, size, 0, 0, arr);
}
// main function
int main(){
   string str = "100100110";
   int size = 9;
   cout << Max(str, size);
   return 0;
}

ผลลัพธ์

3