会议日程安排问题

  1. 题目解释
    1. 一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目宣讲。给你每个项目的开始时间和结束时间，你来安排宣讲的日程，要求会议室进行宣讲的场数最多。
    2. 返回最多的宣讲场次。
  2. 思路：本题常见的几种贪心策略，
    1. 一种是按照谁先开始安排谁，
    2. 第二种按照持续时间短的先安排，
    3. 第三种按照谁先结束安排谁。
  3. 通过验证，无需证明得出第三种贪心策略是正确的
    1. 方法一:全排列,暴力解出
    2. 方法二:写比较器,根据谁的结束时间早,来排序

居民楼路灯问题

  1. 题目解释
    1. 给定一个字符串str，只由‘X’和‘.’两中国字符构成。
    2. ‘X’表示墙，不能放灯，也不需要点亮，‘.’表示居民点，可以放灯，需要点亮。
    3. 如果灯放在i位置，可以让i-1，i和i+1三个位置被点亮，返回如果点亮str中所需要点亮的位置，至少需要几盏灯
    4. 例如： .X…X…X…X. 需要至少5盏灯
  2. 纯暴力，用来做对数器。点的位置放灯和不放灯全排列
  3. 贪心解法
    1. 如果i位置是X,就跳到i+1位置做决定
    2. 如果i位置是.
      1. 如果i+1位置是X,必须在i位置放灯,再去i+2做决定
      2. 如果i+1位置是.
        1. 如果i+2是X,i+1放灯,再去i+3做决定
        2. 如果i+2是.,i+1放灯,再去i+3做决定
  4. 代码:

哈夫曼树问题

  1. 题目解释
    1. 一根金条切成两半，是需要花费和长度值一样的铜板的。
    2. 比如长度为20的金条，不管怎么切，都需要花费20个铜板。一群人想整分整块金条，怎么分最省铜板？
    3. 例如：给定数组[10,20,30]，代表一共三个人，整块金条长度为60，金条要分成10,20,30三个部分。
      1. 如果先把长度为60的金条分成10和50，花费60；
      2. 再把长度为50的金条分成20和30，花费50；一共需要花费110个铜板。
      3. 但是如果先把长度为60的金条分成30和30，花费60;
      4. 再把30的金条分成10和20,花费30；一共花费90个铜板。
    4. 输入一个数组，返回分割的最小代价。
  2. 贪心策略最常用的手段
    1. 小根堆
    2. 大根堆
    3. 排序
  3. coding代码量很少。因为堆天然就具备根据我们自定义的排序规则重新组织数据的能力,然后依次弹出样本,本身包含贪心的意思.
  4. 暴力解法
  5. 贪心解法
    1. 贪心解法，建立一个小根堆，把所有数扔进去
    2. 每一次弹出两个数，合并成一个数
    3. 代价就是非叶子节点

项目花费和利润问题

  1. 题目解释
    1. 输入：正数数组costs，正数数组profits,正数K,正数M
    2. costs[i]表示i号项目的花费，profits[i]表示i号项目在扣除花费之后还能挣到的钱（利润）
    3. K 表示你只能串行的最多 K 个项目， M 表示你的初始资金。
    4. 说明：每做完一个项目，马上获得收益，可以支持你去做下一个项目。不能并行的做项目。
    5. 输出：你最后获得的最大钱数。