文档章节

Java编程题——在一个字符串中查找第一个非重复的字符

crossbell
 crossbell
发布于 2014/06/04 16:19
字数 2218
阅读 39
收藏 0
点赞 0
评论 0

本文由 ImportNew - chenchenchao 翻译自 javarevisited。欢迎加入Java小组。转载请参见文章末尾的要求。

编写一个Java程序来查找一个字符串中第一个非重复的字符,这是在编程测试中很常见的一个问题,因为字符串处理在程序员面试中是一个普遍的话题。面试前最好是准备好一些熟知的编程问题,例如使用递归反转字符串,或者检查一个字符串是否是回文(即正反读顺序一致)。查找第一个非重复字符的问题也是在同一个范畴。在给出解决方案之前,我们先来弄懂这个问题。我们需要编写一个函数,这个函数接受一个字符串作为参数,并返回第一个不重复的字符。例如字符串“hello”,除了“l”之外所有字符都是不重复的,但是“h”是第一个不重复的字符。同样,字符串“swiss”中“w”是第一个不重复的字符。一种解决该问题的方法就是创建一张表来记录每个字符的出现次数,然后选出第一个不重复的元素。关键在于字符的次序,你的代码必须返回第一个非重复的字符。另外,在这篇文章中,我们可以看到3个解决该问题的示例。我们的第一个方案是使用LinkedHashMap来记录字符个数,因为LinkedHashMap维持的元素顺序与插入顺序一致,而我们正是按照字符串中字符出现的顺序来将字符插入Map中的。当我们扫描字符串时,只需要迭代LinkedHashMap并找出值为1的元素。是的,这种方案只需要一个LinkedHashMap以及两个循环。我们的第二种解决方案是时间和空间的折衷,在一次遍历中找出不重复的字符。这次,我们使用一个Set和一个List去分开保存重复和不重复的字符。当我们完成一次时间复杂度为O(n)的字符串扫描后,我们可以通过访问List来获得这个神奇的不重复字符,该时间为复杂度为O(1),因为List是有序的,我们可以通过get(0)获得第一个元素。我们的第三种解决方案也是类似的,不过这次我们使用HashMap而不是LinkedHashMap,我们会在第一扫描计算各个字符的出现次数之后,再次扫描字符串去找到第一个不重复的字符。接下来我们将为这个问题编写示例代码和单元测试程序。你也可以去我的字符串面试问题列表中看看更多类似的Java编程题。

 

如何在字符串中找到第一个不重复的字符

这里有在给定字符串中找到第一个非重复字符的完整示例代码,该程序给出了三个找到第一个非重复字符的方法,每个方法都有自己的解决问题的算法。

第一个算法实现在getFirstNonRepeatedChar(String str)方法中。它首先获得字符串的字符数组,然后遍历数组并建立一个哈希表,哈希表的键为字符,值为该字符出现的次数。下一步它会遍历LinkedHashMap去找到第一个值为1的元素,那便是第一个非重复的字符,因为LinkedHashMap维护的元素顺序与插入顺序一致,而我们遍历字符数组是从头遍历到尾。这种算法的缺点在于它需要两个循环,第一个循环的次数与字符串的字符个数成正比,而第二个循环的次数与字符串中重复的字符个数成正比。最差的情况是非重复的字符出现在字符串的最尾部,那么这个算法需要2*N的时间去解决这个问题。

第二个算法实现在firstNonRepeatingChar(String word)方法中。这种解决方案可以在一次字符串扫描中找到第一个不重复的字符,它应用了典型的空间时间权衡技术。它使用了两个存储空间来减少一次循环,是标准的空间-时间折衷。由于我们将重复和不重复的字符分开存放,在循环结束后,存放不重复字符的列表中的第一个元素就是我们所要找的第一个非重复字符。这种解决方案稍微优于上一种。如果在字符串中没有不重复的字符,你可以选择返回null或者空字符串。

第三个算法实现在firstNonRepeatedCharacter(String word)方法中,它与第一种方案非常类似,唯一不同在于它使用了HashMap。由于HashMap并不保证一种特定的顺序,我们必须依赖源字符串去找到第一个不重复的字符。第三种解决方案的算法如下:

  1. 扫描字符串并将每个字符的出现次数保存在HashMap中

  2. 遍历字符串并从Map中获取每个字符的个数

