Giả sử chúng ta có một danh sách các số nguyên dương; các số nguyên liền kề sẽ thực hiện phép chia float. Vì vậy, ví dụ, [2,3,4] -> 2/3 / 4. Bây giờ, chúng ta có thể thêm bất kỳ số lượng dấu ngoặc nào ở bất kỳ vị trí nào để thay đổi mức độ ưu tiên của các phép toán này. Chúng ta nên tìm cách thêm dấu ngoặc để thu được kết quả tối đa, chúng ta phải tìm biểu thức tương ứng ở dạng chuỗi. Biểu thức của chúng ta KHÔNG được chứa dấu ngoặc đơn thừa. Vì vậy, nếu đầu vào là [1000,100,10,2], thì kết quả sẽ là “1000 / (100/10/2)”.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- n:=kích thước của mảng nums
- nếu n là 0 thì trả về một chuỗi trống.
- num:=nums [0] dưới dạng chuỗi
- nếu n là 1, thì trả về num
- nếu n là 2, thì trả về num nối /, nối nums [1] dưới dạng chuỗi
- den:=một chuỗi trống
- cho tôi trong phạm vi từ 1 đến n - 1
- den:=den + nums [i] dưới dạng chuỗi
- nếu tôi không phải là n - 1, thì den:=den concatenate ‘/’
- trả về num concatenate / concatenate (nối den, nối)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#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));
} Đầu vào
[1000,100,10,2]
Đầu ra
1000/(100/10/2)