程序员的玩具

递归

Leetcode

344. Reverse String

注意的是要求常数空间的限制，要使用递归就会有递归栈导致的额外空间，递归栈的空间我们可以通过尾递归来消除，但是传参和返回值的部分需要额外处理。因此不能传入字符串的拷贝，只能传入指针（在python中就是不要用切片）。而且不能有返回值，要原地处理。

24. Swap Nodes in Pairs

递归思路很简单，注意一个小技巧是不改变节点的指针，而是通过交换节点的值完成交换。

118. Pascal’s Triangle

在小三角形的基础上生成大三角形。

119. Pascal’s Triangle

在已有的行的基础上生成更大的行。

206. Reverse Linked List

没啥

779. K-th Symbol in Grammar

没啥，子问题直接被规约到上一层

95. Unique Binary Search Trees II

子问题是生成节点数少一个的树的列表，不过为了区别在左子树和在右子树时的情况，在构造树的函数中加上一个base参数，表示从几开始构造树。

Memorization技巧

在python中可以用lru_cache装饰器轻松搞定，其他的语言应该也可以用装饰器实现。注意这里的两个题，一个是Fibonacci Number，一个是Climbing Stairs，其实都有了动态规划的影子。

另外补充，在java中，LRU其实就是LinkedHashmap，即使就是一个双向链表加上HashMap。

主定理 Master Theorem

如果递归算法的递推关系符合如下形式：
$$ T(n)=aT(\frac nb)+f(n) $$
其中，$$$a\ge1,b>1$$$，且f是单调递增函数。
那么，根据$$$f(n)$$$和$$$n^{log_ba}$$$的关系，有三种可能性：

  1. 如果$$$f(n)$$$的渐进复杂度多项式级别的低于$$$O(n^{log_ba})$$$，即$$$f(n)=O(n^{log_ba-\epsilon})$$$，其中$$$\epsilon$$$是一个大于0的常数，则$$$T(n)=\Theta(n^{log_ba})$$$。

  2. 如果$$$f(n)$$$的渐进复杂度多项式级别的低于$$$O(n^{log_ba})$$$，即$$$f(n)=O(n^{log_ba+\epsilon})$$$，其中$$$\epsilon$$$是一个大于0的常数，且存在$$$c<1$$$满足$$$af(n/b)≤cf(n)$$$，则$$$T(n)=\Theta(f(n))$$$。

  3. 如果$$$f(n)=O(n^{log_ba}lg^kn)$$$，则$$$T(n)=\Theta(n^{log_ba}lg^{k+1}n)$$$

证明




例题

大数据

Scala笔记

语言特性

Scala 是 Scalable Language 的简写，是一门多范式的编程语言。

面向对象特性
Scala是一种纯面向对象的语言，每个值都是对象。对象的数据类型以及行为由类和特质描述。
类抽象机制的扩展有两种途径：一种途径是子类继承，另一种途径是灵活的混入机制。这两种途径能避免多重继承的种种问题。

函数式编程
Scala也是一种函数式语言，其函数也能当成值来使用。Scala提供了轻量级的语法用以定义匿名函数，支持高阶函数，允许嵌套多层函数，并支持柯里化。Scala的case class及其内置的模式匹配相当于函数式编程语言中常用的代数类型。
更进一步，程序员可以利用Scala的模式匹配，编写类似正则表达式的代码处理XML数据。

静态类型
Scala具备类型系统，通过编译时检查，保证代码的安全性和一致性。类型系统具体支持以下特性：

  • 泛型类
  • 协变和逆变
  • 标注
  • 类型参数的上下限约束
  • 把类别和抽象类型作为对象成员
  • 复合类型
  • 引用自己时显式指定类型
  • 视图
  • 多态方法

Read More

大数据

Kafka笔记(一)

安装

参考:Kafka 安装

只需要前置安装java和zookeeper，基本上不需要配置啥，即开即用。

CLI上手

一些理论

  1. 大数据分布式通信系统中可以归纳为三种常见的通信机制：序列化与远程过程调用、消息队列和多播通信。前者包括直接使用JSon或者XML，也包括专用的序列化框架比如Google的PB、FB的Thrift、Apache的Avro。Kafka属于消息队列工具，作为消息传输过程中的容器或中间件，提供消息路由并保障消息可靠传输。多播通信暂且不提。
  2. 消息中间件通常支持两种模式的队列，消息队列或者Pub-Sub。Kafka是Linkdin开源的Pub-Sub机制的，最初被设计为Log收集工具。
  3. 除了Producer和Consumer，Kafka中另一个重要的角色是代理商Broker。
  4. Kafka消费者采取Pull方式读取消息，不像Flume是Push方式，这样的好处是消费者可以自主控制消费速率，不会导致Push方式的弊端：消费者跟不上生产者导致的消息积压。
  5. Kafka内部，支持对Topic进行数据分片，每个数据分片是有序的、不可改的尾部追加消息队列结构，队列内的每个消息被分配数据分片内的一个uniqueId，称为Offset。生产者可以指定消息分片。
大数据

Spark笔记（二）

开发环境搭建

安装sbt

1
2
3
4
echo "deb https://dl.bintray.com/sbt/debian /" | sudo tee -a /etc/apt/sources.list.d/sbt.list
sudo apt-key adv --keyserver hkp://keyserver.ubuntu.com:80 --recv 2EE0EA64E40A89B84B2DF73499E82A75642AC823
sudo apt-get update
sudo apt-get install sbt

sbt 初识

参考极客学院SBT手册

在scala源代码中编写简单的测试代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
  * Created by protao on 18-5-2.
  */

import org.apache.spark.SparkConf
import org.apache.spark.SparkContext
import org.apache.spark.SparkContext._

object WordCount {
  def main(args: Array[String]) {
    val inputFile =  "/tmp/0401.txt"
    val conf = new SparkConf().setAppName("TestTianjin")
    val sc = new SparkContext(conf)
    val textFile = sc.textFile(args(0))
    val wordCount = textFile.flatMap(line => line.split(" ")).map(word => (word, 1)).reduceByKey((a, b) => a + b)
    wordCount.saveAsTextFile(args(1))
  }
}

Read More

读书笔记

Python Cookbook3 (9)元编程

1. 在函数上添加装饰器

2. 创建装饰器时保留函数元信息

3. 解除一个装饰器

前面好好的看的话，装饰器这个内容现在已经算比较简单了。@wraps 有一个重要特征是它能让你通过属性__wrapped__直接访问被包装函数。__wrapped__ 属性还能让被装饰函数正确暴露底层的参数签名信息。直接访问未包装的原始函数在调试、内省和其他函数操作时是很有用的。但是我们这里的方案仅仅适用于在包装器中正确使用了 @wraps 或者直接设置了 __wrapped__ 属性的情况。如果有多个包装器，那么访问 __wrapped__ 属性的行为是不可预知的，应该避免这样做。在Python3.3中，它会略过所有的包装层（只有3.3）。最后要说的是，并不是所有的装饰器都使用了@wraps ，因此这里的方案并不全部适用。特别的，内置的装饰器 @staticmethod 和 @classmethod 就没有遵循这个约定(它们把原始函数存储在属性 __func__ 中)。

Read More

本站总访问量次