1. 字母异位词分组

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

示例:

输入:[eat", "tea", "tan", "ate", "nat", "bat"]
输出:[[ate","eat","tea"],["nat","tan"],["bat"]]

说明：

所有输入均为小写字母。
不考虑答案输出的顺序。

出处：

https://edu.csdn.net/practice/24612383

代码：

方法一：对每个字符串排序后作为key，将同一key的字符串放入同一个ArrayList中，最后返回所有ArrayList。

方法二：使用计数器的方式，统计每个字符出现的次数，将计数器中的数字拼接成一个字符串作为key，将同一key的字符串放入同一个ArrayList中，最后返回所有ArrayList。

import java.util.*;
public class groupAnagrams {public static List<List<String>> groupAnagrams(String[] strs) {HashMap<String, ArrayList<String>> map = new HashMap<>();for (String str : strs) {char[] cs = str.toCharArray();Arrays.sort(cs);String key = String.valueOf(cs);if (!map.containsKey(key)) {map.put(key, new ArrayList<>());}map.get(key).add(str);}return new ArrayList<>(map.values());}public static List<List<String>> groupAnagrams2(String[] strs) {if (strs.length <= 0) {return new ArrayList<>();}HashMap<String, ArrayList<String>> map = new HashMap<>();for (String str : strs) {char[] cs = str.toCharArray();int[] count = new int[26];for (char c : cs) {++count[c - 'a'];}StringBuilder s = new StringBuilder("");for (int num : count) {s.append(num);}String key = String.valueOf(s);if (!map.containsKey(key)) {map.put(key, new ArrayList<>());}map.get(key).add(str);}return new ArrayList<>(map.values());}public static void main(String[] args) {String[] words = {"eat", "tea", "tan", "ate", "nat", "bat"};for (List<String> word : groupAnagrams(words)) {System.out.print(word);System.out.print("");}System.out.println();for (List<String> word : groupAnagrams2(words)) {System.out.print(word);System.out.print("");}System.out.println();}
}

输出：

[eat, tea, ate][bat][tan, nat]
[bat][tan, nat][eat, tea, ate]

2. 删除链表的倒数第 N 个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

进阶：你能尝试使用一趟扫描实现吗？

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

提示：

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

出处：

https://edu.csdn.net/practice/24612384

代码：

import java.util.*;
public class removeNthFromEnd {public static class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) {this.val = val;}ListNode(int val, ListNode next) {this.val = val;this.next = next;}}public static class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode v = new ListNode(0, head);ListNode handle = v;List<ListNode> index = new ArrayList<>();while (v != null) {index.add(v);v = v.next;}int pre = index.size() - n - 1;int next = index.size() - n + 1;index.get(pre).next = next >= 0 && next < index.size() ? index.get(next) : null;return handle.next;}}public static ListNode[] arraysToLists(int[][] nums) {ListNode[] lists = new ListNode[nums.length];for (int i = 0; i < nums.length; i++) {int[] arr = nums[i];ListNode head = new ListNode(0);ListNode cur = head;for (int num : arr) {cur.next = new ListNode(num);cur = cur.next;}lists[i] = head.next;}return lists;}public static void traverseList(ListNode head) {ListNode cur = head;int count = 0;while (cur != null) {count++;cur = cur.next;}System.out.print("[");for (cur = head; cur != null;) {System.out.print(cur.val);count--;if (count>0) {System.out.print(",");}cur = cur.next;}System.out.println("]");}public static void main(String[] args) {Solution s = new Solution();int[][] lists = {{1,2,3,4,5},{1},{1,2}};int[] n = {2,1,1}; //对应链表的倒数n值ListNode[] heads = arraysToLists(lists);List<ListNode> res = new ArrayList<>();for (int i = 0; i < n.length; i++) {res.add(s.removeNthFromEnd(heads[i], n[i]));traverseList(res.get(i));}}
}

输出：

[1,2,3,5]
[]
[1]

3. 合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示：

1 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= starti <= endi <= 10^4

出处：

https://edu.csdn.net/practice/24612385

代码：

import java.util.*;
public class mergeIntervals {public static class Solution {public int[][] merge(int[][] intervals) {List<int[]> res = new ArrayList<>();if (intervals == null) {return res.toArray(new int[0][]);}Arrays.sort(intervals, (a, b) -> a[0] - b[0]);int i = 0;int left = 0;int right = 0;while (i < intervals.length) {left = intervals[i][0];right = intervals[i][1];while (i < intervals.length - 1 && right >= intervals[i + 1][0]) {i++;right = Math.max(right, intervals[i][1]);}res.add(new int[] { left, right });i++;}return res.toArray(new int[0][]);}}public static void PrintArrays(int[][] arr) {System.out.print("[");for (int i = 0; i < arr.length; i++) {System.out.print("[");for (int j = 0; j < arr[i].length; j++) {System.out.print(arr[i][j]);if (j < arr[i].length - 1) {System.out.print(",");}}System.out.print("]");if (i < arr.length - 1) {System.out.print(",");}}System.out.println("]");}public static void main(String[] args) {Solution s = new Solution(); int[][] intervals = {{1,3},{2,6},{8,10},{15,18}};PrintArrays(s.merge(intervals));int[][] intervals2 = {{1,4},{4,5}};PrintArrays(s.merge(intervals2));}
}

输出：

[[1,6],[8,10],[15,18]]
[[1,5]]