我不知道如何开始我的任务。
我们必须制作一个运行长度编码程序,
例如,用户输入以下字符串:
aaaaPPPrrrrr
被替换为
4a3P5r
有人可以帮我开始吗?
我不知道如何开始我的任务。
我们必须制作一个运行长度编码程序,
例如,用户输入以下字符串:
aaaaPPPrrrrr
被替换为
4a3P5r
有人可以帮我开始吗?
希望这会让你开始你的任务:
游程编码背后的基本思想是连续出现的标记(如 aaaa)可以替换为较短的 4a 形式(意思是“以下四个字符是一个 'a'”)。这种类型的编码在计算机图形学的早期使用,以在存储图像时节省空间。那时,视频卡支持少量颜色,并且图像通常在图像的重要部分具有相同的颜色)
您可以在 Wikipedia 上详细阅读它
http://en.wikipedia.org/wiki/Run-length_encoding
为了对字符串进行游程编码,您可以遍历输入字符串中的字符。有一个计数器来计算你连续看到同一个角色的次数。当你看到不同的字符时,输出计数器的值,然后输出你一直在计数的字符。如果计数器的值为 1(意味着您只能连续看到其中一个字符),则跳过输出计数器。
这可以使用 StringBuilder 和一些辅助变量轻松简单地完成,以跟踪您看到的每个字母的数量。然后随心所欲地构建。
例如:
static String encode(String s) {
StringBuilder sb = new StringBuilder();
char[] word = s.toCharArray();
char current = word[0]; // We initialize to compare vs. first letter
// our helper variables
int index = 0; // tracks how far along we are
int count = 0; // how many of the same letter we've seen
for (char c : word) {
if (c == current) {
count++;
index++;
if (index == word.length)
sb.append(current + Integer.toString(count));
}
else {
sb.append(current + Integer.toString(count));
count = 1;
current = c;
index++;
}
}
return sb.toString();
}
由于这显然是一项家庭作业,因此我挑战您学习方法,而不仅仅是简单地将答案用作家庭作业的解决方案。StringBuilders 对于随手构建东西非常有用,因此在许多情况下保持运行时 O(n)。这里使用几个辅助变量来跟踪我们在迭代“索引”中的位置,另一个来计算我们看到的特定字母的数量“计数”,我们保留所有必要的信息来构建我们的编码字符串,因为我们去。
public String runLengthEncoding(String text) {
String encodedString = "";
for (int i = 0, count = 1; i < text.length(); i++) {
if (i + 1 < text.length() && text.charAt(i) == text.charAt(i + 1))
count++;
else {
encodedString = encodedString.concat(Integer.toString(count))
.concat(Character.toString(text.charAt(i)));
count = 1;
}
}
return encodedString;
}
试试这个。
试试这个:
private static String encode(String sampleInput) {
String encodedString = null;
//get the input to a character array.
// String sampleInput = "aabbcccd";
char[] charArr = sampleInput.toCharArray();
char prev=(char)0;
int counter =1;
//compare each element with its next element and
//if same increment the counter
StringBuilder sb = new StringBuilder();
for (int i = 0; i < charArr.length; i++) {
if(i+1 < charArr.length && charArr[i] == charArr[i+1]){
counter ++;
}else {
//System.out.print(counter + Character.toString(charArr[i]));
sb.append(counter + Character.toString(charArr[i]));
counter = 1;
}
}
return sb.toString();
}
这是我在java中的解决方案
public String encodingString(String s){
StringBuilder encodedString = new StringBuilder();
List<Character> listOfChars = new ArrayList<Character>();
Set<String> removeRepeated = new HashSet<String>();
//Adding characters of string to list
for(int i=0;i<s.length();i++){
listOfChars.add(s.charAt(i));
}
//Getting the occurance of each character and adding it to set to avoid repeated strings
for(char j:listOfChars){
String temp = Integer.toString(Collections.frequency(listOfChars,j))+Character.toString(j);
removeRepeated.add(temp);
}
//Constructing the encodingString.
for(String k:removeRepeated){
encodedString.append(k);
}
return encodedString.toString();
}
例如,如果输入字符串是“wwwwaaadexxxxxx”,那么函数应该返回“w4a3d1e1x6”。
源代码(Java):-
package com.algo.runlengthencoding;
public class RunlengthEncoding
{
// For example, if the input string is “wwwwaaadexxxxxx”,
// then the function should return “w4a3d1e1x6”.
public static void main(String args[]) {
String str = "aaaabbbccdddddddeeffffff";
String value = getRunLengthEncodingForGivenString(str);
System.out.println(value);
}
public static String getRunLengthEncodingForGivenString(String str) {
String value = "", compare = "";
for (int i = 0; i < str.length(); i++) {
CharSequence seq = str.charAt(i) + "";
if (compare.contains(seq))
continue;
compare = compare + str.charAt(i);
int count = 0;
for (int j = 0; j < str.length(); j++) {
if (str.charAt(i) == str.charAt(j))
count = count + 1;
}
value = value + str.charAt(i) + Integer.toString(count);
}
return value;
}
}
import java.util.Scanner;
/**
* @author jyotiv
*
*/
public class RunLengthEncoding {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println("Enter line to encode:");
Scanner s=new Scanner(System.in);
String input=s.nextLine();
int len = input.length();
int i = 0;
int noOfOccurencesForEachChar = 0;
char storeChar = input.charAt(0);
String outputString = "";
for(;i<len;i++)
{
if(i+1<len)
{
if(input.charAt(i) == input.charAt(i+1))
{
noOfOccurencesForEachChar++;
}
else
{
outputString = outputString +
Integer.toHexString(noOfOccurencesForEachChar+1) + storeChar;
noOfOccurencesForEachChar = 0;
storeChar = input.charAt(i+1);
}
}
else
{
outputString = outputString +
Integer.toHexString(noOfOccurencesForEachChar+1) + storeChar;
}
}
System.out.println("Encoded line is: " + outputString);
}
}
我试过这个。它肯定会起作用。