首页 > 试题广场 > 基本字符串压缩
[编程题]基本字符串压缩

利用字符重复出现的次数,编写一个方法,实现基本的字符串压缩功能。比如,字符串“aabcccccaaa”经压缩会变成“a2b1c5a3”。若压缩后的字符串没有变短,则返回原先的字符串。

给定一个string iniString为待压缩的串(长度小于等于10000),保证串内字符均由大小写英文字母组成,返回一个string,为所求的压缩后或未变化的串。

测试样例
"aabcccccaaa"
返回:"a2b1c5a3"
"welcometonowcoderrrrr"
返回:"welcometonowcoderrrrr"
推荐
Ron头像 Ron
import java.util.*;

public class Zipper {
	public String zipString(String iniString) {
		// write code here
		if(iniString==null||iniString.trim().length()==0){
			return "";
		}
		StringBuilder strB = new StringBuilder("");
		char[] iniStr = iniString.toCharArray();
		char pre;
		pre = iniStr[0];
		int count = 1;
		for(int i = 1;i < iniStr.length; i++){
			if(pre == iniStr[i]){
				count++;
			}else{
				strB.append(pre+""+count);
				pre = iniStr[i];
				count = 1;
			}
		}
		strB.append(pre+""+count);
		if(strB.toString().length() >= iniString.length()){
			return iniString;
		}
		return strB.toString();
	}
}

编辑于 2015-10-14 14:31:45 回复(18)
class Zipper {
public:
    string zipString(string iniString) {
	string str;
	int i = 0,j = 0;
	while (i < iniString.length()){
		while (iniString[i] == iniString[j]) i++;
		str += iniString[j];
	        str += to_string(i-j);
		j = i;}
	if (iniString.length() < str.length()) return iniString;
	else return str;
    }
};

发表于 2015-09-17 18:16:15 回复(10)
import java.util.*;
//while (i < iniString.length()-1 && iniString.charAt(i+1) == iniString.charAt(i))中的代码是关键
//大家很多遇到的字符串越界关键在此。iniString.charAt(i+1) == iniString.charAt(i)与i < iniString.length()-1 顺序反过来就错了

public class Zipper {
    public String zipString(String iniString) {
          StringBuffer stringBuffer = new StringBuffer();
        for (int i = 0; i < iniString.length(); i++) {
            char temp = iniString.charAt(i);
            int count = 1;
            while (i < iniString.length()-1 && iniString.charAt(i+1) == iniString.charAt(i)) {
                count ++;
                i ++;
            }
            stringBuffer.append(temp).append(count);
        }
        return iniString.length() > stringBuffer.length() ? stringBuffer.toString() :iniString;
    }
}


编辑于 2017-03-14 21:12:17 回复(2)

python solution

主要思路:使用一个中间变量strCnt表示字符的数量,如果下一个字符与当前的字符不相等,把strCnt置为1即可。遍历完字符串,结果出就出来了。

class Zipper:
    def zipString(self, iniString):
        zipStr = ""
        strCnt = 1
        for i in range(len(iniString) - 1):
            if iniString[i + 1] == iniString[i]:
                strCnt += 1
            else:
                zipStr += iniString[i] + str(strCnt)
                strCnt = 1
        zipStr += iniString[-1] + str(strCnt)
        return zipStr if len(zipStr) < len(iniString) else iniString
编辑于 2017-10-03 17:29:41 回复(0)
//引入一个计数器k就可以了
public class Zipper {
    public String zipString(String iniString) {
       StringBuffer sb = new StringBuffer();
       int k = 1;
       for(int i = 0; i < iniString.length() - 1; i++){
           if(iniString.charAt(i) == iniString.charAt(i+1))
               k++;
           else {
               sb.append(iniString.charAt(i));
               sb.append(k);
               k = 1;
           }
           
       }
        sb.append(iniString.charAt(iniString.length() - 1));
        sb.append(k);
        if(sb.length() >= iniString.length())
            return iniString;
       return sb.toString();
    }
}

编辑于 2017-04-24 09:03:28 回复(4)
import java.util.*;

