【LetMeFly】1758.生成交替二進制字符串的最少操作數(shù)

力扣題目鏈接：https://leetcode.cn/problems/minimum-changes-to-make-alternating-binary-string/

10年積累的成都網(wǎng)站設(shè)計、成都做網(wǎng)站經(jīng)驗，可以快速應(yīng)對客戶對網(wǎng)站的新想法和需求。提供各種問題對應(yīng)的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡(luò)服務(wù)。我雖然不認識你，你也不認識我。但先網(wǎng)站制作后付款的網(wǎng)站建設(shè)流程，更有彝良免費網(wǎng)站建設(shè)讓你可以放心的選擇與我們合作。

給你一個僅由字符'0'和'1'組成的字符串s。一步操作中，你可以將任一'0'變成'1'，或者將'1'變成'0'。

交替字符串 定義為：如果字符串中不存在相鄰兩個字符相等的情況，那么該字符串就是交替字符串。例如，字符串"010"是交替字符串，而字符串"0100"不是。

返回使s變成 交替字符串 所需的 最少 操作數(shù)。

示例 1：

輸入：s = "0100"
輸出：1
解釋：如果將最后一個字符變?yōu)?'1' ，s 就變成 "0101" ，即符合交替字符串定義。

示例 2：

輸入：s = "10"
輸出：0
解釋：s 已經(jīng)是交替字符串。

示例 3：

輸入：s = "1111"
輸出：2
解釋：需要 2 步操作得到 "0101" 或 "1010" 。

提示：

• 1<= s.length<= 104
• s[i]是'0'或'1'

方法一：模擬

要變成的字符串最多有兩種，一種是010101...，一種是101010...

假如我們要把字符串全部變成010101...需要 o n e Z e r o oneZero oneZero步，那么我們將這個字符串變成101010...就需要 s . s i z e ( ) ? o n e Z e r o s.size() - oneZero s.size()?oneZero步。

因此，我們只需要計算出字符串變成010101...需要的步數(shù)即可。

我們遍歷字符串，如果字符串不等于的下標 i % 2 i \% 2 i%2，那么“變更數(shù)量+1”

最終返回“變成010101...”和“變成101010...”所需步數(shù)中最小的一個即可。

• 時間復(fù)雜度 O ( n ) O(n) O(n)
• 空間復(fù)雜度 O ( 1 ) O(1) O(1)

AC代碼 C++

class Solution {public:
    int minOperations(string& s) {int oneZero = 0;  // 101010...
        int n = s.size();
        for (int i = 0; i< n; i++) {oneZero += (s[i] != '0' + i % 2);
        }
        return min(oneZero, n - oneZero);
    }
};

同步發(fā)文于，原創(chuàng)不易，轉(zhuǎn)載請附上原文鏈接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/128107132

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

名稱欄目：LeetCode1758.生成交替二進制字符串的最少操作數(shù)-創(chuàng)新互聯(lián)
轉(zhuǎn)載來于：http://weahome.cn/article/dgdces.html