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

    }
}

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

分享到：
| 自己给自己授权
评论
20 楼 抛出异常的爱 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]);
19 楼 google_fans 2009-06-02  
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;
			}
		}
	}


我喜欢这个实现，同时看出我还差得很远啊


方便是方便，效率呢？
18 楼 ywlqi 2009-06-02  
抛出异常的爱 写道
被同事ＢＳ了 
	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;
			}
		}
	}


我喜欢这个实现，同时看出我还差得很远啊
17 楼 google_fans 2009-06-02  
如果是有中文，楼上的MAX_CHAR 就需要比较大了，对于那些java搞出来的算法，感觉效率很难说的，好多东西都是人家实现的。
16 楼 google_fans 2009-06-02  
楼上这个算法是最优的，我个人比较喜欢这个算法。
15 楼 shaobin0604 2009-06-02   
#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;
}
14 楼 shaquan6776 2009-06-02  
抛出异常的爱 写道
cy729215495 写道
linkedmap,学习了！
高手果然就是高手！
如果我要对字符出现的次数按照从大到小的次序排序各位的方法就很不好扩展了！

如果只是要找出最大的....
我知道的有一种是正则但非常的难以理解.....朋友写出后看了一天都没想明白

把正则贴出来，让大家学习学习。
13 楼 google_fans 2009-06-02  
姜太公 写道
一次遍历，统计每个字符出现次数，保持有序。第一个出现次数为1的就是。效率O(n)


想问下o(n)是怎么做到的？

12 楼 抛出异常的爱 2009-06-02  
cy729215495 写道
linkedmap,学习了！
高手果然就是高手！
如果我要对字符出现的次数按照从大到小的次序排序各位的方法就很不好扩展了！

如果只是要找出最大的....
我知道的有一种是正则但非常的难以理解.....朋友写出后看了一天都没想明白
11 楼 1314520ln 2009-06-02  
突然觉得自己什么都不会....

受教了~
10 楼 lw223 2009-06-01  
看基础去了
9 楼 cy729215495 2009-06-01  
linkedmap,学习了！
高手果然就是高手！
如果我要对字符出现的次数按照从大到小的次序排序各位的方法就很不好扩展了！
8 楼 case0079 2009-06-01  
抛出异常的爱 写道
被同事ＢＳ了 
	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;
			}
		}
	}



这个的复杂度应该是N平方了
7 楼 Checkmate 2009-06-01  
<p>不知道我的想法行不行.........</p>
<pre name="code" class="java">public class Test
{
    public static void main(String[] args)
    {
        Set tempSet = new LinkedHashSet();

        String tempStr = new String("tesabet");

        for (int i = 0; i &lt; tempStr.length(); i++)
        {

            tempSet.add(tempStr.toCharArray()[i]);

        }

        Iterator it = tempSet.iterator();

        int i = 0;

        while (it.hasNext())
        {

            if ((it.next().toString()).toCharArray()[0] != tempStr
                .toCharArray()[i])

            {

                System.out.print((i + 1) + " " + tempStr.toCharArray()[i]);

                break;
            }

            if (i == tempSet.size() - 1)
            {
                System.out.print((i + 1) + " " + tempStr.toCharArray()[i + 1]);
            }

            i++;

        }

    }

}
</pre>
<p> </p>
6 楼 iaimstar 2009-06-01  
抛出异常的爱 写道
被同事ＢＳ了 
	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;
			}
		}
	}


哈哈 ，这种util类型的东西，每次开始都是一大把的代码，很多年过去剩下的，都是区区几行，勾起很多回忆 ～_～

尤其是一些关于time的，string的，check之类，现在都有很多回头乐的故事

不过String里面那一堆堆的loop，还算O（n）么？
5 楼 抛出异常的爱 2009-06-01  
被同事ＢＳ了 
	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;
			}
		}
	}
4 楼 抛出异常的爱 2009-06-01  
axxxx2000 写道
异常大大用了流程形式，没面向对象~~~

你打算娶个什么对象回家?

我只是提醒一下java api 中还有linkedmap这种东西的存在.这题是专门为这个类定制的....
3 楼 axxxx2000 2009-06-01  
异常大大用了流程形式，没面向对象~~~
2 楼 抛出异常的爱 2009-06-01   
	public static void main(String arg[]){
		String test = "tatle";
		char[] array = test.toCharArray();
		LinkedHashMap<String, Integer> map = new LinkedHashMap<String, Integer>();
		for(char tmp : array){
			String str = tmp+"";
			if(map.get(str)==null){
				map.put(str, 1);
			}else{
				map.put(str, 0);
			}
			
		}
	
		for(Entry<String, Integer> tmp : map.entrySet()){
			if(tmp.getValue()!=null&&tmp.getValue()==1){
				System.out.println(tmp.getKey());
				break;
			}
		}
		
	}
1 楼 姜太公 2009-06-01  
一次遍历，统计每个字符出现次数，保持有序。第一个出现次数为1的就是。效率O(n)
发表评论

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

相关推荐

    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