string

User Input Strings

cin considers a space (whitespace, tabs, etc) as a terminating character, which means that it can only display a single word (even if you type many words):

string fullName;
cout << "Type your full name: ";
cin >> fullName;
cout << "Your name is: " << fullName;

// Type your full name: John Doe
// Your name is: John

That’s why, when working with strings, we often use the getline() function to read a line of text. It takes cin as the first parameter, and the string variable as second:

string fullName;
cout << "Type your full name: ";
getline (cin, fullName);
cout << "Your name is: " << fullName;

// Type your full name: John Doe
// Your name is: John Doe

Omitting Namespace

You might see some C++ programs that runs without the standard namespace library. The using namespace std line can be omitted and replaced with the std keyword, followed by the :: operator for string (and cout) objects:

#include <iostream>
#include <string>

int main() {
  std::string greeting = "Hello";
  std::cout << greeting;
  return 0;
}

C风格

对于C风格的字符串，我们只用它进行输入，输出。

它本质是一个字符数组，以\0作为结束的标志

1 2	char str[100]; scanf("%s",str);

%s只能读取一个单词

1	fgets(str,100,stdin);//读取一整行，包括\n

fgets()读取一整行，包括\n

我们可以这样来读入不定数量的行，

char buf[200];
while(fgets(buf,200,stdin) != NULL){
        string str=buf;
        //干掉换行
        str.pop_back();
    }
while(scanf("%s",buf) != EOF){
    
}

C++风格

下面的C++风格的字符串：

1 2	#include<string> using namespace std;

把字符串从c风格转换成c++风格：

1	string str1=str;

把字符串从c++风格转换成c风格：str1.c_str() ——>printf()

连接：str1+”wrold”

删除：str1.erase(下标)

1	str1.erase(str1.length()-1);//把fget的最后一个元素\n干掉

清空：str1.clear()

访问字符：str1[0]

for(int i=0;i<str1.length();i++){
    printf("%c",str1[i]);
}
//迭代器（指针）
for(string::iterator it=str1.begin(); it!=str1.end();it++){
    printf("%c",*it);
}

长度：str1.length()

判断相等：str1==”hello”

比较字典序：str1>”abandon”

查找子串：find()，找到返回子串起点下标，没有找到返回string::npos

string str="howareyou";
int pos=str.find("are");
if(pos!=string::npos){
    printf("Found, position=%d\n",pos);
}

切割字符串

substr(起始下标，子字符串长度)

substr(起始下标)，表示从起始下标到最后一个字符

链接：https://www.nowcoder.com/questionTerminal/c6ca566fa3984fae916e6d7beae8ea7f
来源：牛客网

哈利波特在魔法学校的必修课之一就是学习魔咒。据说魔法世界有100000种不同的魔咒，哈利很难全部记住，但是为了对抗强敌，他必须在危急时刻能够调用任何一个需要的魔咒，所以他需要你的帮助。给你一部魔咒词典。当哈利听到一个魔咒时，你的程序必须告诉他那个魔咒的功能；当哈利需要某个功能但不知道该用什么魔咒时，你的程序要替他找到相应的魔咒。如果他要的魔咒不在词典中，就输出“what?”

输入描述:

首先列出词典中不超过100000条不同的魔咒词条，每条格式为：

[魔咒] 对应功能

其中“魔咒”和“对应功能”分别为长度不超过20和80的字符串，字符串中保证不包含字符“[”和“]”，且“]”和后面的字符串之间有且仅有一个空格。词典最后一行以“@END@”结束，这一行不属于词典中的词条。
词典之后的一行包含正整数N（<=1000），随后是N个测试用例。每个测试用例占一行，或者给出“[魔咒]”，或者给出“对应功能”。

输出描述:

1	每个测试用例的输出占一行，输出魔咒对应的功能，或者功能对应的魔咒。如果魔咒不在词典中，就输出“what?”

示例1

输入

[expelliarmus] the disarming charm
[rictusempra] send a jet of silver light to hit the enemy
[tarantallegra] control the movement of one's legs
[serpensortia] shoot a snake out of the end of one's wand
[lumos] light the wand
[obliviate] the memory charm
[expecto patronum] send a Patronus to the dementors
[accio] the summoning charm
@END@
4
[lumos]
the summoning charm
[arha]
take me to the sky

输出

light the wand
accio
what?
what?

