程序员面试金典 01.06 字符串压缩 (Java版; Easy)

雨点打透心脏的1/2处 2023-05-28 15:45 73阅读 0赞

### [welcome to my blog][] ###

## 程序员面试金典 01.06 字符串压缩 (Java版; Easy) ##

#### 题目描述 ####

字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串aabcccccaaa会变为
    a2b1c5a3。若“压缩”后的字符串没有变短，则返回原先的字符串。你可以假设字符串中只包含大小写英文字母（a至z）。
    
    示例1:
    
     输入："aabcccccaaa"
     输出："a2b1c5a3"
    示例2:
    
     输入："abbccd"
     输出："abbccd"
     解释："abbccd"压缩后为"a1b2c2d1"，比原字符串长度更长。
    提示：
    
    字符串长度在[0, 50000]范围内。

#### 第一次做; 核心:1) 双指针, 固定left, 移动right ####

/* 双指针: 固定left, 移动right; 这个思路在删除链表的重复节点中用过 */
    class Solution { 
        public String compressString(String S) { 
            if(S==null || S.length()<=1){ 
                return S;
            }
            StringBuilder sb = new StringBuilder();
            int n = S.length(), left=0, right=0, count=0;
            while(right<n){ 
                if(S.charAt(right)==S.charAt(left)){ 
                    count++;
                    right++;
                }
                else{ 
                    sb.append(S.charAt(left)).append(count);
                    count=0;
                    left=right;
                }
            }
            if(count>0){ 
                sb.append(S.charAt(left)).append(count);
            }
            return sb.length()>=n? S : sb.toString();
        }
    }

[welcome to my blog]: https://littlehaes.com

发表评论取消回复

表情：

评论列表（有 0 条评论，73人围观）

还没有评论，来说两句吧...

相关阅读

相关程序员面试金典笔记

面试题01.01 判断字符串中字符是否唯一遇到题目，先想需要考虑的情况： 1. 字符串是ASCII字符串还是Unicode字符串？假设为ASCII。 2. 首先得

水深无声/ 2023年07月13日 03:42/ 0 赞/ 101 阅读

相关程序员面试金典 01.06 字符串压缩 (Java版; Easy)

[welcome to my blog][] 程序员面试金典 01.06 字符串压缩 (Java版; Easy) 题目描述字符串压缩。利用字符重复出

雨点打透心脏的1/2处/ 2023年05月28日 15:45/ 0 赞/ 74 阅读

相关程序员的 Redis 面试金典

学好一门技术最有价值的体现就是“面试”，对于大部分人来说 “面试”是涨薪的主要途径之一，因此我们需要认真的准备面试，因为它直接决定着你今后几年内的薪资水平，所以在面试这件事上花

素颜马尾好姑娘i/ 2023年02月20日 10:40/ 0 赞/ 124 阅读

相关程序员面试金典-面试题0106-字符串压缩

程序员面试金典-面试题0106-字符串压缩题目很容易理解，将字符串按照出现的次数进行压缩。但是实现过程中遇到两个bug： 1.压缩后的字符串长度最长并不是strle

r囧r小猫/ 2022年12月31日 12:29/ 0 赞/ 252 阅读

相关 leetcode---程序员面试金典

[面试题 01.01. 判定字符是否唯一][01.01.] 1. 问题：实现一个算法，确定一个字符串 s 的所有字符是否全都不同。示例 1：

落日映苍穹つ/ 2022年12月31日 06:29/ 0 赞/ 261 阅读

相关程序员面试金典-面试题01.09-字符串轮转

程序员面试金典-面试题01.09-字符串轮转程序员面试金典这本书很金典，相信上面的题目应该不错。尝试使用c语言解决上面的题目。本篇为面试题01.09-字符串轮转，

野性酷女/ 2022年12月27日 07:40/ 0 赞/ 275 阅读

相关《程序员面试金典》.pdf

关注“Java后端技术全栈” 回复“面试”获取全套面试资料面试成功与否，取决于面试者的底蕴（气场+技能）、心态和认知及沟通技巧。其实我们只需要搞清楚一个逻辑：“面试官

灰太狼/ 2022年12月22日 09:08/ 0 赞/ 302 阅读

相关程序员面试金典-0803-魔术索引

程序员面试金典-0803-魔术索引本题为有序数组找出下标和索引值相同的最小值，主要有两个思路： 1：有序数组，势必要分治法； 2：递归处理魔术索引。

川长思鸟来/ 2022年11月17日 14:53/ 0 赞/ 269 阅读

相关程序员面试金典-0507-配对交换

程序员面试金典-0507-配对交换本题是针对bit位的交换配对交换。编写程序，交换某个整数的奇数位和偶数位，尽量使用较少的指令（也就是说，位0与位1交换，位

「爱情、让人受尽委屈。」/ 2022年10月10日 04:52/ 0 赞/ 241 阅读

相关程序员面试金典习题集锦01

这道题很简单，但是不一定可以转换到这个思路上来。 ![这里写图片描述][70] 如何使用一个数组实现三个栈？ ![这里写图片描述][70 1] 还有一道关于MinSt

我不是女神ヾ/ 2022年05月26日 11:55/ 0 赞/ 300 阅读