LeetCode 面试题50. 第一个只出现一次的字符

2020-05-08 16:09:26来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

LeetCode 面试题50. 第一个只出现一次的字符

我的LeetCode:https://leetcode-cn.com/u/ituring/

我的LeetCode刷题源码[GitHub]:https://github.com/izhoujie/Algorithmcii

LeetCode 面试题50. 第一个只出现一次的字符

题目

在字符串 s 中找出第一个只出现一次的字符。如果没有,返回一个单空格。

示例:
``
s = "abaccdeff"
返回 "b"

s = ""
返回 " "
``

限制:

  • 0 <= s 的长度 <= 50000

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

思路1-直接用JDK的indexOf和lastIndexOf方法

  • indexOf是查首次出现的位置,lastIndexOf是查最后一次出现的位置,若相同就保证了唯一;

算法复杂度:

  • 时间复杂度: $ {\color{Magenta}{\Omicron\left(n^{2}\right)}} $
  • 空间复杂度: $ {\color{Magenta}{\Omicron\left(1\right)}} $

思路2-用LinkedHashMap统计;

  • LinkedHashMap保证了记录顺序和统计次数;

算法复杂度:

  • 时间复杂度: $ {\color{Magenta}{\Omicron\left(n\right)}} $
  • 空间复杂度: $ {\color{Magenta}{\Omicron\left(n\right)}} $

思路3-统计字符出现次数

使用256长度的数组,因为不知道题中字符范围,实际范围可能需要更大点,但是思路不变;

  • 一次遍历记录字符出现次数;
  • 再次遍历找第一个统计到的次数为1的字符即可;

算法复杂度:

  • 时间复杂度: $ {\color{Magenta}{\Omicron\left(n\right)}} $
  • 空间复杂度: $ {\color{Magenta}{\Omicron\left(1\right)}} $

算法源码示例

package leetcode;

import java.util.Iterator;
import java.util.LinkedHashMap;

/**
 * @author ZhouJie
 * @date 2020年5月8日 下午7:54:53 
 * @Description: 面试题50. 第一个只出现一次的字符 
 *
 */
public class LeetCode_Offer_50 {

}

class Solution_Offer_50 {
	/**
	 * @author: ZhouJie
	 * @date: 2020年5月8日 下午7:55:24 
	 * @param: @param s
	 * @param: @return
	 * @return: char
	 * @Description: 1-直接用indexOf和lastIndexOf方法;
	 *
	 */
	public char firstUniqChar_1(String s) {
		for (int i = 0; i < s.length(); i++) {
			char c = s.charAt(i);
			if (s.indexOf(c) == s.lastIndexOf(c)) {
				return c;
			}
		}
		return ' ';
	}

	/**
	 * @author: ZhouJie
	 * @date: 2020年5月8日 下午8:02:06 
	 * @param: @param s
	 * @param: @return
	 * @return: char
	 * @Description: 2-用LinkedHashMap统计;
	 *
	 */
	public char firstUniqChar_2(String s) {
		LinkedHashMap<Character, Integer> map = new LinkedHashMap<Character, Integer>();
		for (char c : s.toCharArray()) {
			map.put(c, map.getOrDefault(c, 0) + 1);
		}
		Iterator<Character> iterator = map.keySet().iterator();
		while (iterator.hasNext()) {
			Character c = iterator.next();
			if (map.get(c) == 1) {
				return c;
			}
		}
		return ' ';
	}

	/**
	 * @author: ZhouJie
	 * @date: 2020年5月8日 下午8:14:41 
	 * @param: @param s
	 * @param: @return
	 * @return: char
	 * @Description: 3-统计字符出现次数;
	 *
	 */
	public char firstUniqChar_3(String s) {
		int[] all = new int[256];
		char[] cs = s.toCharArray();
		for (char c : cs) {
			all[c]++;
		}
		for (char c : cs) {
			if (all[c] == 1) {
				return c;
			}
		}
		return ' ';
	}

}


原文链接:https://www.cnblogs.com/izhoujie/p/12852859.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:开启 Spring 之旅:第一个 Spring 程序 ![Spring][Eclipse 使用

下一篇:java.lang.IllegalStateException: getOutputStream() has alrea