字串旋轉後首尾字元的最大乘積

---

在這個問題中，我們將透過多次旋轉字串來找到字串首尾字元可能的最大乘積。

樸素的方法是找到字串的所有旋轉，取首尾字元的乘積，並選擇最大乘積作為答案。

另一種方法是找到每個相鄰字元對的乘積，並選擇最大乘積。

問題陳述 - 我們給定一個包含數字字元的字串 num。我們需要找到給定字串多次左旋轉或右旋轉後首尾字元的最大乘積。

示例

輸入

num = "9834546";

輸出

72

解釋 - 我們可以將字串左旋轉 1 次。因此，字串變為 8345469，如果我們取首尾字元的乘積，則得到 72。

輸入

num = "235467";

輸出

42

解釋 - 如果我們進行 1 次右旋轉，則字串變為 723546。因此，第一個字元是 7，最後一個字元是 6。兩者的乘積為 42。

輸入

num = "11278654";

輸出

56

解釋 - 給定字串的一次旋轉是 78654112。因此，首尾字元的乘積為 56。

方法 1

在這種方法中，我們將對字串進行總共 N 次左旋轉。之後，我們將取當前旋轉的首尾字元的乘積，並跟蹤每次旋轉的最大乘積。

演算法

步驟 1 - 使用字串長度初始化 'len' 變數，使用原始字串的首字元初始化 'first' 變數，使用原始字串的尾字元初始化 'last' 變數。同時，使用首尾字元的乘積初始化 'maximum'。

步驟 2 - 開始遍歷 'num' 字串。

步驟 3 - 使用 substr() 方法將子字串左旋轉。

步驟 4 - 獲取當前旋轉的首尾數字值。

步驟 5 - 如果首尾字元的乘積大於 'maximum' 的值，則更新 'maximum' 的值。

步驟 6 - 返回 'maximum' 的值。

示例

#include <bits/stdc++.h>
using namespace std;

int getMaxProduct(string num) {
    int len = num.size();
    int first = num[0] - '0';
    int last = num[len - 1] - '0';
    // Get the product of the first and last character of the original string
    int maximum = first * last;
    // Rotate string by p rotations
    for (int p = 0; p < num.size() - 1; p++) {
        // Make left rotation by 1 unit using the substr() method
        num = num.substr(1) + num[0];
        first = num[0] - '0';
        last = num[len - 1] - '0';
        maximum = max(maximum, first * last);
    }
    return maximum;
}
int main() {
    string num = "9834546";
    cout << "The maximum product of the first and last character after rotation is - " << getMaxProduct(num);
    return 0;
}

輸出

The maximum product of the first and last character after rotation is − 72

時間複雜度 - 對給定字串進行總共 N 次旋轉，時間複雜度為 O(N*N)。

空間複雜度 - O(1)，因為我們沒有使用額外的空間。

方法 2

在這種方法中，我們將取給定字串中相鄰數字的最大乘積。

這裡的邏輯是，當我們向左旋轉字串時，字串的末尾和下一個字元會轉到字串的首位。因此，只需找到相鄰字元的最大乘積就足夠了。

演算法

步驟 1 - 使用相應的值初始化 'len'、'first'、'second' 和 'maximum'。

步驟 2 - 從第二個位置開始遍歷字串。

步驟 3 - 將當前字元放入 'first' 變數，將前一個字元放入 'last' 變數。

步驟 4 - 如果首尾字元的乘積大於 'maximum' 的值，則更新 'maximum' 變數的值。

步驟 5 - 最後返回 'maximum' 變數的值。

示例

#include <bits/stdc++.h>
using namespace std;

int getMaxProduct(string num) {
    int len = num.size();
    int first = num[0] - '0';
    int last = num[len - 1] - '0';
    // Get the product of the first and last character of the original string
    int maximum = first * last;
    for (int p = 1; p < len; p++) {
        first = num[p] - '0';
        last = num[p - 1] - '0';
        // Get the product of first and last after rotation by p.
        maximum = max(maximum, first * last);
    }
    return maximum;
}
int main() {
    string num = "9834546";
    cout << "The maximum product of the first and last character after rotation is " << getMaxProduct(num);
    return 0;
}

輸出

The maximum product of the first and last character after rotation is 72

時間複雜度 - 對所有相鄰字元進行乘積運算，時間複雜度為 O(N)。

空間複雜度 - O(1)，因為我們沒有使用額外的空間。

從時間和空間複雜度的角度來看，第二種方法更有效。有時，我們需要觀察問題解決方案，並需要根據觀察結果編寫程式碼以進一步最佳化程式碼。