`
cy729215495
  • 浏览: 129571 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
社区版块
存档分类
最新评论

面试题目字符统计

面试C#C++C算法 
阅读更多

有人问：

求第一个无重复字符,如"total"的第一个无重复字符是o,"teeter"的第一个无重复字符是r,效率要优于O(n的平方)
public static Character FirstNonRepeated(String)

 

 

说句实话，形如这样的字符串统计规律(什么按字符出现次数排序之类的)的题目，在笔试题目中屡见不鲜，在论坛里面总是有人在问。
笔试是关键，笔试不行，大公司想都不要想了。
这里面方法有很多种，我有一种方法，面向对象的，可解此类问题！ 

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;

public class Tongji {

    /**
     * @param args
     */
    char ch;

    int count = 1;

    int index;

    public Tongji(char ch, int index) {
        this.ch = ch;
        this.index = index;
    }

    @Override
    public int hashCode() {//eclipse自动生成的
        final int PRIME = 31;
        int result = 1;
        result = PRIME * result + ch;
        result = PRIME * result + count;
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        final Tongji other = (Tongji) obj;
        if (ch != other.ch)
            return false;
        if (count == other.count) {
            other.count++;

        }
        return true;
    }

    public static void main(String[] args) {
        String a = "total";
        HashSet set = new HashSet();
        for (int i = 0, k = a.length(); i < k; i++) {
            set.add(new Tongji(a.charAt(i), i));
        }
        List list = new ArrayList(set);
        Collections.sort(list, new Comparator() {//按索引排序
            public int compare(Object o1, Object o2) {
                Tongji t1 = (Tongji) o1;
                Tongji t2 = (Tongji) o2;

                if (t1.index > t2.index)
                    return 1;
                return 0;
            }
        });

        for (Iterator it = list.iterator(); it.hasNext();) {
            Tongji tj = (Tongji) it.next();
            if (tj.count == 1) {
                System.out.println("char:" + tj.ch + " count:" + tj.count);
                break;
            }
        }

    }
}

 这就是面向对象的强大威力！

分享到：
| 自己给自己授权
评论
40 楼 cy729215495 2009-06-03  
而且这是笔试题目，笔试是有时间限制的，用这些最底层的代码来写做这样的题目，
花的时间很长。当然现在不是笔试，你可以在机器上面运行无数遍了然后把代码贴过来，
我们要的是速度和规则来解这类题目，凡事有规律了，当然就好做了！
39 楼 cy729215495 2009-06-03  
这么多的答案，我原本写这个程序是唤醒大家算法问题用面向对象的方法来做很好很强大，用c当然可以实现。

现在如果题目改为求统计重复字符串的个数，怎么做呢？希望大家接着往下面做！
38 楼 抛出异常的爱 2009-06-03  
如果题目要求用底归来作的话....
估计我要作一天.
37 楼 case0079 2009-06-03  
那个C程序是用空间换时间.
实际使用中感觉还是LINKEDHASHMAP稳定些.
36 楼 feiyeguohai 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;
}
}
35 楼 yzzh9 2009-06-03  
楼上的，我没注意看过他的代码，是我失误，但既然是翻译过来就应该注明一下。
34 楼 dch1287 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);
		} 
	}

33 楼 cy729215495 2009-06-03  
csdn上面找的吧
32 楼 yzzh9 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;
		
	}
}
31 楼 yuyoo4j 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);
		} 
	}
30 楼 google_fans 2009-06-02  
难道它把indexOf()做成o(1)的算法？
sun工程师就牛啊
29 楼 tiandp007 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()的实现去做个试验。
28 楼 case0079 2009-06-02  
仔细看了下,确实是比较高效的方法.估计出题者想要的答案就是这个了.用LINKEDHASHMAP可能不太像笔试题目.
27 楼 google_fans 2009-06-02  
要维护顺序干嘛，str里面有顺序。好好看下代码哈
26 楼 case0079 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]是记录各个字符的出现次数.但没有维护字符出现的顺序.
25 楼 xiaobin268 2009-06-02   
li = "aaaAAbbbcCCCddddddEEEEEEEEEEffffffffff"
print([enum for enum in li if li.count(enum)==1].pop())
24 楼 google_fans 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算法。
23 楼 case0079 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;
}


不符合题意:题目要求找第一个不重复的字符,这个实现是找最小的.
22 楼 shaquan6776 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]);

  这个方法只对连续重复的有用.
21 楼 case0079 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实现从时间复杂度上讲是满足出题要求的.
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    c语言面试题之哈希表字符串中的第一个唯一字符.zip

    综上所述，解决“C语言面试题之哈希表字符串中的第一个唯一字符”不仅要求掌握C语言的基础语法，还需理解哈希表的原理和应用，以及具备良好的算法设计和分析能力。熟练掌握这些知识点，对于提升C语言编程技能和应对...

    查找字符串中出现重复次数最多的字符

    在编程领域，尤其是在面试环节，字符串处理问题是常见的一类题目，因为它们涉及到基础的数据结构、算法和逻辑思维。本主题关注的是如何查找一个字符串中出现重复次数最多的字符。这是一个典型的字符串处理问题，对于...

    面试题目_cc++面试-----17道经典编程题目分析

    本文档提供了17道经典的C++面试题目，涵盖了C++语言的各种基础语法和算法，包括字符串处理、数字处理、数组处理等。每个题目都提供了详细的解释和参考答案，旨在帮助读者更好地理解C++语言的实现细节和解决问题的...

    Golang_常见面试题目解析

    标题中提到的“Golang常见面试题目解析”，意味着本篇内容将会围绕Golang语言在面试中常见的题型和解答策略进行讨论。Golang，常被称为Go语言，是由Google开发的一种静态强类型、编译型、并发型，并具有垃圾回收功能...

    c++面试题目总结c++面试题目

    以上是针对给定的C++面试题目的解答，涵盖了字符串处理、算法、数据结构以及C++特性等多个方面。这些题目旨在考察面试者的编程基础、逻辑思维和问题解决能力。在实际面试中，深入理解这些问题的解法和优化策略是非常...

    Java 面试题集

    ### Java面试题集概览 #### HR面试题 1. **Session有效期配置** - **基础知识**：`&lt;session-timeout&gt;`元素通常用于配置`web.xml`中的会话超时时间。这是一种简单且直接的方式来设定HTTP会话的生存周期。 - **配置...

    百度笔试题面试题集总

    代码利用了循环和条件判断，遍历整个字符串，统计连续数字的个数，并记录最长连续数字串的信息。 ### NewCoke案例分析 NewCoke是可口可乐公司于1985年推出的配方改良版可乐，旨在应对百事可乐的竞争压力。然而，...

    JAVA面试题集（附答案）

    这份"JAVA面试题集（附答案）"提供了全面的Java面试问题，涵盖了从基础到高级的各个方面，旨在帮助你更好地准备面试。 在Java基础部分，你需要了解以下知识点： 1. **Java语法**：包括变量声明、数据类型、运算符、...

    C语言-面试题目-汇总

    以下是一些常见的C语言面试题及其解析： 1. **约瑟夫问题** (难度：3)：这是一个经典的循环数组问题，涉及到数组操作和循环逻辑。问题通常设定为所有人在一个圆圈里，每隔一定数量的人被淘汰，直到只剩最后一个人...

    华为OD资源：华为od题目库（字符个数统计、坐标移动、单词倒排等）

    综上所述，华为OD题目库中的字符个数统计、坐标移动和单词倒排题目，从不同侧面考察了编程者的基本技能和对编程思维的理解。通过解决这些题目，应聘者不仅能够提升自己的编程技巧，还能锻炼算法思维和问题建模能力。...

    华为-华为od题库练习题之字符串排序.zip

    7. **计数排序**：适用于字符串长度较小且字符集有限的情况，通过统计每个字符出现的次数，计算出每个字符串的位置。 8. **基数排序**：基于数字位的排序，适合于字符串长度不一，但字符串由相同位数的数字组成的...

    java面试题目

    【Java面试题目】是华为2013年针对校招生进行的技术考核，涵盖了多项编程挑战。以下是这些题目涉及的关键知识点： 1. **字符串操作**： - 大写字母反序输出：这需要理解字符串的基本操作，如遍历字符串、大小写...

    C/C++面试题目及解答.doc

    请完成以下题目。注意，请勿直接调用 ANSI C 函数库中的函数实现。 a)请编写一个 C 函数，该函数给出一个字节中被置 1 的位的个数，并请给出该题的至少一个不同解法。 第一种unsigned int TestAsOne0(char ...

    经典面试题目六道C++

    ### 经典面试题目六道C++解析 #### 第一题：求数组中的最大连续子数组之和 **题目描述**： 给定一个整数数组 `nums = [1, -2, 3, 10, -4, 7, 2, -5]`，找出其中最大连续子数组的和。 **示例**： 输入：`nums = [1...

    中外知名企业面试题目之IBM

    IBM的面试题目覆盖了广泛的技能领域，从基本的算法和数据结构到高级的逻辑推理和概率统计。准备IBM面试的关键在于系统学习相关知识，通过大量练习提升解题速度和准确率，同时保持开放的心态，勇于面对挑战，展现出...

    Redis面试题集

    Redis 单个字符串类型的值最大容量为 512MB。Redis 将所有数据存入内存是为了最大化读写速度，虽然这样可能导致内存使用限制，但在内存充足且需要高性能操作的场景下，Redis 的这种设计尤为合适。 Redis 集群方案...

    Golang常见面试题解析.pdf

    本文将从以下几个常见的面试题目深入分析Go语言的基础知识点、并发编程及字符串操作的高级技巧。 一、交替打印数字和字母 此问题要求使用两个goroutine分别打印数字和字母，并要求这两个goroutine交替执行，最终...

    php面试题目答案php面试题目答案php面试题目答案

    在 Web 开发中，经常需要获取客户端的 IP 地址来进行一些统计或安全方面的控制。 **示例代码：** ```php function get_client_ip() { if (getenv('HTTP_CLIENT_IP')) { $client_ip = getenv('HTTP_CLIENT_IP'); ...

    微创面试题目下载中微创面试题目下载中

    【微创面试题目】涵盖的内容广泛，包括数据结构、算法、C++基础知识、线程与进程、内存管理、字符串处理、委托与反射等多个方面。以下是对这些知识点的详细说明： 1. **链表操作**： - **链表逆序**：涉及到对链表...

    程序员面试题目，程序员即将面试用

    以下是一些常见的面试题目及其解析： 1. **编程题：序列求和** 给定的题目要求计算序列 `1 + 2 - 3 + 4 - 5 + ... + n` 的和。提供的代码使用了循环和数学运算符来实现： ```java public static double calN(int...

Magicbox
Global site tag (gtag.js) - Google Analytics