使用 LinkedHashMap 的字符串中的第一个唯一字符
First unique character in a string using LinkedHashMap
给定一个字符串，找到其中的第一个非重复字符及其索引 return。如果不存在，return -1.
示例：
s = "leetcode"
return 0.
s = "loveleetcode"
return 2.
在我的解决方案中，我可以找到角色本身，但我正在寻找角色的索引！我将如何更改我的代码以使用 LinkedHashMap 获取索引？提前谢谢你。
public static void firstNonRepeatingString(String str) {
LinkedHashMap<Character, Integer> lhm = new LinkedHashMap<>();
char[] charArray = str.toCharArray();
for (char character : charArray) {
if (lhm.get(character) == null) {
lhm.put(character, 1);
} else {
lhm.put(character, lhm.get(character) + 1);
}
}
for (Map.Entry<Character, Integer> entry : lhm.entrySet())
if (entry.getValue() == 1) {
System.out.print(entry.getKey());
break;
}
}
firstNonRepeatingString("aaabcccddeggf");
这将打印 b，但我想打印 3。
HashSet
集合只是为了避免重复计算一个已经见过的字符。该集合不需要遵守插入顺序，因为它的目标只是检查元素是否存在。为此，HashSet 是一个合适的选择。
StringUtils 确实有一些很好的实用程序，其中之一是计算源字符串中单个 char/string 的出现次数。
因为你想要第一个字符是唯一的，如果元素不存在于 set 和 countMatches returns 1，你得到了你的结果。
如果没有发现uniques，return -1 （例如）表示没有uniques在字符串中找到。
public static int firstNonRepeatingCharIndex(String str)
{
HashSet<Character> dupSet = new HashSet<>(); //duplicates list
for(char c : str.toCharArray())
{
if (dupSet.contains(c))
continue;
if (StringUtils.countMatches(str, c) == 1)
return str.indexOf(c);
dupSet.add(c);
}
return -1;
}
这避免了：
- 找到结果后，对所有字符进行无用的迭代。
- 已经看到的字符的无用过程。
- 无用的地图创建及其相关操作，例如聚合。
HashSet + LinkedHashSet
对于这个特定的问题，这不是必需的，但以防万一你想知道哪些是唯一性及其顺序，所以你想迭代到最后，使用两个 Sets 可以是一种选择。
public static int firstNonRepeatingCharIndex(String str)
{
LinkedHashSet<Character> lSet = new LinkedHashSet<>();
HashSet<Character> dupSet = new HashSet<>(); //duplicates list
for(char character : str.toCharArray())
{
if (dupSet.contains(character)) //exists in duplicates, continue
continue;
if (lSet.contains(character)) //exists in the linkedSet, add to duplicates
dupSet.add(character);
else
lSet.add(character); //first time seen, add to linkedSet
}
lSet.removeAll(dupSet); //remove all duplicates
if (lSet.isEmpty())
return -1;
return str.indexOf(lSet.iterator().next());
}
LinkedHashMap
仅当需要完整地图、获取统计信息或其他任何内容时。
请注意，不需要 add/modify 条目。如果key不在map中，我们直接设置出现次数。
public static int firstNonRepeatingCharIndex(String str)
{
LinkedHashMap <Character , Integer> lhm = new LinkedHashMap<>();
int c = 0, index = -1;
for(char character : str.toCharArray())
{
if (lhm.get(character) == null)
{
int oc = StringUtils.countMatches(str,character);
if (oc==1 && index<0)
index = c; //will only bet set once
lhm.put(character, oc);
}
if (index<0)
c++; //no need for this after index is found
}
//showStatsOfMap(lhm); ?
return index;
}
如果你根本不需要地图的结果（这让你想知道为什么这里有地图）
public static int firstNonRepeatingCharIndex(String str)
{
LinkedHashMap <Character , Integer> lhm = new LinkedHashMap<>();
int c = 0;
for(char character : str.toCharArray())
{
if (lhm.get(character)==null)
{
int oc = StringUtils.countMatches(str,character);
if (oc == 1)
return c;
lhm.put(character, oc);
}
c++;
}
//sendNonUniqueMap(lhm); //??? just to make use of it...
return -1;
}
您有 2 个比较明显的选项，它们保留了使用 LinkedHashMap 的精神：
- 您当前将字母映射到它出现的次数。但这实际上并不重要；你只需要知道字母是否是唯一的（你不需要计数，你只需要 'if I had the count, would it be 1?'，这是相当少的信息），你需要知道它出现的位置。
那么为什么不将字符映射到 位置 而不是计数呢？然后，如果你再次击中同一个角色，你需要在地图上放一些东西以确保你知道它不好（你不能删除它，因为第三次出现会再次添加它，这意味着你输入错误输入 aaabc 的答案。也许将其设置为 -1 或其他表示：这不是您想要的答案）的值。
- 保留您的代码，但只需再遍历字符串一次，然后找到索引。或者只使用 String 的
indexOf 方法来做到这一点。这使您可以转弯，例如字母 'b' 到字符串中第一个 'b' 出现的位置。
我的解决方案使用记录地图....需要 Java 14 或更高版本并启用预览功能。看起来有点冗长，但基本上下面的代码所做的是遍历输入字符串中的字符数组并创建一条记录 {character, index, count}。然后，它将创建的记录放在地图上。由于将 returns 放在该键的先前值中，代码随后“合并”了这两个记录，并用保留字符和较低索引并将较高计数递增 1 的新记录替换条目。
最后，它使用流将映射中的所有条目过滤为仅计数为 1 的条目，然后 returns 具有最低索引的条目。
当输入“loveleetcode”时，代码会打印出具有最低索引且计数为 1 的条目：
v=CharacterCount[character=v, index=2, count=1]
请记住，记录并不真的需要字符（因为键就是字符）。记录中您只需要该字符的最低索引和计数。
import java.util.Comparator;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Map.Entry;
public class FirstUniqueCharacterDemo {
public static void main (String[] args) {
// String input1 = "leetcode"; // return 0
String input1 = "loveleetcode"; // return 2
Map<Character, CharacterCount> charMap = new LinkedHashMap<>();
for (int i = 0; i < input1.length(); i++) {
char c = input1.charAt(i);
CharacterCount current = new CharacterCount(c, i, 1); // records are immutable
CharacterCount previous = charMap.put(c, current);
if(previous != null) {
current = current.merge(previous); // combine records (add 1 to count and keep lower index)
charMap.replace(c, current);
}
}
Entry<Character, CharacterCount> lowestIndex = charMap.entrySet().stream()
.filter(recordsWithOneEntry -> recordsWithOneEntry.getValue().count() == 1)
.min(Map.Entry.comparingByValue(Comparator.comparingInt(CharacterCount::index))).orElse(null); // This will return either the CharacterCount record or null if none are found with a count of 1.
System.out.println(lowestIndex);
}
public static record CharacterCount(char character, int index, int count) {
public boolean isIndexGreater(int index) {
return this.index > index;
}
public CharacterCount merge(CharacterCount cc) {
int index = (isIndexGreater(cc.index()) ? cc.index : this.index);
int count = this.count() > cc.count ? this.count() + 1 : cc.count() + 1;
char c = this.character();
return new CharacterCount(c, index, count);
}
}
}
您可以使用String#indexOf方法，即returns指定子字符串在该字符串中第一次出现的索引。
public static void main(String[] args) {
String str1 = "leetcode";
String str2 = "loveleetcode";
String str3 = "aabbcc";
String l1 = firstNonRepeatingString(str1);
String l2 = firstNonRepeatingString(str2);
String l3 = firstNonRepeatingString(str3);
System.out.println(str1.indexOf(l1)); // 0
System.out.println(str2.indexOf(l2)); // 2
System.out.println(str3.indexOf(l3)); // -1
}
public static String firstNonRepeatingString(String str) {
return Arrays
// split string into an array of
// substrings, i.e. characters,
// Stream<String>
.stream(str.split(""))
// collect to map and count the number of repetitions
.collect(Collectors.toMap(
s -> s, c -> 1, Integer::sum, LinkedHashMap::new))
// iterate over entry set of this map
// Stream<Map.Entry<String,Integer>>
.entrySet().stream()
// filter letters without repetitions
.filter(entry -> entry.getValue() == 1)
// take letter
.map(Map.Entry::getKey)
// first one
.findFirst()
// or a null character if
// there are no such letters
.orElse("\u0000");
}
另请参阅：
将存在一次或多次的两组字符分开
(不需要统计字数)
firstNonRepeatingChar( "aaabcccddeggf" );
获取列表 List<Integer> uniques [3, 9, 12]
从 uniques 3
获取第一个元素
public int firstNonRepeatingChar( String s ) {
List<Integer> uniques = IntStream.range( 0, s.length() ).boxed().collect(
partitioningBy(i -> s.indexOf(s.charAt( i ),
s.indexOf(s.charAt( i )) + 1) == -1)).get( true ); // [3, 9, 12]
return( uniques.isEmpty() ? -1 : uniques.get( 0 ) ); // 3
}
停止 limit( 1 ) 找到感兴趣的字符后
aran 的技巧在
上得到的进一步简化
这个流只包含一个匹配的索引，如果有的话
public int firstNonRepeatingChar( String s ) {
return( IntStream.range( 0, s.length() ).dropWhile( i -> s.indexOf(s.charAt( i ),
s.indexOf(s.charAt( i )) + 1) > -1).limit( 1 ).findFirst().orElse( -1 ) ); // 3
}
给定一个字符串，找到其中的第一个非重复字符及其索引 return。如果不存在，return -1.
示例：
s = "leetcode"
return 0.
s = "loveleetcode"
return 2.
在我的解决方案中，我可以找到角色本身，但我正在寻找角色的索引！我将如何更改我的代码以使用 LinkedHashMap 获取索引？提前谢谢你。
public static void firstNonRepeatingString(String str) {
LinkedHashMap<Character, Integer> lhm = new LinkedHashMap<>();
char[] charArray = str.toCharArray();
for (char character : charArray) {
if (lhm.get(character) == null) {
lhm.put(character, 1);
} else {
lhm.put(character, lhm.get(character) + 1);
}
}
for (Map.Entry<Character, Integer> entry : lhm.entrySet())
if (entry.getValue() == 1) {
System.out.print(entry.getKey());
break;
}
}
firstNonRepeatingString("aaabcccddeggf");
这将打印 b，但我想打印 3。
HashSet
集合只是为了避免重复计算一个已经见过的字符。该集合不需要遵守插入顺序，因为它的目标只是检查元素是否存在。为此，HashSet 是一个合适的选择。
StringUtils 确实有一些很好的实用程序，其中之一是计算源字符串中单个 char/string 的出现次数。
因为你想要第一个字符是唯一的，如果元素不存在于 set 和 countMatches returns 1，你得到了你的结果。
如果没有发现uniques，return -1 （例如）表示没有uniques在字符串中找到。
public static int firstNonRepeatingCharIndex(String str)
{
HashSet<Character> dupSet = new HashSet<>(); //duplicates list
for(char c : str.toCharArray())
{
if (dupSet.contains(c))
continue;
if (StringUtils.countMatches(str, c) == 1)
return str.indexOf(c);
dupSet.add(c);
}
return -1;
}
这避免了：
- 找到结果后，对所有字符进行无用的迭代。
- 已经看到的字符的无用过程。
- 无用的地图创建及其相关操作，例如聚合。
HashSet + LinkedHashSet
对于这个特定的问题，这不是必需的，但以防万一你想知道哪些是唯一性及其顺序，所以你想迭代到最后，使用两个 Sets 可以是一种选择。
public static int firstNonRepeatingCharIndex(String str)
{
LinkedHashSet<Character> lSet = new LinkedHashSet<>();
HashSet<Character> dupSet = new HashSet<>(); //duplicates list
for(char character : str.toCharArray())
{
if (dupSet.contains(character)) //exists in duplicates, continue
continue;
if (lSet.contains(character)) //exists in the linkedSet, add to duplicates
dupSet.add(character);
else
lSet.add(character); //first time seen, add to linkedSet
}
lSet.removeAll(dupSet); //remove all duplicates
if (lSet.isEmpty())
return -1;
return str.indexOf(lSet.iterator().next());
}
LinkedHashMap
仅当需要完整地图、获取统计信息或其他任何内容时。
请注意，不需要 add/modify 条目。如果key不在map中，我们直接设置出现次数。
public static int firstNonRepeatingCharIndex(String str)
{
LinkedHashMap <Character , Integer> lhm = new LinkedHashMap<>();
int c = 0, index = -1;
for(char character : str.toCharArray())
{
if (lhm.get(character) == null)
{
int oc = StringUtils.countMatches(str,character);
if (oc==1 && index<0)
index = c; //will only bet set once
lhm.put(character, oc);
}
if (index<0)
c++; //no need for this after index is found
}
//showStatsOfMap(lhm); ?
return index;
}
如果你根本不需要地图的结果（这让你想知道为什么这里有地图）
public static int firstNonRepeatingCharIndex(String str)
{
LinkedHashMap <Character , Integer> lhm = new LinkedHashMap<>();
int c = 0;
for(char character : str.toCharArray())
{
if (lhm.get(character)==null)
{
int oc = StringUtils.countMatches(str,character);
if (oc == 1)
return c;
lhm.put(character, oc);
}
c++;
}
//sendNonUniqueMap(lhm); //??? just to make use of it...
return -1;
}
您有 2 个比较明显的选项，它们保留了使用 LinkedHashMap 的精神：
- 您当前将字母映射到它出现的次数。但这实际上并不重要；你只需要知道字母是否是唯一的（你不需要计数，你只需要 'if I had the count, would it be 1?'，这是相当少的信息），你需要知道它出现的位置。
那么为什么不将字符映射到 位置 而不是计数呢？然后，如果你再次击中同一个角色，你需要在地图上放一些东西以确保你知道它不好（你不能删除它，因为第三次出现会再次添加它，这意味着你输入错误输入 aaabc 的答案。也许将其设置为 -1 或其他表示：这不是您想要的答案）的值。
- 保留您的代码，但只需再遍历字符串一次，然后找到索引。或者只使用 String 的
indexOf方法来做到这一点。这使您可以转弯，例如字母 'b' 到字符串中第一个 'b' 出现的位置。
我的解决方案使用记录地图....需要 Java 14 或更高版本并启用预览功能。看起来有点冗长，但基本上下面的代码所做的是遍历输入字符串中的字符数组并创建一条记录 {character, index, count}。然后，它将创建的记录放在地图上。由于将 returns 放在该键的先前值中，代码随后“合并”了这两个记录，并用保留字符和较低索引并将较高计数递增 1 的新记录替换条目。
最后，它使用流将映射中的所有条目过滤为仅计数为 1 的条目，然后 returns 具有最低索引的条目。
当输入“loveleetcode”时，代码会打印出具有最低索引且计数为 1 的条目：
v=CharacterCount[character=v, index=2, count=1]
请记住，记录并不真的需要字符（因为键就是字符）。记录中您只需要该字符的最低索引和计数。
import java.util.Comparator;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Map.Entry;
public class FirstUniqueCharacterDemo {
public static void main (String[] args) {
// String input1 = "leetcode"; // return 0
String input1 = "loveleetcode"; // return 2
Map<Character, CharacterCount> charMap = new LinkedHashMap<>();
for (int i = 0; i < input1.length(); i++) {
char c = input1.charAt(i);
CharacterCount current = new CharacterCount(c, i, 1); // records are immutable
CharacterCount previous = charMap.put(c, current);
if(previous != null) {
current = current.merge(previous); // combine records (add 1 to count and keep lower index)
charMap.replace(c, current);
}
}
Entry<Character, CharacterCount> lowestIndex = charMap.entrySet().stream()
.filter(recordsWithOneEntry -> recordsWithOneEntry.getValue().count() == 1)
.min(Map.Entry.comparingByValue(Comparator.comparingInt(CharacterCount::index))).orElse(null); // This will return either the CharacterCount record or null if none are found with a count of 1.
System.out.println(lowestIndex);
}
public static record CharacterCount(char character, int index, int count) {
public boolean isIndexGreater(int index) {
return this.index > index;
}
public CharacterCount merge(CharacterCount cc) {
int index = (isIndexGreater(cc.index()) ? cc.index : this.index);
int count = this.count() > cc.count ? this.count() + 1 : cc.count() + 1;
char c = this.character();
return new CharacterCount(c, index, count);
}
}
}
您可以使用String#indexOf方法，即returns指定子字符串在该字符串中第一次出现的索引。
public static void main(String[] args) {
String str1 = "leetcode";
String str2 = "loveleetcode";
String str3 = "aabbcc";
String l1 = firstNonRepeatingString(str1);
String l2 = firstNonRepeatingString(str2);
String l3 = firstNonRepeatingString(str3);
System.out.println(str1.indexOf(l1)); // 0
System.out.println(str2.indexOf(l2)); // 2
System.out.println(str3.indexOf(l3)); // -1
}
public static String firstNonRepeatingString(String str) {
return Arrays
// split string into an array of
// substrings, i.e. characters,
// Stream<String>
.stream(str.split(""))
// collect to map and count the number of repetitions
.collect(Collectors.toMap(
s -> s, c -> 1, Integer::sum, LinkedHashMap::new))
// iterate over entry set of this map
// Stream<Map.Entry<String,Integer>>
.entrySet().stream()
// filter letters without repetitions
.filter(entry -> entry.getValue() == 1)
// take letter
.map(Map.Entry::getKey)
// first one
.findFirst()
// or a null character if
// there are no such letters
.orElse("\u0000");
}
另请参阅：
将存在一次或多次的两组字符分开
(不需要统计字数)
firstNonRepeatingChar( "aaabcccddeggf" );
获取列表 List<Integer> uniques [3, 9, 12]
从 uniques 3
public int firstNonRepeatingChar( String s ) {
List<Integer> uniques = IntStream.range( 0, s.length() ).boxed().collect(
partitioningBy(i -> s.indexOf(s.charAt( i ),
s.indexOf(s.charAt( i )) + 1) == -1)).get( true ); // [3, 9, 12]
return( uniques.isEmpty() ? -1 : uniques.get( 0 ) ); // 3
}
停止 limit( 1 ) 找到感兴趣的字符后
aran 的技巧在
上得到的进一步简化
这个流只包含一个匹配的索引，如果有的话
public int firstNonRepeatingChar( String s ) {
return( IntStream.range( 0, s.length() ).dropWhile( i -> s.indexOf(s.charAt( i ),
s.indexOf(s.charAt( i )) + 1) > -1).limit( 1 ).findFirst().orElse( -1 ) ); // 3
}