public class Zipper {
    public String zipString(String iniString) {
        char[] c = iniString.toCharArray();
        String str2 = "";
        
        for(int i=0; i<c.length-1; i++){
        	int count = 1;
        	int index = i;
        	for(int j=i+1; j<c.length; j++){
        		if(c[j] == c[i]){
        			count ++;
        			index = j;				//标记与位置i处的字符一样的最后下标
        		}else{
        			break;
        		}
        	}
        	str2 += c[i] + "" + count;		//+"" : 变为字符串
        	i = index;					//i直接跳至最后下标处,因为下个循坏前i++,所以i的实际跳转位置是index+1
        }
        return str2.length() < iniString.length() ? str2 : iniString;
    }
}

发表于 2016-07-07 20:29:57 回复(2)
class Zipper {
public:
    string zipString(string iniString) {
        string s ;
        int cnt = 0;
        for(int i = 0; i < iniString.length(); ++i){
            cnt = 1;
           while(i + 1 < iniString.length() && iniString[i] == iniString[i+1]) {
               cnt ++;
               i++;
           }
                s += iniString[i];
				s += to_string(cnt);
        }
        if(iniString.size() > s.size()) return s;
        return iniString;
    }

};

注意to_string()是c++11之后才添加到string中的,在自己的g++中编译时要加上-std=c++11
发表于 2015-09-12 10:14:20 回复(1)
import java.util.*;

public class Zipper {
    public String zipString(String iniString) {
        // write code here
        String ans="";
        int count=1;
        int i;
        for( i=0;i<iniString.length()-1;i++){
            
            if(iniString.charAt(i)==iniString.charAt(i+1)){
                count++;
            }else{
                ans+=iniString.charAt(i);
                ans+=count;
                count=1;
            }
        }
        ans+=iniString.charAt(i);
        ans+=count;
        if(ans.length()<iniString.length()){
             return ans;
        }
        return iniString;
    }
}
看到前面的好多代码写的很简洁,可是很多都存在数组越界情况,在外层循环时,i从到length-1,这样的话在比较最后肯定要取到第length-1到length这两个索引对应值的大小,会发生数组越界。
我的做法比较麻烦,只用一层while,这样一直控制下标小于 length-1,这样只能取到倒数第二个,取到的每一个都和后一个比较,(i从0到length-2,每次比较i和i+1),比较时用count记录后跳的次数,比较不一致时(i和i+1对应的不一致时),这是将第i个字符和count依次放入str。这样会出现一个问题,最后一组(如aaabbbccc中的ccc)因为外层的while阻止了最后一次(length-1到length这两个索引对应值的大小)的比较,所以没法执行最后一次的     将第i个字符和count依次放入str操作,所以在while循环之后再执行一次  将第i个字符和count依次放入str操作。

当然也可以在当前数组最后添加一个 null防止数组越界,欢迎大家指正批评
发表于 2016-09-13 00:47:01 回复(1)
 public String zipString(String iniString) {
      StringBuffer sb = new StringBuffer();
        char[] chs = iniString.toCharArray();
        int count = 1;
        for (int i = 1; i < chs.length; i++) {
            if (chs[i - 1] == chs[i]) {
                count++;
            }else{
                sb.append("" + chs[i - 1] + count);
                count = 1;
            }
            if(i==chs.length-1){
                sb.append("" + chs[i - 1] + count);
            }
        }
        return sb.toString().length()<iniString.length()?sb.toString():iniString;
    }

发表于 2015-08-29 16:02:34 回复(0)
public class Zipper {
    public String zipString(String iniString) {
        StringBuffer res = new StringBuffer();
        StringBuffer tmp = new StringBuffer(); //用来存放一组相同的字符
        
        tmp.append(iniString.charAt(0));
        for(int i=1; i<iniString.length(); i++) {
            //如果当前字符与前一个字符相同,则存入tmp中
            if(iniString.charAt(i) == iniString.charAt(i-1)) {
                tmp.append(iniString.charAt(i));
            }else { //如果当前字符与前一个字符不相同,将tmp中的首字符以及tmp长度加入res中
                res.append(tmp.charAt(0));
                res.append(tmp.length());
                tmp.setLength(0);
                tmp.append(iniString.charAt(i));
            }
        }
        if(tmp.length() != 0) { //将最后一组tmp字符值存入res中
            res.append(tmp.charAt(0));
            res.append(tmp.length());
        }
        //如果压缩后的长度变小,则返回压缩后的字符串,否则返回原字符串
        if(res.length() < iniString.length()) return res.toString();
        return iniString;
    }
}

