Java字符串压缩

Question

我需要创建一个方法，该方法接收一个字符串并返回一个字符串。

例如输入: AAABBBBCC

例如输出：3A4B2C

这很尴尬，我今天在面试中没能做到它（我申请的是初级职位）。现在，在家里我写了一些看起来静态的代码，即没有使用循环，但是我不知道是不是睡眠时间不够，还是其他原因，我无法想出for循环应该怎么写。这是我的代码：

public static String Comprimir(String texto){

    StringBuilder objString = new StringBuilder();

    int count;
    char match;

        count = texto.substring(texto.indexOf(texto.charAt(1)), texto.lastIndexOf(texto.charAt(1))).length()+1;
        match = texto.charAt(1);
        objString.append(count);
        objString.append(match);

    return objString.toString();
}

感谢您的帮助，我正在努力提高我的逻辑能力。

- Cristian

---

ABC 会被“压缩”成 1A1B1C 吗？还是保持为 ABC？那么 AABC -> 2ABC 呢？ - tigrang

ABC 应该返回 ABC。而 AABC 应该返回 2ABC。谢谢！ - Cristian

输入中是否总是相同的字母在一起？也就是说，输入格式是否可以为AAABBBCCCAACDD？ - Jainendra

考试没有指定。我想用更困难（更好）的方法来做 :)。 - Cristian

输入字符串可以包含数字吗？ - Esben Skov Pedersen

Answer 1

遍历字符串并记住你最后看到的内容。每次看到相同的字母时进行计数。当你看到一个新的字母时，将你已经统计过的字符数量放入输出中，并将新的字母设置为你最后看到的字母。

String input = "AAABBBBCC";

int count = 1;

char last = input.charAt(0);

StringBuilder output = new StringBuilder();

for(int i = 1; i < input.length(); i++){
    if(input.charAt(i) == last){
    count++;
    }else{
        if(count > 1){
            output.append(""+count+last);
        }else{
            output.append(last);
        }
    count = 1;
    last = input.charAt(i);
    }
}
if(count > 1){
    output.append(""+count+last);
}else{
    output.append(last);
}
System.out.println(output.toString());

- n00begon

Answer 2

你可以按照以下步骤来进行操作：

• 创建一个HashMap
• 对于每个字符，从hashmap中获取值 -如果值为null，则输入1 -否则，将该值替换为（value + 1）
• 遍历HashMap并不断拼接（Value+Key）

- Chander Shivdasani

---

我不认为这会奏效。AAABBAAA会被压缩为6A2B，而这是无法解压缩的！！！ - Chip

请确保HashMap是LinkedHashMap，因为其他实现会破坏键的顺序。 - Matthieu

你的解决方案对于像这样的字符串不起作用："AAABBBCCAA"。 - Sviatlana

Answer 3

最简单的方法是：时间复杂度为O(n)。

public static void main(String[] args) {
    String str = "AAABBBBCC";       //input String
    int length = str.length();      //length of a String

    //Created an object of a StringBuilder class        
    StringBuilder sb = new StringBuilder(); 

    int count=1;   //counter for counting number of occurances

    for(int i=0; i<length; i++){
        //if i reaches at the end then append all and break the loop
        if(i==length-1){         
            sb.append(str.charAt(i)+""+count);
            break;
        }

        //if two successive chars are equal then increase the counter
        if(str.charAt(i)==str.charAt(i+1)){   
            count++;
        }
        else{
        //else append character with its count                            
            sb.append(str.charAt(i)+""+count);
            count=1;     //reseting the counter to 1
        }
   }

    //String representation of a StringBuilder object
    System.out.println(sb.toString());   

}

- Kushal Shinde

---

非常好的简单回答。 - Sabir Khan

更加简单的方法是将计数器初始化为0，然后我们只需要一个if条件语句 - for(int i=0;i<str.length();i++) { count++; if(i==str.length()-1 || str.charAt(i)!=str.charAt(i+1)) { compressedStr.append(str.charAt(i)).append(count); count=0; } } - coder87

Answer 4

• 使用 StringBuilder (你已经这样做了)
• 定义两个变量 - previousChar 和 counter
• 循环从 0 到 str.length() - 1
• 每次获取 str.charAt(i) 并将其与存储在 previousChar 变量中的内容进行比较
• 如果前一个字符相同，则增加计数器
• 如果前一个字符不同，并且计数器为 1，则增加计数器
• 如果前一个字符不同，并且计数器 >1，则附加 counter + currentChar，重置计数器
• 比较后，将当前字符分配给 previousChar
• 处理像“第一个字符”这样的特殊情况。

类似这样。

- Bozho

