文档章节

一道迅雷面试题:求出一个字符串中每个字母出现的次数

Bob_1112
 Bob_1112
发布于 2015/04/24 15:23
字数 849
阅读 10
收藏 0

By Long Luo

上次在迅雷面试的时候,遇到了一个算法题,题目是:

有一个很长很长的字符串,全部都是由大写字母组成,要求求出其中每个字母在这个字符串中出现的次数。

不允许使用STL中的方法。

当时拿到这个题目,我首先想到了以下几个方法:

  1. 穷举法,一个个比较,最后算出每个字母出现的次数,这种方法可行,但不轻巧与优雅。
  2. 每个字符与’A’想减,会得到一个,统计下这个值出现次数,和方法1类似。(事后回顾这个已经很接近了,但是还是没能完美解决。)

其实这个题目,事后回顾起来,是比较简单的,但遗憾的是,当时未能在规定时间内解答出来,导致未能通过面试,拿到Offer,在此将这个题目记录下来。

重新认真解答这个题目。

How?

其实这个题目有一个很简单的解决防范,新建一个数组,大小为26,将字符串中每个字符都与'A'相减,得到的就是每个字母在数组中的元素下标值,我们最后得到的这个数组就是每个字母在这个字符串中出现的次数。

根据以上分析,可以写出如下代码:

package com.algorithm.alphabetSort;

/**
 * 有一个很长的字符串,其中都是一些字母,求其中每个字母出现的次数(大小写区分)。
 * 
 * @author luolong
 * @date: 2015-04-12 00:54:17
 * 
 */
public class AlphabetSort {
    private static String str = "AWQEYIOAHDHDKKLDLAHFHJALAFHANNAFGJCXCKBZCQIEOPADHAZBZVCFGCSHDJCKCLDMDHFAKAIIAYQO";

    private static int[] outArray = new int[26];

    public static void main(String[] args) {
        AlphabetSortString(str);
        printSortArray(outArray);
    }

    public static void AlphabetSortString(String str) {
        char cTemp;

        for (int i = 0; i < str.length(); i++) {
            cTemp = str.charAt(i);

            outArray[cTemp - 'A']++;
        }
    }

    private static void printSortArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            char c = (char) ('A' + i);
            System.out.print("" + c + "=" + arr[i] + " ");
        }
    }

}

引申与扩展一

如果字符串不仅仅是大写字母,而是大小写字母都存在的情况下,那应该如何写呢?

其实也很简单,如下所示:

if (cTemp >= 'A' && cTemp <= 'Z') {
    /**
    * 大写字母
    */
    outArray[cTemp - 'A']++;
} else if (cTemp >= 'a' && cTemp <= 'z') {
    /**
    * 小写字母
    */
    outArray[cTemp - 'a' + 26]++;
} else {

}

引申与扩展二

如果字符串,假如所有字符都需要统计呢?

那又应该如何做呢?

后来我发现了用HashMap来存储也是可以的,也可以完美解决这个问题,代码如下所示:

package com.algorithm.alphabetSort;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 有一个很长的字符串,其中都是一些字母,求其中每个字母出现的次数(大小写区分)。
 * 
 * @author luolong
 * @date: 2015-04-12 01:03:38
 * 
 */
public class CharSort {
    private static String str = "AWQEYIOAHDHDKKLDLAHFHJALAFHANNAFGJCXCKBZCQIEOPADHAZBZVCFGCSHDJCKCLDMDHFAKAIIAYQO";

    public static void main(String args[]) {
        Map<Character, KeyValue> map = new HashMap<Character, KeyValue>();
        char c;
        KeyValue kv = null;
        for (int i = 0; i < str.length(); i++) {
            c = str.charAt(i);
            kv = map.get(c);
            if (kv == null) {
                kv = new KeyValue();
                kv.ch = c;
                kv.count = 1;
                map.put(c, kv);
            } else {
                kv.count++;
            }
        }
        List<KeyValue> list = new ArrayList<KeyValue>(map.values());
        Collections.sort(list);
        for (KeyValue o : list) {
            System.out.print(o.ch + "=" + o.count + "  ");
        }
    }
}