发表于 2019-04-03 10:08:23 回复(0)
class Zipper {
public:
    string zipString(string iniString) {
        string c="";
        int n=1,j,i=0;
        while(iniString[i]!='\0')
        {
        for( j=i+1;iniString[j]!='\0';j++)
        {
            if(iniString[i]==iniString[j])n++;
            else break;
          }
            c+=iniString[i];
            c+=to_string(n);
            i=j;
            n=1;
        }
        if(iniString.size()>c.size()) return c;
        else return iniString;
    }
};

发表于 2019-03-03 23:07:58 回复(0)
很平凡的思路。pre记录上个字符,cnt为当前字符计数,ss存储压缩串,只要记得循环完再加一下压缩串就行了。
# -*- coding:utf-8 -*-
class Zipper:
    def zipString(self, iniString):
        pre = ''
        cnt = 0
        ss = ''
        for s in iniString:
            if s == pre:
                cnt += 1
            else:
                if pre:
                    ss += pre + str(cnt)
                pre = s
                cnt = 1
        ss += pre + str(cnt)
        if len(ss) < len(iniString):
            return ss
        else:
            return iniString

运行时间:60ms

占用内存:5852k


发表于 2018-09-26 15:21:48 回复(1)
public class Zipper {
    public static String zipString(String iniString) {
        String temp1=iniString+";";
        StringBuffer temp2=new StringBuffer();
        int count=1;
        for(int i=1;i<temp1.length();i++) {
           if(temp1.charAt(i)==temp1.charAt(i-1)&& i<temp1.length()-1) {
               count++;
           }else{
               temp2.append(iniString.charAt(i-1));
               temp2.append(count);
               count=1;
           }
       } 
        if(temp2.length()>=temp1.length()) {
            return iniString;
        }
            return temp2.toString();
    }
}

编辑于 2018-04-23 15:58:52 回复(0)
import java.util.*;
public class Zipper {
    public String zipString(String iniString) {
        int count = 1;
        char a = ' ';
        StringBuffer sb = new StringBuffer();
        for(int i = 1; i < iniString.length(); i++) {
            a = iniString.charAt(i-1);
            if(a == iniString.charAt(i)) {
                count++;
            }else {
                sb.append(a).append(count);
                count = 1;
            }
        }
        if(iniString.length() < sb.length()) return iniString;
        else return sb.append(a).append(count).toString();  
    }
}

发表于 2018-03-27 11:03:23 回复(0)
import java.util.*;

public class Zipper {
    public static String zipString(String iniString) {
        // write code here
        StringBuilder result = new StringBuilder();
        int count = 1;
        int i = 1;
        while (i < iniString.length()) {
            if (iniString.charAt(i - 1) == iniString.charAt(i)) {
                count++;
            } else {
                result.append(iniString.charAt(i - 1));
                result.append(count);
                count = 1;
            }
                 //最后一个字符判断不了,重新加载一次
            if (i == iniString.length() - 1) {
                result.append(iniString.charAt(i - 1));
                result.append(count);
            }
            i++;
        }
        if (result.length() > iniString.length()) {
            return iniString;
        }
        return String.valueOf(result);
    }

}

发表于 2017-11-23 17:19:50 回复(0)

public class Zipper {
    public String zipString(String iniString) {
        String mystr ="";
        char last = iniString.charAt(0);         //先存放第一个字符,循环最后用于存放最后的字符
        int count =1;       //用来存储相同字符串个数
        for(int i=1;i<iniString.length();i++){        //从字符串第二个开始,进行比较
            if(iniString.charAt(i)==last){          //相同,count+1
              count++;                                
          
            }
            else{
                mystr+=last+""+count;               //不相同,mystr用来放字符和次数
                last=iniString.charAt(i);               //将字符往后移,保存在last中
                count=1;                                      //重新将count置1
            }
        }
        String str = mystr+last+count;           
        if(str.length()>=iniString.length()){      //比较原字符和压缩后的字符长度,压缩后没变短返回原字符
            return iniString;
        }else
        return str;
    }
}
发表于 2017-09-23 18:04:37 回复(0)
//扫描一遍,边扫描边保存压缩后的字符串,最后比较和原来的长度相比有没有变短,
//决定返回压缩后的字符串或者原串。

