Je résous 387. Premier caractère unique dans une chaîne Problème LeetCode défini comme:

Étant donné une chaîne, recherchez le premier caractère non répétitif et renvoyez son index. S'il n'existe pas, renvoie -1.

Exemples:

s = "leetcode"
return 0.

s = "loveleetcode",
return 2.

Remarque: Vous pouvez supposer que la chaîne ne contient que des lettres minuscules.

Profitant du fait que l'entrée est entièrement en minuscules ASCII, j'ai créé deux vecteurs de bits à suivre lorsque nous rencontrons un caractère pour la première et la deuxième fois.

Le code ci-dessous peut-il être amélioré davantage? LeetCode dit que le code ci-dessous est meilleur que les solutions à 94,33%. Qu'est-ce qui aurait pu être fait d'autre par les dernières solutions à 5,67% pour dire qu'elles étaient meilleures?

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

}

LeetCode score

Y a-t-il des astuces qui peuvent être faites pour améliorer le score LeetCode? Il semble que la boucle for-each améliorée fonctionne mieux que la boucle for standard mais je ne peux pas le prouver, c'est une observation basée sur quelques-unes de mes soumissions précédentes.

0
Karol Dowbecki 20 nov. 2018 à 02:00

3 réponses

Meilleure réponse

J'ai eu 98,58 % avec ceci: -

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

enter image description here

2
Kartik 20 nov. 2018 à 00:19

Comme le dit @Ruakh dans un commentaire, les horaires précis produits par leetcode sont soumis à un certain caractère aléatoire, ils doivent donc être pris avec un grain de sel:

J'ai l'impression que LeetCode fait un microbenchmark non scientifique qui pourrait dépendre de facteurs aléatoires.

Pourtant, il est possible d'accélérer un peu votre première boucle en supprimant les tests. La boucle suivante est fonctionnellement équivalente; bien qu'il définisse les variables plus souvent, changer la valeur d'une variable locale entière coûte moins cher que de tester s'il est nécessaire de changer:

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

(Il est important que l'affectation soit dans cet ordre, afin que la première ne fasse rien si le personnage n'a pas encore été vu.)

1
rici 20 nov. 2018 à 14:34

Utilisez ceci:

import java.util.Arrays;

class Solution {
    //  0x60 < 'a' < 'z' < 0x80
    private final byte[] bCounter = new byte[0x80];
    private final int[] iCounter = new int[0x80];

    public int firstUniqChar(String s) {
        int len = s.length();
        if ((len & 0xff) == len) {
            Arrays.fill(bCounter, 0x60, 0x80, (byte)-1);
            for (int i = 0; i < len; i++)
                bCounter[s.charAt(i)]++;
            for (int i = 0; i < len; i++)
                if (bCounter[s.charAt(i)] == 0)
                    return i;
        } else {
            Arrays.fill(iCounter, 0x60, 0x80, -1);
            for (int i = 0; i < len; i++)
                iCounter[s.charAt(i)]++;
            for (int i = 0; i < len; i++)
                if (iCounter[s.charAt(i)] == 0)
                    return i;
        }
        return -1;
    }
}
1
John McClane 23 nov. 2018 à 07:25