Giả sử chúng ta có một chuỗi với các chữ cái viết thường và chúng ta cũng có một danh sách các giá trị được gọi là giá trị không âm, chuỗi và danh sách có cùng độ dài. Chúng ta có thể xóa ký tự s [i] cho chi phí [i], sau đó cả ký tự [i] và chi phí [i] đều bị xóa. Chúng tôi phải tìm chi phí tối thiểu để xóa tất cả các ký tự lặp lại liên tiếp.
Vì vậy, nếu đầu vào giống như s ="xxyyx" nums =[2, 3, 10, 4, 6], thì đầu ra sẽ là 6, vì chúng tôi loại bỏ s [0] và s [3] với tổng chi phí là 2 + 4 =6.
Để 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 ngăn xếp
-
chi phí:=0
-
để khởi tạo i:=0, khi i
-
nếu kích thước của st không phải là 0 và s [top of st] giống với s [i], thì:
-
nếu nums [top of st]> nums [i], thì:
-
cost:=cost + nums [i]
-
-
ngược lại:
-
cost:=cost + nums [top of st]
-
phần tử pop từ st
-
đẩy tôi vào st
-
-
-
nếu không thì
-
đẩy tôi vào st
-
-
-
chi phí trả lạ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:
int solve(string s, vector<int>& nums) {
stack<int> st;
int cost = 0;
for (int i = 0; i < s.size(); ++i) {
if (st.size() && s[st.top()] == s[i]) {
if (nums[st.top()] > nums[i]) {
cost += nums[i];
} else {
cost += nums[st.top()];
st.pop();
st.push(i);
}
} else {
st.push(i);
}
}
return cost;
}
};
int solve(string s, vector<int>& nums) {
return (new Solution())->solve(s, nums);
}
main(){
vector<int> v = {2, 3, 10, 4, 6};
string s = "xxyyx";
cout << solve(s, v);
} Đầu vào
"xxyyx",{2,3,10,4,6} Đầu ra
6