压缩字符串(一)

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param param string字符串 
     * @return string字符串
     */
    public String compressString (String param) {
        // write code here
        char[] cs = param.toCharArray();
        StringBuilder res = new StringBuilder();
        int count = 1;
        for(int i = 0; i < cs.length-1; i++){
            if(cs[i] == cs[i+1]){
                count++;
            }else{
                res.append(cs[i]);
                if(count > 1) res.append(count);
                count = 1;
            }
        }
        // 判断最后的字符
        res.append(cs[cs.length-1]);
        if(count > 1) res.append(count);
        return res.toString();
    }
}

#include <stdio.h>
char* compressString(char* param ) {
    int i=0,n=1,j=0;
    char* out=param;
    for (i=0;i<strlen(param);i++)
    {
        if(param[i]==param[i+1])
            {n+=1;}
        else{
            if(n==1){
                out[j]=param[i];
                j+=1;
            }
            else{
                out[j]=param[i];
                out[j+1]='0'+n;
                j+=2;//因为最后j=j+2,所以最后拷贝的时候申请j个字符大小的内存
            }
            n=1;
        }
    }
    char *res=(char*)malloc(j*sizeof(char));
    strncpy(res,out,j);
    return res;
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param param string字符串
     * @return string字符串
     */
    public String compressString (String param) {
        // write code here
        StringBuilder sb = new StringBuilder();
        char arr[] = param.toCharArray();

        int temp = 1;//定义临时变量temp
        for (int i = 0; i < arr.length; i++) {
            if (i + 1 < arr.length && arr[i + 1] == arr[i]) {
                //后一个和当前相等时并且需要满足i+1不能溢出,temp+1
                temp++;
            } else {//不满足上述条件后判断temp,大于1直接加在后边,否则不加temp
                if (temp > 1) {
                    sb.append(arr[i]).append(temp);
                    temp = 1;//还原temp的值
                } else {
                    sb.append(arr[i]);
                }
            }
        }
        return sb.toString();
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param param string字符串
     * @return string字符串
     */
    public String compressString (String param) {
        // write code here
        char[] c = param.toCharArray();
        if(c.length < 2){
            return param;
        }
        StringBuilder sb = new StringBuilder();
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        for (int i = 0; i < c.length; i++) {
            if (map.isEmpty()) {
                map.put(c[i], 1);
            } else if (map.get(c[i]) == null) {
                sb.append(c[i - 1]);
                if (map.get(c[i - 1]) > 1) {
                    sb.append(map.get(c[i - 1]));
                }
                map.clear();
                map.put(c[i], 1);
            } else {
                map.put(c[i], map.get(c[i]) + 1);
            }
        }
        sb.append(c[c.length - 1]);
        if (map.get(c[c.length - 1]) > 1) {
            sb.append(map.get(c[c.length - 1]));
        }
        return sb.toString();
    }
}

双指针

用i和j维护一个相同字符的区间[i, j)（左闭右开区间），然后它们的差值就是字符的个数。

用j遍历字符串，i始终指向区间的下一个字符。首先用x保存第一个字符，然后用while循环找到右边界j。如果字符个数是1，只向答案字符串中加入字符，否则加入字符和数字。

注意while (x == param[++j])是前置++，因为i是这个区间的第一个字符，j应该从它的下一个开始。由于是左闭右开区间，所以j-i不用+1就能表示区间中的字符个数。

代码

class Solution {
public:
    string compressString(string param) {
        string s;
        int n = param.size();
        int i = 0, j = 0;
        while (j < n)
        {
            char x = param[i];
            while (x == param[++j]);
            if (j - i == 1) s += x;
            else if (j - i > 1) s += x, s += to_string(j - i);
            i = j;
        }
        return s;
    }
};

• 时间复杂度：。
• 空间复杂度：。

 char [] chars = param.toCharArray();
        String s = "";
        for (int i = 0; i < param.length(); i++) {
            int num = 1;
            int j = i;
            while (j < param.length() - 1 && chars[j] == chars[j + 1]) {
                ++num;
                j++;
            }
            i = j;
            s = s + chars[i];
            if (num != 1) {
                s = s + String.valueOf(num);
            }

        }
        return s;

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param param string字符串 
     * @return string字符串
     */
    public String compressString (String param) {
        // write code here
        StringBuilder sb = new StringBuilder();
        int start = 0;
        int end = 0;
        while(end < param.length()) {
            if(start == end) {
                sb.append(param.charAt(start));
                end++;
            }
            else {
                if(param.charAt(end) == param.charAt(start)) {
                    end++;
                }
                if((end >= param.length()) || (param.charAt(end) != param.charAt(start)) ) {
                    if(end - start != 1) sb.append(Integer.valueOf(end - start));
                    start = end;
                }
            }
        }
        return sb.toString();
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param param string字符串 
     * @return string字符串
     */
    public String compressString (String param) {
        if (param.length() <= 1) {
            return param;
        }
        int left = 0;
        int right = 0;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < param.length(); i++) {
            if (param.charAt(left) == param.charAt(right)) {
                right++;
            } else {
                sb.append(param.charAt(left));
                if (right - left != 1) {
                    sb.append(right - left);
                }
                left = right;
                right++;
            }
        }
        sb.append(param.charAt(left));
        if (right - left != 1) {
            sb.append(right-left);
        }
        return sb.toString();
            
        
        
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param param string字符串 
     * @return string字符串
     */
    public String compressString (String param) {
        // write code here
        char[] str_list = param.toCharArray();
        // 新建一个拼接字符串
        StringBuilder sb = new StringBuilder();
        if(str_list.length==0)return sb.toString();
        // point是数组下标
        int point = 0;
        // num是对用下表的数字出现多少次
        int num = 1;
        while(point<str_list.length-1){
            // 统计下标和出现此处
            if(str_list[point] == str_list[point+1]){
                point++;
                num++;
                // 如果只出现1次则不拼接1
            }else if(str_list[point] != str_list[point+1] && num == 1){
                sb.append(str_list[point]);
                point++;
                num=1;
                // 如果出现多次，则拼接相应个数
            }else if(str_list[point] != str_list[point+1] && num != 1){
                sb.append(str_list[point]).append(num);
                point++;
                num=1;
            }
        }
        // 追加最后一个字母
        if(num ==1){
            sb.append(str_list[str_list.length-1]);
        }else{
             sb.append(str_list[str_list.length-1]).append(num);
        }
       
        return sb.toString();
    }
}

package main
import _"fmt"
import "strconv"
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param param string字符串 
 * @return string字符串
*/
func compressString( param string ) string {
    if len(param)==0{
        return ""
    }
    ans:=""
    pre:=param[0]
    cnt:=1
    for i:=1;i<len(param);i++{
        if param[i]==pre{
            cnt++
        }else{
            ans+=string(pre)
            if cnt>1{
                ans+=strconv.Itoa(cnt)
            }
            pre=param[i]
            cnt=1
        }
    }
    ans+=string(pre)
    if cnt>1{
        ans+=strconv.Itoa(cnt)
    }
    return ans
}

public class CompressString {
	public String compressString(String param) {
		// write code here
		if (param == null || param.length() == 0) {
			return "";
		}
		String returnString = "";
		char[] chars = param.toCharArray();
		for (int i = 0; i < chars.length; i++) {
			char temp = chars[i];
			int count = 1;
			int nextIndex = 0;
			for (int j = i + 1; j < chars.length; j++) {
				if (temp == chars[j]) {
					count++;
					if (j == chars.length - 1) {
						nextIndex = chars.length;
					}
					continue;
				} else {
					nextIndex = j - 1;
					break;
				}
			}
			if (count == 1) {
				returnString += String.valueOf(temp);
			} else {
				returnString += (String.valueOf(temp) + count);
				
			}
			if (nextIndex != 0 && nextIndex != chars.length - 1) {
				i = nextIndex;
			}
		}
		return returnString;
	}
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param param string字符串
     * @return string字符串
     */
    public String compressString (String param) {
        // write code here
        if (param.equals("")) return "";
        StringBuffer sb = new StringBuffer();
        int i = 0, j = 0;
        for (; j < param.length(); j ++) {
            if (param.charAt(j) == param.charAt(i)) {
                continue;
            } else {
                sb.append(param.charAt(i));
                if (j - i != 1) {
                    sb.append(j - i);
                }
                i = j;
            }
        }
        sb.append(param.charAt(i));
        if (j - i != 1) {
            sb.append(j - i);
        }
        return sb.toString();
    }
}

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param param string字符串 
     * @return string字符串
     */
    string compressString(string param) {
        // write code here
        int n = param.length();
        string str = "";
        int num = 1;
        str += param[0];
        for(int i=1; i<n; i++)
        {
            if(param[i] != param[i-1])
            {
                if(num==1)
                    str += param[i];
                else
                {
                    stack<int> stc;
                    while(num)
                    {
                        stc.push(num % 10);
                        num = num / 10;
                    }
                    while(!stc.empty())
                    {
                        int val = stc.top();
                        stc.pop();
                        str += val + '0';
                    }
//                     str+=num + '0';
                    num=1;
                    str+= param[i];
                }
            }
            else
                num++;
        }
        if(num > 1)
        {
            stack<int> stc;
            while(num)
            {
                stc.push(num % 10);
                num = num / 10;
            }
            while(!stc.empty())
            {
                int val = stc.top();
                stc.pop();
                str += val + '0';
            }
        }
        return str;
    }
};