Skip to content

Latest commit

 

History

History
171 lines (139 loc) · 4.35 KB

README.md

File metadata and controls

171 lines (139 loc) · 4.35 KB
Raw
comments difficulty edit_url rating source tags
true
中等
1600
第 241 场周赛 Q2
贪心
字符串

1864. 构成交替字符串需要的最小交换次数

English Version

题目描述

给你一个二进制字符串 s ，现需要将其转化为一个 交替字符串 。请你计算并返回转化所需的 最小 字符交换次数，如果无法完成转化，返回 -1 。

交替字符串 是指：相邻字符之间不存在相等情况的字符串。例如，字符串 "010" 和 "1010" 属于交替字符串，但 "0100" 不是。

任意两个字符都可以进行交换，不必相邻 。

 

示例 1：

输入：s = "111000"
输出：1
解释：交换位置 1 和 4："111000" -> "101010" ，字符串变为交替字符串。

示例 2：

输入：s = "010"
输出：0
解释：字符串已经是交替字符串了，不需要交换。

示例 3：

输入：s = "1110"
输出：-1

 

提示：

  • 1 <= s.length <= 1000
  • s[i] 的值为 '0' 或 '1'

解法

方法一

Python3

class Solution:
    def minSwaps(self, s: str) -> int:
        s0n0 = s0n1 = s1n0 = s1n1 = 0
        for i in range(len(s)):
            if (i & 1) == 0:
                if s[i] != '0':
                    s0n0 += 1
                else:
                    s1n1 += 1
            else:
                if s[i] != '0':
                    s1n0 += 1
                else:
                    s0n1 += 1
        if s0n0 != s0n1 and s1n0 != s1n1:
            return -1
        if s0n0 != s0n1:
            return s1n0
        if s1n0 != s1n1:
            return s0n0
        return min(s0n0, s1n0)

Java

class Solution {
    public int minSwaps(String s) {
        int s0n0 = 0, s0n1 = 0;
        int s1n0 = 0, s1n1 = 0;
        for (int i = 0; i < s.length(); ++i) {
            if ((i & 1) == 0) {
                if (s.charAt(i) != '0') {
                    s0n0 += 1;
                } else {
                    s1n1 += 1;
                }
            } else {
                if (s.charAt(i) != '0') {
                    s1n0 += 1;
                } else {
                    s0n1 += 1;
                }
            }
        }
        if (s0n0 != s0n1 && s1n0 != s1n1) {
            return -1;
        }
        if (s0n0 != s0n1) {
            return s1n0;
        }
        if (s1n0 != s1n1) {
            return s0n0;
        }
        return Math.min(s0n0, s1n0);
    }
}

JavaScript

/**
 * @param {string} s
 * @return {number}
 */
var minSwaps = function (s) {
    let n = s.length;
    let n1 = [...s].reduce((a, c) => parseInt(c) + a, 0);
    let n0 = n - n1;
    let count = Infinity;
    let half = n / 2;
    // 101、1010
    if (n1 == Math.ceil(half) && n0 == Math.floor(half)) {
        let cur = 0;
        for (let i = 0; i < n; i++) {
            if (i % 2 == 0 && s.charAt(i) != '1') cur++;
        }
        count = Math.min(count, cur);
    }
    // 010、0101
    if (n0 == Math.ceil(half) && n1 == Math.floor(half)) {
        let cur = 0;
        for (let i = 0; i < n; i++) {
            if (i % 2 == 0 && s.charAt(i) != '0') cur++;
        }
        count = Math.min(count, cur);
    }
    return count == Infinity ? -1 : count;
};