发表于 | 阅读次数:
字数统计: 161 | 阅读时长 ≈ 1

先进行划分 划分到两个或者一个 再两两合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


class Solution {
    public ListNode mergeKLists(ListNode[] lists){
        if(lists.length == 0)
            return null;
        if(lists.length == 1)
            return lists[0];
        if(lists.length == 2){
           return mergeTwoLists(lists[0],lists[1]);
        }

        int mid = lists.length/2;
        ListNode[] l1 = new ListNode[mid];
        for(int i = 0; i < mid; i++){
            l1[i] = lists[i];
        }

        ListNode[] l2 = new ListNode[lists.length-mid];
        for(int i = mid,j=0; i < lists.length; i++,j++){
            l2[j] = lists[i];
        }

        return mergeTwoLists(mergeKLists(l1),mergeKLists(l2));

    }
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;

        ListNode head = null;
        if (l1.val <= l2.val){
            head = l1;
            head.next = mergeTwoLists(l1.next, l2);
        } else {
            head = l2;
            head.next = mergeTwoLists(l1, l2.next);
        }
        return head;
    }
}

发表于 | 阅读次数:
字数统计: 231 | 阅读时长 ≈ 1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77


import collections
import functools
from itertools import ifilterfalse


def lru_cache(maxsize=100, on_purge=None):
    """Least-recently-used cache decorator.
    Arguments to the cached function must be hashable.
    Clear the cache with f.clear().
    """
    maxqueue = maxsize * 10

    def decorating_function(user_function):
        cache = {}
        queue = collections.deque()
        refcount = collections.defaultdict(int)
        sentinel = object()
        kwd_mark = object()

        # lookup optimizations (ugly but fast)
        queue_append, queue_popleft = queue.append, queue.popleft
        queue_appendleft, queue_pop = queue.appendleft, queue.pop

        @functools.wraps(user_function)
        def wrapper(*args, **kwargs):
            # cache key records both positional and keyword args
            key = args
            if kwargs:
                key += (kwd_mark,) + tuple(sorted(kwargs.items()))

            # record recent use of this key
            queue_append(key)
            refcount[key] += 1

            # get cache entry or compute if not found
            try:
                result = cache[key]
            except KeyError:
                result = user_function(*args, **kwargs)
                cache[key] = result

                # purge least recently used cache entry
                if len(cache) > maxsize:
                    key = queue_popleft()
                    refcount[key] -= 1
                    while refcount[key]:
                        key = queue_popleft()
                        refcount[key] -= 1
                    if on_purge:
                        on_purge(cache[key])
                    del cache[key], refcount[key]

            # periodically compact the queue by eliminating duplicate keys
            # while preserving order of most recent access
            if len(queue) > maxqueue:
                refcount.clear()
                queue_appendleft(sentinel)
                for key in ifilterfalse(refcount.__contains__,
                                        iter(queue_pop, sentinel)):
                    queue_appendleft(key)
                    refcount[key] = 1
            return result

        def clear():
            if on_purge:
                for value in cache.itervalues():
                    on_purge(value)
            cache.clear()
            queue.clear()
            refcount.clear()

        wrapper._cache = cache
        wrapper.clear = clear
        return wrapper
    return decorating_function

发表于 | 分类于 | 阅读次数:
字数统计: 933 | 阅读时长 ≈ 3

编程范式

函数式编程 就是把一些功能或者逻辑代码通过函数拼接方式来组织的玩法

代码当中还是需要处理状态的 函数式编程一般写出的 都是无状态的代码

对于状态和数据的处理 oop编程的三大特性： 封装、继承、多态

包含数据、属性、代码与方法 对象指的是类的实例

面向对象 设计模式：可复用面向对象软件的基础 23种设计模式

使用者不需要知道数据类型、结构、算法的细节
不需要知道实现细节 只需要知道提供的接口
利于抽象、封装、动态绑定、多态
符合面向对象的特质和理念

继承需要給子类暴漏一些父类的设计和实现细节
父类实现的改变会造成子类也需要改变
继承主要是为了代码重用 但是实际上在子类中需要重新实现很多父类的方法
继承更多的是为了多态 (继承是一种过度设计！！！)

拼装对象
拼装功能
资源管理

oop的优缺点

