暑期考核算法题-2暑期考核算法题-2

93 阅读 0 评论 62 点赞

我是靠谱客的博主唠叨小松鼠，这篇文章主要介绍暑期考核算法题-2暑期考核算法题-2，现在分享给大家，希望可以做个参考。

title: 暑期考核算法题-2
date: 2020-07-15 10:41:23
tags:

算法
categories:
java
算法

暑期考核算法题-2

题目:

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

题目链接：

题目

示例:

复制代码

1
2
3
4
5
6
7
8
9
输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
链接：https://leetcode-cn.com/problems/group-anagrams

解题思路:

1.定义一个Map集合-
复制代码Map<String,List<String>> map=new HashMap<>();
1
2
Map<String,List<String>> map=new HashMap<>();
2.key存排序后的字符串,value存与key排序后相同的字符串集合

3.从第一个字符串开始,每次先排序后判断key里面是否包含,如果包含将原字符串添加到value的List集合中,如果没有创建一个List并将新创建的List集合和此时key里没有的字符串加入到Map集合中-
复制代码List<String> list1=new ArrayList<>(); map.put(s,list1); list1.add(strs[i]);
1
2
3
4
List<String> list1=new ArrayList<>();
map.put(s,list1);
list1.add(strs[i]);
4.重复第三步,直至所有都加入到Map集合中

5.将Map集合中的value集合加入到result集合中-
复制代码List<List<String>> result=new ArrayList<>(); for ( List<String> list:map.values()) { result.add(list); }
1
2
3
4
5
List<List<String>> result=new ArrayList<>();
for ( List<String> list:map.values()) {
result.add(list);
}

算法源代码

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
package com.company;
import java.util.*;
/**
* @author peichendong
*/
public class Test02 {
public static void main(String[] args) {
String[] strings={"eat","tea","tan","ate","nat","bat"};
List<List<String>> result=new ArrayList<>();
result=new Test02().groupAnagrams(strings);
for (List<String> list:result) {
System.out.println(list.toString());
}
}
public List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> result=new ArrayList<>();
Map<String,List<String>> map=new HashMap<>();
for (int i = 0; i < strs.length; i++) {
char[] chars=strs[i].toCharArray();
Arrays.sort(chars);
String s=String.valueOf(chars);
if (map.containsKey(s)){
List<String> list=map.get(s);
list.add(strs[i]);
}else {
List<String> list1=new ArrayList<>();
map.put(s,list1);
list1.add(strs[i]);
}
}
for ( List<String> list:map.values()) {
result.add(list);
}
return result;
}
}