算法分析-二叉树展开为链表
今天继续研究算法：二叉树展开为链表 给你二叉树的根结点 ，请你将它展开为一个单链表：展开后的单链表应该同样使用 ，其中 子指针指向链表中下一个结点，而左子指针始终为 。展开后的单链表应该与二叉树 顺序相同。 进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？ 看到这个题我的头就开始痛了，因为好久没接触树了，连遍历方法都忘得一干二净了，不过既然遇到了那就把它解决掉，长痛不如短痛。 先捡一下…
算法分析-最大子数组和
刚做了乘积最大子数组，现在趁热打铁继续研究：最大子数组和 给你一个整数数组 ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 子数组是数组中的一个连续部分。 理解上一题之后，再看这道题就简单了。 不用担心负号会直接将结果反转，所以不用记录下最小的值。 只需要当前面的子串之和已经是负数时，就截断子串，由当前值重新开一个子串即可。 光说概念有些抽象，现在我将拆解一个例子来…
算法分析-乘积最大子数组
继续研究：乘积最大子数组 给你一个整数数组 ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。测试用例的答案是一个 32 位整数。注意，一个只包含一个元素的数组的乘积是这个元素的值。 这个题的关键在于处理 和负数，因为正数连乘只会越乘越大。 子串中有 ，乘积结果就是 。 子串中有奇数个负数，越乘越小；有偶数个负数，负负得正，也会越来越大。 我尝试使…
算法分析-无重复字符的最长子串
继续研究：无重复字符的最长子串 给定一个字符串 ，请你找出其中不含有重复字符的最长子串的长度。 首先想到的方法是遍历并将字符压入栈中，遇到已经在栈中存在的元素则记录下栈的长度后清空栈，对字符串中每一个字符都如此操作一遍。 不出我所料，提交时果然超时了。 时间 $O(n^3)$：外层循环 次，内层遍历 最坏 次，每次 要线性扫描栈（最坏 ），三层相乘。空间 $O(n)$。 优化一下。既然清空栈的时候…
算法分析-删除链表的倒数第 N 个结点
今天继续尝试：删除链表的倒数第 N 个结点 给你一个链表，删除链表的倒数第 个结点，并且返回链表的头结点。 我的想法是：使用两个指针，让它们相隔 个节点，然后同时向后移动。当后面的快指针到达链表末尾时，慢指针的位置就是待删节点的前驱。 这里使用哨兵节点的原因是为了方便删除节点，比如 等于链表长度时需要删除头节点，不使用哨兵节点的话无法操作。 使用双指针，一趟扫描完，$O(n)$ 时间 $O(1)$…
算法分析-有效的括号
继续研究：有效的括号 给定一个只包括 、、、、、 的字符串 ，判断字符串是否有效。 有效字符串需满足：左括号必须用相同类型的右括号闭合，左括号必须以正确的顺序闭合，每个右括号都有一个对应的相同类型的左括号。 这道题我曾经做过几次，思路基本上是用栈后进先出的特性来解决。 遇到左括号，压入栈中。遇到右括号，看与栈顶左括号能否匹配上，能匹配则弹出栈顶；与栈顶不匹配直接返回 。一一匹配完后看栈中是否还有剩…
算法分析-合并 K 个升序链表
今天尝试：合并 K 个升序链表。 给你一个链表数组，每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中，返回合并后的链表。 思考半天没有头绪，试试暴力解法：遍历链表将所有节点放入一个数组，排序后转成新的链表返回。 比较取巧，利用了 Python 本身的排序。 时间复杂度：$O(N \log N)$， 是所有节点总数。空间：$O(N)$（ 数组）。 这里并没用到"每条链表本身已经有序"这…
算法分析-字母异位词分组
今天研究：字母异位词分组 给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。 读题发现，就是说两个词的字母相同，但是顺序不同，一个词可以通过调整字母顺序变成另一个词，这两个就是字母异位词。 理论上来说，遍历一遍数组，将元素一个个归类就行，难点在于如何知道两个词是异位词。 我首先的想法是将字符串排序，异位词经过排序后就变成了相同的词。然后将排序后的字符串作为 放到字典中归类…