Answer 5

请尝试这个方法。它可以帮助您打印通过控制台以字符串格式传递的字符计数。

import java.util.*;

public class CountCharacterArray {
   private static Scanner inp;

public static void main(String args[]) {
   inp = new Scanner(System.in);
  String  str=inp.nextLine();
   List<Character> arrlist = new ArrayList<Character>();
   for(int i=0; i<str.length();i++){
       arrlist.add(str.charAt(i));
   }
   for(int i=0; i<str.length();i++){
       int freq = Collections.frequency(arrlist, str.charAt(i));
       System.out.println("Frequency of "+ str.charAt(i)+ "  is:   "+freq); 
   }
     }    
}

- Bala

Answer 6

在count=...这一行中，lastIndexOf不会考虑连续的值，只会给出最后一次出现的位置。

例如，在字符串"ABBA"中，子字符串将是整个字符串。

另外，获取子字符串的长度等同于两个索引的差。

我真的认为你需要一个循环。这里有一个例子：

public static String compress(String text) {
    String result = "";

    int index = 0;

    while (index < text.length()) {
        char c = text.charAt(index);
        int count = count(text, index);
        if (count == 1)
            result += "" + c;
        else
            result += "" + count + c;
        index += count;
    }

    return result;
}

public static int count(String text, int index) {
    char c = text.charAt(index);
    int i = 1;
    while (index + i < text.length() && text.charAt(index + i) == c)
        i++;
    return i;
}

public static void main(String[] args) {
    String test = "AAABBCCC";
    System.out.println(compress(test));
}

- Gyscos

---

非常好，我将学习你们提供给我的所有变量。我不想再经历那种尴尬了。 - Cristian

Answer 7

如果您正在寻找基本解决方案，可以使用以下方法。迭代字符串中的每个元素，并在找到所有元素出现之后删除该字符。这样它就不会干扰下一次搜索。

public static void main(String[] args) {
    String string = "aaabbbbbaccc";
    int counter;
    String result="";
    int i=0;
    while (i<string.length()){
        counter=1;
        for (int j=i+1;j<string.length();j++){ 
            System.out.println("string length ="+string.length());  
            if (string.charAt(i) == string.charAt(j)){
                  counter++;
            }
      }
      result = result+string.charAt(i)+counter; 
      string = string.replaceAll(String.valueOf(string.charAt(i)), ""); 
    }
    System.out.println("result is = "+result);
}

输出结果为： result is = a4b5c3

- SurajSr

Answer 8

这只是另一种实现它的方式。

public static String compressor(String raw) {
        StringBuilder builder = new StringBuilder();
        int counter = 0;
        int length = raw.length();
        int j = 0;
        while (counter < length) {
            j = 0;
            while (counter + j < length && raw.charAt(counter + j) == raw.charAt(counter)) {
                j++;
            }

            if (j > 1) {
                builder.append(j);
            }
            builder.append(raw.charAt(counter));
            counter += j;
        }

        return builder.toString();
    }

- Reg

---

谢谢你伙计，希望你有美好的一天。你刚起床就帮了一个人 :) - Cristian

Answer 9

Java不是我的主要语言，我几乎从不使用它，但我想试一试 :] 甚至不确定你的作业是否需要循环，但这里有一个正则表达式方法：

 public static String compress_string(String inp) {
      String compressed = "";
      Pattern pattern = Pattern.compile("([\\w])\\1*");
      Matcher matcher = pattern.matcher(inp);
      while(matcher.find()) {
         String group = matcher.group();
         if (group.length() > 1) compressed += group.length() + "";
         compressed += group.charAt(0);
      }
      return compressed;
   }

- tigrang

Answer 10

使用Map的答案对于像aabbbccddabc这样的情况将无法工作，因为在这种情况下输出应该是a2b3c2d2a1b1c1。

在这种情况下可以使用以下实现：

private String compressString(String input) {
        String output = "";
        char[] arr = input.toCharArray();
        Map<Character, Integer> myMap = new LinkedHashMap<>();
        for (int i = 0; i < arr.length; i++) {
            if (i > 0 && arr[i] != arr[i - 1]) {
                output = output + arr[i - 1] + myMap.get(arr[i - 1]);
                myMap.put(arr[i - 1], 0);
            }
            if (myMap.containsKey(arr[i])) {
                myMap.put(arr[i], myMap.get(arr[i]) + 1);
            } else {
                myMap.put(arr[i], 1);
            }
        }

        for (Character c : myMap.keySet()) {
            if (myMap.get(c) != 0) {
                output = output + c + myMap.get(c);
            }
        }

        return output;
    }

- Abhishek_Mishra