​LeetCode刷题实战604:迭代压缩字符串

共 2206字,需浏览 5分钟

 ·

2022-05-15 11:30

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 迭代压缩字符串,我们先来看题面:
https://leetcode.cn/problems/design-compressed-string-iterator/

对于一个压缩字符串,设计一个数据结构,它支持如下两种操作:next 和 hasNext。
给定的压缩字符串格式为:每个字母后面紧跟一个正整数,这个整数表示该字母在解压后的字符串里连续出现的次数。
next() - 如果压缩字符串仍然有字母未被解压,则返回下一个字母,否则返回一个空格。
hasNext() - 判断是否还有字母仍然没被解压。

注意:
请记得将你的类在 StringIterator 中 初始化 ,因为静态变量或类变量在多组测试数据中不会被自动清空。更多细节请访问 这里 。

示例:
StringIterator iterator = new StringIterator(“L1e2t1C1o1d1e1”);
iterator.next(); // 返回 ‘L’
iterator.next(); // 返回 ‘e’
iterator.next(); // 返回 ‘e’
iterator.next(); // 返回 ‘t’
iterator.next(); // 返回 ‘C’
iterator.next(); // 返回 ‘o’
iterator.next(); // 返回 ‘d’
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 ‘e’
iterator.hasNext(); // 返回 false
iterator.next(); // 返回 ’ ’


解题

https://blog.csdn.net/qq_29051413/article/details/108679703


  定义变量 ch 表示当前字符,num 表示当前字符剩余数量,ptr 遍历压缩字符串的指针。

  ch 和 num 都通过遍历压缩字符串获取;

  1、hasNext: 如果 num 为 0,且 ptr 已经跑到边界外了,于是没有下一个字符了,返回 false;

  2、next:

  2.1 先调用一次 hasNext,如果没有下一个了,返回 ’ ';

  2.2 如果有下一个,则判断 num 是否为 0,如果不为 0,则 num 减一 并返回 ch;

  2.3 如果有下一个,但 num == 0,说明得继续遍历压缩字符串,获取下一个字符和数量:

  获取下一个字符和数量的流程:

  1、ptr 所在索引即下一个字符的索引,ch = str.charAt(ptr);

  2、ptr = ptr+1 为新字符数量字符串的开头,num = num * 10 + res.charAt(ptr) - ‘0’;

  3、继续 ptr++,直到遇到的字符不是数字位置,此时 ptr 所在的索引是下一个字符的位置或者超出边界。

class StringIterator {

    private String res; // 压缩的字符串;
    private char ch = ' '; // 当前字符
    private int num = 0; // 当前字符的剩余数量
    private int ptr = 0;

    public StringIterator(String s) {
        res = s;
    }

    public char next() {
        // 没有下一个字符了
        if (!hasNext()) return ' ';
        // 当前字符数量为 0,但是还有下一个字符
        if (num == 0) {
            ch = res.charAt(ptr++); // ch 更新为新的字符,++放在变量后面,属于先用后加
            // 统计新的字符后面的数字
            while (ptr < res.length() && Character.isDigit(res.charAt(ptr))) {
                // res.charAt(ptr++) - '0' 等效于字符转数字
                num = num * 10 + res.charAt(ptr++) - '0';
            }
        }
        num--; // 返回一个,数量减一
        return ch;
    }

    public boolean hasNext() {
        return ptr != res.length() || num != 0;
    }
}


上期推文:
LeetCode1-600题汇总,希望对你有点帮助!
LeetCode刷题实战601:体育馆的人流量
LeetCode刷题实战602:好友申请 II :谁有最多的好友
LeetCode刷题实战603:连续空余座位

浏览 8
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报