景铭的博客

Thinking will not overcome fear but action will.

Leetcode按题目类型总结(二十)

字典树

所有代码详见:https://github.com/jingminglake/Leetcode 总体思路 前缀树是树结构,特点是其中从根往下走的路径,是有前缀意义的。最常见的是字母前缀树,路径本质是单词和单词的前缀。 前缀树和hashtable的关系 相同之处在于,两者都可以对一组信息(例如一个字典,也就是单词集合)进行存储和管理,对hash技术来说就是存储到一张hash表里...

乐理概要

掌握必要乐理基础知识(一)

乐理对人们对音乐发展中重复性和本质性的内容进行提炼而形成的。通过学习乐理,我们可以站在巨人的肩膀上。 学乐理对实践音乐有巨大帮助,包括欣赏音乐、唱歌、弹琴、交流音乐等等。 一、音乐的物理原理 音乐由声音构成,由人耳感知。往往是物体(例如乐器)在发生形变的时候震动带动了空气一起震动,形成声波然后传入人耳。其中 声波的要素有三个:幅度、时间、频率(每秒多少次震动)。 二、音高 人耳对不同声波进...

Github博客写作

为什么使用Github博客

前言 偶然在网上搜博客搭建,就发现了 qiubaiying 经典教程,就果断决定来操作下。 原来的博客需要花时间迁移过来,现在也还是处于学习阶段。 为什么要迁徙到Github博客呢?请看正文。 正文 静态博客是指主要提供静态文本,而不提供复杂的函数功能服务的博客。这其实已经满足了大部分人的要求,毕竟写文章才是博客的核心。 博文的内容也无非就是技术总结,生活感悟,想法等。对我来说,...

Leetcode按题目类型总结(十九)

线段树(Segment Tree)和树状数组(Binary Indexed Tree)

所有代码详见:https://github.com/jingminglake/Leetcode 总体思路 具体题目 307. Range Sum Query - Mutable 题意:给出一个整数数组nums,求给出下标区间,求区间和,另外,要实现一个update函数,可以修改nums中任意下标的数字。 解:如果是不修改的,那么可以使用前缀数组和来计算,但是当数组可变的情况下...

Leetcode按题目类型总结(十八)

数学类

所有代码详见:https://github.com/jingminglake/Leetcode 总体思路 思路是看出问题的数学本质,找到合适方便的公式。 常用的数学计算编程方法: 判断四个点能否组成矩形 先任意取三个点,看看能不能构造成直角三角形,然后计算第四个点是否是矩形缺的那个点就可以了。 看能否构造直角三角形的方法是勾股定理,也就是看三条边中最大的平方是不是等...

Leetcode按题目类型总结(十六)

系统设计

所有代码详见:https://github.com/jingminglake/Leetcode 534. Design TinyURL 题意:需要在长url和短url之间进行变换,设计两个接口,一个是long2short,另一个是short2long。 解:使用两张hash表进行保存双向的映射。在处理长变短的时候,去生成,生成完之后,保存双向关系。 关于生成短的6位数字和字母相...

Leetcode按题目类型总结(十五)

贪心法

所有代码详见:https://github.com/jingminglake/Leetcode 总体思路 贪心的题目往往比较难,因为很难证明贪心策略是正确的。 至于贪心的解法,一般是求最优解,此时要做的不是暴力看所有的情况,而是以某个接近答案的值作为初始值,然后经过贪心的变形, 就可以变成最后的解。 具体题目 738. Monotone Increasing Digits 题意...

Leetcode按题目类型总结(十四)

分治法

所有代码详见:https://github.com/jingminglake/Leetcode 总体思路 分治法和很多其他题型有交集。 具体题目 4. Median of Two Sorted Arrays 题意:找出两个已排序数组中的总的中位数。中位数在总元素为奇数的时候取中间值,偶数时候取中间两个值的平均值。 解:先想办法求两个已排序数组(假设大小分别为m和n)中的第k小的...

Leetcode按题目类型总结(十三)

动态规划

所有代码详见:https://github.com/jingminglake/Leetcode 总体思路 动态规划适合求解的问题类型是最值类型,也就是求解决方案中最优的,例如最大值,最小值,最好方案情况,方案个数。 求方案个数 求解有多少个解的问题,一般是使用分治法,也就是递归的解决问题,可以使用动态规划去优化解题思路:使用记忆化搜索,或者是直接构造解题顺序,基于...

Leetcode按题目类型总结(十二)

哈希表

所有代码详见:https://github.com/jingminglake/Leetcode 总体思路 技巧 (1)使用数组替换hashmap,前提是key范围有限制,很容易和数组下标对应。 key范围限制举例:(a)字母 (b)字符串长度(c)数组元素数量 (d)整数数组里的值介于最大值和最小值之间。 (2)要注意hash的key已经默认有序的这种隐藏条件,这种情况...