LeetCode Top Interview Questions 387. First Unique Character in a String (Java版; Easy)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode Top Interview Questions 387. First Unique Character in a String (Java版; Easy)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2454字，纯文字阅读大概需要4分钟。
内容图文
welcome to my blog
LeetCode Top Interview Questions 387. First Unique Character in a String (Java版; Easy)
题目描述
Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1.
Examples:
s = "leetcode"
return 0.
s = "loveleetcode",
return 2.
Note: You may assume the string contain only lowercase letters.
第一次做;bit-map记录每个字符出现的次数, 位置信息在原始字符串中; 下面的那个做法在处理位置信息时愚蠢了…
class Solution {
public int firstUniqChar(String s) {
if(s==null||s.length()==0)
return -1;
//
int[] arr = new int[26];
for(int i=0; i<s.length(); i++){
char ch = s.charAt(i);
arr[ch-'a']++;
}
for(int i=0; i<s.length(); i++){
char ch = s.charAt(i);
if(arr[ch-'a']==1)
return i;
}
return -1;
}
}
第一次做;bit-map记录出现次数; StringBuilder记录位置信息(这么做就麻烦了… 直接再遍历一次原始字符串即可); 时间复杂度O(N), 空间复杂度O(N)
/**
26个英文字母, 使用bit-map, 记录每个字符出现的次数, 再配合一个StringBuilder记录扫描过的字符从而保留位置信息
向面试官确认一下是否只有26个英文小写/大写字母
如果是全体ascii的话就需要一个更大一些的数组
*/
class Solution {
public int firstUniqChar(String s) {
if(s==null||s.length()==0)
return -1;
//
int[] arr = new int[26];
StringBuilder sb = new StringBuilder();
for(int i=0; i<s.length(); i++){
char ch = s.charAt(i);
arr[ch-'a']++;
sb.append(ch);
}
for(int i=0; i<sb.length(); i++){
char ch = sb.charAt(i);
if(arr[ch-'a']==1)
return i;
}
return -1;
}
}
leetcode题解中关于该问题的其它思考
Good O(n) solution, but it still can be improved, since you read through the whole array twice.
Take an example of DNA sequence: there could be millions of letters long with just 4 alphabet
letter. What happened if the non-repeated letter is at the end of DNA sequence? This would
dramatically increase your running time since we need to scan it again.
可以使用两个哈希表解决上述问题, 一个哈希表记录出现次数, 另一个哈希表记录索引. 最后遍历第一个哈希表; 我对遍历哈希表的语法不熟
class Solution {
public int firstUniqChar(String s) {
Map<Character, Integer> feq = new HashMap<>();
Map<Character, Integer> index = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
feq.put(s.charAt(i), feq.getOrDefault(s.charAt(i), 0) + 1);
index.put(s.charAt(i), i);
}
int min = Integer.MAX_VALUE;
for (char c : feq.keySet()) {
if (feq.get(c) == 1) {
min = Math.min(min, index.get(c));
}
}
return min == Integer.MAX_VALUE ? -1 : min;
}
}
内容总结
以上是互联网集市为您收集整理的LeetCode Top Interview Questions 387. First Unique Character in a String (Java版; Easy)全部内容，希望文章能够帮你解决LeetCode Top Interview Questions 387. First Unique Character in a String (Java版; Easy)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。