class Zipper {
public:
	string zipString(string iniString) {
		int n = iniString.size();
		if (n == 0)
			return iniString;
		string s;
		int i = 0;
		char tmp;
		while (i<n) {
			tmp = iniString[i];
			int cnt1 = 0;
			while (i<n&&tmp == iniString[i]) {
				i++;
				cnt1++;
			}
			s += tmp;
			s += to_string(cnt1);
		}
		return ((s.size()<n) ? s : iniString);
	}
};

编辑于 2017-08-13 15:54:08 回复(0)
import java.util.*;

public class Zipper {
    public String zipString(String iniString) {
     
        StringBuffer sb = new StringBuffer();
        char[] strArr = iniString.toCharArray();
        int index = 1;
        boolean f = true;
        for (int i = 0; i < strArr.length; i++) {
        	
        	char m = strArr[i];
        	char n;
			try {
				n = strArr[i+1];
			} catch (Exception e) {
				sb.append(m+""+(index));
				if(f){
		        	return iniString;
		        }else{
		        	return sb.toString();
		        }
			}
        	if(m!=n){
        		sb.append(m+""+(index));
        		index=1;
        	}else{
        		f = false;
        		index++;
        	}
		}
        if(f){
        	return iniString;
        }else{
        	return sb.toString();
        }
       
       
    }
       
}

发表于 2017-07-20 14:32:08 回复(0)
两个列表,一个用来输出原始字符串,一个用来输出改变后的字符串; 属于暴力破解:

# -*- coding:utf-8 -*-
class Zipper:
    def zipString(self, iniString):
        # write code here
        iniString = list(iniString)
        resultlst1 = []
        resultlst2 = []
        count = 0
        lens = len(iniString)
        i = 0
        
        while i < lens:
            j = i + 1
            resultlst1.append(iniString[i])
            count += 1
            while j < lens and iniString[i] == iniString[j]:
                count += 1
                j += 1
            else:
                resultlst1.append(str(count))
                resultlst2.append(str(count))
                i = j
                count = 0
        
        
        if len(resultlst2) == lens:
            return ''.join(iniString)
            
        return ''.join(resultlst1)
            

发表于 2017-06-29 21:25:15 回复(0)
class Zipper {
public:
    string zipString(string iniString) {
        // write code here
string str;
        int len =  iniString.size();
int j=0;
while (iniString[j] != '\0'){
char ch = iniString[j];
int i=j+1;
while ((ch == iniString[i]) && (i<=len)){
i++;
str.push_back (ch);
char ch1 = i-j;
str = str + to_string(i-j);
j=i;
}
int len_str=str.size();
if (len_str<len) 
return str;
else 
return iniString;
    }
};
发表于 2017-06-27 16:37:14 回复(0)
import java.util.*;

public class Zipper {
    public String zipString(String iniString) {
        // write code here
        if (iniString == null || iniString.length() == 0)
            return "";
        
        StringBuffer sb = new StringBuffer();
        char pre;
        int count = 1;
        pre = iniString.charAt(0);
        
        for (int i = 1; i < iniString.length(); i++) {
            char now = iniString.charAt(i);
            // 如果新字符等于前一字符
            if (now == pre) {
                count++;
            } else {
                sb.append(pre);
                sb.append(count);
                pre = now;
                count = 1;
            }
        }
		// 最后一个字符在循环中没有处理
        sb.append(now);
        sb.append(count);
        // 如果未压缩,返回原字符
        if(sb.toString().length() >= iniString.length()){
            return iniString;
        }
        return sb.toString();
    }
}

发表于 2017-05-26 20:00:21 回复(0)