数据结构算法题解大全【持续更新】（c++）

提示：觉得题多时看目录查找哦！

1、二维数组查找

题述

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

时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M。

我的思路

  • 该题中二维数组每行从左到右是递增的，每列从上到下是递增的。
  • 起始指针从二维数组末尾行第一元素m开始，
  1. 如果存在m>target，代表目标值小于此行任意一个元素，则可剔除m所在行，指针上移一行，
  2. 如果存在m<target，因为指针是从左下角，即行首列尾出开始的，此时m所在列靠后元素已经查过，则查找m所在行即可
  3. 如果相等则输出。
  • 该题复杂度O(列宽+log行宽)

算法一览

删选+二分查找

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        //有序，从末尾行开始查找
        for(int i = (array.size()-1);i>=0;i--)
        {
                if(array[i][0]<target)//如果该行第一个元素小于目标值
                {
                        //二分查找当前行
                        int low,high,mid;
                        low = 0,high = (array[i].size()-1);
                        while(low<=high)
                        {
                                mid = (low/2+high/2);
                                if(array[i][mid]==target)return true;
                                else if(array[i][mid]<target)low = mid+1;
                                else high = mid-1; 
                        }
                         return false;
                }
        }
       
    }
};

暴力破解

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        //有序，从末尾行开始查找
        for(int i = (array.size()-1);i>=0;i--)
        {
            for(int i = (array.size()-1);i>=0;i--)
            {
                  if(array[i][mid]==target)return true;
            }
       }    
       return false;     
    }
};

2、字符串的排列

题述

热度指数：628718时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

输出描述
按照字典序列输出所有结果。

我的思路

  • 首先需要将字符进行全排列，排列后进行字典排序，题考点是字典序的全排列，比较简单直接上代码。

算法一览

递归实现

class Solution {
public:
    vector<string> Permutation(string str) {
            vector<string> sstream;
            if(str.empty())return sstream;//字符为空，返回结果
            arr(sstream,str,0);//全排列查找所有结果
            sort(sstream.begin(),sstream.end());//字典排序
            return sstream;
    }
    void arr(vector<string> &sstream,string str,int start)
    {
            if(start==str.size()-1)//查找str末尾处，排序完成。
            {
                    //如果vector中没有查找到str，则str存入vector中
                    if(find(sstream.begin(),sstream.end(),str) == sstream.end())sstream.push_back(str);
                    return;
            }
            for(int i= start;i<str.size();i++)//将start位置元素和其后所有元素逐一交换
            {
                    {int cnt = str[i];str[i] = str[start];str[start] = cnt;}//交换
                    arr(sstream,str,start+1);//排列下一个
                    {int cnt = str[i];str[i] = str[start];str[start] = cnt;}//回溯交换
            }
    }
}

next_permutation函数调用版

#include <algorithm>
class Solution {
public:
    vector<string> Permutation(string str) {
            vector<string> sstream;
            if(str.empty())return sstream;//字符为空，返回结果
            do
            {
                if(find(sstream.begin(),sstream.end(),str) == sstream.end())sstream.push_back(str);
            }while(std::next_permutation(str,str+(str.size()));
            
            sort(sstream.begin(),sstream.end());//字典排序
            return sstream;
    }
}

3、简单错误记录

题述

热度指数：56451时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M

开发一个简单错误记录功能小模块，能够记录出错的代码所在的文件名称和行号。
处理:
1.记录最多8条错误记录，对相同的错误记录(即文件名称和行号完全匹配)只记录一条，错误计数增加；(文件所在的目录不同，文件名和行号相同也要合并)
2.超过16个字符的文件名称，只记录文件的最后有效16个字符；(如果文件名不同，而只是文件名的后16个字符和行号相同，也不要合并)
3.输入的文件可能带路径，记录文件名称不能带路径

输入描述:
一行或多行字符串。每行包括带路径文件名称，行号，以空格隔开。

文件路径为windows格式

如：E:\V1R2\product\fpgadrive.c 1325

输出描述:
将所有的记录统计并将结果输出，格式：文件名代码行数数目，一个空格隔开，如: fpgadrive.c 1325 1

结果根据数目从多到少排序，数目相同的情况下，按照输入第一次出现顺序排序。

如果超过8条记录，则只输出前8条记录.

如果文件名的长度超过16个字符，则只输出后16个字符

示例1
输入
E:\V1R2\product\fpgadrive.c 1325
输出
fpgadrive.c 1325 1

我的思路