能和真实的世界交相辉映 符合人的直觉
面向对象和数据库模型设计类型 更多地关注对象间的模型设计
强调于名词而不是动词 更多地关注对象和接口间的接口
根据业务的特征 形成了一个高内聚的对象 有效地分离了抽象和具体实现 增强可重用性和可扩展性
拥有大量非常优秀的设计原则和设计模式

SOLID
单一功能
开闭原则
里氏替换
接口隔离以及依赖反转

缺点：

代码需要附着在一个类上 鼓励了类型
代码需要提供对象达到抽象的效果 导致了相当厚重的“代码粘合层”
太多的封装以及对状态的鼓励 导致了大量不透明并在并发下出现很多问题

基于原型的编程范式

主流的就是javascript

__proto__ 主要是安放在一个实际的对象中 用来产生一个链接 一个原型链 用于寻找方法名或者属性

prototype 是用new来创建一个对象时构造 __proto__ 用的
它是构造函数的一个属性

go语言的委托模式

声明一个struct 和C语言的很像

然后直接把这个struct类型放到另一个struct里面

编程的本质

任何算法 都有两部分 一个是logic部分 用来解决实际问题的

另一个是control部分 用什么策略来解决问题（影响解决这个问题的效率）

程序=算法+数据结构
算法=逻辑+控制

函数式编程 都是一种控制
undo是想要解决的问题 undo的流程是控制
接口是对逻辑的抽象 真正的逻辑放在不同的具体类中 通过依赖或者是依赖注入这样的控制来完成对数据在不同情况下的不同处理

  • control 是可以被标准化的 遍历数据、查找数据、多线程、并发、异步等 都是可以标准化的
  • 需要处理数据 泛型编程
  • 处理用户的逻辑 标准化接口/协议来实现 适配于任何的logic

有效分离logic control data 是写好程序的关键所在！

有效分离logic control data 是写好程序的关键所在！

有效分离logic control data 是写好程序的关键所在！

prolog 逻辑编程范式

发表于 | 分类于 | 阅读次数:
字数统计: 1.3k | 阅读时长 ≈ 4

编程范式游记

  1. C语言是静态弱类型语言 使用变量的时候需要声明变量类型 但是类型间可以有隐式转换

  2. 不同的变量类型 可以用结构体组合起来 以此来声明新的数据类型

  3. typedef 关键字定义类型的别名 以此达到变量类型的抽象

  4. 变量作用域 递归功能的过程式语言

  5. 传递参数一般是传值 也可以传递指针

  6. 通过指针 对内存进行了低级控制 然而引入了非常大的时间复杂度

  7. 编译预处理让编译更具有弹性 比如跨平台

面向过程的C语言无法满足更高层次的编程需求 C++就出现了

用引用来解决指针出现的问题
用namespace解决名字空间冲突的问题
用try-catch解决返回值编程的问题
用class来解决对象的创建、复制 销毁的问题
用重载操作符来达到操作上的泛型
用模板template和虚函数的多态以及运行时识别来达到更高层次的泛型和多态
用RALL 智能指针的方式 解决需要释放资源而出现的一些问题
用STL解决算法和数据结构当中的坑

C++的泛型

从swap函数开始

  • 编程语言中的类型问题
  • 对真实世界中业务代码的抽象、重用和拼装

类型系统用于定义将编程语言当中的数值和表达式归类为许多不同的类型 如何操作这些类型 类型如何互相作用

内建的类型

抽象的类型

  • 程序语言的安全性
  • 利于编译器的优化
  • 代码的可读性
  • 抽象化

静态语言的代表 C C++ java
动态语言 python php javascript

静态类型检查是在编译器进行语义分析时进行的
动态类型检查系统更多的则是在运行时期做动态标记和相关检查

泛型的本质是什么

类型是对内存的一种抽象 不同的类型 会有不同的内存布局和内存分配的策略
不同的类型 有不同的操作 特定的类型 会有特定的一组操作

标准化类型的内存分配、释放和访问
标准化类型的操作
标准化数据容器的操作 比如查找算法、过滤、聚合
标准化类型上特有的操作

编程语言本质上帮助程序员屏蔽底层机器代码的实现 让我们更好的关注于业务代码逻辑 是一件很难trade-off的事

函数式编程fp

编程工作是解决业务上的问题 而不是计算机的问题 因此需要更贴近业务 更为抽象的语言 如oop的C++、java

