Implement a method to perform basic string compression using the counts of repeated characters. For example, the string aabcccccaaa would become a2blc5a3. If the “compressed” string would not become smaller than the original string, your method should return
the original string.
思路:
基本上处理字符串的问题都不好用String,主要是出于效率考虑,而且String在递归传值时也不好用。
所以一律用StringBuilder或者StringBuffer。
思路很简单,就是每个字符和它的前一个比较,同时维护一个count变量,记录重复了多少次。
假如不让用StringBuilder,则可以用一个char array来代替StringBuilder
package Arrays_Strings;
public class S1_5 {
// 计算压缩过后的字符串长度,若是比没压过的还大,则果然返回没压过的
public static int countCompression(String str) {
if(str==null || str.isEmpty()) {
return 0;
}
char last = str.charAt(0);
int size = 0; // compress后的字符长度
int count = 1; // 有多少个重复字符
for(int i=1; i<str.length(); i++) {
if(str.charAt(i) == last) { // 与之前字符相同
count++;
} else{ // 与之前字符不同
last = str.charAt(i);
// 1为字符长度,然后还要加上count的字符串表示长度
size += 1 + String.valueOf(count).length();
count = 1; // 重置count为1
}
}
size += 1 + String.valueOf(count).length();
return size;
}
// 直接用String操作不好
public static String compressBad(String str) {
int size = countCompression(str);
if(str.length() <= size) {
return str;
}
String mystr = "";
char last = str.charAt(0);
int count = 1;
for(int i=1; i<str.length(); i++) {
if(str.charAt(i) == last) {
count++;
} else{
mystr += last + "" + count;
last = str.charAt(i);
count = 1;
}
}
return mystr + last + count;
}
// 应该改用StringBuilder操作
public static String compressBetter(String str) {
int size = countCompression(str);
if(str.length() <= size) {
return str;
}
StringBuilder sb = new StringBuilder();
char last = str.charAt(0);
int count = 1;
for(int i=1; i<str.length(); i++) {
if(str.charAt(i) == last) {
count++;
} else{
sb.append(last);
sb.append(count);
last = str.charAt(i);
count = 1;
}
}
sb.append(last);
sb.append(count);
return sb.toString();
}
// 不用StringBuilder而用array的方法
public static String compressAlternate(String str) {
int size = countCompression(str);
if(str.length() <= size) {
return str;
}
char[] array = new char[size];
int index = 0;
char last = str.charAt(0);
int count = 1;
for(int i=1; i<str.length(); i++) {
if(str.charAt(i) == last) {
count++;
} else{
index = setChar(array, last, index, count);
last = str.charAt(i);
count = 1;
}
}
index = setChar(array, last, index, count);
return String.valueOf(array);
}
// index:标记当前位置,把字符c和有几个c(count)添加到array数组中
// 最后返回更新过的index
public static int setChar(char[] array, char c, int index, int count) {
array[index] = c;
index++;
char[] cnt = String.valueOf(count).toCharArray();
for(char x : cnt) {
array[index] = x;
index++;
}
return index;
}
public static void main(String[] args) {
String str = "abbccccccde";
int c = countCompression(str);
System.out.println(c);
String str2 = compressAlternate(str);
String t = compressBetter(str);
System.out.println("Compression: " + t);
System.out.println("Old String (len = " + str.length() + "): " + str);
System.out.println("New String (len = " + str2.length() + "): " + str2);
System.out.println("Potential Compression: " + c);
}
}
分享到:
相关推荐
Arduino项目开发 Control_Arrays_Arrays.pdf Arduino项目开发 Control_Arrays_Arrays.pdf Arduino项目开发 Control_Arrays_Arrays.pdf Arduino项目开发 Control_Arrays_Arrays.pdf Arduino项目开发 Control_Arrays_...
07_Multidimensional_Arrays_pdf_
Electronically Scanned Arrays_MATLAB Modeling and Simulation 英文高清书籍
day08_17_Arrays练习_字符串倒序排列
Calculate the mutual impedance in an infinite phased arrays.
alx-low_level_programming0x00-hello_world 使用gcc编译C程序以贝蒂风格编写...0x05-pointers_arrays_strings 指针数组弦乐0x06-pointers_arrays_strings 更多的指针将一个字符串数组。0x07-pointers_arrays_strings
0x06-pointers_arrays_strings:将piointer,数组和字符串用于make string函数。 0x07-pointers_arrays_strings:甚至更多的指针,数组和字符串。 0x08-递归:递归。 0x09-static_libraries静态库。 0x0A-argc
Ayush_Arrays_objects_closures:Ayush_Arrays_objects_closures
A basic c# example code for beginners 2.
multiserial arduino file zip
multidimensional array is an antenna array which have a minimum of 2 DIMENSIONAL
Range-Angle Dependent Transmit Beampattern synthesis for linear frequency diverse arrays
关于动态数组的底层实现,采用动态扩容包括增添改查操作
combining scheme for adaptive antenna arrays to combat noise, fading, and to a certain degree, cochannel interference. However, it requires estimation of the spatial signature (i.e., the channel gain ...
设计一矩形栅格的相控阵天线方向图及其仿真;其中包含两个文件(分别是main_antenna_gain和 antenna_gain),其中antenna是调用函数,主要计算方向图增益
This is done through smart-antenna arrays and the associated adaptive beam-forming algorithms. Smart-antenna systems provide opportunities for higher system capacity and improved quality of service ...
国外经典论文,ieee会员论文关于波导缝隙天线理论的详细论证
matlab开发的阵列天线设计工具,可以设计均匀/非均匀、一维/多维等阵列,可画出方向图
利用粒子群算法对直线阵的权系数进行优化,这里只是对相位进行加权,但是程序有很好的宽展功能
编写程序,可以实现m*n矩阵和n*p矩阵相乘。m,n,p均小于10,矩阵元素为整数。 分析: 首先我们可以根据题意写出函数头。可以定为void MatrixMutiply(int m,int n,int p,long lMatrix1[MAX][MAX],long lMatrix2[MAX]...