由于我们从左往右扫描字符,当找到某个字符的计数为1时,我们就可以跳出循环,它就是第一个非重复的字符。在这里,字符次序是靠再次遍历源字符串来实现。

import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
 
public class Programming {
    /**
     * Java Program to find first duplicate, non-repeated character in a String.
     * It demonstrate three simple example to do this programming problem.
     * 
     * @author Javarevisited
     */
    public static char getFirstNonRepeatedChar(String str) {
        Map<Character, Integer> counts = new LinkedHashMap<Character, Integer>(
                str.length());
        for (char c : str.toCharArray()) {
            counts.put(c, counts.containsKey(c) ? counts.get(c) + 1 : 1);
        }
        for (Entry<Character, Integer> entry : counts.entrySet()) {
            if (entry.getValue() == 1) {
                return entry.getKey();
            }
        }
        throw new RuntimeException("didn't find any non repeated Character");
    }
 
    /**
     * Using HashMap to find first non-repeated character from String in Java.
     * Algorithm :
     * 
     * Step 1 : Scan String and store count of each character in HashMap
     * 
     * Step 2 : traverse String and get count for each character from Map. Since
     * we are going through String from first to last character, * when count
     * for any character is 1, we break, it's the first * non repeated
     * character. Here order is achieved by going * through String again.
     */
    public static char firstNonRepeatingChar(String word) {
        Set<Character> repeating = new HashSet<Character>();
        List<Character> nonRepeating = new ArrayList<Character>();
        for (int i = 0; i < word.length(); i++) {
            char letter = word.charAt(i);
            if (repeating.contains(letter)) {
                continue;
            }
            if (nonRepeating.contains(letter)) {
                nonRepeating.remove((Character) letter);
                repeating.add(letter);
            } else {
                nonRepeating.add(letter);
            }
        }
        return nonRepeating.get(0);
    }
 
    /**
     * Using HashMap to find first non-repeated character from String in Java.
     * Algorithm :
     * 
     * Step 1 : Scan String and store count of each character in HashMap
     * 
     * Step 2 : traverse String and get count for each character from Map. Since
     * we are going through String from first to last character, when count for
     * any character is 1, we break, it's the first non repeated character. Here
     * order is achieved by going through String again.
     * 
     * @return
     */
    public static char firstNonRepeatedCharacter(String word) {
        HashMap<Character, Integer> scoreboard = new HashMap<Character, Integer>();
        // build table [char -> count]
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (scoreboard.containsKey(c)) {
                scoreboard.put(c, scoreboard.get(c) + 1);
            } else {
                scoreboard.put(c, 1);
            }
        }
        // since HashMap doesn't maintain order, going through string again
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (scoreboard.get(c) == 1) {
                return c;
            }
        }
        throw new RuntimeException("Undefined behaviour");
    }
}

找到第一个唯一字符的JUnit单元测试

这里有一些JUnit测试用例来测试程序的每个方法。我们测试不同类型的输入,一种包含重复字符而另一种不包含。由于程序并没有定义当输入空字符串,null或者只包含重复字符的字符串该如何处理,你可以自己定义一些有效的处理。

import static org.junit.Assert.*;
import org.cc.source.Programming;
import org.junit.Test;
 
public class ProgrammingTest {
    @Test
    public void testFirstNonRepeatedCharacter() {
        assertEquals('b', Programming.firstNonRepeatedCharacter("abcdefghija"));
        assertEquals('h', Programming.firstNonRepeatedCharacter("hello"));
        assertEquals('J', Programming.firstNonRepeatedCharacter("Java"));
        assertEquals('i', Programming.firstNonRepeatedCharacter("simplest"));
    }
 
    @Test
    public void testFirstNonRepeatingChar() {
        assertEquals('b', Programming.firstNonRepeatingChar("abcdefghija"));
        assertEquals('h', Programming.firstNonRepeatingChar("hello"));
        assertEquals('J', Programming.firstNonRepeatingChar("Java"));
        assertEquals('i', Programming.firstNonRepeatingChar("simplest"));
    }
 
