字符流中的第一个非重复字符

Question

题目要求我们找到新的字符串B。

B 的构成使得每次向流中插入一个字符时我们都必须找到第一个非重复字符，并将其追加到 B 的末尾。如果没有找到非重复字符，则追加 '#' B.

结尾

Example:
    "a"      -   first non repeating character 'a'
    "ab"     -   first non repeating character 'a'
    "aba"    -   first non repeating character 'b'
    "abad"   -   first non repeating character 'b'
    "abadb"  -   first non repeating character 'd'
    "abadbc" -   first non repeating character 'd'

谁能帮我解决我的代码哪里出错了。我的逻辑是使用字符串的子字符串函数并找到唯一字符并将其添加到数组列表并打印整个数组列表。

public class Solution
{
    public String solve(String A) 
    {
        ArrayList<Character>a=new ArrayList<Character>();
        String res="";

        for(int i=0;i<A.length();i++)
        { 
            String ss=A.substring(0,i+1);
            String ue=uniqueCharacters(ss);
           // System.out.println(ue);
      
           if(ue!="") a.add(ue.charAt(0));
           else a.add('#');
        } 
     
        for(Character j:a) res+=j;
    
        return res;
    } 

    public static String uniqueCharacters(String test)
    {
        String temp = "";
    
        for (int i = 0; i < test.length(); i++)
        {
            char current = test.charAt(i);
            if (temp.indexOf(current) < 0) temp = temp + current;
            else temp = temp.replace(String.valueOf(current), "");
        }

        return temp;
    }
}

Answer 1

当您第二次遇到一个字符时，您将其从唯一字符 (1) 中删除，但如果该字符有第三个，则会再次添加 (2)。

public static String uniqueCharacters(String test)
    {
        String temp = "";
    
        for (int i = 0; i < test.length(); i++)
        {
            char current = test.charAt(i);
            if (temp.indexOf(current) < 0) temp = temp + current; <---- (2)
            else temp = temp.replace(String.valueOf(current), ""); <----- (1)
        }

        return temp;
    }

解决方案计算字符数，然后 return 仅计算计数为 1（一）的字符。

Answer 2

最好使用 Set 检测输入字符串中的唯一字符，使用 Set::add 的结果，其中 returns false 如果没有元素实际上添加到集合中，并且一个Queue来保持不重复的字符。

当检测到重复（非唯一）字符时，会将其从队列中删除，如有必要，"#" 将用作占位符。如果检测到唯一字符，则将其添加到队列中。

示例实现：

public static String solve(String str) {
    // verify the input
    if (null == str || str.isEmpty()) {
        return str;
    }
    
    Set<Character> previous = new LinkedHashSet<>();
    Queue<Character> nonRepeated = new LinkedList<>();
    
    StringBuilder sb = new StringBuilder();

    // use the first character
    char curr = str.charAt(0);
    previous.add(curr);
    nonRepeated.add(curr);
    sb.append(curr);
    
    for (int i = 1, n = str.length(); i < n; i++) {
        char c = str.charAt(i);
        
        if (!previous.add(c)) { // duplicate character found
            nonRepeated.remove(c);
            if (nonRepeated.isEmpty()) {
                curr = '#';
            } else { // get the next non-repeated character
                curr = nonRepeated.peek();
            }
        } else { // unique element is detected
            if (curr == '#') {
                curr = c;
            }
            nonRepeated.add(c);
        }
        
        sb.append(curr);
    }
    
    return sb.toString();
}

测试：

for (String t : Arrays.asList("abadbc", "abcdba", "aaabbbacab")) {
    System.out.printf("input: %s --> %s%n----%n", t, solve(t));
}

输出：

input: abadbc --> aabbdd
----
input: abcdba --> aaaaac
----
input: aaabbbacab --> a##b###ccc
----

字符流中的第一个非重复字符

First non-repeating character in a stream of characters

java

string

algorithm

collections

arraylist