  • 选取一个合适的存储空间：vector+map存储，本题中要求最后结果要按错误数量从大到小排序，则使用vector+pair存储组合
  • 大致实现过程是，先按照每行存储输入数据，去掉每行的字符串里‘\’前的数据，再添加到存储组合中，每填一个判断该字符串是否和存储组合里的重复，重复增加错误数量，对数量按值排序，输出即可

算法一览

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<pair<string,int> > filePaths;//文件记录表 

bool compare(pair<string,int> a, pair<string,int> b){
    return a.second > b.second;
}
int main()
{
        string str;//记录一行数据 
        unsigned int loc ;//定位\位置 
        
        while(getline(cin,str))
        {
                if(str.size()==0) break;
                
                //去除字符str的路径，保留文件和行号 
                loc  = str.find_last_of("\\");
//                cout<<loc<<endl;
                if(loc!=string::npos)str = str.substr(loc+1);// 查找到'\',更新str 
//              cout<<str<<endl; 
                
                //如果在文件记录表中找到了str则错误计数加一 ，找不到则错误计数置为 1
                filePaths.push_back(make_pair(str,1)); //初始化添加的值 
                for(int i=0;i<(filePaths.size()-1);i++)//查找该值前面的所有元素 
                {
                    if(filePaths[i].first==str)
                    {
                        filePaths[i].second++; 
                        filePaths.pop_back();//删除最后一个元素 
                        break;
                    }
                } 
                
        }
//        cout<<filePaths.size()<<endl<<endl;
        //按照数目排序
        stable_sort(filePaths.begin(), filePaths.end(), compare);
    
        for(int i =0;i<filePaths.size()&&i<8;i++)
        {
            str = filePaths[i].first;
            //处理大于十六位的字符
            loc = str.find_last_of(' ');
            if(loc>16) str = str.substr(loc-16);
            cout<<str<<" "<<filePaths[i].second<<endl;
        }
        
        
        return 0;
}

4、字符串排序

题述

下列程序的功能是将 s 中的字符串按长度由小到大排列，请为横线处选择合适的程序（）

#include <stdio.h>
#include <string.h>
 
void f(char *p[],int n) {
 
    char *t;
     
    int i,j;
     
    for(i=0;i<n-1;i++)
     
        for(j=i+1;j<n;j++)
     
            if(strlen(*(p+i))>strlen(*(p+j))) {
     
                t=*(p+i);
                 
                *(p+i)=*(p+j);
                 
                *(p+j)=t;
            }
}
main() {
 
    char *s[]={“abc”,”abcdef”,”abbd”};
     
    f(s,3);
     
    for(int i=0;i<3;i++)
     
    printf(“%s\n”,____);
     
}
  • s+i
  • s[i]
  • *s[i]
  • &s[i]

我的解析

答案选B.
题中s[i]等同于是char * c,存储的是一个字符串的首地址，比如char a[] = {"abc"}，则 s[i]=c= a，那么printf(“%s\n”,a);是能够通过a首地址输出整个字符串的,示例如下。

main() {
    char a[]={"abc"};
    char *c = a;
    printf("%s\n",c);
      
}

5、.我要通过！

题述

时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M

“答案正确”是自动判题系统给出的最令人欢喜的回复。本题属于PAT的“答案正确”大派送 —— 只要读入的字符串满足下列条件，系统就输出“答案正确”，否则输出“答案错误”。
得到“答案正确”的条件是：

