[LeetCode] 1758. Minimum Changes To Make Alternating Binary String

You are given a string s consisting only of the characters '0' and '1'. In one operation, you can change any '0' to '1' or vice versa.

The string is called alternating if no two adjacent characters are equal. For example, the string "010" is alternating, while the string "0100" is not.

Return the minimum number of operations needed to make s alternating.

Example 1:

Input: s = "0100"
Output: 1
Explanation: If you change the last character to '1', s will be "0101", which is alternating.

Example 2:

Input: s = "10"
Output: 0
Explanation: s is already alternating.

Example 3:

Input: s = "1111"
Output: 2
Explanation: You need two operations to reach "0101" or "1010".

Constraints:

• 1 <= s.length <= 104
• s[i] is either '0' or '1'.

生成交替二进制字符串的最少操作数。

给你一个仅由字符 '0' 和 '1' 组成的字符串 s 。一步操作中，你可以将任一 '0' 变成 '1' ，或者将 '1' 变成 '0' 。

交替字符串 定义为：如果字符串中不存在相邻两个字符相等的情况，那么该字符串就是交替字符串。例如，字符串 "010" 是交替字符串，而字符串 "0100" 不是。

返回使 s 变成 交替字符串 所需的 最少 操作数。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-changes-to-make-alternating-binary-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题算是字符串类型的题目。我自己做的时候一开始没有想到太简洁的方法，所以分别模拟了 0101 和 1010 两种字符串，然后和 input 字符串比较，看看 diff1 小还是 diff2 小，小的那个就是最少操作数。

时间O(n)

空间O(n)

Java实现

 1 class Solution {
 2     public int minOperations(String s) {
 3         int len = s.length();
 4         char[] inputArray = s.toCharArray();
 5         char[] first = new char[len];
 6         boolean zero = true;
 7         for (int i = 0; i < len; i++) {
 8             if (zero) {
 9                 first[i] = '0';
10             } else {
11                 first[i] = '1';
12             }
13             zero = !zero;
14         }
15         
16         
17         boolean one = true;
18         char[] second = new char[len];
19         for (int i = 0; i < len; i++) {
20             if (one) {
21                 second[i] = '1';
22             } else {
23                 second[i] = '0';
24             }
25             one = !one;
26         }
27         
28         int count1 = 0, count2 = 0;
29         for (int i = 0; i < len; i++) {
30             if (inputArray[i] != first[i]) {
31                 count1++;
32             }
33             if (inputArray[i] != second[i]) {
34                 count2++;
35             }
36         }
37         return Math.min(count1, count2);
38     }
39 }

后来看了评论区的这个帖子，感觉最近还是题刷少了。他的思路是，最理想情况下，字符串应该是类似 01010101 这样的排列。在这种排列中，每个位置上的字符串与其下标 index 有如下关系

index  = 0, 1, 2, 3, 4 % 2

char   = 0, 1, 0, 1, 0

所以我们可以遍历一遍 input 字符串，看一下每个位置的下标 index % 2 之后是否等于同位置上的字符串，记录全局不同的个数 diff。注意因为字符串可以是 0101 类型，也可以是 1010 类型的，所以最后的结果是 Math.min(diff, len - diff)。

时间O(n)

空间O(1)

Java实现

 1 class Solution {
 2     public int minOperations(String s) {
 3         int len = s.length();
 4         int diff = 0;
 5         for (int i = 0; i < s.length(); i++) {
 6             if (i % 2 != s.charAt(i) - '0') {
 7                 diff++;
 8             }
 9         }
10         return Math.min(diff, len - diff);
11     }
12 }

LeetCode 题目总结