group anagrams leetcode java_Leetcode - Group Anagrams

逃离我推掉我的手 2022-11-08 05:55 44阅读 0赞

![a5b818b35866][]

My code:

import java.util.ArrayList;

import java.util.Arrays;

import java.util.HashMap;

import java.util.List;

public class Solution \{

public List> groupAnagrams(String\[\] strs) \{

if (strs == null)

return null;

ArrayList> result = new ArrayList>();

ArrayList group = new ArrayList();

if (strs.length == 0) \{

return result;

Arrays.sort(strs);

HashMap> hm = new HashMap>();

for (int i = 0; i < strs.length; i++) \{

char\[\] tempCharArray = strs\[i\].toCharArray();

Arrays.sort(tempCharArray);

String tempStr = String.valueOf(tempCharArray);

if (!hm.containsKey(tempStr)) \{

ArrayList tempArrayList = new ArrayList();

tempArrayList.add(i);

hm.put(tempStr, tempArrayList);

else \{

ArrayList tempArrayList = hm.get(tempStr);

tempArrayList.add(i);

hm.put(tempStr, tempArrayList);

for (ArrayList temp : hm.values()) \{

for (Integer index : temp)

group.add(strs\[index\]);

result.add(new ArrayList(group));

group = new ArrayList();

return result;

public static void main(String\[\] args) \{

Solution test = new Solution();

String\[\] a = \{"a"\};

System.out.println(test.groupAnagrams(a));

My test result:

![a5b818b35866][]

Paste\_Image.png

首先说下测试结果为什么这么慢。我的理解是，这道题目是8.9才改题的，之前的用户数据可能还保存着，导致我的排名很低。但其实，题目改了之后，复杂度就变了。

这道题目感觉学到了很多。

如何对 string 排序， 利用java API

char\[\] arr = str.toCharArray();

Arrays.sort(arr);

String s = String.valueOf(arr);

用什么去接收Collections 类。 如何获得 HashMap values 的迭代器,使用 .values() 方法

如果value是 T 类型。那么，

for (T temp : hashmap.values())

......

new ArrayList(5); 并不能生成一个 含有 5 的链表。必须要先new一个新的arraylist，然后再插入5进去。

\*\*

总结： String, HashMap, Collections, string sort

\*\*

Anyway, Good luck, Richardo!

My code:

public class Solution \{

public List> groupAnagrams(String\[\] strs) \{

ArrayList> ret = new ArrayList>();

if (strs == null || strs.length == 0)

return ret;

/\*\* key: sorted string value: list for string, convenient for sorting later \*/

HashMap> tracker = new HashMap>();

for (int i = 0; i < strs.length; i++) \{

String curr = strs\[i\];

char\[\] currChar = curr.toCharArray();

Arrays.sort(currChar);

curr = new String(currChar);

if (tracker.containsKey(curr)) \{

List list = tracker.get(curr);

list.add(strs\[i\]);

else \{

ArrayList list = new ArrayList();

list.add(strs\[i\]);

tracker.put(curr, list);

/\*\* traverse the key set of hashmap, sort sub list and add into ret \*/

for (String key : tracker.keySet()) \{

ArrayList list = tracker.get(key);

Collections.sort(list);

ret.add(list);

return ret;

这道题木卡了一会儿。问题出在哪里？

char\[\] tmp = ...

tmp.toString() 返回的是该数组的内存地址，而不是转换而来的 String!!

一定要当心。

其他没什么问题了。

对数组排序，

Arrays.sort();

对链表排序，

Collections.sort();

Anyway, Good luck, Richardo!

My code:

public class Solution \{

public List> groupAnagrams(String\[\] strs) \{

List> ret = new ArrayList>();

HashMap> map = new HashMap>();

for (int i = 0; i < strs.length; i++) \{

char\[\] arr = strs\[i\].toCharArray();

Arrays.sort(arr);

String s = String.valueOf(arr);

if (map.containsKey(s)) \{

map.get(s).add(strs\[i\]);

else \{

map.put(s, new ArrayList());

map.get(s).add(strs\[i\]);

for (String ss : map.keySet()) \{

Collections.sort(map.get(ss));

for (String ss : map.keySet()) \{

ret.add(map.get(ss));

return ret;

并不难，但复杂度不小，因为每个string都需要sort

后来看到了一个新的方法，更高效，利用hashcode 的思想。

统计每个字母的个数与 int\[26\] nums

然后Arrays.hashCode(nums) 拿到哈希值作为hashtable的key

My code:

public class Solution \{

public List> groupAnagrams(String\[\] strs) \{

List> ret = new ArrayList>();

if (strs == null || strs.length == 0) \{

return ret;

HashMap> map = new HashMap>();

for (int i = 0; i < strs.length; i++) \{

int id = getID(strs\[i\]);

if (!map.containsKey(id)) \{

map.put(id, new ArrayList());

map.get(id).add(strs\[i\]);

for (Integer i : map.keySet()) \{

ret.add(map.get(i));

return ret;

private int getID(String s) \{

int\[\] nums = new int\[26\];

for (int i = 0; i < s.length(); i++) \{

nums\[s.charAt(i) - 'a'\]++;

return Arrays.hashCode(nums);

Anyway, Good luck, Richardo! -- 09/20/2016

[a5b818b35866]: /images/20221023/c1db2c206b204b798a4808514d9f7391.png

group anagrams leetcode java_Leetcode - Group Anagrams

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关 group anagrams leetcode java_Leetcode - Group Anagrams

相关 leetcode 49. Group Anagrams

相关 LeetCode49——Group Anagrams

相关【LeetCode】49. Group Anagrams解法及注释

相关 poj----Anagram Groups

相关 leetcode 49. Group Anagrams 字符串排序 + Map记录

相关 49. Group Anagrams

相关 Group Anagrams

相关【LeetCode Top 100】49. Group Anagrams【Medium】【JAVA】

相关 LeetCode : 49. Group Anagrams 分组字符串