#include <cstdio>
#include <string>
#include <map>

using namespace std;

int main() {
    map<string, string> dict;

    while (true) {
        char line[200];
        fgets(line, 200, stdin);
        string str = line;
        str.pop_back();
        if (str == "@END@") {
            break;
        }
        string word = str.substr(0, str.find(']') + 1);
        string info = str.substr(str.find(']') + 2);
        dict[word] = info;
        dict[info] = word;
    }
    int N;
    scanf("%d", &N);
    getchar();          //读取scanf留下的'\n'
    for (int i = 0; i < N; i++) {
        char line[200];
        fgets(line,200,stdin);
        string str=line;
        str.pop_back();

        if(dict.find(str)!=dict.end()){
            if(str[0]=='['){
                printf("%s\n",dict[str].c_str());
            }
            else{
                printf("%s\n",dict[str].substr(1,dict[str].size()-2).c_str());
            }
        }
        else{
            printf("what?\n");
        }

    }

}

map(映射)

key——>value

map<key的类型，value的类型>

#include <map>
#include <cstdio>
#include <string>
using namespace std;
int main(){
    map<string,int> myMap;
    if(myMap.empty()){
        printf("myMap is empty!\n");
    }
    //使用方括号[]插入
    myMap["Caixukun"]=1;
    //使用insert插入
    myMap.insert(pair<string,int>("Wuyifan",2));
    printf("sizo of myMap = %d\n",myMap.size());
    //删除erase(), 参数为key
    myMap.erase("Wuyifan");
    printf("sizo of myMap = %d\n",myMap.size());
    //迭代
    map<string,string>::iterator it;
    for(it=myMap.begin();it!=myMap.end();it++){
        printf("it->first=%s, it->second=%s\n",it->first.c_str(),it->second.c_str());
    }
}
//output
it->first=Caixukun, it->second=ikun
it->first=Wuyifan, it->second=meigeni

#include <cstdio>
#include <string>
#include <map>
using namespace std;
int main(){
        //键 key--> 值 value
        //<键的类型,值的类型>
        map<string,string> myMap ={
        {"Caixukun","ikun"},
        {"Wuyifan","meigeni"}
        };
        char str[100];
        scanf("%s",str);
        string name = str;
        //myMap[key]根据key映射到对应的值(C++风格的字符串)
        printf("%s的粉丝被称为%s\n",name.c_str(),myMap[name].c_str());
}

可以看到我们的输出不是按照输入顺序输出的，因为map已经把元素按key的大小排号序了

描述

输入N个学生的信息，然后进行查询。

输入描述：

输入的第一行为N，即学生的个数(N<=1000) 接下来的N行包括N个学生的信息，信息格式如下： 01 李江男 21 02 刘唐男 23 03 张军男 19 04 王娜女 19 然后输入一个M(M<=10000),接下来会有M行，代表M次查询，每行输入一个学号，格式如下： 02 03 01 04

输出描述：

输出M行，每行包括一个对应于查询的学生的信息。如果没有对应的学生信息，则输出“No Answer!”

示例1

输入：

输出：

02 刘唐 男 23
03 张军 男 19
01 李江 男 21
04 王娜 女 19
03 张军 男 19

#include <cstdio>
#include <map>
#include <string>
using namespace std;
int main(){
    int N;
    map<int, string> myMap;
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        int num=0;
        char buf[100];
        scanf("%d",&num);
        fgets(buf,100,stdin);
        string str=buf;
        str.pop_back();
        myMap[num]=str;
    }
    int M;
    scanf("%d",&M);
    for(int i=0;i<M;i++){
        int num=0;
        scanf("%d",&num);
        if(myMap.find(num)!=myMap.end()){
            printf("%02d%s\n",num,myMap[num].c_str());
        }
        else{
            printf("No Answer!\n");
        }

    }
}

用map代替二分查找

map的底层是一颗二叉搜索树（红黑树），所以，我们把数据插入到map是有序的。查找时间复杂度O(logn)

但，如果我们想要查找的时间复杂度达到O(1)，那么我们要用unorder_map，因为它的底层使用了hash散列

但这样做会使内存增大

先用map<int,int> 保存数组的值和下标，再用.find()方法

描述

输入数组长度 n 输入数组 a[1…n] 输入查找个数m 输入查找数字b[1…m] 输出 YES or NO 查找有则YES 否则NO

输入描述：

