算法分析-二叉树展开为链表
今天继续研究算法：二叉树展开为链表 给你二叉树的根结点 ，请你将它展开为一个单链表：展开后的单链表应该同样使用 ，其中 子指针指向链表中下一个结点，而左子指针始终为 。展开后的单链表应该与二叉树 顺序相同。 进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？ 看到这个题我的头就开始痛了，因为好久没接触树了，连遍历方法都忘得一干二净了，不过既然遇到了那就把它解决掉，长痛不如短痛。 先捡一下…
Category
算法学习
算法分析-最大子数组和
刚做了乘积最大子数组，现在趁热打铁继续研究：最大子数组和 给你一个整数数组 ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 子数组是数组中的一个连续部分。 理解上一题之后，再看这道题就简单了。 不用担心负号会直接将结果反转，所以不用记录下最小的值。 只需要当前面的子串之和已经是负数时，就截断子串，由当前值重新开一个子串即可。 光说概念有些抽象，现在我将拆解一个例子来…
算法分析-乘积最大子数组
继续研究：乘积最大子数组 给你一个整数数组 ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。测试用例的答案是一个 32 位整数。注意，一个只包含一个元素的数组的乘积是这个元素的值。 这个题的关键在于处理 和负数，因为正数连乘只会越乘越大。 子串中有 ，乘积结果就是 。 子串中有奇数个负数，越乘越小；有偶数个负数，负负得正，也会越来越大。 我尝试使…
算法分析-无重复字符的最长子串
继续研究：无重复字符的最长子串 给定一个字符串 ，请你找出其中不含有重复字符的最长子串的长度。 首先想到的方法是遍历并将字符压入栈中，遇到已经在栈中存在的元素则记录下栈的长度后清空栈，对字符串中每一个字符都如此操作一遍。 不出我所料，提交时果然超时了。 时间 $O(n^3)$：外层循环 次，内层遍历 最坏 次，每次 要线性扫描栈（最坏 ），三层相乘。空间 $O(n)$。 优化一下。既然清空栈的时候…
算法分析-删除链表的倒数第 N 个结点
今天继续尝试：删除链表的倒数第 N 个结点 给你一个链表，删除链表的倒数第 个结点，并且返回链表的头结点。 我的想法是：使用两个指针，让它们相隔 个节点，然后同时向后移动。当后面的快指针到达链表末尾时，慢指针的位置就是待删节点的前驱。 这里使用哨兵节点的原因是为了方便删除节点，比如 等于链表长度时需要删除头节点，不使用哨兵节点的话无法操作。 使用双指针，一趟扫描完，$O(n)$ 时间 $O(1)$…