黑马程序员技术交流社区

标题: 用java找出出现频率最高的，长度为四个字母的字符串 [打印本页]

---

作者: 王丽    时间: 2011-7-27 06:14
标题: 用java找出出现频率最高的，长度为四个字母的字符串
给你一个String：
typingoutandthereareprobabytyposandstuffdontexpectoutoreadthisbutifyoucanthenygoodforyouhohohomerryxmasyesimtoolazytowritearandomstringgenerator
请java找出出现频率最高的，长度为四个字母的字符串。

---

作者: 匿名    时间: 2011-7-27 10:30
[code=java]package com.string;

import java.util.ArrayList;

public class StringTest {

        /**
         * @param args
         */
        private String substring;
        private int total;

        public StringTest(String substring, int total) {
                super();
                this.substring = substring;
                this.total = total;
        }

        public String getSubstring() {
                return substring;
        }

        public void setSubstring(String substring) {
                this.substring = substring;
        }

        public int getTotal() {
                return total;
        }

        public void setTotal(int total) {
                this.total = total;
        }

        public static void main(String[] args) {
                // TODO Auto-generated method stub

                String s = "typitypitypingoutandthereareprobabytyposandstuffdontexpectoutoreadthisbutifyoucanthenygoodforyouhohohomerryxmasyesimtoolazytowritearandomstringgenerator ";
                // 拆分字符串形成子字符串队列
                ArrayList<String> arraylist = new ArrayList();
                for (int i = 0; i < s.length() - 4; i++) {
                        arraylist.add(s.substring(i, i + 4));
                }

                // 定义字符串 出现次数类的队列
                ArrayList<StringTest> slist = new ArrayList();

                // 开始查找相同的字符串，如果相同在total上加1并移除该重复出现的子字符串
                for (int i = 0; i < arraylist.size() - 2; i++) {
                        slist.add(new StringTest(arraylist.get(i), 1));
                        for (int j = i + 1; j < arraylist.size() - 1; j++) {
                                if (arraylist.get(i).equals(arraylist.get(j))) {
                                        slist.get(i).setTotal(slist.get(i).getTotal() + 1);
                                        arraylist.remove(j);
                                        j--;// 因为arraylist.get(i)已经移除这时原先的arraylist.get(j+1)会移到前面来处于第j的位置
                                                // 因此为了不漏过遍历 把j--一下
                                }
                        }
                }

                // 对子字符串出现的频率进行降序排序
                StringTest t = null;
                for (int i = 0; i < slist.size() - 1; i++) {
                        for (int j = slist.size() - 1; j > i; j--) {
                                if (slist.get(j).getTotal() > slist.get(j - 1).getTotal()) {
                                        t = slist.get(j);
                                        slist.set(j, slist.get(j - 1));
                                        slist.set(j - 1, t);
                                }
                        }
                }

                // 输出每个子窜出现的频率
                for (int i = 0; i < slist.size(); i++) {
                        System.out.println(slist.get(i).getSubstring() + "出现频率是"
                                        + slist.get(i).getTotal());
                }
        }

}[/code]

---

作者: 匿名    时间: 2011-7-27 11:27
标题: 回复 沙发 的帖子
看了一下 写的非常好 收藏了

---

作者: 崔虎    时间: 2011-7-27 14:14
我感觉还是用集合要方便一些。
题目：请用java找出出现频率最高的，长度为四个字母的字符串。
我感觉,应该这么做:
第一步，找出所有的子串。
第二步，统计每个子串的出现次数。
第三步，找出出现次数最多的那个子串。
我的理解，所谓的子串，就是存在于主串中的，n个连续的字符。比如，字符串abcd所有长度为2的子串是：ab、bc、cd 。

各位，毋庸置疑，此时需要使用Map<String,Integer>了吧? 还有，我现学现用，在咱们论坛看各位写的Map按value排序的方法。

范例1：废话少说。[code=java]package org.cxy.demo;

import java.util.*;
import java.util.Map.*;
public class SubString {
        private String str;
        private Map<String,Integer> map ;
       
        /**
         *   初始化用户指定的参数串。
         * */
        public SubString(String str){
                this.str = str;
        }
       
        /**
         *   功能：指定子串长度，取得str的所有子串，计算每个子串出现的次数。
         *   @param len 子串的长度。
         * */
        public Map<String,Integer> getSubstringByLength(int len){
                this.map = new HashMap<String,Integer>();
                for(int i=0;i<this.str.length()-len+1;i++){
                        String temp = this.str.substring(i,i+len);
                        // 若已经存在了这个子串。
                        if(map.containsKey(temp)){
                                map.put(temp, map.get(temp)+1);
                        }else{
                                map.put(temp, 1);
                        }
                }
                return map;
        }
       
