第一个只出现一次的字符

题目各种坑...
class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        if(str.length()==0)
            return -1;
        int hash[256]={0};
        int i=0;
        while(str[i]!='\0'){
            hash[str[i]]++;
            ++i;
        }
        i=0;
        while(str[i]!='\0'){
            if(1==hash[str[i]]){
                return i;
            }
            i++;
        }
        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;
    }
}

    def FirstNotRepeatingChar(self, s):
        if s == "":
            return -1
        else:
            counts = {}
            for i in s:
                if i not in counts:
                    counts[i] = 1
                else:
                    counts[i] += 1
            for index,i in enumerate(s):
                if counts[i] == 1:
                    return index

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<>();

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;
    }
}

function FirstNotRepeatingChar(str)
{
    for(let i = 0 ;i < str.length; i++){
        if(str.indexOf(str[i]) === str.lastIndexOf(str[i])){
            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;
	}
};

bitmap法求解，空间最优

一共有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;
    }
};