|
锁定老帖子 主题：面试题目字符统计
精华帖 (0) :: 良好帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2009-06-02
最后修改：2009-06-02
shaquan6776 写道 抛出异常的爱 写道 cy729215495 写道 linkedmap,学习了！
高手果然就是高手！ 如果我要对字符出现的次数按照从大到小的次序排序各位的方法就很不好扩展了！ 如果只是要找出最大的.... 我知道的有一种是正则但非常的难以理解.....朋友写出后看了一天都没想明白 把正则贴出来，让大家学习学习。 var regx = /(.)\1+/g;
var toMatch = "aaaAAbbbcCCCddddddEEEEEEEEEEffffffffff";
var arrMatch = toMatch.match(regx);
var charLength = 0;
var charIndex =0;
for(var i =0;i< arrMatch.length;i++){
var currentCharLength = arrMatch[i].split("").length;
if(currentCharLength > charLength){
charLength = currentCharLength; charIndex=i;
}
}
alert(arrMatch[charIndex]);
|
| 返回顶楼 | |
|
发表时间：2009-06-02
google_fans 写道 ywlqi 写道 抛出异常的爱 写道 被同事ＢＳ了
public static void main(String arg[]){
String test = "tatleae";
char[] array = test.toCharArray();
for(char tmp : array){
if(test.indexOf(tmp)==test.lastIndexOf(tmp)){
System.out.println(tmp);
break;
}
}
}我喜欢这个实现，同时看出我还差得很远啊  方便是方便，效率呢？ indexOf()和lastIndexOf()的实现里面均包含一条FOR语句,加上外面的FOR语句.因此这个实现复杂度是N平方.不符合出题要求. 前面使用LINKEDHASHMAP实现从时间复杂度上讲是满足出题要求的. |
| 返回顶楼 | |
|
发表时间：2009-06-02
抛出异常的爱 写道 shaquan6776 写道 抛出异常的爱 写道 cy729215495 写道 linkedmap,学习了！
高手果然就是高手！ 如果我要对字符出现的次数按照从大到小的次序排序各位的方法就很不好扩展了！ 如果只是要找出最大的.... 我知道的有一种是正则但非常的难以理解.....朋友写出后看了一天都没想明白 把正则贴出来，让大家学习学习。 var regx = /(.)\1+/g;
var toMatch = "aaaAAbbbcCCCddddddEEEEEEEEEEffffffffff";
var arrMatch = toMatch.match(regx);
var charLength = 0;
var charIndex =0;
for(var i =0;i< arrMatch.length;i++){
var currentCharLength = arrMatch[i].split("").length;
if(currentCharLength > charLength){
charLength = currentCharLength; charIndex=i;
}
}
alert(arrMatch[charIndex]);这个方法只对连续重复的有用. |
| 返回顶楼 | |
|
发表时间：2009-06-02
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;
}
不符合题意:题目要求找第一个不重复的字符,这个实现是找最小的. |
| 返回顶楼 | |
|
发表时间：2009-06-02
case0079 写道 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;
}
不符合题意:题目要求找第一个不重复的字符,这个实现是找最小的. 这里找出的就是第一个不重复的字符，而且个人认为效率较高，也较简单。 如果是找最小频率分词，那可以考虑用hash算法。 |
| 返回顶楼 | |
|
发表时间：2009-06-02
li = "aaaAAbbbcCCCddddddEEEEEEEEEEffffffffff" print([enum for enum in li if li.count(enum)==1].pop()) |
| 返回顶楼 | |
|
发表时间：2009-06-02
google_fans 写道 case0079 写道 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;
}
不符合题意:题目要求找第一个不重复的字符,这个实现是找最小的. 这里找出的就是第一个不重复的字符，而且个人认为效率较高，也较简单。 如果是找最小频率分词，那可以考虑用hash算法。 int p[MAX_CHAR]是记录各个字符的出现次数.但没有维护字符出现的顺序. |
| 返回顶楼 | |
|
发表时间：2009-06-02
要维护顺序干嘛，str里面有顺序。好好看下代码哈
|
| 返回顶楼 | |
|
发表时间：2009-06-02
仔细看了下,确实是比较高效的方法.估计出题者想要的答案就是这个了.用LINKEDHASHMAP可能不太像笔试题目.
|
| 返回顶楼 | |
|
发表时间：2009-06-02
最后修改：2009-06-02
google_fans 写道 ywlqi 写道 抛出异常的爱 写道 被同事ＢＳ了
public static void main(String arg[]){
String test = "tatleae";
char[] array = test.toCharArray();
for(char tmp : array){
if(test.indexOf(tmp)==test.lastIndexOf(tmp)){
System.out.println(tmp);
break;
}
}
}我喜欢这个实现，同时看出我还差得很远啊 方便是方便，效率呢？ 哥们！其实，有些时候，你不用怀疑SUN的工程师写出来的String.indexOf()会像你所想象的实现！ 不相信你可以自己去做个indexOf()的实现去做个试验。 |
| 返回顶楼 | |
