重要算法题代码

一组 n 个数加 n 个乘号后最大乘积 int getNum int p int begin int end int t 0 for int i begin i end i t t 10 p i return t int maxM int n int m int p int i j k int val 0 for i 1 i n i for j 1 j m j maxvalue i j 0 for i 1 i n i val val 10 p i maxvalue i 0 val for i 2 i n i for j 1 j max i 1 m j for k j k i k val getNum p k 1 i maxvalue i j max maxvalue i j maxvalue k j 1 val return maxvalue n m i 个数 j 个乘号 在罗列第 j 个乘号位置 计算 max k j 1 val 组合问题 void printC int n v size for int i 0 i n i cout v i cout endl 递归的方法 void combination int a int size int num if size num return if num 0 printC return v push back a 0 combination v pop back combination 排列问题 递归法 void printAll int a int start int end int i if start end for i 0 i end i cout a i cout endl num else for i start i0 i if a i a p 1 swap a p 1 a q for i n 1 q p q i i q swap a q a i return true void showPermutation int a int n for int i 0 i n i cout a i num 最长不降序子序列 void LCS int a int size 前推法 O n n int next new int size int max new int size int i j for i 0 i size i max i 1 next i 0 for i 0 i size i for j 0 ja j int large 0 for i 0 i large large max i cout LCS large n int left 0 right len mid left right 2 while lefta mid left mid 1 else if n a mid right mid 1 else return mid mid left right 2 return left void LCS 2 int a int size c i 最长序列为 i 的最后一个数 保证这 个数最小 int i j int c 100 int len 当前求出的最大长度 用来储 存每次循环结束后 c 中已经求出值的元素 的最大下标 c 0 1 c 1 a 0 len 1 此时只有 c 1 求出来 最长递 增子序列的长度为 1 for i 1 i c len len c len a i j find c len a i c j a i if j len 要更新 len 另外补充一点 由二分查找可知 j 只可能比 len 大 1 len j 更新 len 滑雪问题 int points 100 100 int maxlen 100 100 0 int row col DP 的函数 int DP int i int j 在某个点被处理过或者到达边界时退出 int max 0 检查该点是否已经 处理过 原来数组里都初始化为 0 处理过 的数据大于 0 记忆化搜索的方法 if maxlen i j return maxlen i j 递归记录下每个点的最长长度 向上 if j 0 向下 if j points i j 1 向右 if i points i 1 j 读入 for i 0 i row i for j 0 j points i j 逐个点处理 for i 0 i row i for j 0 j col j DP i j 寻找最大值 for i 0 i row i for j 0 j col j if max maxlen i j max maxlen i j cout max endl return 0 最长回文字串 不一定连续 int maxlen MAXLEN MAXLEN 动态规划 int LongestLen char str int slen int i j len for i 0 i slen i maxlen i i 1 所有长度为 2 3 4 n 的串求最长 for len 1 len slen len for i 0 i j 1 maxlen i j 2 else maxlen i j 2 maxlen i 1 j 1 else maxlen i j maxlen i 1 j maxlen i j 1 maxlen i 1 j maxlen i j 1 return maxlen 0 slen 1 递归的方法 int MaxLength char str int i int j if i j return 1 else if i j return 0 else if str i str j return 2 MaxLength str i 1 j 1 else return max MaxLength str i 1 j MaxLength str i j 1 求逆序数 include include include 将两个已排序的子数组合并 A p q 与 A q 1 r 合并成一个新的A 从后往前比较 int merge int A int p int q int r int n1 q 1 p 数组a p q 的长度 int n2 r q 数组a q 1 r 的长度 int i j int L int malloc n1 1 int R int malloc n2 1 长度多 了1 是为了用于存储哨兵牌 for i 1 i n1 i L i A p i 1 L 0 INT MIN for j 1 j p k if L i R j A k L i count count n2 1 j for int l n2 l j l printf d d n L i R l i return count 递归实质是按照树形进行归并 左右根的 顺序 int InversePairCount int A int p int r if p r int q p r 2 int left InversePairCount A p q int right InversePairCount A q 1 r int count merge A p q r return left right count return 0 快排 include include int Partition int a int p int r int x a r 最后一个数作为比较标准 int i p 1 for int j p j r j if a j x i swap a i a j swap a i 1 a r return i 1 注意啊 void QuickSort int a int p int r if p r int m Partition a p r 看作 先序遍历 QuickSort a p m 1 QuickSort a m 1 r int new random int min int max return min int float rand RAND MAX max min int randomize partition int A int p int r int i new random p r swap A i A r return Partition A p r void randomize quicksort int A int p int r int i if p r i randomize partition A p r randomize quicksort A 0 i 1 randomize quicksort A i 1 r 第 k 大的数 void swap int a b b tmp int Partition int a int p int r int x a r 最后一个数作为比较标准 int i p 1 for int j p j r j if a j x i swap a i a j swap a i 1 a r return i 1 注意啊 void quicksort int a int p int r if pr 1 p k 0 printf 超过区间 n return 0 if p r return a p 划分成两个数组 int mid Partition a p r int count mid 1 p p mid if k count mid return a mid 晕死 这儿写错了竟然 else if k count p mid 1 return select a p mid 1 k else mid 1 r return select a mid 1 r k count 线性表结构的最小堆 include using namespace std const int MaxSize 20 template class Minheap private Type heapArr 存放堆中数据元 素的数组 int CurrentSize 堆中当前元素数目 void FilterDown const int p 向下调整 使以 p 为根的子树成为堆 void FilterUp const int p 向上调整 使结 点 p 所在子树成为堆 public Minheap int maxsize 构造函数 Minheap Type a int n 构造函数 Minheap delete heapArr int Insert const Type 插入数据 Type DeleteTop 删除堆顶元素 并返 回被删除值 Type GetTop const return heapArr 0 返 回堆顶元素值 bool IsEmpty return CurrentSize 0 bool IsFull return CurrentSize MaxSize int SizeOfHeap const return CurrentSize 返回堆中元素个数 void SetEmpty CurrentSize 0 将堆置为空 int ShowHeap template Minheap Minheap int maxsize CurrentSize 0 heapArr new Type MaxSize template Minheap Minheap Type a int n if n 0 cerr 堆的大小不能小于 0 0 i FilterDown i 逐个向下调整 cout endl ShowHeap template int Minheap Insert const Type exit 1 heapArr CurrentSize d FilterUp CurrentSize 向上调整 CurrentSize cout N j 1 令 j j 1 总是沿关键字较小的分支调整 2 然后比较 N i 与 N j 的大小 若 N i N j 则交换两结点关键字 否则结束 3 令 i j j 2 j 1 逐层向下比较 当 j MaxSize 时结束 template void Minheap FilterDown const int p int i j i p j 2 i 1 因为从 0 开始的 Type temp heapArr i while j CurrentSize 1 if j heapArr j 1 j j 1 j 指向较小的孩子 if temp heapArr j heapArr i heapArr j else break i j j 2 j 1 heapArr i temp FilterUp 向上调整函数 使用情况 向已建好的堆中插入数据时 思想 0 从结点 j N j 开始 1 比较 N j 的关键字与其双亲节点 i N i 的关键字的大小 若 N j N i 则交 换结点关键字 否则结束 2 使 j i i i 1 2 向上继续 直至 根结点 i 0 结束 template void Minheap FilterU