Strobogrammatic Number III trong C ++

Giả sử chúng ta muốn xác định một hàm để đếm tổng số nét vẽ tồn tại trong phạm vi (thấp và cao). Như chúng ta biết rằng số nét vẽ là số trông giống nhau khi xoay 180 độ.

Vì vậy, nếu đầu vào là low ="50", high ="100", thì đầu ra sẽ là 3 vì có ba kết quả là 69, 88 và 96.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm findStrobogrammatic (), điều này sẽ mất n,

• Xác định ret mảng

• nếu n &1 khác 0 thì -

  • chèn "0" vào cuối ret

  • chèn "1" vào cuối ret

  • chèn "8" vào cuối ret

• Nếu không

  • chèn chuỗi trống vào cuối ret

• cho n> 1, cập nhật n:=n - 2, do -

  • Xác định tạm thời mảng

  • để khởi tạo i:=0, khi tôi

    • s:=ret [i]

    • nếu n> 3, thì -

      • chèn "0" + s + "0" vào cuối nhiệt độ

    • chèn "1" + s + "1" vào cuối tạm thời

    • chèn "8" + s + "8" vào cuối nhiệt độ

    • chèn "6" + s + "9" vào cuối nhiệt độ

    • chèn "9" + s + "6" vào cuối nhiệt độ

  • ret:=temp

• trả lại ret

• Từ phương thức chính, thực hiện như sau -

• ret:=0

• Xác định một mảng v

• để khởi tạo i:=kích thước thấp, khi tôi <=kích thước cao, cập nhật (tăng i lên 1), thực hiện -

  • v:=findStrobogrammatic (i)

  • để khởi tạo j:=0, khi j

    • ret:=ret + (1 khi độ dài v [j]> độ dài thấp VÀ độ dài cao> độ dài v [j])

• trả lại ret

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   vector<string> findStrobogrammatic(int n) {
      vector<string> ret;
      if (n & 1) {
         ret.push_back("0");
         ret.push_back("1");
         ret.push_back("8");
      }
      else {
         ret.push_back("");
      }
      for (; n > 1; n -= 2) {
         vector<string> temp;
         for (int i = 0; i < ret.size(); i++) {
            string s = ret[i];
            if (n > 3) {
               temp.push_back("0" + s + "0");
            }
            temp.push_back("1" + s + "1");
            temp.push_back("8" + s + "8");
            temp.push_back("6" + s + "9");
            temp.push_back("9" + s + "6");
         }
         ret = temp;
      }
      return ret;
   }
   bool compare(string a, string b){
      return a.size() == b.size() ? a >= b : a.size() > b.size();
   }
   int strobogrammaticInRange(string low, string high) {
      int ret = 0;
      vector<string> v;
      for (int i = low.size(); i <= high.size(); i++) {
         v = findStrobogrammatic(i);
         for (int j = 0; j < v.size(); j++) {
            ret += compare(v[j], low) && compare(high, v[j]);
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout <<(ob.strobogrammaticInRange("50", "100"));
}

Đầu vào

"50","100"

Đầu ra

3