您的位置：首页 → 网页设计 → 经验技巧 → 关于百度的面试题？

关于百度的面试题？

时间：2010/1/21 16:31:00来源：本站整理作者：我要评论(0)

百度的一个面试题。“遍历一次字符串，选择出在该字符串中出现次数最多的字符及其出现次数”

比如说当前的字符串为"abc2d2e2fg2e1111bc11yh22fd2a2ai222eur张灯结彩",则我应得到的是字符2，出现次数11。

特定需求，只通过一次遍历来获取。

也就是说，只能循环字符串一次，大概看了一下，就开始入手了。于是写下了下面的代码：

 

view plaincopy to clipboardprint?

1. public static void queryMaxCountByMap(String str) throws Exception{  
2.     Map<String,Integer> map = new HashMap<String,Integer>();  
3.     if(str == null || str.length()<1) return ;  
4.     for(int i=0;i<str.length();i++){  
5.         String _tmp = String.valueOf(str.charAt(i));  
6.         if(map.containsKey(_tmp)){  
7.             int value = map.get(_tmp).intValue()+1;  
8.             map.put(_tmp,value);  
9.         }else{  
10.             map.put(_tmp,1);  
11.         }  
12.     }  
13.     String maxChar = "" ;  
14.     int maxCount = 0 ;  
15.     for(String _tmp:map.keySet()){  
16.         int _tmpCount = map.get(_tmp);  
17.         if(_tmpCount>maxCount){  
18.             maxCount = _tmpCount ;  
19.             maxChar = _tmp ;  
20.         }  
21.     }  
22.       
23.     System.out.println(maxChar);  
24.     System.out.println(maxCount);  
25.       
26. }  

public static void queryMaxCountByMap(String str) throws Exception{ Map<String,Integer> map = new HashMap<String,Integer>(); if(str == null || str.length()<1) return ; for(int i=0;i<str.length();i++){ String _tmp = String.valueOf(str.charAt(i)); if(map.containsKey(_tmp)){ int value = map.get(_tmp).intValue()+1; map.put(_tmp,value); }else{ map.put(_tmp,1); } } String maxChar = "" ; int maxCount = 0 ; for(String _tmp:map.keySet()){ int _tmpCount = map.get(_tmp); if(_tmpCount>maxCount){ maxCount = _tmpCount ; maxChar = _tmp ; } } System.out.println(maxChar); System.out.println(maxCount); }

 

通过Main方法调用，是正确的。

这时，同事看了以后说，你写的这个方法中对map还进行了一次遍历。这样也算是2次遍历了。

于是，开始纠结了。。。。。。。。。。。。。。

要在一次遍历中实现此功能，同时不借助Map等也需要进行遍历的操作。这样，就需要我在每一次的循环中，

就要获取此次循环字符在整个字符串中的出现次数。有的同事也提出了用正则表达式，我对正则表达式属于用到

的时候才去找其定义规则，还不能灵活运用。或许还有别的方法，字符串的操作，看到replaceAll的时候，感觉

豁然开朗了。于是有了下面的一个方法：

 

view plaincopy to clipboardprint?

1.     public static void queryMaxCountByFor(String str)throws Exception{  
2.         if(str == null || str.length()<1) return ;  
3.         String maxChar = "" ;  
4.         int maxCount = 0;  
5.         int len = str.length();  
6.           
7.         for(int i=0;i<len;i++){  
8.             String _tmp = String.valueOf(str.charAt(i));  
9.             str = str.replaceAll(_tmp,"");//将属于该字符的，在当前字符串中清除掉。  
10.             int _tmpCount = len - str.length();//通过前后字符串长度的比较，来确定其出现的次数。  
11.             if(_tmpCount>maxCount){  
12.                 maxChar = _tmp ;  
13.                 maxCount = _tmpCount ;  
14.             }  
15.               
16.             len = str.length();  
17.             i=0;  
18.         }  
19. /*  这种方法更好理解，好实现。缺点就是出现重复遍历的情况。  
20.         for(int i=0;i<len;i++){ 
21.             String _tmp = String.valueOf(str.charAt(i)); 
22.             String _replaceStr = str.replaceAll(_tmp,""); 
23.             int _tmpCount = len - _replaceStr.length(); 
24.             if(_tmpCount>maxCount){ 
25.                 maxChar = _tmp ; 
26.                 maxCount = _tmpCount ; 
27.             } 
28.         }        
29. */        
30.         System.out.println(maxChar);  
31.         System.out.println(maxCount);  
32.           
33.     }  

