目录
1. 变位词组
2. 两数相加
3. 无重复字符的最长子串
对字符串数组进行排序,将所有变位词组合在一起。变位词是指字母相同,但排列不同的字符串。
例子:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
解题方法:
1. 遍历输入集,记录每个字符串中每个字符及出现的次数作为hash表的key
2. 对每个字符串按字符排序,相同的字符归为一组
大神优秀题解法:
public List<List<String>> groupAnagrams(String[] strs) { return new ArrayList<>(Arrays.stream(strs) .collect(Collectors.groupingBy(s -> s.chars() .sorted().mapToObj(t -> String.valueOf((char) t)) .reduce(String::concat))) .values()); }
流式处理:先把入参转List, 字符排序然后相同的归一组
额外了解到的map方法:
List<String> tempList = map.getOrDefault(key, new ArrayList<String>();
一行代码可以减少判断
两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。请你将两个数相加,并以相同形式返回一个表示和的链表。
输入:l1 = [2,4,3], l2 = [5,6,4] 输出:[7,0,8] 解释:342 + 465 = 807.
解题方法:
1. 遍历两链表,依次相加
踩坑:
1. 将链表数据转换为long,然后数值相加,测试数据超出long类型的最大值,计算结果错误
2. 最后一位相加时,进位1为做处理。
找出其中不含有重复字符的 最长子串 的长度。
输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 “abc”, 所以输出3
解题方法:
1. 遍历字符,记录每个字符及下标,当重复出现时,遍历指针跳到此字符下标的地方,记录此子串的长度,后续子串长度大于此子串,则覆盖返回结果
2. 左右指针,左指针依次递增,左指针每移动一次,右指针移动直到出现重复字符,此时左指针和右指针之间的字符为不包含重复的子串,每次记录最大长度。
1. 做题是总是想的太简单,基本都是暴力解法
2. 特殊情况,边界值的考虑不到位