leetcoder专题

LeetCoder 33. Search in Rotated Sorted Array(二分)

是把一个升序的数组，前面的连续的一部分（可以是空）放在数组的后面，然后再这个数组这中找一个给出的值，数组中不存在重复的元素。这个题目也是《剑指offer》二分查找的一道例题 class Solution {public:int search(vector<int>& nums, int target) {int l = 0, r = nums.size()-1;while(l <= r)

Leetcoder Day40｜动态规划part07

322. 零钱兑换给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。你可以认为每种硬币的数量是无限的。示例 1：输入：coins = [1, 2, 5], amount = 11输出：3解释：11 = 5 + 5 + 1 示例 2：输入：coins = [2], amou

Leetcoder Day36｜动态规划part03

343. 整数拆分给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。返回你可以获得的最大乘积。示例 1: 输入: 2输出: 1解释: 2 = 1 + 1, 1 × 1 = 1。示例 2: 输入: 10输出: 36解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。说明: 你可以假设 n 不小于 2 且不大于 58。本题需要注意的是，至

Leetcoder Day37｜动态规划part04 背包问题

01背包理论基础面试掌握01背包，完全背包和重背包就够用了。背包问题的理论基础重中之重是01背包，一定要理解透！ 01 背包有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。每一件物品其实只有两个状态，取或者不取，所以可以使用回溯法搜索出所有的情况，

Leetcoder Day35｜动态规划part02

62.不同路径一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？示例 1：输入：m = 3, n = 7输出：28 示例 2：输入：m = 3, n = 2输出：3解释：从左上角开始，总共有 3 条路径可以

Leetcoder Day34｜动态规划part01

动态规划理论基础什么是动态规划动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。所以动态规划的每一个状态一定是从上一个状态推导出来的，这一点有别于贪心算法，贪心是从局部直接选择最优，不需要推导。比如背包问题：有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i

Leetcoder Day32｜贪心算法part05

738.单调递增的数字给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。（当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。）示例 1: 输入: N = 10输出: 9 示例 2: 输入: N = 1234输出: 1234 示例 3: 输入: N = 332输出: 299 class

Leetcoder Day29｜贪心算法part03

1005.K次取反后最大化的数组和给定一个整数数组 A，我们只能用以下方法修改该数组：我们选择某个索引 i 并将 A[i] 替换为 -A[i]，然后总共重复这个过程 K 次。（我们可以多次选择同一个索引 i。）以这种方式修改数组后，返回数组可能的最大和。示例 1：输入：A = [4,2,3], K = 1输出：5解释：选择索引 (1,) ，然后 A 变为 [4,-2,3]。示例 2：

Leetcoder Day27｜贪心算法part01

语言：Java/Go 理论贪心的本质是选择每一阶段的局部最优，从而达到全局最优。什么时候用贪心？可以用局部最优退出全局最优，并且想不到反例到情况贪心的一般解题步骤将问题分解为若干个子问题找出适合的贪心策略求解每一个子问题的最优解将局部最优解堆叠成全局最优解 455.分发饼干假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩

Leetcoder Day25｜回溯part05：子集+排列

491.递增子序列给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。示例: 输入:[4, 7, 6, 7]输出: [[4, 6], [4, 7], [4, 6, 7], [6, 7], [7,7], [4,7,7]] 说明: 给定数组的长度不会超过15。数组中的整数范围是 [-100,100]。给定数组中可能包含重复数字，相等的数字应该被视为递增的一种情况

Leetcoder Day26｜回溯part06：总结+三道hard题

332.重新安排行程给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。提示：如果存在多种有效的行程，请你按字符自然排序返回最小的行程组合。例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相

Leetcoder Day21｜回溯理论基础+组合

语言：Java/Go 回溯理论基础回溯函数也就是递归函数；所有回溯法的问题都可以抽象为树形结构；回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，都构成的树的深度。适用的题目类型：组合问题：N个数里面按一定规则找出k个数的集合切割问题：一个字符串按一定规则有几种切割方式子集问题：一个N个数的集合里有多少符合条件的子集排列问题：N个数按一定规则全

Leetcoder Day17｜二叉树 part06

语言：Java/C++ 654.最大二叉树给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：二叉树的根是数组中的最大元素。左子树是通过数组中最大值左边部分构造出的最大二叉树。右子树是通过数组中最大值右边部分构造出的最大二叉树。通过给定的数组构建最大二叉树，并且输出这个树的根节点。示例：题目中说了输入的数组大小一定是大于等于1的，所以我们不用考虑小于1

Leetcoder Day18｜二叉树 part07

语言：Java/Go 今天做了一个小决定，如果时间不够的话，可以先看go去找工作，所以现在加上用go去刷题 530.二叉搜索树的最小绝对差给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。示例：遇到二叉搜索树，就要想到中序遍历是有序的，因此依然可以将二叉搜索树转换为中序遍历数组求解。在二叉搜索树上求什么最值，求差值之类的，都要思考一下二叉搜索树可