在此立个 Flag:遵循我的每日安排!并且坚持 21 天!
期间中断不能超过 1 天,避免意外情况。
失败惩罚:一个星期不许进行任何娱乐活动!
算法题
:happy: 今天悟出来的做题经验:
- 先根据题意,写出最简单的、最能想得到的思路。
- 然后把思路转变为代码,并且额外留意区间的临界点。
临界点:除一般情况外,代码逻辑并不能正确执行的某个状态。
- 再根据题目标签(涉及的数据结构)和题目要求,一步一步的优化代码。
链表指定区间反转
给出一个区间的起始位置和结束位置,要求反转这个区间的节点,然后重新和整个链表连接上。
解题思路:找到这个区间的前置节点(起始位置的前一个)和后置节点(同理),然后遍历反转这段区间的节点,再分别用前置和后置节点连上。
临界点:链表为空、区间长度为1。
难点:起始点可能在头部,需要一个假的头节点作为前置节点来连接整个链表。
也可以把这个作为一个“临界点”处理。if m == 1
合并两个有序链表
输入两个递增的链表,单个链表的长度为n,合并这两个链表并使新链表中的节点仍然是递增排序的。
解题思路:创建一个新的头节点用来构建新链表,分别同时遍历两个链表,循环取出值更小的那一个,直到其中一个链表为空,尾部直接全部接上另一个链表。
临界点:任意一个链表为空。
难点:代码条件关系的判断。
字母异位词分组
给一个字符串数组,要求将属于同一类字母异位词的字符串组成一个新的数组。
字母异位词:如果将一个字符串中的所有字母任意排列可以得到另一个字符串,即互为字母异位词。
解题思路:既然每个异位词包含的所有字母都是相同的,那么将字母重新按照字典序排序得到的结果就一定是一样的。此时只需要创建一个以字典序为 key,异位词数组为 value 的哈希表,遍历完整个数组就能得到按异位词分组的数组了。
“bat”, “bta”, “atb” => “abt”
难点:发现一组字母异位词(题干)的共同点(分组依据)。
最长连续序列
给定一个未排序的整数数组 nums
,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。
解题思路:遍历数组,以元素 x 为起始值,尝试匹配 x+1, x+2, … , x+y 符合连续序列的值是否存在,记录最大的连续长度。
难点:降低时间复杂度
- 暴力匹配:第一层遍历元素 x,第二层匹配 1-y 连续值,第三层再次遍历是否存在,总时间 O(n^3^)
- 哈希索引:先遍历一遍构建哈希索引,将第三层的判断缩减为 O(n),总时间 O(n^2^)
- 剔除子区间:在尝试匹配连续序列前,应先检验 x-1 是否存在,如果存在那么从 x-1 开始的序列长度一定大于本元素起始的序列,所以直接跳过匹配,综合计算总时间 O(n)。
面试题
思路:
- 先找到提问关注点,针对性回答。
类似举例的问题可以相对粗略的回答,指明是原理就应该详细回答。
- 不应该直接扯到深层知识,可以留给面试官提问的空间。