    @Test
    public void testGetFirstNonRepeatedChar() {
        assertEquals('b', Programming.getFirstNonRepeatedChar("abcdefghija"));
        assertEquals('h', Programming.getFirstNonRepeatedChar("hello"));
        assertEquals('J', Programming.getFirstNonRepeatedChar("Java"));
        assertEquals('i', Programming.getFirstNonRepeatedChar("simplest"));
    }
}

你可以改进一下测试用例以便测试更多的场景。没有什么比编写详细且有创造性的测试用例更能打动面试官的了,很多程序员都想不到或者没有努力去思考这些。

这就是这篇文章所有要阐述的内容。我们看到了三种解决这个问题的方法,尽管他们的逻辑很类似,但不尽相同,示例程序对于初学者学习Java容器框架也是非常不错的。它让你有机会去了解不同Map的实现,并明白HashMap与LinkedHashMap的区别,以便决定什么时候使用他们。另外,如果你知道解决该问题的其他方法,请分享一下。如果你在面试过程中也遇到过类似问题,你也可以分享一下你的面试经历。

原文链接: javarevisited 翻译: ImportNew.com - chenchenchao
译文链接: http://www.importnew.com/11493.html
[ 转载请保留原文出处、译者和译文链接。]

本文转载自:http://www.importnew.com/11493.html

共有 人打赏支持
crossbell
粉丝 24
博文 167
码字总数 14545
作品 0
海淀
项目经理
Android JNI(一)——NDK与JNI基础

本系列文章如下: Android JNI(一)——NDK与JNI基础 Android JNI学习(二)——实战JNI之“hello world” Android JNI学习(三)——Java与Native相互调用 Android JNI学习(四)——JNI的常用方法...

隔壁老李头 ⋅ 05/09 ⋅ 0

Android JNI学习(四)——JNI的常用方法的中文API

本系列文章如下: Android JNI(一)——NDK与JNI基础 Android JNI学习(二)——实战JNI之“hello world” Android JNI学习(三)——Java与Native相互调用 Android JNI学习(四)——JNI的常用方法...

隔壁老李头 ⋅ 05/09 ⋅ 0

java编程学习常见面试题及答案

Java是一种可以撰写跨平台应用软件的面向对象的程序设计语言。Java 技术具有卓越的通用性、高效性、平台移植性和安全性,广泛应用于PC、数据中心、游戏控制台、科学超级计算机、移动电话和互...

Java小辰 ⋅ 05/22 ⋅ 0

FindBugs、PMD和CheckStyle对比

工具 目的 检查项 FindBugs 检查.class 基于Bug Patterns概念,查找javabytecode(.class文件)中的潜在bug。 它使用静态分析方法标识出Java程序中上百种潜在的不同类型的错误。 主要检查byt...

awesome@qa ⋅ 05/16 ⋅ 0

Java 已老,Kotlin 或将取而代之!

点击上方“CSDN”,选择“置顶公众号” 关键时刻,第一时间送达! Java已经成为历史。它无法发展成现代语言,同时保证向后兼容性。但它为我们带来了最好的JVM生态系统,并引导了许多优秀语言...

CSDN ⋅ 05/12 ⋅ 0

字符串连接你用+还是用StringBuilder

前言 据我所知字符串确实已经成为 Java 开发人员最常用的类了,而且是大量使用。我们都知道,String 其实是封装了字符,所以俩字符串连接就是将字符串对象里面的字符连起来。很多人习惯使用来...

超人汪小建 ⋅ 前天 ⋅ 0

Java面试题全集(上)+JavaSE基础

第一阶段:开发常用 JavaSE基础、Spring、Spring Boot、Spring Cloud、Hibernate、Mybatis、MySQL、Oracle、MariaDB(支持文档数据) 第二阶段:基础提升 JavaSE深入、JVM、数据结构+算法、H...

guod369 ⋅ 2017/12/28 ⋅ 0

2018年Java编程学习面试最全知识点总结

Java是一种可以撰写跨平台应用软件的面向对象的程序设计语言。Java 技术具有卓越的通用性、高效性、平台移植性和安全性,广泛应用于PC、数据中心、游戏控制台、科学超级计算机、移动电话和互...

