每天一道leetcode387-字符串中第一個唯一的字符

• 2019 年 10 月 4 日
• 筆記

昨天的題解

題目

每天一道leetcode387-字符串中第一個唯一的字符 分類：字符串

題目詳述

給定一個字符串，找到它的第一個不重複的字符，並返回它的索引。如果不存在，則返回 -1。

案例:

s = "leetcode" 返回 0.

s = "loveleetcode", 返回 2.

注意事項：您可以假定該字符串只包含小寫字母。

題目詳解

思路

• 由於只有26個小寫字母，可以把用一個數組表示26個字母，數組長度26，第0位代表a,第1位代表b,….(這裡利用ASC碼進行轉換）
• 首先設置一個index=1,然後遍歷字符串s,如果數組中比如對於字符串中a來說，也就是數組下標為0，array[0]如果字符a第一次出現，那麼array[0] = index;然後index++;每第一次出現就把對應的數組下標賦值為index；
• 如果已經出現了，那麼array[i]必然是一個不等於0的大於0的數，那麼就把array[i] = -1;
• 一趟循環以後，遍歷array數組，找到不等於-1的（出現兩次及以上）不等於0的 （要出現，等於0就是沒出現），然後在裏面找index數字最小的，因為在前面index每次都會進行自增，所以index最小的第一次出現的字符

代碼

class Solution {      public int firstUniqChar(String s) {          int index = 1;          int [] array = new int [26];//數組          for(int i=0;i<s.length();i++)          {              int cha  = (int)s.charAt(i) - 97;//根據ASC碼 字符轉數組下標              if(array[cha] == 0)//說明第一次出現              {                  array[cha] = index;//把index值賦值給他                  index++;//然後index務必+1，這樣字符串中以後的字符就算第一次出現，也是index值比第一個第一次出現的index的值大的。              }else{                  array[cha] = - 1;//如果已經出現了，那麼就數組賦值為-1              }          }          int resultIndex = Integer.MAX_VALUE;          char result = '#';          for(int i=0;i<array.length;i++)          {//遍曆數組，找到index最小的那個字符              if(array[i] > 0)              {                  if(array[i] < resultIndex)//每次都找較小的index的，因為index越小，在字符串的位置越靠前，也就是越靠近第一次出現的字符                  {                      resultIndex = array[i];                      result = (char)(i+97);                  }              }          }          if(result == '#')              return -1;//沒找到，返回-1          for(int i=0;i<s.length();i++)          {              if(s.charAt(i) == result)                  return i;//因為要返回字符在字符串的下標，所以去字符串中去尋找字符的下標，然後返回。          }          return -1;  }  }