英文:
Java 8 Streams Remove Duplicate Letter
问题
我正在尝试将自己对流的知识应用于一些 LeetCode 算法问题。以下是问题的一般概述:
给定一个仅包含小写字母的字符串,移除重复字母,使得每个字母只出现一次。确保你的结果在所有可能的结果中,按字典序是最小的。
示例:
输入:"bcabc"
输出:"abc"
另一个示例:
输入:"cbacdcbc"
输出:"acdb"
这看起来像是一个简单的问题,只需要将字符串中的值流式传输到一个新列表中,对值进行排序,找到不重复的值,然后将其放回到列表中,并将列表的值附加到一个字符串中。以下是我想出的代码:
public String removeDuplicateLetters(String s)
{
char[] c = s.toCharArray();
List<Character> list = new ArrayList<>();
for(char ch : c)
{
list.add(ch);
}
List<Character> newVal = list.stream().distinct().collect(Collectors.toList());
String newStr = "";
for(char ch : newVal)
{
newStr += ch;
}
return newStr;
}
第一个示例运行得很完美,但是在第二个示例的输出中,我得到的是 "abcd" 而不是 "acdb"。为什么 "abcd" 不是最小的字典序呢?谢谢!
英文:
I'm trying to apply my knowledge of streams to some leetcode algorithm questions. Here is a general summary of the question:
> Given a string which contains only lowercase letters, remove duplicate
> letters so that every letter appears once and only once. You must make
> sure your result is the smallest in lexicographical order among all
> possible results.
Example:
Input: "bcabc"
Output: "abc"
Another example:
Input: "cbacdcbc"
Output: "acdb"
This seemed like a simple problem, just stream the values into a new list from the string, sort the values, find the distinct values, and then throw it back into a list, and append the list's value to a string. Here is what I came up with:
public String removeDuplicateLetters(String s)
{
char[] c = s.toCharArray();
List<Character> list = new ArrayList<>();
for(char ch : c)
{
list.add(ch);
}
List<Character> newVal = list.stream().distinct().collect(Collectors.toList());
String newStr = "";
for(char ch : newVal)
{
newStr += ch;
}
return newStr;
}
The first example is working perfectly, but instead of "acdb" for the second output, I'm getting "abcd". Why would abcd not be the least lexicographical order? Thanks!
答案1
得分: 4
如我在评论中指出的,使用LinkedHashSet
会是最佳选择,但是对于Stream
的练习,你可以这样做:
public static String removeDuplicateLetters(String s) {
return s.chars().sorted().distinct().collect(
StringBuilder::new,
StringBuilder::appendCodePoint,
StringBuilder::append
).toString();
}
注意:distinct()
在sorted()
之后,以优化流操作,可以在评论中查看Holger的解释,以及这个回答。
这里有很多不同的地方,我将它们编号如下:
-
你可以使用
String#chars()
将字符串的字符转化为流,而不是创建一个List
并将所有字符添加到其中。 -
为了确保结果字符串在字典顺序中最小,我们可以对
IntStream
进行排序。 -
我们可以通过使用
StringBuilder
执行可变规约将IntStream
转换回String
。然后,我们将这个StringBuilder
转换为我们想要的字符串。
可变规约是Stream
方式执行类似于以下操作的等效方法:
for (char ch : newVal) {
newStr += ch;
}
然而,这还具有使用StringBuilder
进行连接而不是String
的附加好处。参见这个回答,了解为什么这更高效。
关于你提出的关于预期输出与实际输出冲突的问题:我认为abcd
是第二个输出的正确答案,因为它在字典顺序中最小。
英文:
As I had pointed out in the comments using a LinkedHashSet
would be best here, but for the Stream
s practice you could do this:
public static String removeDuplicateLetters(String s) {
return s.chars().sorted().distinct().collect(
StringBuilder::new,
StringBuilder::appendCodePoint,
StringBuilder::append
).toString();
}
Note: distinct()
comes after sorted()
in order to optimize the stream, see Holger's explanation in the comments as well as this answer.
Lot of different things here so I'll number them:
-
You can stream the characters of a
String
usingString#chars()
instead of making aList
where you add all the characters. -
To ensure that the resulting string is smallest in lexographical order, we can sort the
IntStream
. -
We can convert the
IntStream
back to aString
by performing a mutable reduction with aStringBuilder
. We then convert thisStringBuilder
to our desired string.
A mutable reduction is the Stream
way of doing the equivalent of something like:
for (char ch : newVal) {
newStr += ch;
}
However, this has the added benefit of using a StringBuilder
for concatenation instead of a String
. See this answer as to why this is more performant.
For the actual question you have about the conflict of expected vs. observed output: I believe abcd
is the right answer for the second output, since it is the smallest in lexographical order.
答案2
得分: 3
Sure, here's the translation of the code:
public static void main(String[] args) {
String string = "cbacdcbc";
string.chars()
.mapToObj(item -> (char) item)
.collect(Collectors.toSet()).forEach(System.out::print);
}
the output: abcd, hope help you!
英文:
public static void main(String[] args) {
String string = "cbacdcbc";
string.chars()
.mapToObj(item -> (char) item)
.collect(Collectors.toSet()).forEach(System.out::print);
}
the output:abcd,hope help you!
答案3
得分: 0
// 第一种方法
String input = "aabscs";
Arrays.stream(input.split(""))
.collect(Collectors.toSet()).forEach(System.out::print);
// 第二种方法
input.chars()
.mapToObj(item -> (char) item)
.collect(Collectors.toSet()).forEach(System.out::print);
// 输出:absc
/**
可以用多种方法来实现,我们也可以使用 Map,但我认为这是一个简单的方法。
希望对你有帮助
*/
英文:
//1st Approach
String input = "aabscs";
Arrays.stream(input.split(""))
.collect(Collectors.toSet()).forEach(System.out::print);
//2nd Approach
input.chars()
.mapToObj(item -> (char) item)
.collect(Collectors.toSet()).forEach(System.out::print);
//Output: absc
/**
It can be done in multiple ways, we can also use Map, but I think this is a simple one.
Hope it will help you
*/
答案4
得分: 0
List<String> c = Arrays
.asList("helloword".split(""))
.stream()
.distinct()
.toList();
英文:
List<String> c = Arrays
.asList("helloword".split(""))
.stream()
.distinct()
.toList();
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论