class KeyValue implements Comparable {
    public int compareTo(Object obj) {
        if (obj instanceof KeyValue) {
            KeyValue kv = (KeyValue) obj;
            return kv.count - this.count;
        }

        return -1;
    }

    char ch;

    int count;
}

以上。

如果大家还有其他更好的方法,欢迎一起讨论:–)

Created by Long Luo at 2015-04-12 01:08:20 @Shenzhen , China.
Completed By Long Luo at 2015-04-12 01:28:39 @Shenzhen , China.

original link:http://longluo.github.io/blog/20150412/a-ThunderSoft-interview-problem-count-every-alphabet-apperence-times-in-a-string/
 written by Frank Luo posted at http://longluo.github.io

本文转载自:http://blog.csdn.net/love__linux/article/details/45174305

Bob_1112
粉丝 1
博文 16
码字总数 0
作品 0
徐汇
程序员
私信 提问
【闲谈】如何统计字符串中出现最多的字母与个数

前言 闲来无事,穷折腾。最近我朋友在找工作,遇到一些面试题,或者遇到一些问题会及时跟我讨论。我则作为他的幕后军师,为他出谋划策。接下来我分享给大家一道简单的面试题。 题目 统计字符...

小小坤
2018/12/14
0
0
在一段英文字母中找出,每个字母的重复数量的方法

在一段英文字母中找出,每个字母重复数量的方法,这是我遇到过的一道面试题。方法有很多种,这里给大家介绍一种比较高效的处理方法。 假设一段英文字母如下: afggsgshdhdddh dh dhd hdgggg...

郑树恒
2015/08/15
520
4
【LeetCode】409. Longest Palindrome (java实现)

原题链接 https://leetcode.com/problems/longest-palindrome/ 原题 Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that......

BookShu
2016/11/04
191
0
python统计前十出现最多的词

一、描述 这是一道python面试题: “一个可读文件,有一万行,一行只有一个单词,单词可以重复的,求出这一万行中出现频繁次数最多的前10个单词” 二、思路 先读取文件变为列表,再用集合去重...

dyc2005
2017/09/29
0
0
微软等公司数据结构+算法面试100题

1.把二元查找树转变成排序的双向链表(树) 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 10 / / 6 14 / / / / 4 ...

chambai
2012/08/05
0
0

没有更多内容

加载失败,请刷新页面

加载更多

nginx学习之模块

1、 stub_status模块: 用于展示nginx处理连接时的状态。 配置语法如下: Syntax:stub_status;Default:默认没有配置Context:server、location 可以编辑default.conf,加上如下配置: ...

码农实战
51分钟前
4
0
MySQL,必须掌握的6个知识点

目录 一、索引B+ Tree 原理 MySQL 索引 索引优化 索引的优点 索引的使用条件 二、查询性能优化使用 Explain 进行分析 优化数据访问 重构查询方式 三、存储引擎InnoDB MyISAM 比较 四、数据类...

李红欧巴
55分钟前
4
0
堆”和“栈

C++作为一款C语言的升级版本,具有非常强大的功能。它不但能够支持各种程序设计风格,而且还具有C语言的所有功能。我们在这里为大家介绍的是其中一个比较重要的内容,C++内存区域的基本介绍。...

SibylY
今天
4
0
总结:Https

一、介绍 简单理解,https即在http协议的基础上,增加了SSL协议,保障数据传输的安全性。 它由以前的http—–>tcp,改为http——>SSL—–>tcp;https采用了共享密钥加密+公开密钥加密的方式 ...

浮躁的码农
今天
6
0
数据库表与表之间的一对一、一对多、多对多关系

表1 foreign key 表2 多对一:表 1 的多条记录对应表 2 的一条记录 利用foreign key的原理我们可以制作两张表的多对多,一对一关系 多对多: 表1的多条记录可以对应表2的一条记录 表2的多条记...

Garphy
今天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部