线性排序算法之基数排序

基数排序也是一种特殊的计数或者桶排序，比如有10万个手机号码从小到大排序，如果用桶排序则数值范围太大了显然不合适，这里我们可以对没一位进行计数排序（每一位数值范围都是0-9范围小很多），利用稳定的排序这样进行11次之后则完成排序，这里的基数则指每次排的那一位。基数排序的时间复杂度为O(k*n), 当k不大的时候，比如手机号排序，则时间复杂度接近于O(n).

阅读全文 >>

线性排序算法之计数排序

计数排序其实是桶排序的一种特殊情况。当要排序的 n 个数据，所处的范围并不大的时候，比如最大值是 k，我们就可以把数据划分成 k 个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间。计数排序由于只涉及到数组的遍历操作，所以时间复杂度为O(n).

阅读全文 >>

线性排序算法之桶排序

桶排序，顾名思义，会用到“桶”，核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。 如果要排序的数据有 n 个，我们把它们均匀地划分到 m 个桶内，每个桶里就有 k=n/m 个元素。每个桶内部使用快速排序，时间复杂度为 O(k logk)。m 个桶排序的时间复杂度就是 O(m k logk)，因为 k=n/m，所以整个桶排序的时间复杂度就是 O(nlog(n/m))。当桶的个数 m 接近数据个数 n 时，log(n/m) 就是一个非常小的常量，这个时候桶排序的时间复杂度接近 O(n)。如果数据经过桶的划分之后，有些桶里的数据非常多，有些非常少，很不平均，那桶内数据排序的时间复杂度就不是常量级了。在极端情况下，如果数据都被划分到一个桶里，那就退化为 O(nlogn) 的排序算法了.

阅读全文 >>

LRU算法

leet code: 146
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。
它应该支持以下操作： 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。
当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间
使用哈希表+双向链表
哈希表: 查询 O(1)
双向链表: 有序, 增删操作 O(1)

阅读全文 >>

cocoscreator中spine局部换皮的探索

1、需求情况

书之国中需要一个人物捏脸系统，要求可以让用户自由选择身体不同部位的形象，比如头发、眼睛、眉毛、上衣、裤子等。已经支持RegionAttacment和MeshAttachment，而且在realtime模式下也可以正常工作。cocoscreator v2.4.4版本验证通过。推荐使用外部图片进行局部换装.

2、方案探索

2.1 多attachment切换

由于spine动画的结构为bone→slot→attachment(即附件、图片)，我们可以在动画文件中针对同一个部位（同一个slot）下做多个attachment，然后根据用户的选择进行切换attachment就行。
优点：web、native等多端统一代码。
缺点：随着可换装的部位越多、同一个部位皮肤越多，动画文件变得越来越大，由于spine动画文件是一次性加载进内存等，导致占用内存较多，实例化速度变慢。

阅读全文 >>

二叉树最大最小深度 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 二叉树的最大深度
def max_deep(treeRoot):
    if not treeRoot:
        return 0
    return max(max_deep(treeRoot.left), max_deep(treeRoot.right)) + 1
    
# 二叉树的最小深度
def min_deep(treeRoot):
    if not treeRoot:
        return 0
    left = min_deep(treeRoot.left)
    right = min_deep(treeRoot.right)
    if left == 0 or right == 0:
        return left + right + 1
    return  min(left,right) + 1

阅读全文 >>