This is the 10th day of my participation in the August More Text Challenge. For details, see:August is more challenging

Topic describes

Find the first character in the string s that occurs only once. If not, return a single space. S contains only lowercase letters.

Example: S = "abaccdeff" return "b" s = "" return" https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.Copy the code

Thought analysis

  • The difficulty is to return the first character that appears only once.
  • First, we can use a hashMap to store the number of occurrences of each character. And then you iterate through the string to get the answer. The code is as follows:

code

    public char firstUniqChar(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (char ch : s.toCharArray()) {
            map.put(ch, map.getOrDefault(ch, 0) + 1);
        }
        Set<Character> set = new HashSet<>();
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            if (entry.getValue() == 1) { set.add(entry.getKey()); }}char ans = ' ';
        if (set.size() > 0) {
            for (char ch : s.toCharArray()) {
                if (set.contains(ch)) {
                    ans = ch;
                    break; }}}return ans;
    }
Copy the code
  • This is a simple topic, but it’s easy to write redundant and inefficient code if you’re not careful. Still, it takes a lot of practice to write the lean code below.
    public char firstUniqChar(String s) {
        int[] cnt = new int[256];
        char[] chars = s.toCharArray();
        for (char ch : chars) {
            cnt[ch]++;
        }
        char ans = ' ';
        for (char ch : chars) {
            if (cnt[ch] == 1) {
                ans = ch;
                break; }}return ans;
    }
Copy the code

conclusion

  • The above code is O(n) in time and O(n) in space.
  • The above optimized code, mainly using the IDEA of ASCII code optimization.
  • Briefly introduce the ASCII code related knowledge. In a computer, all data is stored and processed using binary numbers (because the computer uses high and low levels to represent 1 and 0, respectively). ASCII is the general specification for storage.

An ASCII code uses a specified combination of 7 – or 8-bit binary numbers to represent 128 or 256 possible characters. Standard ASCII code, also known as basic ASCII code, uses 7-digit binary numbers to represent all uppercase and lowercase letters, digits 0 to 9, and punctuation marks. 32 to 126(a total of 95) are characters (32SP is space), and 48 to 57 are 0 to 9 Arabic digits. There are 26 uppercase letters from 65 to 90, 26 lowercase letters from 97 to 122, and the rest are punctuation marks and operation symbols.

  • Stick to a daily question, come on!