编程范式

函数式编程是一种编程范式，我们常见的编程范式有命令式编程、函数式编程、逻辑式编程，常见的面向对象编程是一种命令式编程。

命令式编程

命令式编程是面向计算机硬件的抽象，有变量（对应存储单元），赋值语句（获取，存储指令），表达式（内存引用和算术运算）和控制语句（跳转指令），命令式程序就是一个冯诺依曼的指令序列。

函数式编程（FP）

函数式编程是面向数学的抽象， 将计算描述为一种表达式求值， 函数式程序就是一个表达式。

函数式编程中的函数这个术语不是指计算机中的函数，而是指数学中的函数，即自变量的映射。也就是说一个函数的值仅决定于函数参数的值，不依赖于其他状态。比如sqrt(x)函数计算x的平方根，只要x不变，不论什么时候调用，调用几次，值都是不变的。

由于函数式编程是面向数学的抽象，更接近人的语言。函数式编程更关注结果，相对的命令式编程关注解决问题的步骤。使用函数式编程，代码会比较简洁，也容易被理解。

游戏描述

Nim游戏是对一些放置成堆的一定数量的硬币开始的：硬币和堆的数量取决于你。有两名玩家玩这个游戏，当轮到某位玩家时，他能从某一堆里取任意数量的硬币，但是至少要取一枚硬币，但是也不能从除你取的这个堆以外的其他堆里再取硬币。取得最后一枚硬币的人获胜。

游戏预测

Nim-Sum：对每一堆硬币进行XOR(异或)得到的最终值成为Nim-Sum
例如：设HeapA，HeapB，HeapC，每个堆分别有8，12，13个元素
则Nim-Sum = 8⊕12⊕13 = 9

对于Nim游戏，假设两个玩家足够聪明（都不会犯错），游戏的结果取决于两个因素：

• 硬币堆数及每堆初始化数量（Nim-Sum值）
• 游戏从谁开始

如果游戏开始时Nim-Sum非零，首先开始的玩家将获胜，否则首先开始的玩家输掉游戏。

问题描述

给定字符串 x = x0…n-1,为构造x为回文最少需要插入几个字符。
例如：

• x: Ab3bd
• 可以构造 “dAb3bAd” 或 “Adb3bdA” 通过插入两个字符

问题描述

用1 x 2的骨牌放满3 x n的矩形有多少种方法

例如：下面是铺满3 x 12的一个方法

问题描述

给定两个序列，找出它们中最长的子序列的长度。子序列是以相同的相对顺序出现的序列，但不一定是连续的。例如，“abc”，“abg”，“bdf”，“aeg”，“”acefg“等等是”abcdefg“的子序列。所以一个长度为n的字符串有2 ^ n个不同的子序列。

例如：
“ABCDGH”和 “AEDFHR” 的LCS是“ADH” 长度为3
“AGGTAB”和 “GXTXAYB”的LCS是“GTAB” 长度为4

算法设计——Dynamic Pragraming 1-dimensional

举个栗子

问题：给定n，求 将n 表达为1，3，4的和的写法数量

例如 n = 5 , 答案是：6

5 = 1 + 1 + 1 + 1 + 1

5 = 1 + 1 + 3

5 = 1 + 3 + 1

5 = 3 + 1 + 1

5 = 1 + 4

5 = 4 + 1

举个栗子

给定一个二叉树，找到两个节点NA， NB的最近公共祖先(LCA)。

方便理解、比如对于下图:

举个栗子

为了方便理解Binary Indexed Tree,考虑以下问题：

对于数组 arr[1…n]，执行以下两种操作:

• getSum()操作：计算前i个元素的和。
• update()操作：改变第i个元素的值，arr[i] = x (1 <= i <= n)。

两个简单的解决方案

方案一： 通过遍历数组计算前i个元素的和O( n )的时间复杂度。更新元素直接赋值O( 1 )的时间复杂度。

方案二：创建另一个数组，并在这个数组的第i个索引存储从开始到结束的总和。可以在O（1）时间内计算给定范围的总和，但是更新操作需要O（n）个时间。

两种方案在需操作数组量很大的情况下，都不是很理想，有什么方案能让两种操作都在O（log n）的时间复杂度内完成呢？。

写在前面

本文是在Binary Search Tree的基础上讨论构建AVL树，了解Binary Search Tree 戳我

AVL 树

定义：AVL树是具有以下性质的二叉搜索树：

• 在AVL树中任何节点的两个子树的高度最大差值为1。
• 插入或删除操作可能需要通过一次或多次树旋转来重新平衡这个树。

二叉搜索树

定义：二叉搜索树为具有以下性质的二叉树：对于每个节点 v

• v 的值 > v的左子树的每个节点的值
• v 的值 < v的右子树的每个节点的值
• 没有重复的节点