Leetcode - Group Anagrams

图片 1

图片 2Paste_Image.png

My code:

My code:

import java.util.ArrayList;import java.util.Arrays;import java.util.HashMap;import java.util.List;public class Solution { public List<List<String>> groupAnagrams(String[] strs) { if (strs == null) return null; ArrayList<List<String>> result = new ArrayList<List<String>>(); ArrayList<String> group = new ArrayList<String>(); if (strs.length == 0) { return result; } Arrays.sort; HashMap<String, ArrayList<Integer>> hm = new HashMap<String, ArrayList<Integer>>(); for (int i = 0; i < strs.length; i++) { char[] tempCharArray = strs[i].toCharArray(); Arrays.sort(tempCharArray); String tempStr = String.valueOf(tempCharArray); if (!hm.containsKey { ArrayList<Integer> tempArrayList = new ArrayList<Integer>(); tempArrayList.add; hm.put(tempStr, tempArrayList); } else { ArrayList<Integer> tempArrayList = hm.get; tempArrayList.add; hm.put(tempStr, tempArrayList); } } for (ArrayList<Integer> temp : hm.values { for (Integer index : temp) group.add(strs[index]); result.add(new ArrayList<String>; group = new ArrayList<String>(); } return result; } public static void main(String[] args) { Solution test = new Solution(); String[] a = {"a"}; System.out.println(test.groupAnagrams; }}
import java.util.ArrayList;import java.util.Arrays;import java.util.HashMap;import java.util.List;/** * Definition for an interval. * public class Interval { * int start; * int end; * Interval() { start = 0; end = 0; } * Interval(int s, int e) { start = s; end = e; } * } */public class Solution { public List<Interval> merge(List<Interval> intervals) { ArrayList<Interval> result = new ArrayList<Interval>(); if (intervals == null || intervals.size return result; if (intervals.size { result.add(intervals.get; return result; } int[] begin = new int[intervals.size()]; HashMap<Integer, Integer> range = new HashMap<Integer, Integer>(); range.put(intervals.get.start, intervals.get; begin[0] = intervals.get.start; for (int i = 1; i < intervals.size { begin[i] = intervals.get.start; if (range.containsKey(intervals.get && intervals.get.end <= range.get) continue; else range.put(intervals.get.start, intervals.get; } Arrays.sort; Interval interval = new Interval(begin[0], range.get); for (int i = 1; i <= begin.length; i++) { if (i == begin.length) result.add; else if (begin[i] > interval.end) { result.add; interval = new Interval(begin[i], range.get); } else if (begin[i] < interval.start) { if (range.get <= range.get(begin[i - 1])) interval = new Interval(begin[i], range.get(begin[i - 1])); else interval = new Interval(begin[i], range.get); } else if (range.get > interval.end) interval = new Interval(interval.start, range.get); else continue; } return result; } public static void main(String[] args) { Solution test = new Solution(); Interval a0 = new Interval; Interval a1 = new Interval; ArrayList<Interval> result = new ArrayList<Interval>(); result.add; result.add; System.out.println(test.merge; }}

My test result:

My test result:

图片 3Paste_Image.png

图片 4Paste_Image.png

首先说下测验结果为何如此慢。小编的明白是,那道标题是8.9才改题的,在此之前的客户数量大概还保留着,导致笔者的排行相当低。但实际上,题目改了将来,复杂度就变了。那道难题以为学到了数不胜数。

那道标题不算很难。平素在思考三个主题材料,怎么样保存这种范围的投射,这种start和end的映射。最终依旧决定用HashMap, key -> start, value -> end.将全数的数据保存在哈希表中,同期,将全体的早先数字,保存在begin数组中。注意保留哈希表的时候,借使当前头在哈希表中已经存在的话,必要看清下其尾是不是高出哈希表对应的val。要是还是不是,则跳过,如若是,则更新哈希表。然后对 begin[] 排序。然后遵照一定的准则,管理那些数组,不断地插入新的interval到结果中去。差不离就像此了。

  1. 如何对 string 排序, 利用java API

**总计: Array, sort, hash table先天到底把三道难点的量实现了。深夜和初级中学同学吃饭。猝然明白了那么一句话。作者奋力了这么久,就是为着和你喝一杯咖啡。以为他们的社会风气,和自己的不等。他们对知识的左右程度,也远凌驾自身。但一样的,他们也亟需思量小车在何地买实惠。租的房舍干不到头。那些他们也不可能幸免。然后,笔者要潜下心来,默默地,变强。最终,希望选课顺遂!**

Anyway, Good luck, Richardo!

char[] arr = str.toCharArray();Arrays.sort;String s = String.valueOf;

My code:

  1. 用哪些去接受Collections 类。 怎么样收获 HashMap values 的迭代器,使用 .values() 方法即使value是 T 类型。那么,
import java.util.ArrayList;import java.util.Collections;import java.util.Comparator;import java.util.List;/** * Definition for an interval. * public class Interval { * int start; * int end; * Interval() { start = 0; end = 0; } * Interval(int s, int e) { start = s; end = e; } * } */public class Solution { public List<Interval> merge(List<Interval> intervals) { if (intervals == null || intervals.size return intervals; Collections.sort(intervals, new Comparator<Interval>() { public int compare(Interval o1, Interval o2) {// int start1 = o1.start;// int start2 = o2.start;// int end1 = o1.end;// int end2 = o2.end;// if (start1 == start2 && end1 == end2)// return 0;// else if (start1 <= start2 && end1 <= end2)// return -1;// else// return 1; return o1.start - o2.start; } }); for (int i = 1; i < intervals.size { int frontStart = intervals.get.start; int frontEnd = intervals.get.end; int backStart = intervals.get.start; int backEnd = intervals.get.end; if (backStart > frontEnd) continue; else { intervals.get.start = Math.min(frontStart, backStart); intervals.get.end = Math.max(frontEnd, backEnd); intervals.remove; i--; } } return intervals; } public static void main(String[] args) { Interval a1 = new Interval; Interval a2 = new Interval; Interval a3 = new Interval; Interval a4 = new Interval; ArrayList<Interval> intervals = new ArrayList<Interval>(); intervals.add; intervals.add; intervals.add; intervals.add; Solution test = new Solution(); System.out.println(test.merge(intervals)); }}

那是自家自个儿写的,直接在内部改成分。可是速度非常慢。为啥吧?因为笔者有八个删减操作。链表的删除操作复杂度是O,所以如若测量检验案例的重合成分比相当多,笔者的进度会相当的慢异常慢。于是有了八个校对措施,正是新建三个ArrayList<...> ret,然后把供给塞进去的,已经更新好了的interval放进去,那样就不会再有删除操作了。一样也是遍历整个链表。链表的.add()并非很耗时的操作。小编就懒得写了,不过速度应该会越来越快。然后就出现了一个主题材料,在此以前根本未有遇上过:

for (T temp : hashmap.values ......
Line 19: java.lang.IllegalArgumentException: Comparison method violates its general contract!
  1. new ArrayList<Integer>; 并不能生成三个 含有 5 的链表。必供给先new四个新的arraylist,然后再插入5跻身。

本人查了下,大致是,如若 A = B, 那么 B = A, 而本身的comparator方法写得恐怕违反了那或多或少。

**总结: String, HashMap, Collections, string sort**

Collections.sort(intervals, new Comparator() { public int compare(Object o1, Object o2) { int start1 = ( o1).start; int start2 = ( o2).start; if (start1 <= start2) return -1; else return 1; } });

Anyway, Good luck, Richardo!

那是这段错误的代码。作者改了下,

My code:

Collections.sort(intervals, new Comparator<Interval>() { public int compare(Interval o1, Interval o2) {// int start1 = o1.start;// int start2 = o2.start;// int end1 = o1.end;// int end2 = o2.end;// if (start1 == start2 && end1 == end2)// return 0;// else if (start1 <= start2 && end1 <= end2)// return -1;// else// return 1; return o1.start - o2.start; } });
public class Solution { public List<List<String>> groupAnagrams(String[] strs) { ArrayList<List<String>> ret = new ArrayList<List<String>>(); if (strs == null || strs.length == 0) return ret; /** key: sorted string value: list for string, convenient for sorting later */ HashMap<String, ArrayList<String>> tracker = new HashMap<String, ArrayList<String>>(); for (int i = 0; i < strs.length; i++) { String curr = strs[i]; char[] currChar = curr.toCharArray(); Arrays.sort; curr = new String; if (tracker.containsKey { List<String> list = tracker.get; list.add; } else { ArrayList<String> list = new ArrayList<String>(); list.add; tracker.put(curr, list); } } /** traverse the key set of hashmap, sort sub list and add into ret */ for (String key : tracker.keySet { ArrayList<String> list = tracker.get; Collections.sort; ret.add; } return ret; }}

借使直白用注释的一部分,是对的。用当下部分也是对的。作者依然无法很好地理解那个破绽百出。等回了学院再精研下。

那道题木卡了会儿。难题出在哪儿?char[] tmp = ...tmp.toString() 重临的是该数组的内部存储器地址,并不是改动而来的 String!!应当要警醒。别的没什么难点了。对数组排序,Arrays.sort();对链表排序,Collections.sort();

接下来本身看了原先的做法,竟然能够用HashMap来做,也果然是各式各样!我又协和重写了下,错了一点次才AC。思路和代码比此前要从简很多。但实际上和自家上边的本子大致的。正是三个排序。一个用Comparator达成,二个用HashMap完毕。

Anyway, Good luck, Richardo!

import java.util.ArrayList;import java.util.Arrays;import java.util.HashMap;import java.util.List;/** * Definition for an interval. * public class Interval { * int start; * int end; * Interval() { start = 0; end = 0; } * Interval(int s, int e) { start = s; end = e; } * } */public class Solution { public List<Interval> merge(List<Interval> intervals) { ArrayList<Interval> result = new ArrayList<Interval>(); if (intervals == null || intervals.size return result; int[] begin = new int[intervals.size()]; HashMap<Integer, Integer> range = new HashMap<Integer, Integer>(); for (int i = 0; i < intervals.size { int start = intervals.get.start; int end = intervals.get.end; begin[i] = start; if (range.containsKey && range.get >= end) continue; else range.put(start, end); } Arrays.sort; result.add(new Interval(begin[0], range.get)); for (int i = 1; i < begin.length; i++) { if (begin[i] == begin[i - 1]) continue; else { if (begin[i] > result.get(result.size.end) result.add(new Interval(begin[i], range.get)); else result.get(result.size.end = Math.max(result.get(result.size.end, range.get); } } return result; } public static void main(String[] args) { Solution test = new Solution(); Interval a0 = new Interval; Interval a1 = new Interval; Interval a2 = new Interval; Interval a3 = new Interval; Interval a4 = new Interval; ArrayList<Interval> result = new ArrayList<Interval>(); result.add; result.add; result.add; result.add; result.add; System.out.println(test.merge; }}

My code:

**牢记了,链表的remove操作很费时间,决定性浪费时间!能不用就毫无把!还会有八个comparator 难题绝非搞精通!**

public class Solution { public List<List<String>> groupAnagrams(String[] strs) { List<List<String>> ret = new ArrayList<List<String>>(); HashMap<String, List<String>> map = new HashMap<String, List<String>>(); for (int i = 0; i < strs.length; i++) { char[] arr = strs[i].toCharArray(); Arrays.sort; String s = String.valueOf; if (map.containsKey { map.get.add; } else { map.put(s, new ArrayList<String>; map.get.add; } } for (String ss : map.keySet { Collections.sort(map.get; } for (String ss : map.keySet { ret.add(map.get; } return ret; }}

Anyway, Good luck, Richardo!

并轻松,但复杂度一点都不小,因为各样string都供给sort

More efficient solution:My code:

后来看见了三个新的办法,更敏捷,利用hashcode 的思辨。总括各个字母的个数与 int[26] nums然后Arrays.hashCode 获得哈希值作为hashtable的key

/** * Definition for an interval. * public class Interval { * int start; * int end; * Interval() { start = 0; end = 0; } * Interval(int s, int e) { start = s; end = e; } * } */public class Solution { public List<Interval> merge(List<Interval> intervals) { ArrayList<Interval> ret = new ArrayList<Interval>(); if (intervals == null || intervals.size return ret; Collections.sort(intervals, new Comparator<Interval>() { public int compare(Interval o1, Interval o2) { return o1.start - o2.start; } }); Interval preInterval = intervals.get; for (int i = 1; i < intervals.size { Interval curr = intervals.get; if (curr.start > preInterval.end) { ret.add(preInterval); preInterval = curr; } else { Interval merge = new Interval(preInterval.start, Math.max(preInterval.end, curr.end)); preInterval = merge; } } ret.add(preInterval); return ret; }}

My code:

Anyway, Good luck, Richardo!

public class Solution { public List<List<String>> groupAnagrams(String[] strs) { List<List<String>> ret = new ArrayList<List<String>>(); if (strs == null || strs.length == 0) { return ret; } HashMap<Integer, List<String>> map = new HashMap<Integer, List<String>>(); for (int i = 0; i < strs.length; i++) { int id = getID; if (!map.containsKey { map.put(id, new ArrayList<String>; } map.get.add; } for (Integer i : map.keySet { ret.add(map.get; } return ret; } private int getID { int[] nums = new int[26]; for (int i = 0; i < s.length { nums[s.charAt - 'a']++; } return Arrays.hashCode; }}

My code:

reference:

/** * Definition for an interval. * public class Interval { * int start; * int end; * Interval() { start = 0; end = 0; } * Interval(int s, int e) { start = s; end = e; } * } */public class Solution { public List<Interval> merge(List<Interval> intervals) { List<Interval> ret = new ArrayList<Interval>(); if (intervals == null || intervals.size { return ret; } ret.add(intervals.get; for (int i = 1; i < intervals.size { Interval curr = intervals.get; int j = ret.size() - 1; for (; j >= 0; j--) { Interval cmp = ret.get; if (cmp.end < curr.start) { ret.add(j + 1, curr); break; } else if (cmp.start <= curr.start) { cmp.end = Math.max(cmp.end, curr.end); break; } else if (cmp.start <= curr.end) { cmp.start = curr.start; cmp.end = Math.max(cmp.end, curr.end); curr = cmp; ret.remove; } else { continue; } } if  { ret.add; } } return ret; }}

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

友善写了出去。应该是 Insert sort 的一种变形。注意地点是,假如在向左遍历途中,更新了一个Interval导致他的start变小了,那么很有望那么些interval会覆盖他前方叁个interval。这年就要把当前Interval从链表里面删除掉。然后更新curr指针。让她和下贰个interval再一次举办比较。

list remove 操作。日常意况下,时间复杂度是O要是删的是底部或然尾部,时间复杂度是O

原先的不胜用HashMap达成sort的主意也是很风趣的。

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

本文由365bet体育在线官网发布于网络编程,转载请注明出处:Leetcode - Group Anagrams

TAG标签:
Ctrl+D 将本页面保存为书签,全面了解最新资讯,方便快捷。