  1. 字符串中必须仅有P, A, T这三种字符，不可以包含其它字符；
  2. 任意形如 xPATx 的字符串都可以获得“答案正确”，其中 x 或者是空字符串，或者是仅由字母 A 组成的字符串；
  3. 如果 aPATc 是正确的，那么 aaaaa..PAATcccccc.. 也是正确的，其中 a, c 均或者是空字符串，或者是仅由字母 A 组成的字符串。
    现在就请你为PAT写一个自动裁判程序，判定哪些字符串是可以获得“答案正确”的。

输入描述:
每个测试输入包含1个测试用例。第1行给出一个自然数n (<10)，是需要检测的字符串个数。接下来每个字符串占一行，字符串长度不超过100，且不包含空格。

输出描述:
每个字符串的检测结果占一行，如果该字符串可以获得“答案正确”，则输出YES，否则输出NO。

输入
8
PAT
PAAT
AAPATAA
AAPAATAAAA
xPATx
PT
Whatever
APAAATAA
输出
YES
YES
YES
YES
NO
NO
NO
NO

我的思路

  • 根据题中条件，判断字符串中，PAT字符是否存在，不存在则“答案不正确”，在PT字符前面后面中间都进行条件判断，记录记过，最后输出结果即可。

算法一览

#include <iostream>
#include <string>
#include <vector>
using namespace std;
bool is_true(string s)//校验失败，返回真
{
        int cnt =0;
        while(cnt<s.length()){if(s[cnt]!='A'&&s[cnt]!=' '){return true;}cnt++;}
        return false;
}
int main()
{
        vector<string> ss;
        int n;
        cin>>n;
        string s;
        unsigned int ploc,aloc,tloc;
        for(int i=0;i<n;i++)
        {
                cin>>s;
                //没有找到P、A、T，输出错误
                ploc = s.find('P');  
                aloc = s.find('A');
                tloc = s.find('T');
                if(ploc==string::npos||aloc==string::npos||tloc==string::npos){ss.push_back("no");continue;}
               
                string pfs = s.substr(0,ploc);//截取p前面字符，
                string pts = s.substr(ploc+1,tloc-ploc-1);//截取pt中间字符，
                string ths = s.substr(tloc+1);//截取t后面字符，
                //校验p前面字符
                if(is_true(pfs)){ss.push_back("NO");continue;}
                //校验pt中间字符
                if(pts!="AA"&&pts!="A"){ss.push_back("NO");continue;}
                //校验t后面的字符
                if(is_true(ths)){ss.push_back("NO");continue;}
                //提交答案正确
                ss.push_back("YES");
        }
        vector<string>::iterator begin = ss.begin();
        while(begin!=ss.end())
        {
                cout<<*begin<<endl;
                begin++;
        }
        
        return 0;
}

6、邻接矩阵删节点

题述

用邻接矩阵存储有n个结点(0,1,...,n)和e条边的有向图(0≤e≤n(n-1))。在邻接矩阵中删除结点i(0≤i≤n-1)的时间复杂度是（）
A. O(1)
B. O(n)
C. O(e)
D. O(n+e)

我的解析

答案选B.
删除节点B时，在邻接矩阵中需要把指向B的边全部删除，B指向的边也全部删除。
而邻接矩阵表示法由一个顶点表（一维数组），一个边集（邻接矩阵，二维数组）组成。由顶点表查找i，复杂度为O(1)，然后查找二维数组i行i列，置i行i列均为0（即删除i节点），复杂度为2*O（n）。
结果为O(n)，选择 B。

int i，j，k，w;
scanf("%d%d"，&G->n，&G->e); //输入顶点数和边数
for(i = 0;i < G->n;i++) //读入顶点信息，建立顶点表
{
    G->vexs[i]=getchar();
}
for(i = 0;i < G->n;i++)
{
    for(j = 0;j < G->n;j++)
    {
        G->edges[i][j] = 0; //邻接矩阵初始化
    }
}
//构造邻接矩阵
for(k = 0;k < G->e;k++)
{//读入e条边，建立邻接矩阵
    scanf("%d%d%d"，&i，&j，&w); //输入边(v i ,v j )上的权w
    G->edges[i][j]=w;
}
}//CreateMGraph

