Java教程

算法题今日总结(20210801)

本文主要是介绍算法题今日总结(20210801),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录

1. 变位词组

2. 两数相加

3. 无重复字符的最长子串


1. 变位词组

对字符串数组进行排序,将所有变位词组合在一起。变位词是指字母相同,但排列不同的字符串。

例子:

输入: ["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>();

一行代码可以减少判断

2. 两数相加

两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。请你将两个数相加,并以相同形式返回一个表示和的链表。

输入:l1 = [2,4,3], l2 = [5,6,4]
输出:[7,0,8]
解释:342 + 465 = 807.

解题方法:

1.  遍历两链表,依次相加

踩坑:

1. 将链表数据转换为long,然后数值相加,测试数据超出long类型的最大值,计算结果错误

2. 最后一位相加时,进位1为做处理。

3. 无重复字符的最长子串

找出其中不含有重复字符的 最长子串 的长度。

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 “abc”, 所以输出3

解题方法:

1. 遍历字符,记录每个字符及下标,当重复出现时,遍历指针跳到此字符下标的地方,记录此子串的长度,后续子串长度大于此子串,则覆盖返回结果

2. 左右指针,左指针依次递增,左指针每移动一次,右指针移动直到出现重复字符,此时左指针和右指针之间的字符为不包含重复的子串,每次记录最大长度。

今日小结:

1. 做题是总是想的太简单,基本都是暴力解法

2. 特殊情况,边界值的考虑不到位

这篇关于算法题今日总结(20210801)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!