【九度OJ1283】|【剑指offer35】第一个只出现一次的字符
博客专区 > aqia358 的博客 > 博客详情
【九度OJ1283】|【剑指offer35】第一个只出现一次的字符
aqia358 发表于5年前
【九度OJ1283】|【剑指offer35】第一个只出现一次的字符
  • 发表于 5年前
  • 阅读 42
  • 收藏 1
  • 点赞 0
  • 评论 0

【腾讯云】新注册用户域名抢购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);
		}
	}
}
  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 6
博文 81
码字总数 30297
×
aqia358
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: