每日一题:LeetCode:1576.替换所有问号

浏览次数 : 次 2022-01-05

博文字数统计 : 797字 | 阅读所需时长 : 3分

× 文章目录

1. 2022-01-05：LeetCode：1576.替换所有问号
1. 1.1. 1. 题目描述
2. 1.2. 2. 方法：简单模拟

每日一题：LeetCode：1576.替换所有问号
- 时间：2022-01-05
- 力扣难度：Easy
- 个人难度：Easy
- 数据结构：字符串
- 算法：数学、模拟

2022-01-05：LeetCode：1576.替换所有问号

1. 题目描述

题目：原题链接
- 给你一个仅包含小写英文字母和 ‘?’ 字符的字符串 s，请你将所有的 ‘?’ 转换为若干小写字母，使最终的字符串不包含任何连续重复的字符。
- 注意：不能修改非 ‘?’ 字符。
- 题目测试用例保证除 ‘?’ 字符之外，不存在连续重复的字符。
- 在完成所有转换（可能无需转换）后返回最终的字符串。
- 如果有多个解决方案，请返回其中任何一个。可以证明，在给定的约束条件下，答案总是存在的。
输入输出规范
- 输入：字符串s
- 输出：替换后的字符串
输入输出示例
- 输入：”???”
- 输出：”aba”

2. 方法：简单模拟

思路
- 暴力模拟，遍历整个字符串，遇到”?”时需要获取其前后两个字符并比较是否重复
- 判断时注意不要超出边界，对于首尾元素要单独判断
- 由于是否连续仅需要和前后相邻的两个字符进行比较，所以无需构建小写字母的哈希表，直接用常量空间即可
- 思考：本题对替换成的字母没有要求，任意小写字母即可，如果要求按照字典序优先替换要如何实现
复杂度分析：n是正整数的数值大小
- 时间复杂度：$O(26*n)$
- 空间复杂度：$O(1)$

题解

public String modifyString(String s) {
    if(s == null || s.length() == 0) return null;
    char[] chs = s.toCharArray();
    char ch;
    for(int i = 0; i < s.length(); i++) {
        if(chs[i] == '?') {
            ch = 'a';
            while((i - 1 >= 0 && chs[i - 1] == ch) || (i + 1 < s.length() && chs[i + 1] == ch)){
                ch++;
            }
            chs[i] =  (char) ch;

        }            
    }
    return String.valueOf(chs);
}

思考与优化
- 思考：本题对替换成的字母没有要求，任意小写字母即可，如果要求按照字典序优先替换要如何实现
- 优化：实际上，本题在替换时只需要判断三个连续的小写字母与字符串中”?”前后两个字符是否相同即可，无需用到全部26个小写字母
- 因此可以优化循环内的判断和替换的部分，内层循环只需要遍历三个连续字母
- 实际上，两种方式的真实复杂度是差不多的，因为前者的条件会使得其最多执行三次就跳出循环
复杂度分析：n是正整数的数值大小
- 时间复杂度：$O(3*n)$，因为内层只遍历三个连续字母
- 空间复杂度：$O(1)$

题解：优化版本

public String modifyString(String s) {
    if(s == null || s.length() == 0) return null;
    char[] chs = s.toCharArray();
    for(int i = 0; i < s.length(); i++) {
        for(int c = 0; c < 3 && chs[i] == '?'; c++) {
            if(i - 1 >= 0 && chs[i - 1] == c + 'a') continue;
            if(i + 1 < s.length() && chs[i + 1] == c +'a') continue;
            chs[i] = (char) (c + 'a');
        }
    }
    return String.valueOf(chs);
}

本文作者： Chthollists
发布时间： 2022-01-05 11:18:42
最后更新： 2022-01-21 23:09:05
本文标题： 每日一题:LeetCode:1576.替换所有问号
本文链接： https://chthollists.github.io/post/b870a415.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！