经典算法题整合

算法题整合"/>

经典算法题整合

——记录我的学习之路
2019/12/27
期末停更，准备pat甲级，复习期末QAQ

1.题目描述

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

程序解析

class Solution {
public:bool Find(int target, vector<vector<int> > array) {int i=array.size()-1,j=0;while(i>=0 && j<array[0].size()){if(target>array[i][j])j++;else if (target<array[i][j])i--;else return true;}return false;}
};

2.题目描述

请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

程序解析

class Solution {
public:void replaceSpace(char *str,int length) {int blank=0,space=0;for(int i=0;i<length;i++)if(*(str+i)==' ')blank++;space=length+2*blank+1;for(int i=length+1;i>=0;i--){if(*(str+i)==' '){*(str+space)='0';space--;*(str+space)='2';space--;*(str+space)='%';space--;}else{*(str+space)=*(str+i);space--;}}}
};

3.题目描述

输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

程序解析

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:vector<int> printListFromTailToHead(ListNode* head) {vector<int>reV;while(head!=NULL){reV.push_back(head->val);head=head->next;}reverse(reV.begin(),reV.end());return reV;}
};

4.题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

程序解析

/*** Definition for binary tree* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {int root=pre[0],length=0;for(int i=0;i<vin.size();i++){if(root==vin[i])break;length++;}TreeNode* T=new TreeNode(root);if(length!=0){vector<int> p1(pre.begin()+1,pre.begin()+length+1);vector<int> i1(vin.begin(),vin.begin()+length);T->left=reConstructBinaryTree(p1,i1);}if(length+1!=vin.size()){vector<int> p2(pre.begin()+length+1,pre.end());vector<int> i2(vin.begin()+length+1,vin.end());T->right=reConstructBinaryTree(p2,i2);}return T;}
};

5.题目描述

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

程序解析

class Solution
{
public:void push(int node) {stack1.push(node);}int pop() {while(!stack1.empty()){stack2.push(stack1.top());stack1.pop();}int temp=stack2.top();stack2.pop();while(!stack2.empty()){stack1.push(stack2.top());stack2.pop();}return temp;}private:stack<int> stack1;stack<int> stack2;
};

6.题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

程序解析

class Solution {
public:int minNumberInRotateArray(vector<int> rotateArray) {if(rotateArray.empty())return 0;int i=0;while(true){if(i==rotateArray.size()){return rotateArray[0];}if(rotateArray[i]>rotateArray[i+1])return rotateArray[i+1];i++;}}
};

7.题目描述

给定一个根为R，权为W的非空树
分配给每个树节点T . 从R到L的路径的权重被定义为沿从R到任何叶节点L的路径的所有节点的权重之和。
现在给定任何加权树，你应该找到所有的路径，它们的权重等于给定的数。例如，让我们考虑树：对于每个节点，上面的数字是节点ID，这是一个两位数的数字，下面的数字是该节点的权重。假设给定数为24，则存在4个不同的路径，它们具有相同的给定权重：{ 105 2 7 }，{10 4 10 }，{10 3 3 3 }和{α} }。

程序解析

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=200;
struct node{int weight;vector<int> child;
}Node[maxn];
int n,m,theweight,tempweight=0,equalnum=0;
int father,childnum,child;
vector<int> temppath;
vector<vector<int> >ans;
bool cmp(vector<int> a,vector<int> b){for(int i=0;i<a.size()&&i<b.size();i++){if(a[i]!=b[i]) return a[i]>b[i];}return false;
}
void DFS(int now){temppath.push_back(Node[now].weight);tempweight+=Node[now].weight;if(Node[now].child.size()==0){if(tempweight==theweight) ans.push_back(temppath);}for(int i=0;i<Node[now].child.size();i++)DFS(Node[now].child[i]);temppath.pop_back();tempweight-=Node[now].weight;
}
int main(){cin>>n>>m>>theweight;for(int i=0;i<n;i++)cin>>Node[i].weight;for(int i=0;i<m;i++){cin>>father>>childnum;for(int j=0;j<childnum;j++){cin>>child;Node[father].child.push_back(child);}}DFS(0);sort(ans.begin(),ans.end(),cmp);for(int i=0;i<ans.size();i++){for(int j=0;j<ans[i].size();j++){if(j!=ans[i].size()-1) cout<<ans[i][j]<<" ";else cout<<ans[i][j]<<endl;}}return 0;
}

8.题目描述

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39

程序解析

class Solution {
public:int Fibonacci(int n) {if(n==0)return 0;if(n==1)return 1;int n1=0,n2=1,n3;for(int i=3;i<=n+1;i++){n3=n1+n2;n1=n2;n2=n3;}return n3;}};

9.题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

程序解析

class Solution {
public:int jumpFloor(int number) {if(number==1)return 1;if(number==2)return 2;int n1=1,n2=2,n3;for(int i=3;i<=number;i++){n3=n1+n2;n1=n2;n2=n3;}return n3;}
};

10.题目描述

实现一个图的类库

程序解析

//main.cpp
#include"graph.h"
#include"graph.template.h"
void test();
int main()
{test();return 0;
}void test()
{char data[6] = {'A', 'B', 'C', 'D', 'E', 'F'};UnDMaGraph<char> G2(data, 6, 10);G2.Dijstra(0);G2.DFS(0);G2.BFS(0);G2.Show();
}

//graph.h#ifndef __GRAPH__H__
#define __GRAPH__H__#include<iostream>
#include <queue>
#define INFINITY 2e9
#define UnDAlGraph DAlGraph
//邻接矩阵和邻接表的最大存储空间
const int MAXSIZE=10;//点的数据域，访问状态，权重
template<class T>
struct Vertex
{T data;bool visited;int weight;
};//弧结点，邻接顶点所在表头的下标以及下一条弧的信息struct ArcNode
{int adjvex;int weight;struct ArcNode* nextArc;
};//表头结点，顶点，第一条弧以及是否访问的信息
template<class T>
struct VertexNode
{T vertex;ArcNode* firstArc;bool visited;
};//---------------------邻接矩阵无向图数据结构---------------------
template<class T>
class UnDMaGraph
{
public:Vertex<T> vertex[MAXSIZE];int arc[MAXSIZE][MAXSIZE];int vNum, arcNum;public:/***输入每个点的数据，图的总点数目和总边数目并生成图***/UnDMaGraph(T a[], int n, int e);/****输出每个点及其对应的数据域*从0点以dfs算法遍历输出点*/void Show();/****将点的访问情况初始化**/void clear();/****深度优先遍历算法：递归实现**/void DFS_traversal(int i);void DFS(int i);/****广度优先遍历算法：队列实现**/void BFS_traversal(int i);void BFS(int i);/****单源最短路径算法，各点到S点的最小距离**/void Dijstra(int S);
};
//---------------------邻接矩阵无向图数据结构---------------------//---------------------邻接矩阵有向图数据结构---------------------
template<class T>
class DMaGraph:public UnDMaGraph<T>
{
public:/***输入每个点的数据，图的总点数目和总边数目并生成图***/DMaGraph(T a[], int n, int e);
};
//---------------------邻接矩阵有向图数据结构---------------------//---------------------邻接表无向图数据结构---------------------template<class T>
class UnDAlGraph
{
private:VertexNode<T> adjList[MAXSIZE];        ///结点（顶点）表int vNum, arcNum;       //顶点个数和弧的数目public:/***给定一个边的数组，图的总点数目和总边数目并生成图***/UnDAlGraph(T a[], int n, int e, int arc[][3]);/****初始化有n个顶点的图**/UnDAlGraph(T a[], int n);/****进一步初始化成有e条弧的图，以输入模式进行**/void CreateGraph(int e);/****析构函数**/~UnDAlGraph();/******/void Show();/******/void clear();                   ///用于将遍历后visited[]重置为false，即未访问过的状态/******/void DFS_traversal(int i);void DFS(int i);/******/void BFS_traversal(int i);void BFS(int i);void Dijkstra(int v0);
};
//---------------------邻接表无向图数据结构---------------------#else
// DO NOTHING.
#endif

