|
锁定老帖子 主题：面试题目字符统计
精华帖 (0) :: 良好帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2009-06-02
难道它把indexOf()做成o(1)的算法？
sun工程师就牛啊 |
| 返回顶楼 | |
|
发表时间：2009-06-03
最后修改：2009-06-03
我也来献丑,效率要优于O(n的平方):
public static void testFirstNonRepeated(String str) {
if (null == str) return;
char[] base = new char[Character.MAX_VALUE];
char[] arr = str.toCharArray();
for (char item : arr) {
base[item]++;
}
int value = -1;
for (char item : arr) {
if (base[item] == 1) {
value = item;
break;
}
}
if (value == -1) {
System.out.println("没找到");
} else {
System.out.println((char)value);
}
}
|
| 返回顶楼 | |
|
发表时间：2009-06-03
最后修改：2009-06-03
shaobin0604 写道
#include <stdio.h>
#include <stdlib.h>
#define MAX_CHAR 256
int firstNonRepeatedChar(char str[], char *c) {
int i = 0;
int j = 0;
int p[MAX_CHAR];
for (j = 0; j < MAX_CHAR; j++) {
p[j] = 0;
}
while (str[i] != '\0') {
p[str[i]]++;
i++;
}
for (i = 0; str[i] != '\0'; i++) {
if (p[str[i]] == 1) {
*c = str[i];
return 1;
}
}
return 0;
}
int main() {
char str[] = "total";
char a;
if (firstNonRepeatedChar(str, &a) == 1) {
printf("%c", a);
}
return 0;
}
翻译为java代码如下：
public class firstNonRepeatedChar {
private static final int MAX_CHAR = 256;
public static void main(String[] args) {
String str = "total";
firstNoRepeatedChar(str);
}
public static int firstNoRepeatedChar(String str) {
int i = 0;
int j = 0;
int[] p = new int[MAX_CHAR];
char[] chars = str.toCharArray();
//初始化数组p，p用于保存字符出现的次数
for (j = 0; j < MAX_CHAR; j++) {
p[j] = 0;
}
//统计字符出现的次数
for(i=0;i<chars.length;i++){
p[chars[i]]++;
}
//寻找第一个统计次数为1的字符
for (i = 0; chars[i] != -1; i++) {
if (p[chars[i]] == 1) {
System.out.println(chars[i]);
return 1;
}
}
return 0;
}
}
|
| 返回顶楼 | |
|
发表时间：2009-06-03
csdn上面找的吧
|
| 返回顶楼 | |
|
发表时间：2009-06-03
最后修改：2009-06-03
yzzh9 写道 shaobin0604 写道
#include <stdio.h>
#include <stdlib.h>
#define MAX_CHAR 256
int firstNonRepeatedChar(char str[], char *c) {
int i = 0;
int j = 0;
int p[MAX_CHAR];
for (j = 0; j < MAX_CHAR; j++) {
p[j] = 0;
}
while (str[i] != '\0') {
p[str[i]]++;
i++;
}
for (i = 0; str[i] != '\0'; i++) {
if (p[str[i]] == 1) {
*c = str[i];
return 1;
}
}
return 0;
}
int main() {
char str[] = "total";
char a;
if (firstNonRepeatedChar(str, &a) == 1) {
printf("%c", a);
}
return 0;
}
翻译为java代码如下：
public class firstNonRepeatedChar {
private static final int MAX_CHAR = 256;
public static void main(String[] args) {
String str = "total";
firstNoRepeatedChar(str);
}
public static int firstNoRepeatedChar(String str) {
int i = 0;
int j = 0;
int[] p = new int[MAX_CHAR];
char[] chars = str.toCharArray();
//初始化数组p，p用于保存字符出现的次数
for (j = 0; j < MAX_CHAR; j++) {
p[j] = 0;
}
//统计字符出现的次数
for(i=0;i<chars.length;i++){
p[chars[i]]++;
}
//寻找第一个统计次数为1的字符
for (i = 0; chars[i] != -1; i++) {
if (p[chars[i]] == 1) {
System.out.println(chars[i]);
return 1;
}
}
return 0;
}
}
google_fans 写道 姜太公 写道 一次遍历，统计每个字符出现次数，保持有序。第一个出现次数为1的就是。效率O(n)
想问下o(n)是怎么做到的？ 有人问how看看下面的就知道了 yuyoo4j 已经给出符合java习惯的版本了 yuyoo4j 写道 我也来献丑,效率要优于O(n的平方):
public static void testFirstNonRepeated(String str) {
if (null == str) return;
char[] base = new char[Character.MAX_VALUE];
char[] arr = str.toCharArray();
for (char item : arr) {
base[item]++;
}
int value = -1;
for (char item : arr) {
if (base[item] == 1) {
value = item;
break;
}
}
if (value == -1) {
System.out.println("没找到");
} else {
System.out.println((char)value);
}
}
|
| 返回顶楼 | |
|
发表时间：2009-06-03
楼上的，我没注意看过他的代码，是我失误，但既然是翻译过来就应该注明一下。
|
| 返回顶楼 | |
|
发表时间：2009-06-03
最后修改：2009-06-03
用set写了一个，利用set的无重复元素的特性
String a = "19821231"; char[] array = a.toCharArray(); int b1 = 1; Set set = new HashSet(); for(int i=0;i<array.length;i++){ String s = String.valueOf(array[i]); set.add(s); if(b1==set.size()){ b1++; }else{ System.out.println("----"+s); break; } } |
| 返回顶楼 | |
|
发表时间：2009-06-03
那个C程序是用空间换时间.
实际使用中感觉还是LINKEDHASHMAP稳定些. |
| 返回顶楼 | |
|
发表时间：2009-06-03
如果题目要求用底归来作的话....
估计我要作一天. |
| 返回顶楼 | |
|
发表时间：2009-06-03
这么多的答案，我原本写这个程序是唤醒大家算法问题用面向对象的方法来做很好很强大，用c当然可以实现。
现在如果题目改为求统计重复字符串的个数，怎么做呢？希望大家接着往下面做！ |
| 返回顶楼 | |
