在一个长为 字符串中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1(需要区分大小写).(从0开始计数)
数据范围:,且字符串只有字母组成。
要求:空间复杂度 ,时间复杂度
//可以利用哈希表或者map,set class Solution { public: int FirstNotRepeatingChar(string str) { map<char,int>m; for(int i=0;i<str.size();++i) ++m[str[i]]; int i; for(i=0;i<str.size();++i) { if(m[str[i]]==1) return i; } if(i<str.size()) return str.size()-1; else return -1; } };
class Solution: def FirstNotRepeatingChar(self, s): # write code here if len(s)<0: return -1 for i in s: if s.count(i)==1: return s.index(i) break return -1书中所述创建哈希表,下标为ACII值,值为出现次数
#建立哈希表,字符长度为8的数据类型,共有256种可能,于是创建一个长度为256的列表 ls=[0]*256 #遍历字符串,下标为ASCII值,值为次数 for i in s: ls[ord(i)]+=1 #遍历列表,找到出现次数为1的字符并输出位置 for j in s: if ls[ord(j)]==1: return s.index(j) break return -1
#方法一:利用数组自己建立个哈希表 class Solution: def FirstNotRepeatingChar(self, s): # write code here if s==' ': return -1 hashtable=[0]*256 for i in s: hashtable[ord(i)] += 1 for i in s: if hashtable[ord(i)]==1: return s.index(i) return -1 #方法二:利用python自带的字典 class Solution: def FirstNotRepeatingChar(self, s): # write code here if s==' ': return -1 d=dict() #第一次遍历字符串,将每个字符的次数存入字典 for i in s: d[i]=d.get(i,0)+1 #第二次遍历字符串,检查每个字符出现的次数 for i in s: if d[i]==1: #O(1) return s.index(i) return -1
public class Solution { public int FirstNotRepeatingChar(String str) { if (str.length() == 0) { return -1; } char c = 'A'; if(str.charAt(0) >= 'a'){ c = 'a'; } int[] counts = new int[26]; for (int i = 0; i < str.length(); i++) { counts[str.charAt(i) - c]++; } for (int i = 0; i < str.length(); i++) { if (counts[str.charAt(i) - c] == 1){ return i; } } return -1; } }
class Solution { public: //坑爹啊,说长度在1<=length<=1000的,结果放了个空,返回-1. //说是大写字母,结果给个google什么意思。还是做了个256的hash表。 int FirstNotRepeatingChar(string str) { unsigned int ch[256]={0}; if(str.length()<=0) return -1; for(int i=0;i<str.length();i++) { ch[(int)str[i]]++; } for(int i=0;i<str.length();i++) { if(ch[(int)str[i]]==1) return i; } return -1; } };
Map<Character, Integer> map = new HashMap<>();char[] arr = str.toCharArray();
public class Solution { public int FirstNotRepeatingChar(String str) { char[] chars = str.toCharArray(); int[] map = new int[256]; for (int i = 0; i < chars.length; i++) { map[chars[i]]++; } for (int i = 0; i < chars.length; i++) { if (map[chars[i]] == 1) return i; } return -1; } }
//感觉自己的代码比较清晰 class Solution { public: int FirstNotRepeatingChar(string str) { int i; if(str.length()<1) return -1; for(i=0;i<str.length();i++){ int position1=str.find(str[i]); int position2=str.rfind(str[i]); if(position1!=position2) continue; else break; } return i; } };
import java.util.HashMap; public class Solution { public int FirstNotRepeatingChar(String str) { HashMap<Character, Integer> hashMap = new HashMap<Character, Integer>(); for (int i = 0; i < str.length(); i++) { if (!hashMap.containsKey(str.charAt(i))) { hashMap.put(str.charAt(i), 1); } else { hashMap.put(str.charAt(i), hashMap.get(str.charAt(i)) + 1); } } for (int i = 0; i < str.length(); i++) { if(hashMap.get(str.charAt(i))==1){ return i; } } return -1; } }
public int FirstNotRepeatingChar(String str) { for (int i = 0; i < str.length(); i++) { // 第一次出现的位置和最后一次出现的位置一样 while (str.indexOf(str.charAt(i)) == str.lastIndexOf(str.charAt(i))) { return i; } } return -1; }
class Solution { public: int FirstNotRepeatingChar(string str) { int size = str.size(); if (size<1 || size>10000) return -1; set<char> s1; set<char> s2; for (int i = 0; i < size; i++) { if (!s1.insert(str[i]).second) s2.insert(str[i]); } if (s1.empty()) return -1; for (int j = 0; j < size; j++) { if (s2.insert(str[j]).second) return j; } return -1; } };
一共有256个字符,每个字符用2位来记录它当前出现的次数,00表示没有出现,01表示出现1次,10表示出现两次以上,所以bitmap的大小应该为256*2=512 bit,一个int是四个字节,32bit,所以需要大小为16的int数组就可以存储所有的表示
class Solution {
public:
int FirstNotRepeatingChar(string str) {
int* bitmap = new int[16]();
int arr_idx, bit_idx;
for(int i = 0; i < str.length(); ++i){
arr_idx = str[i] * 2 / 32;
bit_idx = str[i] * 2 % 32;
if(((bitmap[arr_idx] >> bit_idx) & 1) == 0){
bitmap[arr_idx] |= (1 << bit_idx);
}else if(((bitmap[arr_idx] >> (bit_idx+1)) & 1) == 0){
bitmap[arr_idx] |= (1 << (bit_idx+1));
}
}
for(int i = 0; i < str.length(); ++i){
arr_idx = str[i] * 2 / 32;
bit_idx = str[i] * 2 % 32;
if(((bitmap[arr_idx] >> bit_idx) & 1) == 1 && ((bitmap[arr_idx] >> (bit_idx+1)) & 1) == 0){
return i;
}
}
return -1;
}
};
/*解题思路: 这个方法可能有点笨哈,请大神批评指正><: 从第一个字符开始和每一个字符相比较,当遇到和自己相同并且不是同一个位置时, 直接跳出内循环,从下一个字符开始和每一个比较,一旦出现不同的的时判断是否到了 字符串的末尾,不是的话继续比较,否则的话,返回外循环的值 (此时外循环的值正是第一个不重复字符). */ class Solution { public: int FirstNotRepeatingChar(string str) { int len = str.length(); if(len == 0) return -1; for(int i = 0;i < len;i++){ for(int j = 0;j < len;j++){ if(str[i] == str[j] && i != j){ break; } if(i != j && str[i] != str[j]){ if(j == len -1 ) return i; else continue; } } } return -1; } };
import java.util.ArrayList; /** *用ArrayList存储字符数组,每次删除字符数组中一种字符 *若删除后字符数组长度-1,则证明该字符只出现一次 */ public class Solution { public int FirstNotRepeatingChar(String str) { if(str.equals("")) return -1; for(int j = 0;j < str.length();j++){ ArrayList<Character> list = new ArrayList<Character>(); for(int i = 0;i < str.length();i++){ list.add(str.charAt(i)); } for(int i = 0,len = list.size();i < len;i++ ){ if(list.get(i) == str.charAt(j)){ list.remove(i); --len; --i; } } if(str.length() - list.size() == 1) return j; } return 0; } }
public class Solution_35 { public int FirstNotRepeatingChar(String str) { if(str.equals("")) return -1; int[][] map = new int[58][2]; for (int i = 0; i < str.length(); i++) { char c = str.charAt(i); int pos = c - 'A'; if(map[pos][0] == 0){ map[pos][1] = i; } map[pos][0]++; } int ret = Integer.MAX_VALUE; for (int i = 0; i < 58; i++) { if(map[i][0] == 1){ ret = Math.min(ret, map[i][1]); } } return ret; } }
class Solution { public: int FirstNotRepeatingChar(string str) { int len=str.length();//也可以用size(); if(len<1||len>10000) return -1; int hashmap[256]={0},i; for(i=0;i<len;i++){ hashmap[str[i]]++; } for(i=0;i<len;i++){ if(hashmap[str[i]]==1) return i; } return -1; } };
//题目各种坑 class Solution { public: int FirstNotRepeatingChar(string str) { int length = str.size(); int i=0; if(length==0) return -1; const int tableSize = 26; unsigned int hashTable[tableSize]; for(int i=0;i<tableSize;i++) hashTable[i]=0; i=0; while(str[i]!='\0') { hashTable[str[i++]-'a']++; } i=0; while(str[i]!='\0') { if(hashTable[str[i++]-'a']==1) break; } if(str[i]=='\0') return -1; else return i-1; } };