        /**
         *   功能：指定子串长度，取得str的所有子串中，出现的次数最多的那个子串。
         *   @param len 子串的长度。
         * */
        public Map.Entry<String, Integer> getMaxCountByLength(int len){
                if(this.map == null){
                        // 先查询出str的所有子串。
                        this.getSubstringByLength(len);
                }
                // 您懂的。
                Set<Map.Entry<String,Integer>> set = this.map.entrySet();
                // 返回出现次数最多的那个子串。
                return Collections.max(set, new Comparator<Map.Entry<String, Integer>>(){
                                public int compare(Entry<String, Integer> a1,Entry<String, Integer> a2) {
                                        // 按子串出现的次数,从小到达排序。
                                        return a1.getValue() - a2.getValue();
                                }
                });
        }
        public static void main(String[] args){
                SubString sub = new SubString("aaaafdfefesvfefefe");
                int len = 4;
                System.out.printf("所有长度为 %d 的子串的信息如下：\n",len);
                Set<Map.Entry<String,Integer>> set = sub.getSubstringByLength(len).entrySet();
                for(Map.Entry<String, Integer> temp : set){
                  System.out.printf("子串 = %s , 出现次数 = %d\n", temp.getKey(),temp.getValue());
                }
                Map.Entry<String, Integer> entry =         sub.getMaxCountByLength(len);
                System.out.println("出现次数最多的子串：key = "+entry.getKey()+",value="+entry.getValue());
        }
}[/code]程序执行结果：[code=java]所有长度为 4 的子串的信息如下：
子串 = aafd , 出现次数 = 1
子串 = afdf , 出现次数 = 1
子串 = efef , 出现次数 = 1
子串 = efes , 出现次数 = 1
子串 = svfe , 出现次数 = 1
子串 = fesv , 出现次数 = 1
子串 = dfef , 出现次数 = 1
子串 = aaaf , 出现次数 = 1
子串 = aaaa , 出现次数 = 1
子串 = fdfe , 出现次数 = 1
子串 = fefe , 出现次数 = 3
子串 = vfef , 出现次数 = 1
子串 = esvf , 出现次数 = 1
出现次数最多的子串：key = fefe,value=3[/code]程序使用的HashMap存储数据，因此，数据的输出顺序和数据的插入顺序，是不一样的。
程序中还有一个问题，字符串“fefefe” 中，是出现了一个fefe呢，还是2个fefe呢。在上面的范例中，认为这个字符串中包含了2个fefe。
验证程序结果是否正确，也十分简单，把咱们的字符串复制到记事本内，然后把光标设置到文件的最开头，接着输入ctrl+f 。然后 ，您懂的。  记事本认为“fefefe”中只有1个“fefe” 。 其实，这个问题很好解决。 写过或学习过kmp算法的人，都懂的。
[ 本帖最后由 崔虎 于 2011-07-27  14:28 编辑 ]

---

作者: 匿名    时间: 2011-7-27 15:08
看代码：[code=java]package com.itcast.d23;

import java.util.HashMap;
import java.util.Map;

public class TestS {

        public static void main(String[] args) throws Exception {
                String str = "typingoutandthereareprobabytyposandstuffdontexpectoutoreadthisbutifyoucanthenygoodforyouhohohomerryxmasyesimtoolazytowritearandomstringgenerator";
                // String str = "typi";
                // map key保存四个字符，value保存出现的次数
                Map<String, Integer> map = new HashMap<String, Integer>();
                // 如果str只有4个字符，for循环就只遍历一次，他的条件应该是str.length() - 3
                for (int i = 0; i < str.length() - 3; i++) {
                        String subVal = str.substring(i, 4 + i);
                        boolean flag = false; // 标示一个字符是否处理过。
                        for (String key : map.keySet()) {
                                // 如果有相同的字符 value + 1 否则把字符存入map
                                if (key.equals(subVal)) {
                                        map.put(key, map.get(key) + 1);
                                        flag = true; // 字符标示为处理过
                                }
                        }
                        // 如果字符没有处理过就在这里处理
                        if (!flag) {
                                map.put(subVal, 1);
                        }
                }
                /*
                 * 排序
                 */
                Object[] strArray =  map.keySet().toArray();
                Object temp = null;
                for (int i = 0; i < strArray.length; i++) {
                        for (int j = 1 + i; j < strArray.length; j++) {
                                if (map.get(strArray[i]) < map.get(strArray[j])) {
                                        temp = strArray[i];
                                        strArray[i] = strArray[j];
                                        strArray[j] = temp;       
                                }
                        }
                }
                for (Object object : strArray) {
                        System.out.println(object + "出现的次数："+ map.get(object));
                }
               
        }
}[/code]

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2