如何加快第一个唯一字符查找 [英] How to speed up first unique character lookup

问题描述

我正在解决

是否有一些技巧可以提高LeetCode得分？似乎增强型 for-each 循环的性能比标准 for 循环要好，但我无法证明这一点，

解决方案

我得到 98.58 ％的内容是：-

  public int firstUniqChar（String s）{
 int count [] = new int [122-96]; 
 final char [] chars = s.toCharArray（）; 
 for（int i = 0; i< chars.length; i ++）{
 count [chars [i]-97] ++; 
} 
 for（int i = 0; i< chars.length; i ++）{
 if（count [chars [i]-97] == 1）
返回一世; 
} 
返回-1； 
} 
  

I'm solving 387. First Unique Character in a String LeetCode problem defined as:

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.

Taking advantage of the input being fully lowercase ASCII I created two bit vectors to track when we encounter a character for the first and second time.

Can below code be improved further? LeetCode says that below code is better than 94.33% solutions. What else could have been done by the last 5.67% solutions that they were better?

class Solution {

  public int firstUniqChar(String s) {
    int firstSpot = 0;
    int secondSpot = 0;
    char[] chars = s.toCharArray();

    for (char c : chars) {
      int mask = 1 << c - 'a';
      if ((firstSpot & mask) == 0) {
        firstSpot |= mask;
      } else if ((secondSpot & mask) == 0) {
        secondSpot |= mask;
      }
    }

    int i = 0;
    for (char c : chars) {
      int mask = 1 << c - 'a';
      if ((secondSpot & mask) == 0) {
         return i;
      }
      i++;
    }
    return -1;
  }

}

Are there tricks that can be done to improve the LeetCode score? It seems that enhanced for-each loop performs better than standard for loop but I can't prove it, It's an observation based on few of my previous submissions.

解决方案

I got 98.58% with this:-

public int firstUniqChar(String s) {
    int count[] = new int[122 - 96];
    final char[] chars = s.toCharArray();
    for (int i = 0; i < chars.length; i++) {
        count[chars[i] - 97]++;
    }
    for (int i = 0; i < chars.length; i++) {
        if (count[chars[i] - 97] == 1)
            return i;
    }
    return -1;
}

这篇关于如何加快第一个唯一字符查找的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！