ITKeyword,专注技术干货聚合推荐

注册 | 登录

算法与数据结构面试题(21)-在一个字符串中找到第一个只出现一次的字符

qhshiniba 分享于 2014-12-30

推荐:15. Google面试题:在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff,则输出b

题目:在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff,则输出b。 分析: 一般方法是使用每个字符间都比较一次,算法复杂度为o(n^2) 可以使用空间

2020腾讯云共同战“疫”,助力复工(优惠前所未有!4核8G,5M带宽 1684元/3年),
地址https://cloud.tencent.com/act/cps/redirect?redirect=1053

2020阿里云最低价产品入口,含代金券(新老用户有优惠),
地址https://www.aliyun.com/minisite/goods

题目


在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff,则输出b。

解题思路


上一道题是求字符串中各个字符的个数,其实大同小异,这道题比上道题还要简单点,只需要得到第一个为1的就结束遍历。比较容易。但是需要改造一些之前的代码


推荐:一道面试题:从一个字符串中找出第一个不重复字符;算法一;

一道面试题:从一个字符串中找出第一个不重复字符;比如对于字符串abbbccdefafgg,其中d、e只出现一次,只需要找出d(第一个出现的不重复字符)即可 。 import jav

public class CharCount {

	public void count(String str) {
		if (str == null || str.length() == 0) {
			return;
		}
		StringBuilder builder = new StringBuilder(str.length());
		isContainsChar(str, str.length(), builder);
		if (builder.length() == 0) {
			System.out.println("无任何字符");
			return;
		}
		// 有序hashmap来统计所有字符的个数,时间复杂度为O(n)
		Map<Character, Integer> countMap = new LinkedHashMap<Character, Integer>();
		for (int i = 0; i < builder.length(); i++) {
			Character c = builder.charAt(i);
			if (countMap.containsKey(c)) {
				int num = countMap.get(c);
				countMap.put(c, ++num);
			} else {
				countMap.put(c, 1);
			}
		}

		System.out.println("含有字符: " + builder);
		printCountInfo(countMap);
		// 遍历map
		if (!countMap.containsValue(1)) {
			System.out.println("该字符串中不含有只出现一次的字符");
			return;
		}
		Set<Map.Entry<Character, Integer>> set = countMap.entrySet();
		Iterator<Entry<Character, Integer>> iterator = set.iterator();
		while (iterator.hasNext()) {
			Entry<Character, Integer> entry = iterator.next();
			if (entry.getValue() == 1) {
				System.out.println("第一个只出现一次的字符为  : "
						+ entry.getKey());
				return;
			}
		}

	}

	private void isContainsChar(String str, int length, StringBuilder builder) {
		str = str.toLowerCase();
		Pattern pattern = Pattern.compile("[a-z]+");
		Matcher matcher = pattern.matcher(str);
		int k = 0;
		while (k < length) {
			if (matcher.find()) {
				builder.append(matcher.group());
				if (matcher.end() == length) {
					// System.out.println("over");
					break;
				}
			}
			k++;
		}
	}

	private void printCountInfo(Map<Character, Integer> map) {
		if (!map.isEmpty()) {
			Set<Entry<Character, Integer>> set = map.entrySet();
			Iterator<Entry<Character, Integer>> iter = set.iterator();
			while (iter.hasNext()) {
				Entry<Character, Integer> entry = iter.next();
				System.out.println(String.format("%c : %d", entry.getKey(),
						entry.getValue()));
			}
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String[] strArray = { "123456",// 测试无字符的情况,能否区分数字
				"“   $@!-=)(&^%#@!",// 测试无字符的情况,能否区分特殊符号
				"asdfsewrewe",// 测试小写字符的统计
				"ASDFDSFWEGSDFSD",// 测试大写字符的统计
				"12324aasdfds",// 测试小写字符和非字符组合的情况
				"12324ASDFDSFWEGSDFSD",// 测试大写字符和非字符组合的情况
				"aasdfdsASDFDSFWEGSDFSD",// 测试小写和大写组合的情况
				"aasdfdsASDFDSFWEGSDFSD“   $@!-=)(&^%#@!",// 测试小写、大写和非字符组合的情况
				null,// 测试空字符串的情况
				""// 测试字符串大小为0的情况
		};
		CharCount charCount = new CharCount();
		for (String str : strArray) {
			System.out.println(String.format("字符串 %s中字符分配情况:", str));
			charCount.count(str);
			System.out.println("=================================");
		}

	}
}

执行程序输出结果


字符串 123456中字符分配情况:
无任何字符
=================================
字符串 “   $@!-=)(&^%#@!中字符分配情况:
无任何字符
=================================
字符串 asdfsewrewe中字符分配情况:
含有字符: asdfsewrewe
a : 1
s : 2
d : 1
f : 1
e : 3
w : 2
r : 1
第一个只出现一次的字符为  : a
=================================
字符串 ASDFDSFWEGSDFSD中字符分配情况:
含有字符: asdfdsfwegsdfsd
a : 1
s : 4
d : 4
f : 3
w : 1
e : 1
g : 1
第一个只出现一次的字符为  : a
=================================
字符串 12324aasdfds中字符分配情况:
含有字符: aasdfds
a : 2
s : 2
d : 2
f : 1
第一个只出现一次的字符为  : f
=================================
字符串 12324ASDFDSFWEGSDFSD中字符分配情况:
含有字符: asdfdsfwegsdfsd
a : 1
s : 4
d : 4
f : 3
w : 1
e : 1
g : 1
第一个只出现一次的字符为  : a
=================================
字符串 aasdfdsASDFDSFWEGSDFSD中字符分配情况:
含有字符: aasdfdsasdfdsfwegsdfsd
a : 3
s : 6
d : 6
f : 4
w : 1
e : 1
g : 1
第一个只出现一次的字符为  : w
=================================
字符串 aasdfdsASDFDSFWEGSDFSD“   $@!-=)(&^%#@!中字符分配情况:
含有字符: aasdfdsasdfdsfwegsdfsd
a : 3
s : 6
d : 6
f : 4
w : 1
e : 1
g : 1
第一个只出现一次的字符为  : w
=================================
字符串 null中字符分配情况:
=================================
字符串 中字符分配情况:
=================================




推荐:【面试题】:统计一串字符串中仅出现一次的第一个字符

这个题思路就是,利用hash表把所有的字符存储进去,然后通过链表寻找的方式来找到第一个仅出现一次的字符 跟我前面做的一道OJ题非常类似,这道题值得称道的地方

题目 在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff,则输出b。 解题思路 上一道题是求字符串中各个字符的个数,其实大同小异,这道题比上道题还要简单点,只需要得到第一个为1的

相关阅读排行


相关内容推荐

最新文章

×

×

请激活账号

为了能正常使用评论、编辑功能及以后陆续为用户提供的其他产品,请激活账号。

您的注册邮箱: 修改

重新发送激活邮件 进入我的邮箱

如果您没有收到激活邮件,请注意检查垃圾箱。