`
cy729215495
  • 浏览: 129222 次
  • 性别: 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;
            }
        }

    }
}

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

分享到：
| 自己给自己授权
评论
60 楼 yyf16 2010-01-13  
<p> </p>
<pre name="code" class="java">import java.util.HashMap;
import java.util.Map;


public class firstNonRepeatedChar  {

    public static void main(String args[]) {
        String s = "tbbbotoal";
        Map map = new HashMap();       
        char[] charArgs = s.toCharArray();
        char flag = ' ';
        for(char c : charArgs){
           
            if(!map.containsKey(c) &amp;&amp; flag != c){
                map.put(c, "value");
            } else {
                map.remove(c);
                flag = c;
            }
        }
       
        System.out.println(map.keySet().toArray()[0]);
    }
}</pre>
<pre name="code" class="java">输出：a</pre>
59 楼 piao_bo_yi 2010-01-11  
asd 写道
这种字符统计，必然是一个255大小的状态数组啊，在c程序员看来都是拿不出手的题目，用什么库函数啊。

“箱子排序”果然是这种问题的通解啊~~~
58 楼 piao_bo_yi 2010-01-11  
piao_bo_yi 写道
asd 写道
这种字符统计，必然是一个255大小的状态数组啊，在c程序员看来都是拿不出手的题目，用什么库函数啊。

可是得输出第一个不重复的字符啊，你的方法能行么？？

明白了，原来能行。
57 楼 piao_bo_yi 2010-01-11  
asd 写道
这种字符统计，必然是一个255大小的状态数组啊，在c程序员看来都是拿不出手的题目，用什么库函数啊。

可是得输出第一个不重复的字符啊，你的方法能行么？？
56 楼 asd 2009-12-02  
这种字符统计，必然是一个255大小的状态数组啊，在c程序员看来都是拿不出手的题目，用什么库函数啊。
55 楼 yfkscu 2009-12-02  
<p>一个时间复杂度为n的算法。第一次发帖有什么不足之处还请指教哈！</p>
<p> </p>
<pre name="code" class="java">//一个时间复杂度为n的算法

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map.Entry;

public class TestClass {
public static void main(String[] args) {
HashMap&lt;Character, Integer&gt; map = new HashMap&lt;Character, Integer&gt;();
String str = "kabcdabc";
int len = str.length();
for (int i = 0; i &lt; len; i++) {
char c = str.charAt(i);
if (map.containsKey(c)) {
map.remove(c);
} else {
map.put(c, i);
}
}

int minIndex = len;
Entry&lt;Character, Integer&gt; minEntry = null;
for (Iterator&lt;Entry&lt;Character, Integer&gt;&gt; iter = map.entrySet()
.iterator(); iter.hasNext();) {
Entry&lt;Character, Integer&gt; entry = iter.next();
if (entry.getValue() &lt; minIndex) {
minEntry = entry;
}
}
System.out.println(minEntry.getKey());
}
}
</pre>
<p> 输出结果为：</p>
<p>k</p>
54 楼 sbkyv 2009-08-18  
最好不要把count放在循环里！犯了错误
53 楼 sbkyv 2009-08-18  
           来个php的
            $old =str_split("eerrttyyf");
            $chars = array_flip($old);
            $l = count($old);
            for($i=0;$i<$l;$i++){
                if($i==$chars[$old[$i]]){
                    echo($old[$i]);
                    break;
                }
                else
                {
                    $chars[$old[$i]]=0;
                }
            }
52 楼 rabbitbug 2009-08-17  
这种算法题，就不是让你用java类库来做的，肯定是要用最简单的东西，一用到类库效率要低好几个等级
51 楼 gowish 2009-08-05  
还一种更快的：
private static char getDuplicateChr2(String param) {
char[] chrList = param.toCharArray();
for (int i=0;i<chrList.length;i++) {
if (param.indexOf(chrList[i]) == param.lastIndexOf(chrList[i])) {
return chrList[i];
}
}
return ' ';
}
50 楼 gowish 2009-08-05  
private static char getDuplicateChr(String param) {
char[] chrList = param.toCharArray();
List<Character> unique = new ArrayList<Character>();
for(int i=0;i<chrList.length;i++) {
if (unique.contains(chrList[i])) {
continue;
} else {
int index = param.indexOf(chrList[i]);
            if (index == i) {
                if (-1 != param.substring(index+1).indexOf(chrList[i])) {
                unique.add(chrList[i]);
                continue;
                } else {
                return chrList[i];
                }
            } else {
            break;
            }
}
}
return ' ';
}
49 楼 kukuqiu001 2009-07-20  
我是根据异常兄的linkedHashMap改写的
统计字符串里面每个字母出现的频率 


import java.util.LinkedHashMap;
import java.util.Map.Entry;


public class CountCharInString {

	public static void main(String[] args) {
       String str ="total";
       char[] charArr = str.toCharArray();
       LinkedHashMap<String, Integer> linkedMap = new LinkedHashMap<String, Integer>();
       int count=1;
       for(char ch: charArr){
    	   String chStr = ch+"";
    	   if(linkedMap.get(chStr)!=null){
    		   linkedMap.put(chStr, linkedMap.get(chStr)+1);
    	   }else{
    		   linkedMap.put(chStr, count);
    	   }
    	   
       }
       
       for(Entry<String, Integer> temp : linkedMap.entrySet()){
    	 if(temp.getValue()!=null && temp.getKey()!=null){
    		 System.out.println("key =" + temp.getKey()+",value ="+ temp.getValue());
    	 }
       }
	}

}
48 楼 cy729215495 2009-07-17  
google_fans 写道
cy729215495 写道
而且这是笔试题目，笔试是有时间限制的，用这些最底层的代码来写做这样的题目，
花的时间很长。当然现在不是笔试，你可以在机器上面运行无数遍了然后把代码贴过来，
我们要的是速度和规则来解这类题目，凡事有规律了，当然就好做了！


这个题目的C语言版本很快的，熟悉的人几分钟就OK了。

比如说一个题目需要用hash表来解决，一个人是用c语言实现了自己的hash结构，一个人是用的类库。
你喜欢哪个人？

哦？就算是熟悉的人碰到这样的题目了，用算法几分钟就能搞定的人并不多吧。
47 楼 clx_wq 2009-07-16  
String str="toaltoa";

for(int i=0; i<str.length(); i++){
int count=0;
for(int j=0; j<str.length(); j++){
if(String.valueOf(str.charAt(i)).equals(String.valueOf(str.charAt(j)))){
count+=1;
}
}
if(count==1){
System.out.print(str.charAt(i));
break;
}
}
46 楼 google_fans 2009-06-05  
cy729215495 写道
而且这是笔试题目，笔试是有时间限制的，用这些最底层的代码来写做这样的题目，
花的时间很长。当然现在不是笔试，你可以在机器上面运行无数遍了然后把代码贴过来，
我们要的是速度和规则来解这类题目，凡事有规律了，当然就好做了！


这个题目的C语言版本很快的，熟悉的人几分钟就OK了。

比如说一个题目需要用hash表来解决，一个人是用c语言实现了自己的hash结构，一个人是用的类库。
你喜欢哪个人？
45 楼 google_fans 2009-06-05  
case0079 写道
那个C程序是用空间换时间.
实际使用中感觉还是LINKEDHASHMAP稳定些.


这个空间开销很小的

如果有中文，开销要大些
44 楼 yzzh9 2009-06-03  
统计重复个数的用上面那个c程序对应的java版改动一下就可以了： 
public class firstNonRepeatedChar {
	private  static final int MAX_CHAR = 256;   
	
	public static void main(String[] args) {
		String str = "tootaddl";
		int count = firstNoRepeatedChar(str);
		System.out.println(count);
	}

	public static int firstNoRepeatedChar(String str) {
		 int i = 0;   
		 int j = 0;   
		 int count = 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]]++;
		 }
		 
		 for(int n=0;n<MAX_CHAR;n++){
			 if(p[n]>1) count++;
		 }
		 return count;
	}
}
43 楼 wnzz95391511 2009-06-03  
我感觉像这样的笔试题，主要考察的还是效率方面，要首先以O(n)为基准点。
不使用类库的为好！
之前用C的那个程序和对应的JAVA版本，都挺好的。
42 楼 抛出异常的爱 2009-06-03  
cy729215495 写道
这么多的答案，我原本写这个程序是唤醒大家算法问题用面向对象的方法来做很好很强大，用c当然可以实现。

现在如果题目改为求统计重复字符串的个数，怎么做呢？希望大家接着往下面做！

个数不爽....

最长自反字符串好玩一些.
abcdeacdrtt=>cd(2)
41 楼 merman 2009-06-03  
<div class="quote_title">楼主 写道</div>
<div class="quote_div">
<pre name="code" class="java">    @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;
    }
</pre>
</div>
<p>我觉得equals不能这样来用，使用equals要满足 自反性 a.equals(a) is true; 对称性 a.equals(b) = b.equals(a); 传递性 a.equals(b) = true b.equals(c) = true 那么 a.equals(c) = true； 一致性 任何时候调用a.equals(b)得到的结果都是一样的。</p>
发表评论

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

相关推荐

    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语法**：包括变量声明、数据类型、运算符、...

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

    本文将深入探讨“华为OD题目库”中的几个关键知识点：字符个数统计、坐标移动以及单词倒排。 1. 字符个数统计： 这是一个基础的字符串处理问题，要求统计给定字符串中各个字符出现的次数。在编程中，我们通常使用...

    C语言-面试题目-汇总

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

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

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

    java面试题目

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

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

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

    富士康JAVA面试题2.doc

    本资源主要关注Java面试题目，涵盖了日期计算、字符串处理、排序算法和Java与C++混合编程等方面的知识点。 日期计算 在Java中，计算某一特定日期是星期几可以使用以下方法： 1. 使用`java.time`包中的`LocalDate`...

    经典面试题目六道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. **链表操作**： - **链表逆序**：涉及到对链表...

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