Leetcode 236：二叉树的最近公共祖先 题目描述 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 示例 示例 1: 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出: 3 解释: 节点 5 和节点 1 的最近公共祖先是节点 3。 示例 2: 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出: 5 解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近…

Leetcode 239：滑动窗口最大值 题目描述 给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回滑动窗口中的最大值。 示例 输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3 输出: [3,3,5,5,6,7] 解释: 滑动窗口的位置 最大值 --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 …

Leetcode 279：完全平方数 题目描述 给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。 示例 示例1： 输入: n = 12，输出: 3 解释: 12 = 4 + 4 + 4. 示例2： 输入: n = 13输出: 2 解释: 13 = 4 + 9. 解题思路 这个题很容易想到用动态规划做，为什么呢？因为我们输入一个元素，可以把它分割为多个子问题（例如13=4+9,4有多少种方法、9有多少种方法，就是子问题），而且它…

Leetcode 287：寻找重复数 题目描述 给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。 示例 输入: [1,3,4,2,2]，输出: 2 输入: [3,1,3,4,2]，输出: 3 解题思路 代码实现 int findDuplicate(vector<int>& nums) { int len = nums.size(); if (len < 1) retur…

Leetcode 301：删除无效的括号 题目描述 删除最小数量的无效括号，使得输入的字符串有效，返回所有可能的结果。 说明: 输入可能包含了除 ( 和 ) 以外的字符。 示例 示例1： 输入: "()())()" 输出: ["()()()", "(())()"] 示例2： 输入: "(a)())()" 输出: ["(a)()()", "(a())()"] 示例3： 输入: ")(" 输出: [""] 代码实现 class Solution { public: void DFS(string s, char ch,…

题目描述 题目1： 买卖股票的最佳时机 I。给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。注意你不能在买入股票前卖出股票。 题目2： 买卖股票的最佳时机 II。给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 题目3： 买卖股票的最佳…

Leetcode 309：最佳买卖股票时机含冷冻期 题目描述 给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。 设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。 示例 输入: [1,2,3,0,2] 输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出] 解题思路 这又是一个动态规划问题，我们思…