2021-11-24：把一个01字符串切成多个部分，要求每一部分的0和1比例一样，同时要求尽可能多的划分， 比如 : 01010101， 01 01 01 01 这是一种切法，0和1比例为 1 : 1， 0101 0101 也是一种切法，0和1比例为 1 : 1， 两种切法都符合要求，但是那么尽可能多的划分为第一种切法，部分数为4， 比如 : 00001111， 只有一种切法就是00001111整体作为一块，那么尽可能多的划分，部分数为1， 给定一个01字符串str，假设长度为N，要求返回一个长度为N的数组ans， 其中ans[i] = str[0...i]这个前缀串，要求每一部分的0和1比例一样，同时要求尽可能多的划分下，部分数是多少？ 输入: str = "010100001"， 输出: ans = [1, 1, 1, 2, 1, 2, 1, 1, 3]。 来自京东。

答案2021-11-24：

考点是分数表示，保证没有精度损失。 1.分数表示。 分子是0的个数，分母是1的个数。 key是分子/分母。在go语言中，用结构体表示分数。 value是个数。 2.如果整体的分数和局部的分数一样，那么整体的个数一定加1。 时间复杂度：O((N)。 空间复杂度：O(N)。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
    arr := []int{0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0}
    ret := split(arr)
    fmt.Println("两个变量表示分数：", ret)
    ret = split2(arr)
    fmt.Println("结构体表示分数：", ret)
}

type r struct {
    a int
    b int
}

func NewR(a int, b int) r {
    res := r{}
    g := gcd(a, b)
    res.a = a / g
    res.b = b / g
    return res
}

func split2(arr []int) []int {
    // key : 分子
    // value : 属于key的分母表, 每一个分母，及其 分子/分母 这个比例，多少个前缀拥有
    pre := make(map[r]int)
    n := len(arr)
    ans := make([]int, n)
    zero := 0 // 0出现的次数
    one := 0  // 1出现的次数
    for i := 0; i < n; i++ {
        if arr[i] == 0 {
            zero++
        } else {
            one++
        }
        if zero == 0 || one == 0 {
            ans[i] = i + 1
        } else { // 0和1，都有数量 -> 最简分数
            pre[NewR(zero, one)]++
            ans[i] = pre[NewR(zero, one)]
        }
    }
    return ans
}

// 001010010100...
func split(arr []int) []int {

    // key : 分子
    // value : 属于key的分母表, 每一个分母，及其 分子/分母 这个比例，多少个前缀拥有
    //HashMap<Integer, HashMap<Integer, Integer>> pre = new HashMap<>();
    pre := make(map[int]map[int]int)
    n := len(arr)
    ans := make([]int, n)
    zero := 0 // 0出现的次数
    one := 0  // 1出现的次数
    for i := 0; i < n; i++ {
        if arr[i] == 0 {
            zero++
        } else {
            one++
        }
        if zero == 0 || one == 0 {
            ans[i] = i + 1
        } else { // 0和1，都有数量 -> 最简分数
            gcd := gcd(zero, one)
            a := zero / gcd
            b := one / gcd
            // a / b 比例，之前有多少前缀拥有？ 3+1 4 5+1 6
            if _, ok := pre[a]; !ok {
                pre[a] = make(map[int]int)
            }
            if _, ok := pre[a][b]; !ok {
                pre[a][b] = 1
            } else {
                pre[a][b] = pre[a][b] + 1
            }
            ans[i] = pre[a][b]
        }
    }
    return ans
}

func gcd(m, n int) int {
    if n == 0 {
        return m
    } else {
        return gcd(n, m%n)
    }
}

执行结果如下： 图片

左神java代码