LeetCode初级算法之动态规划：53.最大子序和
题目信息
题目地址：https://leetcode-cn.com/problems/maximum-subarray/
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
123输入: [-2,1,-3,4,-1,2,1,-5,4]输出: 6解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
解法一：动态规划首先我们去划分一下子问题。整个数列的最大子序和，他是可能就等于n-1的最大子序和，它也可以是个新的值。至少是这两种情况
情况一：
123[-1,3,1,-4,1]当前数列的最大子序和就是4也就是(1,2)项。它也是前n-1项的最大子序和
情况二：
123[-1,3,1,-4,5]当前数列的最大子序和是5也就是(4)项而前n-1项的数列最大子序和还是4也就是(1,2)项
每次往后迭代一个值它的结果可能变化也可能不变化，这就是记录的点。我们算出当前最大的值然后与之前的result进行比较可能更新result也可能不变，进行下个迭代再次 ...
LeetCode初级算法之动态规划：121.买卖股票的最佳时机
题目信息
题目地址：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
1234输入：[7,1,5,3,6,4]输出：5解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：
123输入：prices = [7,6,4,3,1]输出：0解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
提示：
121 <= prices.length <= 1050 <= prices[i] < ...
去大理
《去大理》谱子收藏、全文查看
您的浏览器不支持视频标签
再见
《再见》谱子收藏、全文查看
您的浏览器不支持视频标签
LeetCode初级算法之动态规划：70.爬楼梯
题目信息
题目地址： https://leetcode-cn.com/problems/climbing-stairs/
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意： 给定 n 是一个正整数。
示例 1：
12345输入： 2输出： 2解释： 有两种方法可以爬到楼顶。1. 1 阶 + 1 阶2. 2 阶
示例 2：
123456输入： 3输出： 3解释： 有三种方法可以爬到楼顶。1. 1 阶 + 1 阶 + 1 阶2. 1 阶 + 2 阶3. 2 阶 + 1 阶
思路一：斐波那契数列我们可以看先推演几个看看
一个台阶：只有一种跳法就是跳一格
两个台阶：跳一格跳两次和跳一次2格的
三个台阶：1+1+1、2+1、1+2（共三种）
四个台阶：1+1+1+1、2+1+1、1+2+1、1+1+2、2+2（共五种）
五个台阶1+1+1+1、2+1+1+1、1+2+1+1、1+1+2+1、1+1+1+2、2+2+1、2+1+2、1+2+2（共八种）
我们可以得到一个规律，他是一个斐波那契数列，题目正 ...
LeetCode初级算法之排序和搜索：278.第一个错误版本
题目信息
题目地址：https://leetcode-cn.com/problems/first-bad-version/
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例：
1234567给定 n = 5，并且 version = 4 是第一个错误的版本。调用 isBadVersion(3) -> false调用 isBadVersion(5) -> true调用 isBadVersion(4) -> true所以，4 是第一个错误的版本。
解法一：暴力从第一个版本直接顺着遍历直到首次出现错误版本，不就是第一个嘛
123456789pub ...
LeetCode初级算法之排序和搜索：88.合并两个有序数组
题目信息
题目地址：https://leetcode-cn.com/problems/merge-sorted-array/
给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
说明：
初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
示例：
12345输入：nums1 = [1,2,3,0,0,0], m = 3nums2 = [2,5,6], n = 3输出：[1,2,2,3,5,6]
提示：
123-10^9 <= nums1[i], nums2[i] <= 10^9nums1.length == m + nnums2.length == n
解法一：双指针（顺序扫描）很直接的就是双指针扫描，与上次我们在链表时写过【合并有序链表】同样的通过扫描与大小比较最终扫描完两个序列（m+n），前者是新建一个头节点然后遍历过程中慢慢连。这边也是可以创建一个数组，每扫描一 ...
LeetCode初级算法之树：108.将有序数组转二叉树
题目信息
题目地址：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
12345 0 / \ -3 9 / /-10 5
题解：递归（中序）一个升序数组，转二叉树还是并且是搜索树（右子树小左子树），因此这个数组相当于是搜索树的中序遍历
对于示例的数组：[-10,-3,0,5,9]，转化为二叉搜索树结果是有很多
比如：
12345 0 / \ -3 5 / \-10 9
12345 5 / \ -3 9 / \ -10 0
题目当前是要得高度平衡的一个解（因此上面一个 ...