# algorithmTest
**Repository Path**: wuyinghao/algorithmTest
## Basic Information
- **Project Name**: algorithmTest
- **Description**: 一些算法题，主要来自庞果网
- **Primary Language**: C++
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No
## Statistics
- **Stars**: 1
- **Forks**: 0
- **Created**: 2016-04-27
- **Last Updated**: 2020-12-19
## Categories & Tags
**Categories**: Uncategorized
**Tags**: None
## README
## 算法说明 ##
---
都是一些来自[庞果网](http://pongo.cn)的题目，具体算法说明参见[blog](http://blog.csdn.net/ygrx)
### largestRect.cc ###
---
给定直方图，每一小块的height由N个非负整数所确定，每一小块的width都为1，请找出直方图中面积最大的矩形。
如下图所示，直方图中每一块的宽度都是1，每一块给定的高度分别是[2,1,5,6,2,3]：
|
| |
| |
| | |
| | | | |
| | | | | |
面积最大值是5和6那个矩形，面积为10
---
### minNum.cc ###
---
给了A、B两个单词和一个单词集合Dict，每个的长度都相同。
我们希望通过若干次操作把单词A变成单词B，每次操作可以改变单词中的一个字母，同时，新产生的单词必须是在给定的单词集合Dict中。
求所有行得通步数最少的修改方法。
举个例子如下：
Given:
A = "hit"
B = "cog"
Dict = ["hot","dot","dog","lot","log"]
Return
[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
即把字符串A = "hit"转变成字符串B = "cog"，有以下两种可能：
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
"hit" -> "hot" -> "lot" -> "log" -> "cog"
---
### palindrome.cc ###
---
回文字符串是指从左到右和从右到左相同的字符串，现给定一个仅由小写字母组成的字符串，你可以把它的字母重新排列，以形成不同的回文字符串。
- 输入：非空仅由小写字母组成的字符串，长度不超过100；
- 输出：能组成的所有回文串的个数（因为结果可能非常大，输出对1000000007取余数的结果）。
例如：
- 输入"aabb"
- 输出为2（因为“aabb”对应的所有回文字符串有2个：abba和baab）
---
### perfect.cc ###
---
我们要给每个字母配一个1-26之间的整数，具体怎么分配由你决定，但不同字母的完美度不同， 而一个字符串的完美度等于它里面所有字母的完美度之和，且不在乎字母大小写，也就是说字母F和f的完美度是一样的。
现在给定一个字符串，输出它的最大可能的完美度。
例如：dad，你可以将26分配给d，25分配给a，这样整个字符串最大可能的完美度为77。
---
### water.cc ###
---
有两个容器，容积分别为A升和B升，有无限多的水，现在需要C升水。
我们还有一个足够大的水缸，足够容纳C升水。起初它是空的，我们只能往水缸里倒入水，而不能倒出。
可以进行的操作是：
- 把一个容器灌满；
- 把一个容器清空（容器里剩余的水全部倒掉，或者倒入水缸）；
- 用一个容器的水倒入另外一个容器，直到倒出水的容器空或者倒入水的容器满。
**问是否能够通过有限次操作，使得水缸最后恰好有C升水。**
- 输入：三个整数A, B, C，其中 0 < A , B, C <= 1000000000
- 输出：0或1，表示能否达到要求。
---
### xmlParser.cc ###
---
本题来自蓝港在线技术团队的idea，详情如下：
XML-可扩展标记语言 ，用于标记电子文件使其具有结构性的标记语言，可以用来标记数据、定义数据类型，是一种允许用户对自己的标记语言进行定义的源语言，被广泛的运用于数据传输和存储。
请编写一段程序，不使用语言之外的开源库，解析对应的XML文件，并把输出结果打印出来。
举个例子如下，当给定下述XML文件时（注：不需要将输入输出格式话，只是举个例子）：
它应该输出：
Books
Book 1
Name:The C++ Programming Language
Author:Bjarne Stroustrup
Book 2
Name:Effective C++
Author:Scott Meyers
- 本题输入：简化的一段xml文件，用字符串表示，如下（属性名字不包含引号和等号，也不包含大于小于等特殊字符，详细规则见下面的答题说明）
`string in = "";`
- 本题输出：对输入的xml字符串解析，得到输出如下：
`string out = "Books\r\n\tBook 1\r\n\t\tName:The C++ Programming Language\r\n\t\tAuthor:Bjarne Stroustrup\r\n\tBook 2\r\n\t\tName:Effective C++\r\n\t\tAuthor:Scott Meyers";`
---
### minLength.cc ###
---
给定一个字符串，仅由a,b,c 3种小写字母组成。当出现连续两个不同的字母时，你可以用另外一个字母替换它，如:
- 有ab或ba连续出现，你把它们替换为字母c
- 有ac或ca连续出现时，你可以把它们替换为字母b
- 有bc或cb 连续出现时，你可以把它们替换为字母a。
你可以不断反复按照这个规则进行替换，你的目标是使得最终结果所得到的字符串尽可能短，求最终结果的最短长度。
- 输入：字符串。长度不超过200，仅由abc三种小写字母组成。
- 输出： 按照上述规则不断消除替换，所得到的字符串最短的长度。
例如：
- 输入cab，输出2。
因为我们可以把它变为bb或者变为cc
- 输入bcab，输出1。
尽管我们可以把它变为aab -> ac -> b，
也可以把它变为bbb，但因为前者长度更短，所以输出1。
---
### sortArray.cc ###
---
本题来自caopengcs，只要你有兴趣，每个人都可以出题（出题入口在主页右侧边栏“贡献题目”内），以下是题目详情：
给定一个包含1-n的数列，我们通过交换任意两个元素给数列重新排序。
求最少需要多少次交换，能把数组排成按1-n递增的顺序，其中，数组长度不超过100。
例如：
- 原数组是3,2,1， 我们只需要交换1和3就行了，交换次数为1，所以输出1。
- 原数组是2,3,1，我们需要交换2和1，变成1,3,2，再交换3和2，变为1，2，3，总共需要的交换次数为2，所以输出2。
函数头部： C/C++ int run(const int *a,int n);
---
### subArray.cc ###
---
本题同样来自caopengcs，只要你有兴趣，每个人都可以出题（出题入口在主页右侧边栏“贡献题目”->“我要发布”内），以下是题目详情：
- 子序列的定义：对于一个序列a=a[1],a[2],......a[n]，则非空序列a'=a[p1],a[p2]......a[pm]为a的一个子序列
- 其中1<=p1