输入有多组数据。每组输入n，然后输入n个整数，再输入m，然后再输入m个整数（1<=m,n<=100）。

输出描述：

如果在n个数组中输出YES否则输出NO。

示例1

输入：

输出：

1
2
3

YES
YES
NO

#include <cstdio>
#include <map>
using namespace std;
int main(){
    int n;//数组长度
    scanf("%d",&n);
    int arr[n];
    map<int,int> findIndex;
    for(int i=0;i<n;i++){//读入n个元素
        scanf("%d",&arr[i]);
        //数组元素——>key, 下标——>value插入到map
        findIndex[arr[i]]=i;
    }
    int m;//查找m个数
    scanf("%d",&m);
    for(int i=0;i<m;i++){
        int findNum;//待查元素
        scanf("%d",&findNum);
        //find函数会返回找到元素的指针，如果没有找到则返回尾后指针（最后元素的再后一个）
        if(findIndex.find(findNum)==findIndex.end()){//findIndex.end()返回尾后指针
            printf("NO\n");
        }
        else{
            printf("YES\n");
        }
    }
}

sort

#include<algorithm>
using namespace std;

sort(第一个元素的指针，最后一个元素再后一个元素的指针);

排序&交换

加上一个交换规则函数comp，不交换return true;否则return false;

1	sort(第一个元素的指针，最后一个元素再后一个元素的指针，comp);

加上序号seq变量——>稳定排序

struct Student {
    char name[100];
    int grade;
    int seq;//记录数据读入次序
};

描述

输入10个整数，彼此以空格分隔。重新排序以后输出(也按空格分隔)，要求: 1.先输出其中的奇数,并按从大到小排列； 2.然后输出其中的偶数,并按从小到大排列。

输入描述：

任意排序的10个整数（0～100），彼此以空格分隔。

输出描述：

可能有多组测试数据，对于每组数据，按照要求排序后输出，由空格分隔。 1. 测试数据可能有很多组，请使用while(cin>>a[0]>>a[1]>>…>>a[9])类似的做法来实现; 2. 输入数据随机，有可能相等。

示例1

输入：

1	4 7 3 13 11 12 0 47 34 98

输出：

1	47 13 11 7 3 0 4 12 34 98

#include <cstdio>
#include<algorithm>
using namespace std;

bool comp(int lhs, int rhs) {
    //不交换顺序:1.大奇数，小奇数 2.小偶数，大偶数 3. 奇数，偶数
    if (lhs % 2 == 1 && rhs % 2 == 1 && lhs > rhs)
        return true;
    else if (lhs % 2 == 0 && rhs % 2 == 0 && lhs < rhs)
        return true;
    else if (lhs % 2 == 1 && rhs % 2 == 0)
        return true;
    else {
        return false;
    }
}
int main() {
    int arr[10];
    while (scanf("%d%d%d%d%d%d%d%d%d%d", arr, arr + 1, arr + 2, arr + 3, arr + 4,
                 arr + 5, arr + 6, arr + 7, arr + 8, arr + 9) != EOF) {
        sort(arr, arr + 10, comp);
        for (int i = 0; i < 10; i++) {
            printf("%d ", arr[i]);
        }
        printf("\n");
    }
}

struct自定义类型

当一个学生记录既要存储学号，也要存储成绩的时候（即要存储多个信息），用int类型的一维数组并不满足需求，所以若有多个item的时，我们要自定义类型。

//类    类名
struct Student{
    int num;//学号
    int grade;//成绩
};//分号不能省略

动态数组（向量 vector)

C风格数组的限制

在定义数组时就要固定大小。

1
2
3

int n=10;
int arr[n]; //在低版本中这样用变量创建数组是有问题的
int arr1[100];//必须这样用常量创建

在内存的栈区中不能过大。

C++风格vector

#include <cstdio>
#include <vector>
using namespace std;
int main(){
    //初始化vector, 元素全0
    vector<int> vec(100);
    //长度为0
    vector<int> vec1;
    //尾部扩容
    vec1.push_back(1);
    //初始化vector
    vector<int> vec2 {1,2,3};
    //迭代器
    //随机插入，删除某个位置
    vector<int>::iterator it=vec2.begin()+1;
    vec2.insert(it,4);
    vec2.erase(vec2.begin());
    for(vector<int>::iterator it=vec2.begin();it!=vec2.end();it++){
        printf("%d ",*it);
    }
    //尾部弹出
    vec2.pop_back();
    //访问
    for(unsigned i=0;i<vec2.size();i++){
        printf("%d ",vec2[i]);
    }
}

