LeetCode 热题 100-二叉树二叉树的中序遍历递归123456789101112131415161718192021222324252627/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right;

LeetCode 热题 100-链表相交链表双指针 123456789101112131415161718192021222324/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x),

LeetCode 热题 100-矩阵矩阵置零分析 一个直观的解决方案是使用 O(mn) 的额外空间：即用一个$m \times n$的数组保存原数组。 一个简单的改进方案是使用 O(m + n) 的额外空间：即用两个标记数组分别记录每一行和每一列是否有零出现。 可以用矩阵的第一行和第一列代替方法一中的两个标记数组，以达到 O(1) 的额外空间。但这样会导致原数组的第一行和第一列被修改，无法记录

LeetCode 热题 100-普通数组最大子数组和动态规划 划分阶段：按子数组结尾的位置划分阶段。 定义状态：dp[i]表示以nums[i]结尾的最大子数组和。 状态转移方程：dp[i] = max(dp[i-1], 0) + nums[i]。 初始条件：dp[0] = nums[0]。 返回结果：维护一个最大和变量。 123456789101112class Soluti

LeetCode 热题 100-子串和为k的子数组前缀和数组不是单调的话，不要用滑动窗口，考虑用前缀和。前缀和i到j-1之间为prefix[j] - prefix[i] = k，即prefix[i] = prefix[j] - k，即遍历所有的j，统计prefix[i]出现的次数。 两次遍历做法： 12345678910111213141516171819class Solution {

LeetCode 热题 100-滑动窗口无重复字符的最长子串滑动窗口使用哈希表+滑动窗口。如果当前字符没有在哈希表中出现过，就将其加入哈希表，右指针继续向右，right-left+1是当前长度，不断更新最大长度；否则不断向右滑动左窗口，直至遇到哈希表内没有当前元素，再把当前元素加入哈希表。 123456789101112131415161718192021222324252627282930313

单调栈（矩形面积/贡献法/最小字典序）如果当前元素比栈顶小，直接入栈；否则，把所有小于等于它的元素弹出，再将其放入。因此，栈中的元素一定是有序的，称之为单调栈。 每日温度从右向左如果当前元素比栈顶小，直接入栈，并且当前元素的下一个更高温度就是1；否则，把所有小于等于它的元素弹出，再将其放入，当前元素的下一个更高温度就是栈顶元素。即，找到第一个大于当前元素的栈中元素，其值应该是栈

LeetCode 热题 100-双指针移动零分析一个指针逐个遍历元素，如果它所指的元素是0，就定义一个新的指针，不断后移直到其所指不为0，交换两指针元素。 1234567891011121314151617class Solution {public: void moveZeroes(vector<int>& nums) { int n

LeetCode 热题 100-哈希表两数之和哈希表使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N) 降低到 O(1)。 创建一个哈希表，对于每一个 x，首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。 1234567891011121314class Solution {public: vec

07.04 第 088 ~ 100 题（第 13 ~ 16 天）买股票的最佳时机分析初步考虑每次结算出在第i天买入在第j天售出所能获得的利润，且j> i，维护一个变量记录最大值。但是这样的时间复杂度是O(n)，无法通过所有的测试用例，因此进行优化。 假设股票在第i天售出，那么需要知道前i-1天中股票价格的最小值，用一个变量维护，因此只需一次遍历即可。 12345678910111213141