leetcode 1737 解题思路及注释code 贪心

浅浅的花香味﹌ 2023-01-10 14:54 114阅读 0赞

## 备忘录 ##

最近在刷leetcode，好不容易搞懂一道题，还是希望记录下来，以防之后忘记，也希望可以分享给大家思路。

## [题目要求][Link 1] ##

> 给你两个字符串 a 和 b ，二者均由小写字母组成。一步操作中，你可以将 a 或 b 中的 任一字符 改变为 任一小写字母 。  
> 操作的最终目标是满足下列三个条件 之一 ：
> 
>  *  a 中的 每个字母 在字母表中 严格小于 b 中的 每个字母 。
>  *  b 中的 每个字母 在字母表中 严格小于 a 中的 每个字母 。
>  *  a 和 b 都 由 同一个 字母组成。  
>     返回达成目标所需的 最少 操作数  
>     ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lrZjE3Mw_size_16_color_FFFFFF_t_70]

## 题目注意点 ##

>  *  给的三个条件，条件一和条件二注意是都大于或者都小于，而不是对应字母。
>  *  条件三也是都，即全部都等于同一个字母，如 a=‘aaa’, b='bbb’这不属于该种情况，可以归为条件一了。（而 a=‘aaa’， b='aaaa’则属于该种情形）

## 解题思路 ##

>  *  注：为了不混淆，下文中str1和str2即原题目中的a,b字符串
>  *  看了看题解，没有使用什么太难的算法，只是比较抽象
>  *  统计每个字符串字母表中每个字母个数（这个比较有技巧性，可以直接使用ASCII映射到0-25的数组中，当然也可以用字典哈希表存储，但是毕竟这样占得空间大一些，由于字母表的规律性，没有什么必要）
>  *  循环判断以每个字母为边界，左端与右端的字符个数即需要修改的个数（这一点是解这道题的关键）。条件一转换为这种思路即为，对于字符串str1，字母表中比如判断到b这一字母节点，绝对小的情况即为b右端字符全部转换为a或者b（这不重要，关键是str2右端的字符总数）；同理对于字符串str2也是相同的思路，即必须所有字符都转化为大于b字符，需要变的字符即为str2中a的个数加b的个数。当然条件二与条件一类似。（这里需要注意的是z这个字符没必要判断，注意到都是不包含临界点的，如例子中的b。这样看来，在题目的要求下，没有比z大的字符，当然判断也可以这样多做了无用功，因为程序找不到这样的情况。当然str1,str2都是字母z也是可以的，这就条件三种的一种情况。）
>  *  条件三，即str1，str2中全部的不是当前某字母的个数。
>  *  这样取三者最小值即可。
>  *  还需要注意的一点是，有的同学直接把最小值置为很大的数，如float(“inf”)无限大的数，但是本着“量才适用”不浪费的原则，可以将最小值置为str1和str2字符串长度之和。

## python3代码即注释 ##

class Solution:
        def minCharacters(self, a: str, b: str) -> int:
            len_a, len_b = len(a), len(b)
            ta = [0 for _ in range(26)]
            tb = [0 for _ in range(26)]
            aASCII = ord('a')  # 97
            for char in a:
                ta[ord(char) - aASCII] += 1
    
            for char in b:
                tb[ord(char) - aASCII] += 1
    
            sa, sb = 0, 0
            ans = len_a + len_b
    
            # a > b
            for i in range(25):  # 不考虑z
                sa += ta[i]
                sb += tb[i]
                ans = min(ans, len_a - sa + sb)  # a > b
                ans = min(ans, len_b - sb + sa)  # b > a
                ans = min(ans, len_b + len_a - ta[i] - tb[i])  # a == b
    
            ans = min(ans, len_a + len_b - ta[-1] - tb[-1])  # 考虑z
    
            return ans
    
    
    if __name__ == '__main__':
        s = Solution()
    
        a0, b0 = "dabadd", "cda"
        a1, b1 = "aaa", "cda"
        a2, b2 = "vvv", "cda"
        a3, b3 = "acv", "cda"
        a4, b4 = "abc", "def"
    
        for i in range(5):
            a = eval('a%s' % i)
            b = eval('b%s' % i)
    
            print(s.minCharacters(a, b))

[Link 1]: https://leetcode-cn.com/problems/change-minimum-characters-to-satisfy-one-of-three-conditions/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lrZjE3Mw_size_16_color_FFFFFF_t_70]: /images/20221119/8ecfff4d248243bb911bedf6c9de8788.png