队列

队列其实就是一个受限的数组，只能在两端操作

循环队列的实现也很简单：先出队pop，再入队push

#include <cstdio>
#include <queue>
using namespace std;
int main(){
    queue<int> q;
    for(int i=0;i<5;i++){
        //入队
        q.push(i);
    }
    while(true){
        //如果队列为空，则返回true
        if(q.empty()){
            printf("queue is empty");
            break;
        }
        //输出队首元素
        printf("the front of queue is %d\n",q.front());
        //弹出队首元素
        q.pop();
    }
}

栈

栈也是一个受限的数组，只能在其一端（栈顶top）进行操作

#include <stack>
#include <cstdio>
using namespace std;
int main(){
    stack<int> myStack;
    //压栈
    for(int i=0;i<10;i++){
        myStack.push(i);
    }
    //栈长度
    printf("the size of myStack = %d\n",myStack.size());
    //判断栈是否为空
    while(!myStack.empty()){
        //获取栈顶元素
        printf("%d ",myStack.top());
        //弹栈
        myStack.pop();
    }
}

指针和引用

#include <cstdio>
void fun(int i){
    i++;
    printf("the i in fun%d\n",i);
}
int main(){
    int i=1;
    fun(i);
    printf("the i in main() = %d\n",i);
}
the i in fun() = 2
the i in main() = 1

可以见到在fun中改变i的值，并不会改变到main中i的值

原因是他们是两个函数，在栈区中开辟两个不同的栈帧，这两个栈帧中都有各自的局部变量i，他们互不影响。

如果我们要在fun函数中，访问main中的i变量，则需要得到main中i的内存地址。

#include <cstdio>
void fun(int* i){
    (*i)++;
}
int main(){
    int i=1;
    fun(&i);
    printf("the i in main() = %d\n",i);
}
the i in main() = 2

法二：引用

使用引用后，在fun中的i变量其实是在main中。

#include <cstdio>
void fun(int& i){//引用main中的i变量
    i++;
}
int main(){
    int i=1;
    fun(i);
    printf("the i in main() = %d\n",i);
}

堆空间

如果我们想函数fun中创建链表，就一定要在堆空间创建链表，只有这样我们的链表才不会随栈帧在内存中的释放而消失。

#include <cstdio>
int* addNote(int i){
    int* pNote = new int;//在堆区中创建一个int变量，返回变量地址
    *pNote=i;
    return pNote;
}
int main(){
    int* arr[10];
    for(int i=0;i<10;i++){
        arr[i] = addNote(i);
    }

}

由于堆区中的变量不会主动释放。如果使用new创建变量，就要当我们不用他们的时候，就要delete。如果不去回收堆空间，这种情况就叫内存泄漏。

1
2
3

for(int i=0;i<10;i++){
    delete arr[i];
}

二叉树

