日期:2014-05-20  浏览次数:20612 次

字符串相关算法题。求最优算法。
如何找出一个字符串中出现字符最多的,可能有多个出现最多的字符。
如何找出一个字符串中出现最多的前三个字符。
如果有三个字符出现次数超过字符串长度的1/4如何找出它们。



------解决方案--------------------
Java code

String str = "aglakjsflajfla;sfdjalsfjal;sjfdlasjfdljsafljasljflasfj";
char [] strArray = str.toCharArray();
int [] rs = new int[strArray.length * 2];

int index = 0;
for (int i = 0; i < strArray.length; i++)
{
    char tmp1 = strArray[i];
    if (c == 0)
    {
        continue;
    }
    rs[index++] = tmp1;
    rs[index] = 1;
    for (int j = i + 1; j < strArray.length; j++)
    {
        char tmp2 = strArray[j];
        if (tmp2 == 0)
        {
            continue;
        }
        if (tmp1 == tmp2)
        {
            strArray[j] = 0;
            rs[index]++;
        }
    }
    index++;
}

int max1 = 0;
int max2 = 0;
int max3 = 0;
int thePos1 = 0;
int thePos2 = 0;
int thePos3 = 0;
for (int i = 0; i < index; i += 2)
{
    if (rs[i] > max1)
    {
        max1 = rs[i];
        thePos1 = i;
    }
}
rs[thePos1] = -max1;
for (int i = 0; i < index; i += 2)
{
    if (rs[i] > max2)
    {
        max2 = rs[i];
        thePos2 = i;
    }
}
rs[thePos2] = -max2;
for (int i = 0; i < index; i += 2)
{
    if (rs[i] > max3)
    {
        max3 = rs[i];
        thePos3 = i;
    }
}
System.out.println("No1. " + (char)rs[thePos1 - 1] + ":" + max1);
System.out.println("No2. " + (char)rs[thePos2 - 1] + ":" + max2);
System.out.println("No3. " + (char)rs[thePos3 - 1] + ":" + max3);

------解决方案--------------------
String str = "aglakjsflajfla;sfdjalsfjal;sjfdlasjfdljsafljasljflasfj";
char[] strArray = str.toCharArray();

int[] charCount = new int[1000];
for(int i = 0; i < strArray.length; i++)
{
int value = (int)strArray[i];
charCount[value] += 1;
}

for(int i = 0; i < strArray.length; i++)
{
int value = (int)strArray[i];
System.out.print(strArray[i]);
System.out.print(":");
System.out.println(charCount[value]);
}

基本原理如下:遍历字符数组strArray,将字符转换成整数,如A就是65?97?。
然后用这样一个整数作为下标,将该字符出现的次数记录在整形数组charCount中,charCount[65]就是A出现的次数了。
和前面提到的hashtable原理差不多
------解决方案--------------------
唉....我也玩玩.....
import java.util.Comparator;
import java.util.TreeMap;
import java.util.TreeSet;

class Parent implements Comparator<String>{

@Override
public int compare(String o1, String o2) {
if(o1.equals(o2)){
return 0;
}else if(Integer.parseInt(o1.substring(0,o1.length()-1))>Integer.parseInt(o2.substring(0,o2.length()-1))){
return 1;
}
return -1;
}

}
public class Child {

public static void main(String[] args) {
int count;
String[] st;
String s = "shldg./asm'aoaayaaaypwy3u2.......0373902...tSk'al'f,askr[auirp0au2q6";
TreeSet<String> set = new TreeSet<String>(new Parent());
TreeMap<Character,Integer> map = new TreeMap<Character,Integer>();
for(char c:s.toCharArray()){
if(map.get(c) == null){
map.put(c, 1);
}else{
count = map.get(c)+1;
map.put(c, count);
}
}
for(Character c:map.keySet()){
set.add(""+map.get(c)+c);
}
st = set.toArray(new String[0]);
count = 0;
System.out.print("出现最多的字符:"+st[st.length-1].charAt(st[st.length-1].length()-1));
for(int i = st.length-2;i>=0;i--){
if(st[i].charAt(0) == st[i+1].charAt(0)){
System.out.print(" "+st[i].charAt(1));
}else{
break;
}
}
System.out.println();