LWC 56:443. String Compression

LWC 56:443. String Compression

传送门:443. String Compression

Problem:

Given an array of characters, compress it in-place. The length after compression must always be smaller than or equal to the original array. Every element of the array should be a character (not int) of length 1. After you are done modifying the input array in-place, return the new length of the array.

Example 1:

Input: [“a”,”a”,”b”,”b”,”c”,”c”,”c”] Output: Return 6, and the first 6 characters of the input array should be: [“a”,”2”,”b”,”2”,”c”,”3”] Explanation: “aa” is replaced by “a2”. “bb” is replaced by “b2”. “ccc” is replaced by “c3”.

Example 2:

Input: [“a”] Output: Return 1, and the first 1 characters of the input array should be: [“a”] Explanation: Nothing is replaced.

Example 3:

Input: [“a”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”] Output: Return 4, and the first 4 characters of the input array should be: [“a”,”b”,”1”,”2”]. Explanation: Since the character “a” does not repeat, it is not compressed. “bbbbbbbbbbbb” is replaced by “b12”. Notice each digit has it’s own entry in the array.

Note:

All characters have an ASCII value in [35, 126].

1 <= len(chars) <= 1000.

思路: 非常暴力,按顺序计数即可,遇到不同重新归零,记录上一回合信息。

代码如下:

    public int compress(char[] chars) {
        int n = chars.length;

        if (n == 0) return 0;
        StringBuilder sb = new StringBuilder();

        char p = chars[0];
        int cnt = 1;
        for (int i = 1; i < n; ++i) {
            if (chars[i] == p) {
                cnt ++;
            }
            else {
                if (cnt == 1) {
                    sb.append(p);
                }
                else {
                    sb.append(p + "" + cnt);
                }
                cnt = 1;
            }
            p = chars[i];
        }

        if (cnt == 1) {
            sb.append(p);
        }
        else {
            sb.append(p + "" + cnt);
        }

        for (int i = 0; i < sb.length(); ++i) {
            chars[i] = sb.charAt(i);
        }

        return sb.length();
    }

优化一下:

    public int compress(char[] chars) {
        int n = chars.length;

        if (n == 0) return 0;

        char p = chars[0];
        int cnt = 1;
        int tot = 0;

        for (int i = 1; i < n; ++i) {
            if (chars[i] == p) {
                cnt ++;
            }
            else {
                if (cnt == 1) {
                    chars[tot++] = p;
                }
                else {
                    chars[tot++] = p;
                    String num = String.valueOf(cnt);
                    for (int j = 0; j < num.length(); ++j) {
                        chars[tot++] = num.charAt(j);
                    }
                }
                cnt = 1;
            }
            p = chars[i];
        }

        if (cnt == 1) {
            chars[tot++] = p;
        }
        else {
            chars[tot++] = p;
            String num = String.valueOf(cnt);
            for (int j = 0; j < num.length(); ++j) {
                chars[tot++] = num.charAt(j);
            }
        }

        return tot;
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏我的博客

Objective-C基础知识

1.标示符:字母、下划线、美元符号和数字组成,字母和下划线美元符号开头,区分大小写 2.代码区存放代码,数据区存放静态变量和字符串常量,栈存放局部变量,堆存放...

1883
来自专栏C/C++基础

C++11委托构造函数

委托构造函数(Delegating Constructor)由C++11引入,是对C++构造函数的改进,允许构造函数通过初始化列表调用同一个类的其他构造函数,目...

811
来自专栏牛肉圆粉不加葱

(3) - Scala case class那些你不知道的知识

除了在模式匹配中使用之外,unapply 方法可以让你结构 case class 来提取它的字段,如:

761
来自专栏JetpropelledSnake

Python面试题之Python中的类和实例

类,在学习面向对象我们可以把类当成一种规范,这个思想就我个人的体会,感觉很重要,除了封装的功能外,类作为一种规范,我们自己可以定制的规范,从这个角度来看,在以后...

792
来自专栏Hongten

java开发_""和null的区别

1342
来自专栏大闲人柴毛毛

稳扎稳打JS——this

this的值是在运行时确定的 JS中的this究竟代表什么,这是在程序运行时根据上下文环境确定,可以分为以下几种情况。 1. 全局作用域中的this 在全局作...

3795
来自专栏wym

运算符重载(超详细)

C++中预定义的运算符的操作对象只能是基本数据类型。但实际上,对于许多用户自定义类型(例如类),也需要类似的运算操作。这时就必须在C++中重新定义这些运算符,赋...

852
来自专栏GreenLeaves

JavaScript之数组学习

在JavaScript中,数组用关键字Array来声明。声明数组的同时还可以指定数组初始元素的大小,也就是数组的长度;下面代码定义了一个数组长度为6的数组; v...

19910
来自专栏GreenLeaves

auguements实参对象的数组化

<!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>Ti...

19310
来自专栏静默虚空的博客

[Java 基础]方法

方法的定义 Java方法是语句的集合,它们在一起执行一个功能。 方法是解决一类问题的步骤的有序组合 方法包含于类或对象中 方法在程序中被创建,在其他地方被引用 ...

1867

扫码关注云+社区