在线性表的基础上做出改进，由原来的1前驱1后继，变成1前驱2后继(父子关系）。

由于二叉树的结构复杂，不能像顺序表一样在内存中顺序存储，所以我们要采用链式存储：一个区域存放数据，另一个区域存放指针

层次建树

#include <cstdio>
#include <queue>
using namespace std;
struct TreeNode {
    //数据域
    char data;
    //指针域
    TreeNode *leftChild;
    TreeNode *rightChild;
};
struct QueueNode {   //队列的每个结点，存储父亲的位置，以及是否插入过左孩子
    TreeNode *parent;
    bool isLeftIn;
};

//插入操作需要改变main中的变量，所以要加引用&符号
void insertTreeNode(TreeNode *&root, queue<QueueNode *> &myQueue, char data) {
    if (data != '#') {
        //创建二叉树结点，因为是在被调函数内创建，所以要申请堆空间
        TreeNode *pTreeNode = new TreeNode;
        //(*pTreeNode).data=data; //注意：*的优先级低于.所以要加()得到Node结点
        pTreeNode->data = data;//与上一行等价
        //入队，我们就知道新进来的结点是插parent的左边还是右边
        QueueNode *pQueueNode = new QueueNode;
        pQueueNode->parent = pTreeNode;
        pQueueNode->isLeftIn = false;
        myQueue.push(pQueueNode);
        //插入
        if (root == NULL) {
            //插入第一个结点
            root = pTreeNode;
        } else {
            //插入的不是根
            //找到要插入结点的父亲的位置（队头）
            QueueNode *pParent = myQueue.front();
            if (pParent->isLeftIn == false) {
                pParent->parent->leftChild = pTreeNode;
                pParent->isLeftIn = true;
            } else {
                pParent->parent->rightChild = pTreeNode;
                //出队
                myQueue.pop();
                delete pParent;
            }
        }
    } else{
        //是#，插入NULL
        if(root!=NULL){
            QueueNode* pParent=myQueue.front();
            if(pParent->isLeftIn == false){
                pParent->parent->leftChild=NULL;
                pParent->isLeftIn= true;
            }else{
                pParent->parent->rightChild=NULL;
                myQueue.pop();
                delete pParent;
            }
        }
    }
}
int main() {
    TreeNode *root=NULL;
    char charList[] = "abc##de#g##f###";
    queue<QueueNode *> myQueue;
    for (int i = 0; charList[i] != '\0'; ++i) {
        insertTreeNode(root, myQueue, charList[i]);
    }
    levelOrder(root);
}

层次遍历（广度优先——>辅助队列）

辅助队列：访问起点，把起点的所有邻居加入队列。再按队列访问，把被访问结点的邻居入队。

//层次遍历
void levelOrder(TreeNode* root){
    //辅助队列，存储二叉树结点地址
    queue<TreeNode *> pos;
    pos.push(root);
    while (!pos.empty()){
        TreeNode *pCur=pos.front();
        pos.pop();
        printf("%c",pCur->data);
        if(pCur->leftChild!=NULL){
            pos.push(pCur->leftChild);
        }
        if(pCur->rightChild!=NULL){
            pos.push(pCur->rightChild);
        }
    }
    printf("\n");
}

递归遍历

一颗树也可以将大问题转换成小问题。

把树分成三个部分：根，左子树，右子树。（左子树，右子树，分别为小问题）

递归出口：空树

//递归遍历
void preOrder(TreeNode* root){
    if(root!=NULL){
        printf("%c",root->data);
        preOrder(root->leftChild);
        preOrder(root->rightChild);
    }
}

void InOrder(TreeNode* root){
    if(root!=NULL){
        InOrder(root->leftChild);
        printf("%c",root->data);
        InOrder(root->rightChild);
    }
}

void postOrder(TreeNode* root){
    if(root!=NULL){
        postOrder(root->leftChild);
        postOrder(root->rightChild);
        printf("%c",root->data);
    }
}

已知前中序，求后序

给定一棵二叉树的前序遍历和中序遍历，求其后序遍历（提示：给定前序遍历与中序遍历能够唯一确定后序遍历）。

链接：https://www.nowcoder.com/questionTerminal/6e732a9632bc4d12b442469aed7fe9ce

输入描述:

1
2
3

两个字符串，其长度n均小于等于26。
第一行为前序遍历，第二行为中序遍历。
二叉树中的结点名称以大写字母表示：A，B，C....最多26个结点。

输出描述:

1 2	输入样例可能有多组，对于每组测试样例，输出一行，为后序遍历的字符串。

示例1

输入

ABC
BAC
FDXEAG
XDEFAG

输出

1 2	BCA XEDGAF

#include <cstdio>
#include <string>
using namespace std;
struct TreeNode{
    char data;
    TreeNode* lchild;
    TreeNode* rchild;
};

TreeNode* rebuild(string preOrder,string inOrder){
    if(preOrder.empty()){
        return NULL;
    } else{
        //从先序确定根
        char rootdata=preOrder[0];
        TreeNode* pNewNode=new TreeNode;
        pNewNode->data=rootdata;
        //拿根去切割先序，中序
        int pos=inOrder.find(rootdata);
        //preOrder.substr(1,pos)
        //preOrder.substr(pos+1)
        //inOrder.substr(0,pos)
        //inOrder.substr(pos+1)
        pNewNode->lchild= rebuild(preOrder.substr(1,pos),inOrder.substr(0,pos));
        pNewNode->rchild= rebuild(preOrder.substr(pos+1),inOrder.substr(pos+1));
        return pNewNode;
    }

}

void postOrder(TreeNode* root){
    if(root!=NULL){
        postOrder(root->lchild);
        postOrder(root->rchild);
        printf("%c",root->data);
    }
}

int main(){
    char preOrder[50];
    char inOrder[50];
    while(scanf("%s%s",preOrder,inOrder)!=EOF){
        TreeNode* root= rebuild(preOrder,inOrder);
        postOrder(root);
        printf("\n");
    }
}

已知带空叶子的先序

因为先序按（根，左，右）的顺序进行，并且带有空叶子，所以一定能表示出一棵树。

这样也可以采用递归进行构建二叉树。

链接：https://www.nowcoder.com/questionTerminal/4b91205483694f449f94c179883c1fef

编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

输入描述:

1	输入包括1行字符串，长度不超过100。

输出描述:

1
2
3

可能有多组测试数据，对于每组数据，
输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。
每个输出结果占一行。

示例1

输入

1	abc##de#g##f###

输出

1	c b e g d f a


#include <cstdio>
#include <string>
using namespace std;
struct TreeNode{
    char data;
    TreeNode* lchild;
    TreeNode* rchild;
};
TreeNode* RecursiveBuildTree(int &i, string str){
    char c=str[i];
    ++i;
    if(c=='#'){
        return NULL;
    }
    else{
        TreeNode* pNewNode=new TreeNode;
        pNewNode->data=c;
        pNewNode->lchild= RecursiveBuildTree(i,str);
        pNewNode->rchild= RecursiveBuildTree(i,str);
        return pNewNode;
    }

}

void InOrder(TreeNode* root){
    if(root!=NULL){
        InOrder(root->lchild);
        printf("%c ",root->data);
        InOrder(root->rchild);
    }
}

int main(){
    char buf[150];
    while(fgets(buf,150,stdin)!=NULL){
        string str=buf;
        str.pop_back();
        int i=0;
        TreeNode* root= RecursiveBuildTree(i,str);
        InOrder(root);
    }

}

二叉搜索树（BST)

