Java 8流 删除重复字母

huangapple go评论93阅读模式
英文:

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: &quot;bcabc&quot;
Output: &quot;abc&quot;

Another example:

Input: &quot;cbacdcbc&quot;
Output: &quot;acdb&quot;

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&lt;Character&gt; list = new ArrayList&lt;&gt;();
    for(char ch : c) 
    {
        list.add(ch);
    }
    
    List&lt;Character&gt; newVal = list.stream().distinct().collect(Collectors.toList()); 
    String newStr = &quot;&quot;;
    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的解释,以及这个回答

这里有很多不同的地方,我将它们编号如下:

  1. 你可以使用String#chars()将字符串的字符转化为流,而不是创建一个List并将所有字符添加到其中。

  2. 为了确保结果字符串在字典顺序中最小,我们可以对IntStream进行排序。

  3. 我们可以通过使用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 Streams 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:

  1. You can stream the characters of a String using String#chars() instead of making a List where you add all the characters.

  2. To ensure that the resulting string is smallest in lexographical order, we can sort the IntStream.

  3. We can convert the IntStream back to a String by performing a mutable reduction with a StringBuilder. We then convert this StringBuilder 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 = &quot;cbacdcbc&quot;;
    string.chars()
            .mapToObj(item -&gt; (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 = &quot;aabscs&quot;;
Arrays.stream(input.split(&quot;&quot;))
      .collect(Collectors.toSet()).forEach(System.out::print);

//2nd Approach

input.chars()
            .mapToObj(item -&gt; (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&lt;String&gt; c = Arrays
  .asList(&quot;helloword&quot;.split(&quot;&quot;))
  .stream()
  .distinct()
  .toList();

huangapple
  • 本文由 发表于 2020年8月22日 11:18:13
  • 转载请务必保留本文链接:https://go.coder-hub.com/63532247.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定