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 <= 300 <= Node.val <= 1001 <= 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^4intervals[i].length == 20 <= 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]]
🌟 每日一练刷题专栏 🌟
✨持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
☸ 主页：https://hannyang.blog.csdn.net/