左<根<右（左子树和右子树分别又是一颗二次搜索树）

中序是一个有序序列。

二叉搜索树的查找和插入。

他的查找过程类似于二分查找。

链接：https://www.nowcoder.com/questionTerminal/30a0153649304645935c949df7599602

二叉排序树，也称为二叉查找树。可以是一颗空树，也可以是一颗具有如下特性的非空二叉树： 1. 若左子树非空，则左子树上所有节点关键字值均不大于根节点的关键字值； 2. 若右子树非空，则右子树上所有节点关键字值均不小于根节点的关键字值； 3. 左、右子树本身也是一颗二叉排序树。现在给你N个关键字值各不相同的节点，要求你按顺序插入一个初始为空树的二叉排序树中，每次插入后成功后，求相应的父亲节点的关键字值，如果没有父亲节点，则输出-1。

输入描述:

1
2
3

输入包含多组测试数据，每组测试数据两行。
第一行，一个数字N（N<=100），表示待插入的节点数。
第二行，N个互不相同的正整数，表示要顺序插入节点的关键字值，这些值不超过10^8。

输出描述:

1	输出共N行，每次插入节点后，该节点对应的父亲节点的关键字值。

示例1

输入

1 2	5 2 5 1 3 4

输出

#include <cstdio>
#include <string>

using namespace std;
struct TreeNode {
    long long data;
    TreeNode *lchild;
    TreeNode *rchild;
};

void insertBST(TreeNode *&root, long long data) {
    TreeNode *pNewNode = new TreeNode;
    pNewNode->data = data;
    pNewNode->lchild = NULL;
    pNewNode->rchild = NULL;
    if (root == NULL) {
        root = pNewNode;
        printf("-1\n");
    } else {
        TreeNode *pPre = root;
        TreeNode *pCur;
        while (true) {
            if (data < pPre->data) {    //比pPre小就往左走
                pCur = pPre->lchild;
                if (pCur == NULL) { //判断左边为空，就直接插入
                    pPre->lchild = pNewNode;
                    printf("%lld\n", pPre->data);
                    break;
                } else {         //不为空，就往下移动
                    pPre = pCur;
                }
            } else {              //pCur比pPre大就往右走
                pCur = pPre->rchild;
                if (pCur == NULL) { //为空，就插入
                    pPre->rchild = pNewNode;
                    printf("%lld\n", pPre->data);
                    break;
                } else {           //不为空，就往下移动
                    pPre = pCur;
                }
            }
        }
    }

}

