資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究透過交換相鄰字元將字串 S 轉換為 T 的最大點數
在這個問題中，我們將根據題設條件，找到將字串 S 轉換為 T 的最大點數。
我們可以遍歷字串 S，透過最大交換次數使字串 S 的每個字元與其在字串 T 中相同索引處的字元相同，從而獲得最大點數。
在另一種方法中，我們將根據字串的觀察結果制定一個數學公式來得到答案。
問題陳述 - 我們得到了包含字母和數字字元的字串 S 和 T。我們需要計算將字串 S 轉換為 T 的最大點數。
為了獲得 ($\mathrm{S_{p}-s_{p}+1}$) 分，我們需要交換字串 S 的 $\mathrm{S_{p}}$ 和 $\mathrm{S_{p}+1}$ 元素。
示例
輸入
S = "543"; T = "345";
輸出
4
解釋
首先，交換 (4, 3) 得到 1 分，字串將變為 534。
接下來，交換 (5, 3) 得到 2 分，字串將變為 354。
在最後一步，交換 (5, 4) 得到 1 分，字串將變為與 T 相同。
輸入
S = "1234"; T = "1234";
輸出
0
解釋 - 兩個字串已經相同，所以我們得到 0 分。
輸入
S = "179"; T = "125";
輸出
-1
解釋 - 無論如何，我們都不能透過交換字元將字串 S 轉換為 T。所以，它輸出 -1。
方法 1
在這種方法中，如果兩個字串在第 p 個索引處的字元不匹配，我們找到字串 S 中匹配字元的下一個索引。之後，我們將匹配字元與字串字元交換，將其放在第 p 個索引處，並對獲得的點數求和。透過這種方式，我們替換字串 S 的每個不匹配字元，並對其點數求和。
演算法
步驟 1 - 將 'pnt' 初始化為 0 以儲存最大點數。
步驟 2 - 開始遍歷字串。
步驟 3 - 如果字串 S 和 T 中第 p 個索引處的字元相同，則轉到下一個迭代。
步驟 4 - 否則，在字串 S 中查詢 T[p] 的下一個索引。如果找不到字元，則返回 -1，因為我們無法將字串 S 轉換為 T。
步驟 5 - 使用 while 迴圈進行迭代，直到 q > p 以交換字串字元。
步驟 6 - 將 S[q - 1] - S[q] 新增到 'pnt' 值中，這是交換 S[q - 1] 和 S[q] 字元獲得的點數。
步驟 7 - 使用 swap() 方法交換 S[q - 1] 和 S[q] 字元。同時，將 q 的值減 1。
步驟 8 - 返回 'pnt' 值。
示例
#include <iostream>
using namespace std;
int getMaximumPoint(string S, string T, int str_len) {
int pnt = 0;
for (int p = 0; p < str_len; p++) {
// When characters are the same at the same index
if (S[p] == T[p]) {
continue;
}
int q = p + 1;
// Finding the index of the next matching character
while (q < str_len && S[q] != T[p]){
q++;
}
// If no matching character is found
if (q == str_len){
return -1;
}
// Swap characters and get points
while (q > p) {
pnt += S[q - 1] - S[q];
swap(S[q], S[q - 1]);
q--;
}
}
// Return total points
return pnt;
}
int main() {
string S = "543";
string T = "345";
int str_len = S.length();
cout << "The maximum pnt we can get while converting string S to T is "
<<getMaximumPoint(S, T, str_len) << endl;
return 0;
}
輸出
The maximum pnt we can get while converting string S to T is 4
時間複雜度 - O(N*N)，用於遍歷字串並查詢匹配字元的下一個索引。
空間複雜度 - O(1)，因為我們沒有使用任何額外空間。
方法 2
在這種方法中，我們將建立一個公式來獲得問題的輸出。
當我們交換 $\mathrm{S_{p}}$ 和 $\mathrm{S_{p}+1}$ 字元時，我們獲得的點數等於 ($\mathrm{S_{p}+1-s_{p}}$)。
假設字元的初始位置是 p，交換後字元的位置是 q。
每當我們交換 $\mathrm{S_{p} + 1}$ 和 $\mathrm{S_{p}}$ 時，成本會增加 ($\mathrm{S_{p}+1-s_{p}}$)。在這裡，q 在每次交換中增加 1。
在這裡，我們可以說，每當 q 增加 1 時，點數增加 Sp，每當 q 減小 1 時，點數減小 $\mathrm{S_{p}}$。
因此，單個字元的最終成本是 $\mathrm{S_{p}(q - p)}$。
這裡，$\mathrm{S_{p} * q}$ 等於 $\mathrm{T_{p} * p}$，因為我們使字串 S 等於 T。
因此，單個字元的成本是 $\mathrm{T_{p} * p - S_{p} * p}$，其中 'p' 是特定索引。
這是獲得輸出的最終公式。
Sum($\mathrm{T_{p} * p - S_{p} * p}$)，其中 1 <= p <= 字串長度
演算法
步驟 1 - 開始遍歷字串。
步驟 2 - 將字元值與其在 T 和 S 字串中的索引相乘，然後從 S 中減去 T 值。之後，將結果值新增到 'pnt' 變數中。
步驟 3 - 返回 'pnt' 值。
示例
#include <iostream>
using namespace std;
long getMaximumPoint(string S, string T, int str_len) {
// To store the sum of the multiplication of each digit and its index
int pnt = 0;
for (int p = 0; p < str_len; p++) {
pnt += (T[p] - '0') * 1l * (p + 1) - (S[p] - '0') * 1l * (p + 1);
}
return pnt;
}
int main() {
string S = "543";
string T = "345";
int str_len = S.length();
cout << "The maximum pnt we can get while converting string S to T is "
<< getMaximumPoint(S, T, str_len) << endl;
return 0;
}
輸出
The maximum pnt we can get while converting string S to T is 4
時間複雜度 - O(N)，用於遍歷字串。
空間複雜度 - O(1)，因為我們沒有使用任何動態空間。
在第二種方法中，我們根據觀察結果建立了公式來解決問題。它也適用於包含多個相同字元的字串，因為無論元素出現多少次，我們交換另一個元素，成本都保持不變。
91 次瀏覽