//graph.template.h
#include"graph.h"template<class T>
DMaGraph<T>::DMaGraph(T a[], int n, int e)
{this->vNum = n;this->arcNum = e;int i, j,w;for(int k=0; k<n; ++k){this->vertex[k].data = a[k];this->vertex[k].visited = false;}for(i=0; i<n; ++i)for(j=0; j<n; ++j)this->arc[i][j] = 0;this->Show();std::cout<<"初始化图:输入一条边两点的值，并输入边的权重\n";for(int k=0; k<e; ++k){std::cin>>i>>j>>w;this->arc[i][j] = w;}
};template<class T>
UnDMaGraph<T>::UnDMaGraph(T a[], int n, int e)
{vNum = n;arcNum = e;int i, j,w;for(int k=0; k<n; ++k){vertex[k].data = a[k];vertex[k].visited = false;}for(i=0; i<n; ++i)for(j=0; j<n; ++j)arc[i][j] = INFINITY;Show();std::cout<<"初始化图:输入一条边两点的值，并输入边的权重\n";for(int k=0; k<e; ++k){std::cin>>i>>j>>w;arc[i][j] = w;arc[j][i] = arc[i][j];}
}template<class T>
void UnDMaGraph<T>::DFS_traversal(int i)
{std::cout<<vertex[i].data<<"->";vertex[i].visited = true;for(int j=0; j<vNum; ++j){if(arc[i][j]!=INFINITY && vertex[j].visited==false)DFS_traversal(j);}
}template<class T>
void UnDMaGraph<T>::DFS(int i)
{std::cout<<"DFS:"<<std::endl;DFS_traversal(i);std::cout<<"None"<<std::endl;for(int j=0; j<vNum; ++j){if(arc[i][j]==INFINITY && vertex[j].visited==false){DFS_traversal(j);std::cout<<"None"<<std::endl;}}clear();
}template<class T>
void UnDMaGraph<T>::BFS_traversal(int i)
{int queue[MAXSIZE];int f=0, r=0;std::cout<<vertex[i].data<<"->";vertex[i].visited = true;queue[++r] = i;while(f!=r){i = queue[++f];for(int j=0; j<vNum; ++j){if(arc[i][j]!=INFINITY && vertex[j].visited==false){std::cout<<vertex[j].data<<"->";vertex[j].visited = true;queue[++r] = j;}}}
}template<class T>
void UnDMaGraph<T>::BFS(int i)
{std::cout<<"BFS:"<<std::endl;BFS_traversal(i);std::cout<<"None"<<std::endl;for(int j=0; j<vNum; ++j){if(arc[i][j]==INFINITY && vertex[j].visited==false){BFS_traversal(j);std::cout<<"None"<<std::endl;}}clear();
}template<class T>
void UnDMaGraph<T>::Show()
{std::cout<<"————————————数据域与下标对照表————————————"<<std::endl;std::cout<<"下标：|";for(int i=0; i<vNum; ++i)std::cout<<i<<"   |";std::cout<<std::endl;std::cout<<"数据：|";for(int i=0; i<vNum; ++i)std::cout<<vertex[i].data<<"   |";std::cout<<std::endl<<"——————————————————————————————————————————"<<std::endl;std::cout<<"图的连接情况："<<std::endl;DFS(0);BFS(0);
}template<class T>
void UnDMaGraph<T>::clear()
{for(int k=0; k<vNum; ++k)vertex[k].visited = false;
}
template<class T>
void UnDMaGraph<T>::Dijstra(int S)
{bool isvisit[MAXSIZE]={false};int dist[MAXSIZE];for(int i=0;i<vNum;