int main() {
    TreeNode *root = NULL;
    int N;
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        long long num;
        scanf("%lld",&num);
        insertBST(root,num);
    }

}

优先队列（大根堆）

应用：在一个动态的队列中，不断去得到最大值。

一个大根堆要满足两个特征：

形状特征：由大根堆是完全二叉树（由结点的个数，就能确定一个二叉树的形状），所以我们不再采用链式存储，而采用顺序存储。

数值特征：父>左，父>右（根最大）

大根堆删除

最大值先出队。其位置于堆尾结点交换。
小元素不断下坠（如其比两个孩子的最大值更小，就跟两个孩子的最大值交换）

所以大根堆出堆顶的时间复杂的O(log n)(因为最坏的情况下，在下坠的过程中，交换log n 次，而完全二叉树的高度h约=logn)

priority_queue

#include <cstdio>
#include <queue>
using namespace std;
int main(){
    int arr[]={2,4,1,6,5};
    priority_queue<int> myPQueue;
    for(int i=0;i<5;i++){
        myPQueue.push(arr[i]);
    }
    while(!myPQueue.empty()){
        printf("%d ",myPQueue.top());
        myPQueue.pop();
    }
    printf("The priority queue is empty.");

}

构建小根堆

法1：取巧的方案（只适用于全部都是正数）

先把数组全变成负数。然后push到priority_queue，等到top取出元素的时候，我们才把他变为正数。

法2：运算符重载（但只支持自定义类型运算符重载）

#include <queue>
using namespace std;
struct Element{
    int value;
};
//运算符重载（跟函数的构造很像）
bool operator <(Element lhs,Element rhs){
    return lhs.value > rhs.value;
}

int main(){
    priority_queue<Element> pQueue;
    int arr[]={6,4,2,5,3,1};
    for(int i=0;i<6;i++){
        Element e;
        e.value=arr[i];
        pQueue.push(e);
    }
}

哈夫曼树

把所有结点加入集合中（集合要使用小根堆）
若k的size>1，

取出权重最小的两个结点，并求和，放回集合中
若k集合中只剩下一个元素，那么就是树的根

链接：https://www.nowcoder.com/questionTerminal/162753046d5f47c7aac01a5b2fcda155

哈夫曼树，第一行输入一个数n，表示叶结点的个数。需要用这些叶结点生成哈夫曼树，根据哈夫曼树的概念，这些结点有权值，即weight，题目需要输出所有结点的值与权值的乘积之和的最小值。

输入描述:

1 2	输入有多组数据。每组第一行输入一个数n，接着输入n个叶节点（叶节点权值不超过100，2<=n<=1000）。

输出描述:

输出权值。

示例1

输入

1 2	5 1 2 2 5 9

输出

#include <cstdio>
#include <queue>
using namespace std;
int main(){
    int n;
    priority_queue<int> pQueue;     //存入相反数
    while(scanf("%d",&n)!=EOF){
        for(int i=0;i<n;i++){
            int num;
            scanf("%d", &num);
            pQueue.push(-num);
        }
        int res=0;      //存储带权路径和的中间结果
        while(1<pQueue.size()){
            int num1=pQueue.top();
            pQueue.pop();
            int num2=pQueue.top();
            pQueue.pop();
            //计算带权路径和 = L的带权路径和 + L的叶子权重和 + R的带权路径和 + R的叶子权重和
            res=res+num1+num2;

            pQueue.push(num1+num2);
        }
        printf("%d\n",-res);
    }
}

图

广度优先（BFS）

优先转移到所有的邻居，由于要存储邻居，我们要设置辅助队列。由于，要记录已经被访问过的结点，要设置一个辅助集合isVisit

用途：求最优解

Catch That Cow

