2021-09-30发表2021-09-30更新算法与数据结构11 分钟读完 (大约1697个字)贪心算法基础-2本文继续介绍重要的贪心算法，比如哈夫曼编码、最小生成树等算法。 最优前缀码及哈夫曼编码 二元前缀码 二元前缀码：用0-1字符串作为代码表示字符，要求任何字符的代码都不能作为其它字符代码的前缀。 非前缀码的例子： a: 001, b: 00, c: 010, d: 01 解码的歧义，例如字符串0100001 解码1：01,00,001 ⟹ \implies⟹ d,b,a 解码2：010,00,01 ⟹ \implies⟹ c,b,d 阅读更多
2021-09-18发表2021-09-18更新算法与数据结构15 分钟读完 (大约2219个字)贪心算法基础本文开始记录贪心算法的学习。 贪心算法的例子——活动选择问题 输入：S={1,2,...,n}S=\{1,2,...,n\}S={1,2,...,n}为nnn项活动的集合，sis_isi、fif_ifi分别为活动iii的开始和结束时间。 活动iii 与jjj相容 ⟺ si≥fj\iff s_i \ge f_j⟺si≥fj 或 sj≥fis_j \ge f_isj≥fi 求：最大的两两相容的活动集AAA阅读更多