2022-03-25：给定一个长度为 N 的字符串 S，由字符‘a‘和‘b‘组成，空隙由 ‘?‘ 表示。你的任务是用a字符或b字符替换每个间隙，替换完成后想

原创

福大大架构师每日一题

发布于 2022-03-25 20:51:24

1.2K0

发布于 2022-03-25 20:51:24

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2022-03-25：给定一个长度为 N 的字符串 S，由字符'a'和'b'组成，空隙由 '?' 表示。

你的任务是用a字符或b字符替换每个间隙，

替换完成后想让连续出现同一种字符的最长子串尽可能短。

例如，S = "aa??bbb"，

如果将"??"替换为"aa" ，即"aaaabbb"，则由相等字符组成的最长子串长度为4。

如果将"??"替换为"ba" ，即"aababbb"，则由相等字符组成的最长子串长度为3。

那么方案二是更好的结果，返回3。

S的长度 <= 10^6。

来自CMU入学申请考试。

答案2022-03-25：

根据S的长度 <= 10^6推断，复杂度是O(N)才能过。

1.左 == 右，中间问号长度是奇数。a?a变成aba。

2.左 == 右，中间问号长度是偶数。a????a变成abaaba。

3.左 != 右，中间问号长度是偶数。a????b变成ababab。

4.左 != 右，中间问号长度是大于1的奇数。a???b变成abaab或者aabab。

5.左 != 右，中间问号长度等于1。a?b的问号根据ab数量决定，谁小成全谁。相等的时候，成全左边。

先根据1,2,3,4过滤问号，再根据5过滤问号。

时间复杂度：O(N)。

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

package main

import (
	"fmt"
)

func main() {
	s := "aa??bbb"
	ret := minContinuous2(s)
	fmt.Println(ret)
}

func minContinuous2(s string) int {
	if len(s) == 0 {
		return 0
	}
	str := []byte(s)
	N := len(str)
	L := 0
	R := -1
	for i := 0; i < N; i++ {
		if str[i] != '?' {
			set(str, L, R)
			L = i + 1
			R = i
		} else {
			R++
		}
	}
	set(str, L, R)
	// 下面的for循环，是单独处理，条件5）
	for i := 1; i < N; i++ {
		if str[i] == '?' {
			// baaaa?bbbbbbbba
			for L = i - 1; L >= 0 && str[L] == str[i-1]; L-- {

			}
			for R = i + 1; R < N && str[R] == str[i+1]; R++ {

			}
			L = i - L - 1
			R = R - i - 1
			if L <= R {
				str[i] = str[i-1]
			} else {
				str[i] = str[i+1]
			}
		}
	}
	return maxLen(str)
}

// L...R 都是？
// 如果这一坨问号，满足1）2）3）4）中的一种，就填好
// 如果满足5），就不填！a?b
func set(str []byte, L, R int) {
	N := len(str)
	if L > R {
		return
	}
	if L == 0 && R == N-1 {
		for i := 0; i < N; i++ {
			str[i] = twoSelectOne((i&1) == 0, 'a', 'b')
		}
	} else if L == 0 {
		for i := R; i >= 0; i-- {
			str[i] = twoSelectOne(str[i+1] == 'a', 'b', 'a')
		}
	} else if R == N-1 {
		for i := L; i < len(str); i++ {
			str[i] = twoSelectOne(str[i-1] == 'a', 'b', 'a')
		}
	} else {
		if str[L-1] == str[R+1] || L != R {
			for ; L <= R; L, R = L+1, R-1 {
				str[L] = twoSelectOne(str[L-1] == 'a', 'b', 'a')
				str[R] = twoSelectOne(str[R+1] == 'a', 'b', 'a')
			}
		}
	}
}

func maxLen(str []byte) int {
	ans := 1
	cur := 1
	for i := 1; i < len(str); i++ {
		if str[i] != str[i-1] {
			ans = getMax(ans, cur)
			cur = 1
		} else {
			cur++
		}
	}
	ans = getMax(ans, cur)
	return ans
}

func getMax(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}
func twoSelectOne(c bool, a, b byte) byte {
	if c {
		return a
	} else {
		return b
	}
}

执行结果如下：

左神java代码

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

java

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

java

登录后参与评论

0 条评论

热度