函数式编程的特点

  • stateless 不维护任何状态
  • immutale 输入数据是不能动的

优势：

  • 没有状态就没有伤害
  • 并行执行没有伤害
  • copy-paste重构代码没有伤害
  • 函数的执行没有并行上的问题

还带来了一些好处

  • 惰性求值
  • 确定性

劣势：

数据复制比较严重
完全纯函数式haskell
容易写纯函数
纯函数需要花点精力

头等函数
尾递归优化
map&reduce
pipeline管道
递归
柯里化 多个参数分解成多个函数
高阶函数

把函数当成变量来用 关注描述问题而不是怎么实现 这样可以让代码更易读
因为函数返回里面的这个函数 所以函数关注的是表达式 关注的是描述这个问题 而不是怎么实现这个事情

函数式编程LISP语言

修饰器模式（装饰器）

Java Annotation

一种纯粹的函数式编程的技巧

用一个函数来构造另一个函数

关注带参数的装饰器

类装饰器

一个 __init \call__ 调用

python的语法糖 写出的代码比较酷 但是对于没有修饰器语法糖这类语言 看看go的代码

1
2


反射机制 获取函数名

Go的修饰器模式 好像无法做到泛型 无法做到通用

最大的泛型是interface{} 还有比较简单的reflection机制

表面上看 装饰器模式就是扩展现有的一个函数的功能 干一些其他的事情 或者是附加一些别的功能
除了体验到函数式编程的代码扩展能力 还能感受到代码互相和随意拼装带来的好处
Decorator这个函数其实是可以修饰几乎所有的函数的 可以将一些非业务功能 属于控制类型的代码抽象出来 像是for-loop 或者是打印日志 函数路由 或者是求函数运行时间这种非业务功能性的代码

发表于 | 分类于 | 阅读次数:
字数统计: 776 | 阅读时长 ≈ 2

100 亿是一个很大的数量级，这里每条 url 平均 64 字节，全部存储的话需要 640G 的内存空间。又因为使用了散列表这种数据结构，而散列表是会出现散列冲突的。为了让散列表维持较小的装载因子，避免出现过多的散列冲突，需要使用链表法来处理，这里就要存储链表指针。因此最后的内存空间可能超过 1000G 了。

判断一个数 是否存在 两种状态 存在true 或者不存在false

用每一位来存放某种状态，适用于大规模数据，但数据状态又不是很多的情况。

另外，位图法有一个优势就是空间不随集合内元素个数的增加而增加。它的存储空间计算方式是找到所有元素里面最大的元素（假设为 N ），所占空间为 N/8 bytes

出于对性能和内存占用的考虑 使用布隆过滤器 才是最好的

对于布隆过滤器而言，它的本质是一个位数组：位数组就是数组的每个元素都只占用 1 bit ，并且每个元素只能是 0 或者 1。

布隆过滤器除了一个位数组，还有 K 个哈希函数。当一个元素加入布隆过滤器中的时候，会进行如下操作：

使用 K 个哈希函数对元素值进行 K 次计算，得到 K 个哈希值。
根据得到的哈希值，在位数组中把对应下标的值置为 1。
举个例子，假设布隆过滤器有 3 个哈希函数：f1, f2, f3 和一个位数组 arr。现在要把 2333 插入布隆过滤器中：

对值进行三次哈希计算，得到三个值 n1, n2, n3。
把位数组中三个元素 arr[n1], arr[n2], arr[3] 都置为 1。
当要判断一个值是否在布隆过滤器中，对元素进行三次哈希计算，得到值之后判断位数组中的每个元素是否都为 1，如果值都为 1，那么说明这个值在布隆过滤器中，如果存在一个值不为 1，说明该元素不在布隆过滤器中。

不存在 一定是真的

存在 可能是误判！！！

布隆过滤器的最大的用处就是，能够迅速判断一个元素是否在一个集合中。因此它有如下三个使用场景:

网页爬虫对 URL 的去重，避免爬取相同的 URL 地址
进行垃圾邮件过滤：反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱（同理，垃圾短信）
有的黑客为了让服务宕机，他们会构建大量不存在于缓存中的 key 向服务器发起请求，在数据量足够大的情况下，频繁的数据库查询可能导致 DB 挂掉。布隆过滤器很好的解决了缓存击穿的问题。