文档章节

【九度OJ1283】|【剑指offer35】第一个只出现一次的字符

aqia358
 aqia358
发布于 2013/10/17 11:33
字数 747
阅读 42
收藏 1

题目描述:

在一个字符串(1<=字符串长度<=10000,全部由大写字母组成)中找到第一个只出现一次的字符。

输入:

输入有多组数据
每一组输入一个字符串。

输出:

输出第一个只出现一次的字符下标,没有只出现一次的字符则输出-1

方法1:

看到这个题目,最直观的想法就是就是遍历法,也就是从头开始取字符串中的一个字符,将其与其后的所有字符比较,如果有相同的字符,那么就证明它不是 只出现一次的字符。当第一次出现遍历完其后字符并且没有重复时,表明这个字符就是“第一个只出现一次的字符”。如果字符串有n个字符,每个字符可能与后面 的O(n)个字符相比较,因此这种思路的时间复杂度是O(n2)。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void findOne(String s){
		for(int i = 0; i < s.length(); i++){
			boolean flag = false;
			for(int j = 0; j < s.length(); j++){
				if(s.charAt(i) == s.charAt(j) && i != j)
					flag = true;
			}
			if(!flag){
				System.out.println(1);
				return;
			}
		}
		System.out.println(-1);
			
	}
	public static void main(String[] args) {
//		findOne("ABA");
//		findOne("AA");
		InputStreamReader isr = new InputStreamReader(System.in);
		BufferedReader br = new BufferedReader(isr);
		while(true){
			try {
				String s = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
	}
}

方法2:

题目中要求第一个只出现一次的字符,那么就跟字符出现的次数有关。我们考虑如何统计字符出现的次数,然后找出第一个次数为1的那个字符。这里我们需要一个数据容器来保存字符出现次数,并且能够通过字符找出其相对应的次数。哈希表就是一种常用用的容器。

我们可以定义哈希表的键值(Key)是字符的ASCII值,而值(Value)是该字符出现的次数。同时我们需要扫描两次字符串,第一次扫描字符串 时,每扫描到一个字符就在哈希表的对应项中把次数加1。接下来第二次扫描的时候,没扫描到一个字符就能在哈希表中得到该字符出现的次数。找出第一个 Value为1的那个key就是我们需要找到那个字符。

哈希1:

import java.util.Scanner;

public class Copy_2_of_Main {

	public static void findOne(String s) {
		int[]a = new int[256];
		for (int i = 0; i < s.length(); i++) {
			int b = s.charAt(i);
			if(a[b] == 1)
				a[b] = 2;
			else
				a[b] = 1;
		}
		for(int j = 0; j < s.length(); j++){
			if(a[s.charAt(j)] == 1){
				System.out.println(j);
				return;
			}
		}
		System.out.println(-1);
	}

	public static void main(String[] args) {
//		findOne("AA");
//		findOne("ABACCDEFF");
		Scanner s = new Scanner(System.in);
		while (true) {
			String str = s.next();
			findOne(str);
		}
	}
}
哈希2
import java.util.Scanner;

public class Main {

	public static void findOne(String s) {
		int[] a = new int[26];
		int lenght = s.length();
		for (int i = 0; i < lenght; i++) {
			a[s.charAt(i) - 'A']++;
		}
		for (int j = 0; j < lenght; j++) {
			if (a[s.charAt(j) - 'A'] == 1) {
				System.out.println(j);
				return;
			}
		}
		System.out.println(-1);
	}

	public static void main(String[] args) {
//		 findOne("AA");
//		 findOne("ABACCDEFF");
		Scanner s = new Scanner(System.in);
		while (s.hasNext()) {
			String str = s.next();
			findOne(str);
		}
	}
}

© 著作权归作者所有

共有 人打赏支持
aqia358
粉丝 6
博文 82
码字总数 30297
作品 0
海淀
程序员
[算法总结] 13 道题搞定 BAT 面试——字符串

本文首发于我的个人博客:尾尾部落 1. KMP 算法 谈到字符串问题,不得不提的就是 KMP 算法,它是用来解决字符串查找的问题,可以在一个字符串(S)中查找一个子串(W)出现的位置。KMP 算法把...

繁著
09/05
0
0
经典算法学习——第一个只出现一次的字符

这同样是剑指Offer中的很经典的一道面试题。题目描述为:在字符串中找出第一个只出现一次的字符。如输入“abaccdeff”,则输出'b'. 一开始大家就会想到最简单的方法就是每访问到一个字符的时...

chenyufeng1991
2016/08/21
0
0
[剑指offer] 字符流中第一个不重复的字符

本文首发于我的个人博客:尾尾部落 题目描述 请实现一个函数用来找出字符流中第一个只出现一次的字符。例如,当从字符流中只读出前两个字符"go"时,第一个只出现一次的字符是"g"。当从该字符...

繁著
07/29
0
0
python剑指offer66题

二维数组的查找 替换空格 从头到尾打印链表 重建二叉树 用两个栈实现队列 选择数组中的最小数字 斐波那契数列 跳台阶 变态跳台阶 矩形覆盖 二进制中1的个数 数值的整数次方 调整数组顺序使奇...

lyy0905
06/03
0
0
去哪儿笔试题2015 - 研发

有序数列二分查找 最简单,最纯粹的二分查找问题,应该是用循环的方法去做的话会得分较高。 2. 寻找第一个出现两次的字符 举个例子:字符串“qywyer23tdd”中第一个出现了两次的字符串是'y'...

NineRec
2014/09/10
0
0

没有更多内容

加载失败,请刷新页面

加载更多

992. Sort Array By Parity II - LeetCode

Question 992. Sort Array By Parity II Solution 题目大意:给一个int数组,一半是奇数一半是偶数,分别对偶数数和奇数数排序并要求这个数本身是偶数要放在偶数位上 思路:把奇数数和偶数数...

yysue
23分钟前
1
0
Snackbar源码分析

目录介绍 1.最简单创造方法 1.1 Snackbar作用 1.2 最简单的创建 1.3 Snackbar消失的几种方式 2.源码分析 2.1 Snackbar的make方法源码分析 2.2 对Snackbar属性进行设置 2.3 Snackbar的show显示...

潇湘剑雨
55分钟前
1
0
分布式作业系统 Elastic-Job-Lite 源码分析 —— 作业数据存储

分布式作业系统 Elastic-Job-Lite 源码分析 —— 作业数据存储 摘要: 原创出处 http://www.iocoder.cn/Elastic-Job/job-storage/ 本文基于 Elastic-Job V2.1.5 版本分享 1. 概述 本文主要分享...

DemonsI
今天
1
0
jmockit demo

1、@Mocked,标识一个指定的class的实例或被测对象的参数被Mock掉。 2、@Capturing,标识一个被Mock的对象,从该对象派生的子类也被Mock了。 3、@Injectable,标识只有一个指定的被测对象的内...

我的老腰啊
今天
1
0
内容换行

用 <textarea>13611112222 这里想换行 13877779999</textarea><textarea>13611112222 13877779999</textarea>...

小黄狗
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部