Java小辰 ⋅ 05/14 ⋅ 0

深入理解Java虚拟机的体系结构

JAVA虚拟机的生命周期 一个运行时的Java虚拟机实例的天职是:负责运行一个java程序。当启动一个Java程序时,一个虚拟机实例也就诞生了。当该程序关闭退出,这个虚拟机实例也就随之消亡。如果...

java进阶 ⋅ 昨天 ⋅ 0

Java 使用 happen-before 规则实现共享变量的同步操作

前言 熟悉 Java 并发编程的都知道,JMM(Java 内存模型) 中的 happen-before(简称 hb)规则,该规则定义了 Java 多线程操作的有序性和可见性,防止了编译器重排序对程序结果的影响。按照官方的...

stateIs0 ⋅ 01/20 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Sqoop

1.Sqoop: 《=》 SQL to Hadoop 背景 1)场景:数据在RDBMS中,我们如何使用Hive或者Hadoop来进行数据分析呢? 1) RDBMS ==> Hadoop(广义) 2) Hadoop ==> RDBMS 2)原来可以通过MapReduce I...

GordonNemo ⋅ 19分钟前 ⋅ 0

全量构建和增量构建的区别

1.全量构建每次更新时都需要更新整个数据集,增量构建只对需要更新的时间范围进行更新,所以计算量会较小。 2.全量构建查询时不需要合并不同Segment,增量构建查询时需要合并不同Segment的结...

无精疯 ⋅ 30分钟前 ⋅ 0

如何将S/4HANA系统存储的图片文件用Java程序保存到本地

我在S/4HANA的事务码MM02里为Material维护图片文件作为附件: 通过如下简单的ABAP代码即可将图片文件的二进制内容读取出来: REPORT zgos_api.DATA ls_appl_object TYPE gos_s_obj.DA...

JerryWang_SAP ⋅ 48分钟前 ⋅ 0

云计算的选择悖论如何对待?

导读 人们都希望在工作和生活中有所选择。但心理学家的调查研究表明,在多种选项中进行选择并不一定会使人们更快乐,甚至不会产生更好的决策。心理学家Barry Schwartz称之为“选择悖论”。云...

问题终结者 ⋅ 55分钟前 ⋅ 0

637. Average of Levels in Binary Tree - LeetCode

Question 637. Average of Levels in Binary Tree Solution 思路:定义一个map,层数作为key,value保存每层的元素个数和所有元素的和,遍历这个树,把map里面填值,遍历结束后,再遍历这个map,把每...

yysue ⋅ 今天 ⋅ 0

IDEA配置和使用

版本控制 svn IDEA版本控制工具不能使用 VCS-->Enable Version Control Integration File-->Settings-->Plugins 搜索Subversion,勾选SVN和Git插件 删除.idea文件夹重新生成项目 安装SVN客户......

bithup ⋅ 今天 ⋅ 0

PE格式第三讲扩展,VA,RVA,FA的概念

作者:IBinary 出处:http://www.cnblogs.com/iBinary/ 版权所有,欢迎保留原文链接进行转载:) 一丶VA概念 VA (virtual Address) 虚拟地址的意思 ,比如随便打开一个PE,找下它的虚拟地址 这边...

simpower ⋅ 今天 ⋅ 0

180623-SpringBoot之logback配置文件

SpringBoot配置logback 项目的日志配置属于比较常见的case了,之前接触和使用的都是Spring结合xml的方式,引入几个依赖,然后写个 logback.xml 配置文件即可,那么在SpringBoot中可以怎么做?...

小灰灰Blog ⋅ 今天 ⋅ 0

冒泡排序

原理:比较两个相邻的元素,将值大的元素交换至右端。 思路:依次比较相邻的两个数,将小数放在前面,大数放在后面。即在第一趟:首先比较第1个和第2个数,将小数放前,大数放后。然后比较第...

人觉非常君 ⋅ 今天 ⋅ 0

Vagrant setup

安装软件 brew cask install virtualboxbrew cask install vagrant 创建project mkdir -p mst/vmcd mst/vmvagrant init hashicorp/precise64vagrant up hashicorp/precise64是一个box......

遥借东风 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部