ค้นหาผลคูณที่ใหญ่ที่สุดของ 3 จากอาร์เรย์ของหลัก - ชุดที่ 2 ใน C++

สมมติว่าเรามีอาร์เรย์ของตัวเลขต่างกัน เราต้องหาตัวคูณที่ใหญ่ที่สุดของ 3 ที่สามารถสร้างได้โดยการต่อตัวเลขที่ระบุในอาร์เรย์นั้นในลำดับใดก็ได้ คำตอบอาจมีขนาดใหญ่มาก ให้ทำเป็นสตริง หากไม่มีคำตอบ ให้คืนค่าสตริงว่าง

ดังนั้นหากอินพุตเท่ากับ [7,2,8] เอาต์พุตจะเป็น 87

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดอาร์เรย์ 2 มิติ d หนึ่งชุด จะมีสามแถว

• เรียงเลขอาร์เรย์

• ผลรวม :=0

• สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาดของหลัก อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

  • x :=หลัก[i]

  • ใส่ตัวเลข[i] ต่อท้าย d[x mod 3]

  • ผลรวม :=ผลรวม + x

  • sum :=sum mod 3

• ถ้าผลรวมไม่เป็นศูนย์ ดังนั้น −

  • ถ้าไม่ใช่ขนาดของ d[sum] แล้ว −

    • rem :=3 - ผลรวม

    • ถ้าขนาดของ d[rem] <2 แล้ว −

      • คืนค่าสตริงว่าง

    • ลบองค์ประกอบสุดท้ายจาก d[rem] สองครั้ง

  • มิฉะนั้น

    • ลบองค์ประกอบสุดท้ายออกจาก d[sum]

• ret :=สตริงว่าง

• สำหรับการเริ่มต้น i :=0 เมื่อ i <3 อัปเดต (เพิ่ม i ขึ้น 1) ให้ทำ -

  • สำหรับการเริ่มต้น j :=0 เมื่อ j

    • ret :=ret concatenate d[i, j] เป็นสตริง

• จัดเรียงอาร์เรย์ ret

• ถ้าขนาดของ ret และ ret[0] เท่ากับ '0' ดังนั้น −

  • ส่งคืน "0"

• รีเทิร์น

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   string largestMultipleOfThree(vector<int>& digits) {
      vector<vector<int>> d(3);
      sort(digits.begin(), digits.end(), greater<int>());
      int sum = 0;
      for (int i = 0; i < digits.size(); i++) {
         int x = digits[i];
         d[x % 3].push_back(digits[i]);
         sum += x;
         sum %= 3;
      }
      if (sum) {
         if (!d[sum].size()) {
            int rem = 3 - sum;
            if (d[rem].size() < 2)
               return "";
            d[rem].pop_back();
            d[rem].pop_back();
         }
         else {
            d[sum].pop_back();
         }
      }
      string ret = "";
      for (int i = 0; i < 3; i++) {
         for (int j = 0; j < d[i].size(); j++) {
            ret += to_string(d[i][j]);
         }
      }
      sort(ret.begin(), ret.end(), greater<int>());
      if (ret.size() && ret[0] == '0')
         return "0";
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {7,2,8};
   cout << (ob.largestMultipleOfThree(v));
}

อินพุต

{7,2,8}

ผลลัพธ์

87