|
锁定老帖子 主题：面试题目
精华帖 (0) :: 良好帖 (0) :: 新手帖 (16) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2009-08-01
meiwf520 写道 evabibi 写道
public static void main(String[] args) {
String s= "sdfsddddddddddfffff,sdfsdf,";
s=s.replaceAll("[^a-zA-Z]","");
int max = 0;
int temp = 0;
String tempString = "";
for(int i = 0 ;i<s.length() ; i++ ){
tempString = s.substring(0,1);
String subs = s.replace(s.substring(0,1),"");
temp = s.length() - subs.length();
if(max<temp){
max=temp;
}
s = subs;
}
System.out.println(tempString+" max= "+max);
}
>_< 运行了下，不正确呀！ 确实不正确，tempString是获取到最后一次循环截取都字符串，max倒是 正确了。 |
| 返回顶楼 | |
|
发表时间：2009-08-02
最后修改：2009-08-02
楼主的好复杂啊
public static void main(String[] args) {
String str = "tx.tCEsfuio.RIKj.pRGClSBXm.sgSAdm.hbzbmypE.sUGJuXrb.ALABN";
Map<Character, Integer> map = new HashMap<Character, Integer>();
for (Character ch : str.replaceAll("[^A-Za-z]", "").toCharArray()) {
Integer freq = map.get(ch);
map.put(ch, freq == null ? 1 : freq + 1);
}
int max = Collections.max(map.values());
int min = Collections.min(map.values());
Set<Character> maxChars = new HashSet<Character>();
Set<Character> minChars = new HashSet<Character>();
for (Map.Entry<Character, Integer> entry : map.entrySet()) {
if (entry.getValue().equals(max)) {
maxChars.add(entry.getKey());
}
if (entry.getValue().equals(min)) {
minChars.add(entry.getKey());
}
}
System.out.println("max: " + max);
System.out.println("max character(s):" + maxChars);
System.out.println("min: " + min);
System.out.println("min character(s):" + minChars);
}
运行结果: max: 3 max character(s):[s, b, A, m] min: 1 min character(s):[f, g, d, L, o, N, l, j, I, J, h, i, K, U, r, z, y, x] |
| 返回顶楼 | |
|
发表时间：2009-08-02
是有点复杂，有很多方法。我粗略得写了下。感谢这么多朋友的拍砖。。学习
|
| 返回顶楼 | |
|
发表时间：2009-08-03
可以申请一个(112-65)大小的数组来存储吧
O(n)的时间复杂度 |
| 返回顶楼 | |
|
发表时间：2009-08-03
最后修改：2009-08-03
Jiagoo 写道 meiwf520 写道 evabibi 写道
public static void main(String[] args) {
String s= "sdfsddddddddddfffff,sdfsdf,";
s=s.replaceAll("[^a-zA-Z]","");
int max = 0;
int temp = 0;
String tempString = "";
for(int i = 0 ;i<s.length() ; i++ ){
tempString = s.substring(0,1);
String subs = s.replace(s.substring(0,1),"");
temp = s.length() - subs.length();
if(max<temp){
max=temp;
}
s = subs;
}
System.out.println(tempString+" max= "+max);
}
>_< 运行了下，不正确呀！ 确实不正确，tempString是获取到最后一次循环截取都字符串，max倒是 正确了。
public static void main(String[] args) {
String s= "sdfsddddddddddfffff,sdfsdf,";
s=s.replaceAll("[^a-zA-Z]","");
int max = 0;
int temp = 0;
String tempString = "";
String maxString = "";
for(int i = 0 ;i<s.length() ; i++ ){
tempString = s.substring(i,1);
String subs = s.replace(tempString,"");
temp = s.length() - subs.length();
if(max<temp){
max=temp;
maxString = tempString;
}
s = subs;
}
System.out.println(maxString+" max= "+max);
}
思路不错，貌似代码确实是最简洁的，但效率不是最高的，如果改写成递归，每一次调用自身时把重复的字符replace掉，那效率就高了。 |
| 返回顶楼 | |
|
发表时间：2009-08-03
最后修改：2009-08-03
首先evabibi方法本来就是错误的, 它根本没考虑字符出现次数相同的情况, 只会得出出现最多次数的最后一个字符
其次evabibi方法的效率也是很低的(当然代码的效率跟实际需求相关,如果字符串长度就100而言没必要谈效率) 在长度为10000的字符串情况下 evabibi方法需要的时间是32ms 我的方法是9ms 在长度1000000的字符串情况下 evabibi方法需要的时间是2017ms 我的方法是133ms 至于代码的简洁这个就见人见智了, 如果只求最大的出现次数的话我的方法只需要6行代码, 前面已经说了evabibi方法本来就是错误的 至于代码的阅读难度(可能跟简洁重复了), 我相信大家可以看一眼就明白我的方法在做什么, 至于evabibi的嘛, 说实话如果不是非必要我是不会想要去看理解它的意图的 欢迎大家拍砖, 我的方法不是最好的, 我相信有更好的方法, 我只是不明白为什么这样一个糟糕的方法却受到大家的追捧(而且是不正确的)
public class Ex {
public static void main(String[] args) {
String str10000 = RandomStringUtils.randomAlphanumeric(10000);
evabibi(str10000);
gordianyuan(str10000);
String str1000000 = RandomStringUtils.randomAlphanumeric(1000000);
evabibi(str1000000);
gordianyuan(str1000000);
}
private static void gordianyuan(String str) {
long startTime = System.currentTimeMillis();
Map<Character, Integer> map = new HashMap<Character, Integer>();
for (Character ch : str.toCharArray()) {
if ((ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z')) {
Integer freq = map.get(ch);
map.put(ch, freq == null ? 1 : freq + 1);
}
}
int max = Collections.max(map.values());
int min = Collections.min(map.values());
Set<Character> maxChars = new HashSet<Character>();
Set<Character> minChars = new HashSet<Character>();
for (Map.Entry<Character, Integer> entry : map.entrySet()) {
if (entry.getValue().equals(max)) {
maxChars.add(entry.getKey());
}
if (entry.getValue().equals(min)) {
minChars.add(entry.getKey());
}
}
System.out.println("max: " + max);
System.out.println("max character(s):" + maxChars);
System.out.println("min: " + min);
System.out.println("min character(s):" + minChars);
System.out.println("gordianyuan spend time: "
+ (System.currentTimeMillis() - startTime));
}
public static void evabibi(String s) {
long startTime = System.currentTimeMillis();
s = s.replaceAll("[^a-zA-Z]", "");
int max = 0;
int temp = 0;
String tempString = "";
for (int i = 0; i < s.length(); i++) {
tempString = s.substring(0, 1);
String subs = s.replace(s.substring(0, 1), "");
temp = s.length() - subs.length();
if (max < temp) {
max = temp;
}
s = subs;
}
System.out.println(tempString + " max= " + max);
System.out.println("evabibi spend time: "
+ (System.currentTimeMillis() - startTime));
}
}
|
| 返回顶楼 | |
|
发表时间：2009-08-03
\
gordianyuan 写道 首先evabibi方法本来就是错误的, 它根本没考虑字符出现次数相同的情况, 只会得出出现最多次数的最后一个字符
其次evabibi方法的效率也是很低的(当然代码的效率跟实际需求相关,如果字符串长度就100而言没必要谈效率) 在长度为10000的字符串情况下 evabibi方法需要的时间是32ms 我的方法是9ms 在长度1000000的字符串情况下 evabibi方法需要的时间是2017ms 我的方法是133ms 至于代码的简洁这个就见人见智了, 如果只求最大的出现次数的话我的方法只需要6行代码, 前面已经说了evabibi方法本来就是错误的 至于代码的阅读难度(可能跟简洁重复了), 我相信大家可以看一眼就明白我的方法在做什么, 至于evabibi的嘛, 说实话如果不是非必要我是不会想要去看理解它的意图的 欢迎大家拍砖, 我的方法不是最好的, 我相信有更好的方法, 我只是不明白为什么这样一个糟糕的方法却受到大家的追捧(而且是不正确的)
public class Ex {
public static void main(String[] args) {
String str10000 = RandomStringUtils.randomAlphanumeric(10000);
evabibi(str10000);
gordianyuan(str10000);
String str1000000 = RandomStringUtils.randomAlphanumeric(1000000);
evabibi(str1000000);
gordianyuan(str1000000);
}
private static void gordianyuan(String str) {
long startTime = System.currentTimeMillis();
Map<Character, Integer> map = new HashMap<Character, Integer>();
for (Character ch : str.toCharArray()) {
if ((ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z')) {
Integer freq = map.get(ch);
map.put(ch, freq == null ? 1 : freq + 1);
}
}
int max = Collections.max(map.values());
int min = Collections.min(map.values());
Set<Character> maxChars = new HashSet<Character>();
Set<Character> minChars = new HashSet<Character>();
for (Map.Entry<Character, Integer> entry : map.entrySet()) {
if (entry.getValue().equals(max)) {
maxChars.add(entry.getKey());
}
if (entry.getValue().equals(min)) {
minChars.add(entry.getKey());
}
}
System.out.println("max: " + max);
System.out.println("max character(s):" + maxChars);
System.out.println("min: " + min);
System.out.println("min character(s):" + minChars);
System.out.println("gordianyuan spend time: "
+ (System.currentTimeMillis() - startTime));
}
public static void evabibi(String s) {
long startTime = System.currentTimeMillis();
s = s.replaceAll("[^a-zA-Z]", "");
int max = 0;
int temp = 0;
String tempString = "";
for (int i = 0; i < s.length(); i++) {
tempString = s.substring(0, 1);
String subs = s.replace(s.substring(0, 1), "");
temp = s.length() - subs.length();
if (max < temp) {
max = temp;
}
s = subs;
}
System.out.println(tempString + " max= " + max);
System.out.println("evabibi spend time: "
+ (System.currentTimeMillis() - startTime));
}
}
去掉Min部分
import org.apache.commons.lang.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
String str10000 = RandomStringUtils.randomAlphanumeric(100000);
gordianyuan(str10000);
}
private static void gordianyuan(String str) {
long startTime = System.nanoTime();
Map<Character, Integer> map = new HashMap<Character, Integer>();
for (Character ch : str.toCharArray()) {
if ((ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z')) {
Integer freq = map.get(ch);
map.put(ch, freq == null ? 1 : freq + 1);
}
}
int max = Collections.max(map.values());
Set<Character> maxChars = new HashSet<Character>();
for (Map.Entry<Character, Integer> entry : map.entrySet()) {
if (entry.getValue().equals(max)) {
maxChars.add(entry.getKey());
}
}
System.out.println("max: " + max);
System.out.println("max character(s):" + maxChars);
System.out.println("gordianyuan spend time: "
+ (System.nanoTime() - startTime));
}
}
用数组重写
import org.apache.commons.lang.RandomStringUtils;
public class Main2 {
private static long result[] = new long[60];
private static int index = 0;
private static long max = -1;
public static void main(String[] args) {
count(RandomStringUtils.randomAlphanumeric(100000));
}
private static void count(String content) {
long startTime = System.nanoTime();
for (char temp : content.toCharArray()) {
if ((temp >= 65 && temp <= 90) || (temp >= 97 && temp <= 122)) {
temp -= 65;
result[temp]++;
}
}
for (int i = 0; i < result.length; i++) {
if (result[i] > max) {
index = i;
max = result[i];
}
}
System.out.println((char) (index + 67));
System.out.println(max);
System.out.println("KimShen spend time: " + (System.nanoTime() - startTime));
}
}
运行3次 gordianyuan spend time: 31178824 gordianyuan spend time: 31477744 gordianyuan spend time: 29229972 KimShen spend time: 8187074 KimShen spend time: 8156065 KimShen spend time: 8584890 我很自豪，我秒杀你了。 但问题是这样吗？ 你认为谁的可读性更好？ 速度固然重要，可读性更加重要。 |
| 返回顶楼 | |
|
发表时间：2009-08-03
最后修改：2009-08-03
首先我不是针对谁, 我只是谈论程序, 如果我说的有什么得罪的地方我先道歉
KimShen, 如果其他人推崇的是的你方法我没什么意见, 我是针对evabibi的方法, KimShen你的方法不错, 不过有几点可以再改善一下 1.不要使用magic number. 2.你的方法如果遇到字符串, 例如"oopp", 你的方法就是错误的, 你只能求出最大字符为'p', 程序的正确性比一切都重要. 当然这个问题改起来不难, 但这并不能成为你出错的理由. 程序的可读性我就不说了, 大家自己评价吧 先来我的方法 Map<Character, Integer> map = new HashMap<Character, Integer>();
for (Character ch : str.toCharArray()) {
if ((ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z')) {
Integer freq = map.get(ch);
map.put(ch, freq == null ? 1 : freq + 1);
}
}
int max = Collections.max(map.values());
System.out.println("max: " + max);
KimShen的方法
long result[] = new long[60];
for (char temp : content.toCharArray()) {
if ((temp >= 65 && temp <= 90) || (temp >= 97 && temp <= 122)) {
temp -= 65;
result[temp]++;
}
}
for (int i = 0; i < result.length; i++) {
if (result[i] > max) {
index = i;
}
}
System.out.println(max);
我去掉了max char(s), 为什么呢? 前面已经说了KimShen的方法是错误的. 对于效率我无话可说, 你的效率是很高的, 也完全符合需求, 但我前面已经说了, "代码的效率跟实际需求相关,如果字符串长度就100而言没必要谈效率", 但如果没有确切的性能需求, 我更喜欢我的方法, 保留了可读性, 前面讨论效率是因为 在长度1000000的字符串情况下 evabibi方法需要的时间是2017ms 我的方法是133ms 可能KimShen没有看到我最后的一句话, 欢迎大家拍砖, 我的方法不是最好的, 我相信有更好的方法, 我只是不明白为什么这样一个糟糕的方法却受到大家的追捧(而且是不正确的) KimShen 写道 \
gordianyuan 写道 首先evabibi方法本来就是错误的, 它根本没考虑字符出现次数相同的情况, 只会得出出现最多次数的最后一个字符
其次evabibi方法的效率也是很低的(当然代码的效率跟实际需求相关,如果字符串长度就100而言没必要谈效率) 在长度为10000的字符串情况下 evabibi方法需要的时间是32ms 我的方法是9ms 在长度1000000的字符串情况下 evabibi方法需要的时间是2017ms 我的方法是133ms 至于代码的简洁这个就见人见智了, 如果只求最大的出现次数的话我的方法只需要6行代码, 前面已经说了evabibi方法本来就是错误的 至于代码的阅读难度(可能跟简洁重复了), 我相信大家可以看一眼就明白我的方法在做什么, 至于evabibi的嘛, 说实话如果不是非必要我是不会想要去看理解它的意图的 欢迎大家拍砖, 我的方法不是最好的, 我相信有更好的方法, 我只是不明白为什么这样一个糟糕的方法却受到大家的追捧(而且是不正确的)
public class Ex {
public static void main(String[] args) {
String str10000 = RandomStringUtils.randomAlphanumeric(10000);
evabibi(str10000);
gordianyuan(str10000);
String str1000000 = RandomStringUtils.randomAlphanumeric(1000000);
evabibi(str1000000);
gordianyuan(str1000000);
}
private static void gordianyuan(String str) {
long startTime = System.currentTimeMillis();
Map<Character, Integer> map = new HashMap<Character, Integer>();
for (Character ch : str.toCharArray()) {
if ((ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z')) {
Integer freq = map.get(ch);
map.put(ch, freq == null ? 1 : freq + 1);
}
}
int max = Collections.max(map.values());
int min = Collections.min(map.values());
Set<Character> maxChars = new HashSet<Character>();
Set<Character> minChars = new HashSet<Character>();
for (Map.Entry<Character, Integer> entry : map.entrySet()) {
if (entry.getValue().equals(max)) {
maxChars.add(entry.getKey());
}
if (entry.getValue().equals(min)) {
minChars.add(entry.getKey());
}
}
System.out.println("max: " + max);
System.out.println("max character(s):" + maxChars);
System.out.println("min: " + min);
System.out.println("min character(s):" + minChars);
System.out.println("gordianyuan spend time: "
+ (System.currentTimeMillis() - startTime));
}
public static void evabibi(String s) {
long startTime = System.currentTimeMillis();
s = s.replaceAll("[^a-zA-Z]", "");
int max = 0;
int temp = 0;
String tempString = "";
for (int i = 0; i < s.length(); i++) {
tempString = s.substring(0, 1);
String subs = s.replace(s.substring(0, 1), "");
temp = s.length() - subs.length();
if (max < temp) {
max = temp;
}
s = subs;
}
System.out.println(tempString + " max= " + max);
System.out.println("evabibi spend time: "
+ (System.currentTimeMillis() - startTime));
}
}
去掉Min部分
import org.apache.commons.lang.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
String str10000 = RandomStringUtils.randomAlphanumeric(100000);
gordianyuan(str10000);
}
private static void gordianyuan(String str) {
long startTime = System.nanoTime();
Map<Character, Integer> map = new HashMap<Character, Integer>();
for (Character ch : str.toCharArray()) {
if ((ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z')) {
Integer freq = map.get(ch);
map.put(ch, freq == null ? 1 : freq + 1);
}
}
int max = Collections.max(map.values());
Set<Character> maxChars = new HashSet<Character>();
for (Map.Entry<Character, Integer> entry : map.entrySet()) {
if (entry.getValue().equals(max)) {
maxChars.add(entry.getKey());
}
}
System.out.println("max: " + max);
System.out.println("max character(s):" + maxChars);
System.out.println("gordianyuan spend time: "
+ (System.nanoTime() - startTime));
}
}
用数组重写
import org.apache.commons.lang.RandomStringUtils;
public class Main2 {
private static long result[] = new long[60];
private static int index = 0;
private static long max = -1;
public static void main(String[] args) {
count(RandomStringUtils.randomAlphanumeric(100000));
}
private static void count(String content) {
long startTime = System.nanoTime();
for (char temp : content.toCharArray()) {
if ((temp >= 65 && temp <= 90) || (temp >= 97 && temp <= 122)) {
temp -= 65;
result[temp]++;
}
}
for (int i = 0; i < result.length; i++) {
if (result[i] > max) {
index = i;
max = result[i];
}
}
System.out.println((char) (index + 67));
System.out.println(max);
System.out.println("KimShen spend time: " + (System.nanoTime() - startTime));
}
}
运行3次 gordianyuan spend time: 31178824 gordianyuan spend time: 31477744 gordianyuan spend time: 29229972 KimShen spend time: 8187074 KimShen spend time: 8156065 KimShen spend time: 8584890 我很自豪，我秒杀你了。 但问题是这样吗？ 你认为谁的可读性更好？ 速度固然重要，可读性更加重要。 |
| 返回顶楼 | |
|
发表时间：2009-08-04
这个是我的感觉还可以楼主不妨看下能实现你说的
/** * 判断并打出输入的字符串中 出现最多的字符和数量 * @param ch */ public void NumMaxChar(String ch) { Map<String, Integer> sum = new HashMap<String, Integer>(); Pattern pattern = Pattern.compile("[a-zA-Z]"); for (int i = 0; i < ch.length(); i++) { char num = ch.charAt(i); String su = String.valueOf(num); Matcher matcher = pattern.matcher(su); boolean b = matcher.matches(); if (b) { int fo = 0; if (sum.get(su) != null) { fo = sum.get(su); } if (fo == 0) { sum.put(su, 1); } else { fo = fo+1; sum.put(su, fo); } } } List<Map.Entry<String, Integer>> list = new ArrayList<Map.Entry<String, Integer>>( sum.entrySet()); String key=""; int max=0; for (int i = 0; i < list.size(); i++) { //String id=list.get(i).toString(); int ok=max-list.get(i).getValue(); if(ok<0){ key=list.get(i).getKey(); max=list.get(i).getValue(); } //System.out.println(id); //System.out.println("最大的字母为:"+key+"它的值为"+max); } System.out.println("出现最多的字母为:"+key+"----出现次数为:"+max); } |
| 返回顶楼 | |
|
发表时间：2009-08-04
先定义一个对象，如下：
MaxCount.java
package yeku;
public class MaxCount {
private String appearChar;
private int appearCount;
public MaxCount(){
this.appearCount = 0;
}
public String getAppearChar() {
return appearChar;
}
public void setAppearChar(String appearChar) {
this.appearChar = appearChar;
}
public int getAppearCount() {
return appearCount;
}
public void setAppearCount(int appearCount) {
this.appearCount = appearCount;
}
}
Main所在Class定义两个私有方法： private static boolean LookupList(List<MaxCount> cList, char c) {
boolean flag = false;
String $c = String.valueOf(c);
MaxCount maxCount = null;
for (int i = 0; i < cList.size(); i++) {
maxCount = cList.get(i);
if ($c.equals(maxCount.getAppearChar())) {
flag = true;
maxCount = null;
break;
} else {
maxCount = null;
continue;
}
}
return flag;
}
private static void getMaxCountByBean(String s) {
if (null != s && !"".equals(s)) {
@SuppressWarnings("unused")
List<MaxCount> cList = new ArrayList<MaxCount>();
String maxAppearString = "";
int maxAppearCount = 0;
char[] sCh = s.toCharArray();
for (char c : sCh) {
if ((c >= 65 && c <= 90) || (c >= 97 && c <= 122)) {
if (LookupList(cList, c)) {
for (int i = 0; i < cList.size(); i++) {
MaxCount maxCount = cList.get(i);
String $c = String.valueOf(c);
if ($c.equals(maxCount.getAppearChar())) {
cList.get(i).setAppearCount(
maxCount.getAppearCount() + 1);
}
}
} else {
MaxCount mc = new MaxCount();
mc.setAppearChar(String.valueOf(c));
mc.setAppearCount(1);
cList.add(mc);
}
}
}
for (MaxCount maxCount : cList) {
if (maxCount.getAppearCount() > maxAppearCount) {
maxAppearString = maxCount.getAppearChar();
maxAppearCount = maxCount.getAppearCount();
}
}
System.out.println("出现次数最多的字符为：" + maxAppearString);
System.out.println("该字符出现的次数为：" + maxAppearCount);
}
}
然后在main函数中调用就可以了： public static void main(String[] args) throws Exception{
getMaxCountByBean("UUBSfsdgdqweqweasdasdgfdacxzasddddeqwewqeq");
}
貌似我把简单的问题搞得很复杂了，但这确实是我第一眼看到的看到这个题目时的思路，可能是做Web应用做太多的原因吧，思维被格式化了 
|
| 返回顶楼 | |
