資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++程式：查詢移除連續重複字元的最小成本？
假設我們有一個包含小寫字母的字串，並且我們還有一個包含非負值的列表，稱為成本，字串和列表具有相同的長度。我們可以刪除字元 s[i] 並花費 costs[i] 的成本，然後 s[i] 和 costs[i] 都將被移除。我們必須找到刪除所有連續重複字元的最小成本。
因此，如果輸入類似於 s = "xxyyx" nums = [2, 3, 10, 4, 6]，則輸出將為 6，因為我們可以刪除 s[0] 和 s[3]，總成本為 2 + 4 = 6。
要解決此問題，我們將遵循以下步驟
定義一個棧 st
cost := 0
for 初始化 i := 0，當 i < s 的大小，更新（i 增加 1），執行
如果 st 的大小不為 0 且 st 的頂部元素與 s[i] 相同，則
如果 st 的頂部元素 > nums[i]，則
cost := cost + nums[i]
否則
cost := cost + st 的頂部元素
從 st 中彈出元素
將 i 推入 st
否則
將 i 推入 st
返回 cost
讓我們檢視以下實現以更好地理解
示例
#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);
}輸入
"xxyyx",{2,3,10,4,6}輸出
6
更新於： 2020年11月10日
415 次檢視
廣告