笔试强训-day18_T1 NC101 压缩字符串(一)

本文主要是介绍笔试强训-day18_T1 NC101 压缩字符串(一)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、题目链接
NC101 压缩字符串(一)

二、题目描述
利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串aabcccccaaa会变为a2bc5a3。
1.如果只有一个字符，1不用写
2.字符串中只包含大小写英文字母（a至z）。

数据范围:
0<=字符串长度<=50000

要求：时间复杂度O(N）

示例1
输入：“aabcccccaaa”
返回值：“a2bc5a3”
示例2
输入：“shopeew”
返回值：“shope2w”

三、答案解析
算法原理

双指针模拟
利用栈

代码解答

//1、双指针模拟
import java.util.*;
public class Solution
{public String compressString (String param) {StringBuffer ret = new StringBuffer();char[] s = param.toCharArray();int left = 0, right = 0, n = s.length;while(left < n){while(right + 1 < n && s[right + 1] == s[right]) right++;int len = right - left + 1;ret.append(s[left]);if(len > 1){ret.append(len);}left = right + 1;right = left;}return ret.toString();}
}//2、利用栈计数
import java.util.Stack;public class Test1 {public String compressString(String param) {Stack<Character> stack = new Stack<>();int count = 0;StringBuilder stringBuilder = new StringBuilder();for (int i = 0; i < param.length(); i++) {if (stack.isEmpty() || stack.peek() == param.charAt(i)) {stack.add(param.charAt(i));count++;} else if (stack.peek() != param.charAt(i)) {stringBuilder.append(param.charAt(i - 1));if (count != 1) {stringBuilder.append(count);}count = 0;stack.add(param.charAt(i));count++;}if (i == param.length() - 1) {stringBuilder.append(param.charAt(i));if (count != 1) {stringBuilder.append(count);}}}return stringBuilder.toString();}
}