7、插入排序

题述

具有 n 个整数的数组 A=[29,6,28,20,2,24] 使用插入排序（ Insertion Sort ）算法排序，算法伪代码如下：


q.png

经过三趟排序后，数组 A 的排列状态将是（C）

  • 6,29,28,20,2,24
  • 6,28,20,2,24,29
  • 6,20,28,29,2,24
  • 2,6,20,24,28,29

8、链表合并

题述

将N条长度均为M的有序链表进行合并，合并以后的链表也保持有序，时间复杂度为()?
A. O(N * M * logN)
B. O(N*M)
C. O(N)
D. O(M)

我的解析

我的答案：A
M不确定，无法手动取出M链表中每个的最小值然后比较。
可以将M个链表合并为无序的一个顺序表，快速排序后输出到链表中。
合并一个顺序表O(M乘N),快排O(logN乘n)，输出到链表中O(M乘N)，总共O(N * M * logN)

9、堆排序

题述

将整数数组（ 7-6-3-5-4-1-2 ）按照堆排序的方式进行升序排列，请问在第一轮排序结束之后，数组的顺序是（）
A 1-2-3-4-5-6-7
B 2-6-3-5-4-1-7
C 6-5-3-2-4-1-7
D 5-4-3-2-1-6-7

我的解析

我的答案：C
根据题意升序排列及堆排序排序时首尾交换原则，我们知道应该调整堆为大根堆，这样每次堆顶与末尾元素交换时总会将最大元素置于末尾构成升序排列。所以本题解法如下：
首先调整为大根堆，然后排序，再调节成大根堆。因为要求一轮排序结束则查看结果，隐含步骤包括大根堆堆顶和数组末尾元素交换，然后重新生成大根堆。

10、最小调整有序

题述

有一个整数数组，请编写一个函数，找出索引m和n，只要将m和n之间的元素排好序，整个数组就是有序的。注意：n-m应该越小越好，也就是说，找出符合条件的最短序列。

给定一个int数组A和数组的大小n，请返回一个二元组，代表所求序列的起点和终点。(原序列位置从0开始标号,若原序列有序，返回[0,0])。保证A中元素均为正整数。

测试样例：
[1,4,6,5,9,10],6
返回：[2,3]

我的解析

本题中n、m位置完全可以通过原数组A和排序后数组B对比得到，即当A中元素与B中元素不同时则代表A中该元素需要排序，记录最开始排序的位置和最末尾需要排序的位置，则得出答案

算法一览

class Rearrange {
public:
    vector<int> findSegment(vector<int> A, int n) {
        // write code here
        vector<int> com(A);
        sort(com.begin(),com.end());//对结果排序
        
        int start,end;start=end =0;//初始化start,end
        for(int i=0;i<A.size();i++)//对比最小值无序点
        {
                if(A[i]!=com[i]){start = i;break;}
        }
        for(int i=A.size()-1;i>=0;i--)//对比最大值无序点
        {
                if(A[i]!=com[i]){end = i;break;}
        }
        
        //输出结果    
        vector<int> ans;
        ans.push_back(start);
        ans.push_back(end);
        return ans;
    }
};

2020.05.06之后更新内容详见：数据结构算法集锦

©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 204,189评论 6赞 478
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 85,577评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 150,857评论 0赞 337
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,703评论 1赞 276
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,705评论 5赞 366
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,620评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,995评论 3赞 396
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,656评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,898评论 1赞 298
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,639评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,720评论 1赞 330
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,395评论 4赞 319
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,982评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,953评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,195评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 44,907评论 2赞 349
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,472评论 2赞 342