详细介绍一下 贪心算法

贪心算法（Greedy Algorithm）是一种在每一步选择当前状态下局部最优解的算法策略，希望通过一系列局部最优选择得到全局最优解。

贪心算法通常比其他方法（如动态规划）简单、高效，但它并不总是适用，也无法保证在所有情况下找到最优解。

因此，使用贪心算法时需要先确认问题是否满足贪心选择的条件。

贪心算法的特点

1. 贪心选择性质：

   • 在解决问题时，可以通过每一步的局部最优选择来构成最终的全局最优解。
   • 这一性质意味着每一步的选择不会影响后续选择，从而使得只需关注当前状态下的最优决策，而不需要回溯或全面搜索。

2. 最优子结构：

   • 问题的最优解包含子问题的最优解，即可以通过递归或逐步的方式构建全局解。
   • 最优子结构性质是动态规划和贪心算法的共同特点，但贪心算法是基于“局部最优”，而动态规划则基于“全局最优”。

3. 无后效性：

   • 每一个选择只依赖当前状态，不受后续状态的影响。选完一次后，无需再回头修改。

给定一个二维整数数组 items ，其中 items[i] = [pricei, weighti] 表示第 i 个物品的价格和重量。

还给定一个 正 整数容量 capacity 。

每个物品可以分成两个部分，比率为 part1 和 part2 ，其中 part1 + part2 == 1 。

第一个物品的重量是 weighti * part1 ，价格是 pricei * part1 。

同样，第二个物品的重量是 weighti * part2 ，价格是 pricei * part2 。

使用给定的物品，返回填满容量为 capacity 的背包所需的 最大总价格 。

给定一个大小为 n 的整数数组 nums，其中包含从 0 到 n - 1 (包含边界) 的 每个 元素。

从 1 到 n - 1 的每一个元素都代表一项目，元素 0 代表一个空白区域。

在一个操作中，您可以将 任何 项目移动到空白区域。如果所有项目的编号都是 升序 的，并且空格在数组的开头或结尾，则认为 nums 已排序。

例如，如果 n = 4，则 nums 按以下条件排序:

nums = [0,1,2,3] 或
nums = [1,2,3,0]

...否则被认为是无序的。

返回排序 nums 所需的最小操作数。

给你一个二维 二进制 数组 grid。请你找出一个边在水平方向和竖直方向上、面积 最小 的矩形，并且满足 grid 中所有的 1 都在矩形的内部。

返回这个矩形可能的 最小 面积。

示例 1：

输入： grid = [[0,1,0],[1,0,1]]

输出： 6

解释：

0  1   0
1  0   1

是什么？

递归算法是一种在计算机科学中非常常见的解决问题的方法，它通过函数调用自身来解决问题。

递归通常将复杂的问题分解成更小的子问题，通过逐步缩小问题规模直到满足某种条件（基准情况或边界条件）停止递归调用，从而得到解答。

递归的基本组成部分

一个典型的递归算法包含两个关键部分：

1. 基准条件（Base Case）：基准条件是递归算法停止递归的条件。它通常用于处理最简单的情况，不需要进一步分解。例如，计算阶乘时，0! = 1 就是基准条件。

2. 递归条件（Recursive Case）：递归条件定义了如何将问题分解为更小的子问题，并递归地调用函数自身来处理这些子问题。例如，计算阶乘时，n! = n * (n - 1)! 是递归条件。

题目

汉诺塔（Tower of Hanoi）是一个经典的递归问题。问题描述是，有三个柱子和若干个盘子，初始状态下所有盘子按大小从小到大叠在第一个柱子上。目标是将所有盘子从第一个柱子移动到第三个柱子，但每次只能移动一个盘子，且大盘子不能放在小盘子上面。

解题思路

1. 分解问题：假设有 ( n ) 个盘子在柱子 A 上，要将它们移动到柱子 C 上，可以分解为两个步骤：

   • 步骤1：将前 ( n-1 ) 个盘子从 A 移动到柱子 B，借助 C。
   • 步骤2：将第 ( n ) 个盘子从 A 移动到柱子 C。
   • 步骤3：将 ( n-1 ) 个盘子从 B 移动到 C，借助 A。

2. 递归实现：将步骤 1 和步骤 3 递归调用，直到只剩下一个盘子为止。当只有一个盘子时，直接将它从起始柱子移动到目标柱子。

3. 基准条件：如果只有一个盘子，则直接从 A 移动到 C，不再进行递归。

为了便于大家学习，所有实现均已开源。欢迎 fork + star~

https://github.com/houbb/leetcode

56. 合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。

请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

大家好，我是老马。

今天我们一起来学习一下数组这种数据结构。

主要知识

数组需要拆分下面几个部分：

1. 理论介绍

2. 源码分析

3. 数据结构实现？

4. 题目练习（按照算法思想分类）

5. 梳理对应的 sdk 包

6. 应用实战

因为这个是 leetcode 系列，所以重点是 4、5(对4再一次总结)。

为了照顾没有基础的小伙伴，会简单介绍一下1的基础理论。

大家好，我是老马。

今天我们一起来学习一下数组这种数据结构。

主要知识

数组需要拆分下面几个部分：

1. 理论介绍

2. 源码分析

3. 数据结构实现？

4. 题目练习（按照算法思想分类）

5. 梳理对应的 sdk 包

6. 应用实战

因为这个是 leetcode 系列，所以重点是 4、5(对4再一次总结)。

为了照顾没有基础的小伙伴，会简单介绍一下1的基础理论。

大家好，我是老马。

今天我们一起来学习一下数组这种数据结构。

主要知识

数组需要拆分下面几个部分：

1. 理论介绍

2. 源码分析

3. 数据结构实现？

4. 题目练习（按照算法思想分类）

5. 梳理对应的 sdk 包

6. 应用实战

因为这个是 leetcode 系列，所以重点是 4、5(对4再一次总结)。

为了照顾没有基础的小伙伴，会简单介绍一下1的基础理论。