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

Question

这个问题要求我们找到新的字符串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'

有人能帮我找出我的代码哪里出了问题吗。我的逻辑是使用字符串的子字符串函数，找到唯一的字符并将其添加到arraylist中，然后打印整个arraylist。

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(一(的字符。