文档章节

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

aqia358
 aqia358
发布于 2013/10/17 11:33
字数 747
阅读 43
收藏 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
剑指offer 54. 字符流中第一个不重复的字符

题目描述 请实现一个函数用来找出字符流中第一个只出现一次的字符。例如,当从字符流中只读出前两个字符"go"时,第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时,第...

dby_freedom
11/25
0
0
python剑指offer66题

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

lyy0905
06/03
0
0

没有更多内容

加载失败,请刷新页面

加载更多

my.ini

1

architect刘源源
9分钟前
0
0
docker dns

There is a opensource application that solves this issue, it's called DNS Proxy Server It's a DNS server that solves containers hostnames, if could not found a hostname that mat......

kut
17分钟前
0
0
寻找数学的广度——《这才是数学》读书笔记2700字

寻找数学的广度——《这才是数学》读书笔记2700字: 文|程哲。数学学习方式之广:国内外数学教育方面的专家,进行了很多种不同的数学学习方式尝试,如数学绘本、数学游戏、数学实验、数学步道...

原创小博客
23分钟前
5
0
ubuntu常用操作

显卡GPU 查看显卡信息sudo lshw -numeric -class video# 查看显卡型号lspci | grep -i nvidia# 查看驱动版本sudo dpkg --list | grep nvidia-*或者 ubuntu-drivers devices#查看显卡...

hc321
昨天
2
0
SpringBoot + Mybatis 配置多数据源(Srping boot 二)

前置条件,你已经配置好spring boot+mybatis,可以参考之前的博客 实现逻辑通过注解+aop切面编程来动态更新datasource 第一步,配置多个DataSource server: port: 8080freezing: ...

小海bug
昨天
15
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部