สมมติว่าเรามีรายการจำนวนเต็มบวก จำนวนเต็มที่อยู่ติดกันจะทำการหารแบบทศนิยม ตัวอย่างเช่น [2,3,4] -> 2 / 3 / 4 ตอนนี้ เราสามารถเพิ่มวงเล็บในตำแหน่งใดก็ได้เพื่อเปลี่ยนลำดับความสำคัญของการดำเนินการเหล่านี้ เราควรหาวิธีเพิ่มวงเล็บเพื่อให้ได้ผลลัพธ์สูงสุด เราต้องหานิพจน์ที่เกี่ยวข้องในรูปแบบสตริง นิพจน์ของเราไม่ควรมีวงเล็บซ้ำซ้อน ดังนั้นหากอินพุตเป็น [1000,100,10,2] ผลลัพธ์จะเป็น “1000/(100/10/2)”
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- n :=ขนาดของอาร์เรย์ nums
- ถ้า n เป็น 0 ให้คืนค่าสตริงว่าง
- num :=nums[0] เป็นสตริง
- ถ้า n เป็น 1 ให้คืนค่า num
- ถ้า n เป็น 2 ให้คืนค่า num concatenate /, concatenate nums[1] เป็นสตริง
- den :=สตริงว่าง
- สำหรับ i ในช่วง 1 ถึง n – 1
- den :=den + nums[i] เป็นสตริง
- ถ้าฉันไม่ใช่ n – 1 แล้ว den :=den concatenate ‘/’
- ส่งคืน num concatenate / concatenate ( concatenate den , concatenate )
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string optimalDivision(vector<int>& nums) {
int n = nums.size();
if(n == 0) return "";
string num = to_string(nums[0]);
if(n == 1) return num;
if(n == 2) return num + "/" + to_string(nums[1]);
string den = "";
for(int i = 1; i < n; i++){
den += to_string(nums[i]);
if(i != n - 1) den += "/";
}
return num + "/" + "(" + den + ")";
}
};
main(){
vector<int> v = {1000,100,10,2};
Solution ob;
cout << (ob.optimalDivision(v));
} อินพุต
[1000,100,10,2]
ผลลัพธ์
1000/(100/10/2)