Description

Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 ≤ N ≤ 100,000) on a number line and the cow is at a point K (0 ≤ K ≤ 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting.

Walking: FJ can move from any point X to the points X - 1 or X + 1 in a single minute
Teleporting: FJ can move from any point X to the point 2 × X in a single minute.
If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?

Input

Line 1: Two space-separated integers: N and K
Output

Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.
Sample Input

5 17

Sample Output

可以知道，本题是一个最优解问题。

#include <cstdio>
#include <queue>
using namespace std;
struct Info{
    int pos;
    int time;
};

int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    queue<Info> posQueue;
    bool isVisit[100001];   //记录该结点是否被访问过
    for(int i=0;i<100001;i++){
        isVisit[i]= false;
    }
    Info first;
    first.pos=n;
    first.time=0;
    posQueue.push(first);
    while (!posQueue.empty()){
        Info cur=posQueue.front();
        posQueue.pop();
        if(cur.pos==k){
            printf("%d\n",cur.time);
            break;
        }
        isVisit[cur.pos]=true;
        //把邻居加入队列
        Info neighbor;
        if(cur.pos-1>=0 && cur.pos-1<=100000 && isVisit[cur.pos-1]== false){
            neighbor.pos=cur.pos-1;
            neighbor.time=cur.time+1;
            posQueue.push(neighbor);
        }
        if(cur.pos+1>=0 && cur.pos+1<=100000 && isVisit[cur.pos+1]== false){
            neighbor.pos=cur.pos+1;
            neighbor.time=cur.time+1;
            posQueue.push(neighbor);
        }
        if(cur.pos*2>=0 && cur.pos*2<=100000 && isVisit[cur.pos*2]== false){
            neighbor.pos=cur.pos*2;
            neighbor.time=cur.time+1;
            posQueue.push(neighbor);
        }

    }

}

Find The Multiple

描述

Given a positive integer n, write a program to find out a nonzero multiple m of n whose decimal representation contains only the digits 0 and 1. You may assume that n is not greater than 200 and there is a corresponding m containing no more than 100 decimal digits.
输入

The input file may contain multiple test cases. Each line contains a value of n (1 <= n <= 200). A line containing a zero terminates the input.
输出

For each value of n in the input print a line containing the corresponding value of m. The decimal representation of m must not contain more than 100 digits. If there are multiple solutions for a given value of n, any one of them is acceptable.
样例输入

2 6 19 0
样例输出

10 100100100100100100 111111111111111111

#include <cstdio>
#include <queue>
using namespace std;
int main(){
    int n;
    while(true){
        scanf("%d",&n);
        if(n==0){
            break;
        }
        queue<long long> m;
        m.push(1);
        while (!m.empty()){
            long long cur=m.front();
            m.pop();
            if(cur%n==0){
                printf("%lld\n",cur);
                break;
            }
            m.push(cur*10);
            m.push(cur*10+1);
        }
    }
}

深度优先(DFS)

优先使用递归，去重：辅助结合isVisit。路径：Stack

A Knight’s Journey

描述

Background
The knight is getting bored of seeing the same black and white squares again and again and has decided to make a journey around the world. Whenever a knight moves, it is two squares in one direction and one square perpendicular to this. The world of a knight is the chessboard he is living on. Our knight lives on a chessboard that has a smaller area than a regular 8 * 8 board, but it is still rectangular. Can you help this adventurous knight to make travel plans?

Problem
Find a path such that the knight visits every square once. The knight can start and end on any square of the board.

输入

The input begins with a positive integer n in the first line. The following lines contain n test cases. Each test case consists of a single line with two positive integers p and q, such that 1 <= p * q <= 26. This represents a p * q chessboard, where p describes how many different square numbers 1, . . . , p exist, q describes how many different square letters exist. These are the first q letters of the Latin alphabet: A, . . .

输出

The output for every scenario begins with a line containing “Scenario #i:”, where i is the number of the scenario starting at 1. Then print a single line containing the lexicographically first path that visits all squares of the chessboard with knight moves followed by an empty line. The path should be given on a single line by concatenating the names of the visited squares. Each square name consists of a capital letter followed by a number.
If no such path exist, you should output impossible on a single line.

样例输入

样例输出

Scenario #1:
A1

Scenario #2:
impossible

Scenario #3:
A1B3C1A2B4C2A3B1C3A4B2C4

Basic syntax

string

User Input Strings

Omitting Namespace

C风格

C++风格

map(映射)

用map代替二分查找

sort

排序&交换

加上序号seq变量——>稳定排序

struct自定义类型

动态数组（向量 vector)

C风格数组的限制

C++风格vector

队列

栈

指针和引用

堆空间

二叉树

层次建树

层次遍历（广度优先——>辅助队列）

递归遍历

已知前中序，求后序

已知带空叶子的先序

二叉搜索树（BST)

二叉搜索树的查找和插入。

优先队列（大根堆）

大根堆删除

priority_queue

构建小根堆

哈夫曼树

图

广度优先（BFS）

Catch That Cow

深度优先(DFS)