1737 - 满足三条件之一需改变的最少字符数 - 枚举 - 贪心

LightningBilly · 2021 年1 月 27 日 06:08

欢迎关注更多精彩
关注我，学习常用算法与数据结构，一题多解，降维打击。

[toc]

题目描述

[1737] 满足三条件之一需改变的最少字符数

力扣

给你两个字符串 a 和 b ，二者均由小写字母组成。一步操作中，你可以将 a 或 b 中的任一字符改变为任一小写字母。

操作的最终目标是满足下列三个条件之一：

a 中的每个字母在字母表中严格小于 b 中的每个字母。
b 中的每个字母在字母表中严格小于 a 中的每个字母。
a 和 b 都由同一个字母组成。
返回达成目标所需的最少操作数。

示例 1：

输入：a = “aba”, b = “caa”
输出：2
解释：满足每个条件的最佳方案分别是：

将 b 变为 “ccc”，2 次操作，满足 a 中的每个字母都小于 b 中的每个字母；
将 a 变为 “bbb” 并将 b 变为 “aaa”，3 次操作，满足 b 中的每个字母都小于 a 中的每个字母；
将 a 变为 “aaa” 并将 b 变为 “aaa”，2 次操作，满足 a 和 b 由同一个字母组成。
最佳的方案只需要 2 次操作（满足条件 1 或者条件 3）。
示例 2：

输入：a = “dabadd”, b = “cda”
输出：3
解释：满足条件 1 的最佳方案是将 b 变为 “eee” 。

提示：

1 <= a.length, b.length <= 105
a 和 b 只由小写字母组成

题目剖析&信息挖掘

此题主要用枚举思想，将复杂问题简化，再利用贪心思想求解。

赛中没有想到枚举，只想着直接求出最优解，要考虑的情况复杂。

给了一个启发是以后遇到范围型的题目最优范围是固定的，模板小的情况下可以尝试枚举思路。

解题思路

方法一枚举+贪心

分析

分成2类讨论，一类是全部变成相同的
二类是有一个串变成大的，另一个变成小的
枚举思想
一类来说最终的字母肯定是已经出现过的一个，可以贪心直接求得，也可以使用枚举。
二类，枚举一个中间值，使得一个都小于等于这个中间值，另一个大于这个中间值。
复杂度26*O(n)

思路

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func getCnt(a string) []int {
	cnt := make([]int, 200)
	for _, c := range a {
		cnt[c]++
	}
	return cnt
}

// 贪心求解变成同一个字母的代价
func sameCost(cnta []int, cntb []int) int {
	
}

// 以mid为中点，使得cnta<=mid<cntb
func diffCost(cntoa []int, cntob []int, mid int32) int {
	
}

/*
分成2类讨论，一类是全部变成相同的
二类是有一个串变成大的，另一个变成小的
枚举思想
一类来说可以直接求得
二类，枚举一个中间值，使得一个都小于等于这个中间值，另一个大于这个中间值。
复杂度26*O(n)
 */
func minCharacters(a string, b string) int {
	cnta := getCnt(a)
	cntb := getCnt(b)

	best := sameCost(cnta, cntb)
	for c :='a';c<'z';c++ { // mid = z时没有答案所以不用枚举
		
	}
	return best
}

注意

mid = z时不可能成立
题目中说的相同字母是指2个串都用同一个字母

知识点

枚举
贪心

复杂度

时间复杂度：O(n)
空间复杂度：O(n)

代码实现

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func getCnt(a string) []int {
	cnt := make([]int, 200)
	for _, c := range a {
		cnt[c]++
	}
	return cnt
}

// 贪心求解变成同一个字母的代价
func sameCost(cnta []int, cntb []int) int {
	sum := 0 // 总数
	maxCost := 0 // 存储数量最多的字母总数

	for i, v := range cnta {
		sum += v+cntb[i]
		maxCost = max(maxCost, v+cntb[i])
	}

	return sum - maxCost // 都往数量最多的字母转化为最优答案
}

// 以mid为中点，使得cnta<=mid<cntb
func diffCost(cntoa []int, cntob []int, mid int32) int {
	sum:=0

	// 把cntoa>mid的字母变成<=mid
	for c:=mid+1; c<='z';c++ {
		sum += cntoa[c]
	}

	// 把cntob <= mid的字母变成>mid
	for c:=mid; c>='a';c-- {
		sum += cntob[c]
	}

	return sum
}

/*
分成2类讨论，一类是全部变成相同的
二类是有一个串变成大的，另一个变成小的
枚举思想
一类来说可以直接求得
二类，枚举一个中间值，使得一个都小于等于这个中间值，另一个大于这个中间值。
复杂度26*O(n)
 */
func minCharacters(a string, b string) int {
	cnta := getCnt(a)
	cntb := getCnt(b)

	best := sameCost(cnta, cntb)
	for c :='a';c<'z';c++ { // mid = z时没有答案所以不用枚举
		best = min(best, diffCost(cnta, cntb, c))
		best = min(best, diffCost(cntb, cnta, c))
	}
	return best
}