数据结构和算法.

参考:

贪心算法

  1. 贪心算法属于局部优化算法, 无法保证找到全局最优解(如果需要请考虑动态规划)

贪心算法适合以下两种情况:

  • 最优解可以被贪心算法捕获 – 此种情况下, 贪心较动态规划,回溯要高效
  • 只需要近似最优解的结果 – 复杂问题下的近似最优解, 贪心也许是较高效率能够完成的

关于最优解能够被贪心算法捕获问题的贪心选择特质:局部最有特性同样延续到全局整体, 即: 最优子结构

逻辑思考步骤:

  1. 问题分析: 状态, 约束和目标
  2. 贪心策略: 最小步骤的贪心逻辑
  3. 正确性证明: 贪心选择性和最优子结构. 数学方法->归纳法或者反证法.

典型例题:

硬币找零 [leetcode #322 零钱兑换]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        // coins 有序列表, 如果无序就需要排序
        int i = coins.size() - 1;
        int count = 0;
        while(amount > 0) {
            // 找到小于且最接近剩余金币的硬币
            while (i > 0 && coins[i] > amount) {
                i--;
            }
            amount -= coins[i];
            count++;
        }
        return amount == 0 ? count : -1;
    }
};
// [2,5,10,1] 27 需要排序才行

红黑树 [Red-Black-Tree]

红黑树的详细实现设计和实现逻辑, 请参考:剑指offer–深入理解红黑树原理

二叉树–>平衡二叉树–>红黑树

二叉树会在极端情况下退化成链表, 为了防止这种情况出现, 于是发明了平衡二叉树[保证节点的子树高度不超过1], 但是, 为了维护树的平衡性, 就需要左旋或者右旋进行节点调整, 而频繁的插入和删除时就会带来频繁的旋转操作, 进而近似平衡的红黑树的出现, 折中平衡和旋转效率.

红黑树实现时以下5条约束实现:

  1. 根节点是黑色
  2. 节点不是红色就是黑色
  3. nil节点一定是黑色
  4. 若一个节点是红色的，则它的子节点必须是黑色
  5. 一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点

以上5个约束条件推算红黑树存在以下优势:

  • 红黑树从根节点到叶子节点的最长路径, 不会大于最短路径的两倍. –>限制红黑树的平衡差
  • n个节点的红黑树的深度最多为2log(1+n), 不平衡都会在O(1)次旋转内解决. –> 二叉树查找次数取决于深度, 红黑树效率是O(logn)级别