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

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

最好使用

Set

来检测输入字符串中的唯一字符，使用

Set::add

的结果，如果没有元素实际添加到集合中，则返回

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

Answer 2

当您第二次遇到某个字符时，您可以将其从唯一字符中删除 (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;
    }

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

Answer 3

使用 java 8 从字符串中查找非重复字符的简单方法：

公开课主课{

public static void main(String[] args) {

    String s="AAHJAKTMJ";

    Map<String, Long> counts = Arrays.stream(s.split(""))
            .collect(Collectors.groupingBy(i -> i, Collectors.counting()));

    // Display repeating elements and their counts
    counts.forEach((element, count) -> {
        if (count == 1) {
            System.out.println("Non Repeating Character From String: " +element);
        }
    });
}

}