public static void queryMaxCountByFor(String str)throws Exception{ if(str == null || str.length()<1) return ; String maxChar = "" ; int maxCount = 0; int len = str.length(); for(int i=0;i<len;i++){ String _tmp = String.valueOf(str.charAt(i)); str = str.replaceAll(_tmp,"");//将属于该字符的，在当前字符串中清除掉。 int _tmpCount = len - str.length();//通过前后字符串长度的比较，来确定其出现的次数。 if(_tmpCount>maxCount){ maxChar = _tmp ; maxCount = _tmpCount ; } len = str.length(); i=0; } /* 这种方法更好理解，好实现。缺点就是出现重复遍历的情况。 for(int i=0;i<len;i++){ String _tmp = String.valueOf(str.charAt(i)); String _replaceStr = str.replaceAll(_tmp,""); int _tmpCount = len - _replaceStr.length(); if(_tmpCount>maxCount){ maxChar = _tmp ; maxCount = _tmpCount ; } } */ System.out.println(maxChar); System.out.println(maxCount); }

 

以及下面用while的一段实现，跟for循环类似。就当熟悉一下吧。

 

view plaincopy to clipboardprint?

1. public static void queryMaxCountByWith(String str)throws Exception{  
2.     String maxChar = "" ;  
3.     int maxCount = 0 ;  
4.     String tmp ;  
5.     int len = str.length();  
6.       
7.     while(len>0){  
8.         String charAt = String.valueOf(str.charAt(0));  
9.         str = str.replaceAll(charAt,"");  
10.         int newLen = str.length();  
11.         int charLen = len - newLen ;  
12.         len = newLen ;  
13.         if(maxCount<charLen){  
14.             maxChar = charAt ;  
15.             maxCount = charLen ;  
16.         }  
17.     }  
18.       
19.     System.out.println(maxChar);  
20.     System.out.println(maxCount);         
21. }  

public static void queryMaxCountByWith(String str)throws Exception{ String maxChar = "" ; int maxCount = 0 ; String tmp ; int len = str.length(); while(len>0){ String charAt = String.valueOf(str.charAt(0)); str = str.replaceAll(charAt,""); int newLen = str.length(); int charLen = len - newLen ; len = newLen ; if(maxCount<charLen){ maxChar = charAt ; maxCount = charLen ; } } System.out.println(maxChar); System.out.println(maxCount); }

 

在写完这些后，又仔细看了一下，replaceAll这个方法，内部是否也是一层遍历呢？

 public String replaceAll(String regex, String replacement) {


 	return Pattern.compile(regex).matcher(this).replaceAll(replacement);

}


纠结，俺先去学正则表达式了。







根据大家的评论，又增加了一个方法：

view plaincopy to clipboardprint?
public static void queryMaxCount(String str) throws Exception{  
    int maxCount =0;  
    String maxChar = "" ;  
    Map<String,Integer> map = new HashMap<String,Integer>();  
    if(str == null || str.length()<1) return ;  
    for(int i=0;i<str.length();i++){  
        String _tmp = String.valueOf(str.charAt(i));  
        int value = 0;  
        if(map.containsKey(_tmp)){  
            value = map.get(_tmp).intValue()+1;  
            map.put(_tmp,value);  
        }else{  
            value = 1 ;  
            map.put(_tmp,1);  
        }  
        if(value>maxCount){  
            maxCount = value ;  
            maxChar = _tmp ;  
        }  
    }  
    System.out.println(maxChar);  
    System.out.println(maxCount);         
      
}  
	public static void queryMaxCount(String str) throws Exception{
		int maxCount =0;
		String maxChar = "" ;
		Map<String,Integer> map = new HashMap<String,Integer>();
		if(str == null || str.length()<1) return ;
		for(int i=0;i<str.length();i++){
			String _tmp = String.valueOf(str.charAt(i));
			int value = 0;
			if(map.containsKey(_tmp)){
				value = map.get(_tmp).intValue()+1;
				map.put(_tmp,value);
			}else{
				value = 1 ;
				map.put(_tmp,1);
			}
			if(value>maxCount){
				maxCount = value ;
				maxChar = _tmp ;
			}
		}
		System.out.println(maxChar);
		System.out.println(maxCount);		
		
	}
 

相关阅读 .net面试题库(不断更新)及面试技巧IBM面试题试解（关于50条狗、50个人、病狗）dnf遗忘国度的古代金币怎么得dnf遗忘国度的古代金币怎么获得 dnf遗忘国度的古代金币有什么用百度打不开网页怎么办百度网盘隐藏空间在哪里百度app怎么清理内存手机百度怎么换头像

文章评论

查看所有0条评论>>

发表评论

我来说两句...

提交评论