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> 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代码
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)