java 字符串的第一个唯一字符-Leetcode

yzuktlbb  于 12个月前  发布在  Java
关注(0)|答案(8)|浏览(198)

我试过 * 387.First Unique Character In A string *
给定一个字符串s,找到其中第一个不重复的字符并返回其索引。如果不存在,返回-1。

  • 示例:1*
Input: s = "leetcode"
 
 Output: 0

字符串

  • 示例:2*
Input: s = "loveleetcode"

 Output: 2


我一直在尝试这个问题。我想我们会一个接一个地选择所有的字符,并检查是否存在重复的字符,从循环中中断。如果没有,然后返回该索引。我已经想过一个解决方案,我认为这不是最有效的方法,但我想知道我如何解决这个问题,下面给出的方法:

public int firstUniqChar(String s) {
  for(int i=0;i<s.length();i++){
      for(int j=i+1;j<s.length();j++){
          if(s.charAt(i)==s.charAt(j)){
              break;
          }
          
      }
      
  }
    return -1;
}


我搞不懂怎么返回索引,找不到后面的逻辑:

for(int j=i+1;j<s.length();j++){
              if(s.charAt(i)==s.charAt(j)){
                  break;
              }
              
          }


如果有人能帮我找出这里的逻辑。

v7pvogib

v7pvogib1#

试试这个.

public static int firstUniqChar(String s) {
    L: for (int i = 0, length = s.length(); i < length; i++) {
        for (int j = 0; j < length; j++)
            if (i != j && s.charAt(i) == s.charAt(j))
                continue L;
        return i;
    }
    return -1;
}

public static void main(String[] args) {
    System.out.println(firstUniqChar("leetcode"));
    System.out.println(firstUniqChar("loveleetcode"));
    System.out.println(firstUniqChar("aabb"));
}

字符串
产出:

0
2
-1

mmvthczy

mmvthczy2#

可以使用flag变量。

public int firstUniqChar(String s) {
     int flag=0;
     for(int i=0;i<s.length();i++){
        flag=0;
        for(int j=0;j<s.length();j++){
            if(s.charAt(i)==s.charAt(j) && i!=j){
                flag=1;
                break;
            }
        }
        if(flag==0){
            return i;
        } 
    }
   return -1;
}

字符串

goucqfw6

goucqfw63#

有26个可能的英文字母,所以你可以使用两个26元素数组。
一个数组letterCount保存每个字母的计数。从0开始,每当相应的字母出现在文本字符串中时加1。第二个数组position保存该字母第一次出现的位置,或者如果该字母从未出现则为-1。您需要将该数组的所有元素初始化为-1。
按顺序处理字符串,记录初始位置,每个字母只记录一次,并递增字符串中每个字母的计数。
处理完字符串后,查看letterCount数组。如果没有计数为1的字母,则返回-1。如果恰好有一个字母计数为1,则返回position数组中该字母的位置。如果有多个字母计数为1,则选择其位置值最小的字母。
使用两个循环是解决这个问题的一种非常低效的方法。字符串可以长达100,000个字符,并且您正在多次处理它。最好只处理一次,跟踪到目前为止找到的内容。

x33g5p2x

x33g5p2x4#

修复你的代码

您需要添加一个变量,告诉您是否已中断循环

static int firstUniqChar(String s) {
    boolean duplicate;
    for (int i = 0; i < s.length(); i++) {
        duplicate = false;
        for (int j = i + 1; j < s.length(); j++) {
            if (s.charAt(i) == s.charAt(j)) {
                duplicate = true;
                break;
            }
        }
        if (!duplicate) {
            return i;
        }
    }
    return -1;
}

字符串

提升

有一个更聪明的方法,那就是找到当前字符的最后一个索引,如果它等于当前索引:那个字符是唯一的,你返回它的索引

static int firstUniqChar(String s) {
    for (int i = 0; i < s.length(); i++) {
        if (s.lastIndexOf(s.charAt(i)) == i) {
            return i;
        }
    }
    return -1;
}

yjghlzjz

yjghlzjz5#

如果你不担心使用IdenxOF操作的时间复杂度,那么你可以尝试这个解决方案。

indexOf()-也是线性时间运行的。它遍历内部数组并逐个检查每个元素。因此此操作的时间复杂度始终需要O(n)时间。

int firstUniqCharOneLoop(String str) {
            for (int i = 0; i < str.length(); i++) {
                if (str.indexOf(str.charAt(i))== str.lastIndexOf(str.charAt(i)) ) {
                    return i;
                }
            }
            return -1;
        }

字符串

ru9i0ody

ru9i0ody6#

我设法实现的最低复杂度:

public class UniqueSymbolFinder {
    static int findFirstUniqueChar(String s) {
        Set<Character> set = new HashSet<>(s.length());
        List<CharWithIndex> candidates = new LinkedList<>();

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            CharWithIndex charWithIndex = new CharWithIndex(ch, i);
            
            if (set.add(ch)) {
                candidates.add(charWithIndex);
            } else {
                candidates.remove(charWithIndex);
            }
        }
        return candidates.size() == 0 ? -1 : candidates.get(0).index;
    }

    /**
     * Class for storing the index. 
     * Used to avoid of using an indexOf or other iterations.
     */
    private static class CharWithIndex {
        int index;
        char ch;

        private CharWithIndex(char ch, int index) {
            this.ch = ch;
            this.index = index;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            CharWithIndex that = (CharWithIndex) o;
            return ch == that.ch;
        }

        @Override
        public int hashCode() {
            return Objects.hash(ch);
        }
    }
}

字符串
我相信内存使用仍然可以优化。

u1ehiz5o

u1ehiz5o7#

100%正确的JAVA解决方案

因为这个问题是关于返回字符串中第一个非重复字符的索引,所以我们需要一些数据结构来保存字符串中每个字符的索引。
这里我选择Java的HashMap。基本上,你可以用它做什么,你可以保存一对值(或一对其他数据结构)。
所以,在我的解决方案中,我保存了一个Character * 字符串对。第一个被认为是一个键(这里是字符串中的每个字符),第二个是它的索引值
这里的问题是,我们只想保留非重复字符的最小索引,这就是为什么如果你看看下面,你会发现maxIndexForRepeatedValues被设置为10power5,因为输入约束说1 <= s.length <= 10 power 5
然而,我使用这个值来忽略在HashMap中会找到的重复字符,最后,我们检索最小索引,当然是Map中第一个字符的索引,或者如果只有重复字符,我们返回**-1**。
为了使代码更短,我使用了ternary-operator,但如果你愿意,你可以用if-else来写它!

class Solution {
    public int firstUniqChar(String s) {

        int maxIndexForRepeatedValues = 100000;
        Map<Character, Integer> map = new HashMap<>();

        for (int i = 0 ; i < s.length() ; i++) {

            char key = s.charAt(i);
            int resIndex = map.containsKey(key) ? maxIndexForRepeatedValues : i;
            map.put(key, resIndex);

        }

        int minIndex = Collections.min(map.values());
        return minIndex == maxIndexForRepeatedValues ? -1 : minIndex;
    }
}

字符串

gj3fmq9x

gj3fmq9x8#

class Solution {
    public int firstUniqChar(String s) {
        for(int i=0;i<s.length();i++){
        char current =s.charAt(i);
        if(s.indexOf(current)==s.lastIndexOf(current)){
            return i;
        }
        }
    return -1;
  }
}

字符串

相关问题