提示：覺得題多時(shí)看目錄查找哦！
1、二維數(shù)組查找
題述
在一個(gè)二維數(shù)組中（每個(gè)一維數(shù)組的長(zhǎng)度相同），每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請(qǐng)完成一個(gè)函數(shù)，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷數(shù)組中是否含有該整數(shù)。
時(shí)間限制：C/C++ 1秒，其他語言2秒空間限制：C/C++ 32M，其他語言64M。
我的思路
- 該題中二維數(shù)組每行從左到右是遞增的，每列從上到下是遞增的。
- 起始指針從二維數(shù)組末尾行第一元素m開始，
- 如果存在m>target，代表目標(biāo)值小于此行任意一個(gè)元素，則可剔除m所在行，指針上移一行，
- 如果存在m<target，因?yàn)橹羔樖菑淖笙陆?，即行首列尾出開始的，此時(shí)m所在列靠后元素已經(jīng)查過，則查找m所在行即可
- 如果相等則輸出。
- 該題復(fù)雜度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)//如果該行第一個(gè)元素小于目標(biāo)值
{
//二分查找當(dāng)前行
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、字符串的排列
題述
熱度指數(shù)：628718時(shí)間限制：C/C++ 1秒，其他語言2秒空間限制：C/C++ 32M，其他語言64M
輸入一個(gè)字符串,按字典序打印出該字符串中字符的所有排列。例如輸入字符串a(chǎn)bc,則打印出由字符a,b,c所能排列出來的所有字符串a(chǎn)bc,acb,bac,bca,cab和cba。
輸入描述:
輸入一個(gè)字符串,長(zhǎng)度不超過9(可能有字符重復(fù)),字符只包括大小寫字母。
輸出描述
按照字典序列輸出所有結(jié)果。
我的思路
- 首先需要將字符進(jìn)行全排列，排列后進(jìn)行字典排序，題考點(diǎn)是字典序的全排列，比較簡(jiǎn)單直接上代碼。
算法一覽
遞歸實(shí)現(xiàn)
class Solution {
public:
vector<string> Permutation(string str) {
vector<string> sstream;
if(str.empty())return sstream;//字符為空，返回結(jié)果
arr(sstream,str,0);//全排列查找所有結(jié)果
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);//排列下一個(gè)
{int cnt = str[i];str[i] = str[start];str[start] = cnt;}//回溯交換
}
}
}
next_permutation函數(shù)調(diào)用版
#include <algorithm>
class Solution {
public:
vector<string> Permutation(string str) {
vector<string> sstream;
if(str.empty())return sstream;//字符為空，返回結(jié)果
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、簡(jiǎn)單錯(cuò)誤記錄
題述
熱度指數(shù)：56451時(shí)間限制：C/C++ 1秒，其他語言2秒空間限制：C/C++ 64M，其他語言128M
開發(fā)一個(gè)簡(jiǎn)單錯(cuò)誤記錄功能小模塊，能夠記錄出錯(cuò)的代碼所在的文件名稱和行號(hào)。
處理:
1.記錄最多8條錯(cuò)誤記錄，對(duì)相同的錯(cuò)誤記錄(即文件名稱和行號(hào)完全匹配)只記錄一條，錯(cuò)誤計(jì)數(shù)增加；(文件所在的目錄不同，文件名和行號(hào)相同也要合并)
2.超過16個(gè)字符的文件名稱，只記錄文件的最后有效16個(gè)字符；(如果文件名不同，而只是文件名的后16個(gè)字符和行號(hào)相同，也不要合并)
3.輸入的文件可能帶路徑，記錄文件名稱不能帶路徑
輸入描述:
一行或多行字符串。每行包括帶路徑文件名稱，行號(hào)，以空格隔開。
文件路徑為windows格式
如：E:\V1R2\product\fpgadrive.c 1325
輸出描述:
將所有的記錄統(tǒng)計(jì)并將結(jié)果輸出，格式：文件名代碼行數(shù)數(shù)目，一個(gè)空格隔開，如: fpgadrive.c 1325 1
結(jié)果根據(jù)數(shù)目從多到少排序，數(shù)目相同的情況下，按照輸入第一次出現(xiàn)順序排序。
如果超過8條記錄，則只輸出前8條記錄.
如果文件名的長(zhǎng)度超過16個(gè)字符，則只輸出后16個(gè)字符
示例1
輸入
E:\V1R2\product\fpgadrive.c 1325
輸出
fpgadrive.c 1325 1
我的思路
- 選取一個(gè)合適的存儲(chǔ)空間：vector+map存儲(chǔ)，本題中要求最后結(jié)果要按錯(cuò)誤數(shù)量從大到小排序，則使用vector+pair存儲(chǔ)組合
- 大致實(shí)現(xiàn)過程是，先按照每行存儲(chǔ)輸入數(shù)據(jù)，去掉每行的字符串里‘\’前的數(shù)據(jù)，再添加到存儲(chǔ)組合中，每填一個(gè)判斷該字符串是否和存儲(chǔ)組合里的重復(fù)，重復(fù)增加錯(cuò)誤數(shù)量，對(duì)數(shù)量按值排序，輸出即可
算法一覽
#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;//記錄一行數(shù)據(jù)
unsigned int loc ;//定位\位置
while(getline(cin,str))
{
if(str.size()==0) break;
//去除字符str的路徑，保留文件和行號(hào)
loc = str.find_last_of("\\");
// cout<<loc<<endl;
if(loc!=string::npos)str = str.substr(loc+1);// 查找到'\',更新str
// cout<<str<<endl;
//如果在文件記錄表中找到了str則錯(cuò)誤計(jì)數(shù)加一 ，找不到則錯(cuò)誤計(jì)數(shù)置為 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();//刪除最后一個(gè)元素
break;
}
}
}
// cout<<filePaths.size()<<endl<<endl;
//按照數(shù)目排序
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 中的字符串按長(zhǎng)度由小到大排列，請(qǐng)為橫線處選擇合適的程序（）
#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,存儲(chǔ)的是一個(gè)字符串的首地址，比如char a[] = {"abc"}，則 s[i]=c= a，那么printf(“%s\n”,a);是能夠通過a首地址輸出整個(gè)字符串的,示例如下。
main() {
char a[]={"abc"};
char *c = a;
printf("%s\n",c);
}
5、.我要通過！
題述
時(shí)間限制：C/C++ 1秒，其他語言2秒空間限制：C/C++ 32M，其他語言64M
“答案正確”是自動(dòng)判題系統(tǒng)給出的最令人歡喜的回復(fù)。本題屬于PAT的“答案正確”大派送 —— 只要讀入的字符串滿足下列條件，系統(tǒng)就輸出“答案正確”，否則輸出“答案錯(cuò)誤”。
得到“答案正確”的條件是：
- 字符串中必須僅有P, A, T這三種字符，不可以包含其它字符；
- 任意形如 xPATx 的字符串都可以獲得“答案正確”，其中 x 或者是空字符串，或者是僅由字母 A 組成的字符串；
- 如果 aPATc 是正確的，那么 aaaaa..PAATcccccc.. 也是正確的，其中 a, c 均或者是空字符串，或者是僅由字母 A 組成的字符串。
現(xiàn)在就請(qǐng)你為PAT寫一個(gè)自動(dòng)裁判程序，判定哪些字符串是可以獲得“答案正確”的。
輸入描述:
每個(gè)測(cè)試輸入包含1個(gè)測(cè)試用例。第1行給出一個(gè)自然數(shù)n (<10)，是需要檢測(cè)的字符串個(gè)數(shù)。接下來每個(gè)字符串占一行，字符串長(zhǎng)度不超過100，且不包含空格。
輸出描述:
每個(gè)字符串的檢測(cè)結(jié)果占一行，如果該字符串可以獲得“答案正確”，則輸出YES，否則輸出NO。
輸入
8
PAT
PAAT
AAPATAA
AAPAATAAAA
xPATx
PT
Whatever
APAAATAA
輸出
YES
YES
YES
YES
NO
NO
NO
NO
我的思路
- 根據(jù)題中條件，判斷字符串中，PAT字符是否存在，不存在則“答案不正確”，在PT字符前面后面中間都進(jìn)行條件判斷，記錄記過，最后輸出結(jié)果即可。
算法一覽
#include <iostream>
#include <string>
#include <vector>
using namespace std;
bool is_true(string s)//校驗(yàn)失敗，返回真
{
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，輸出錯(cuò)誤
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后面字符，
//校驗(yàn)p前面字符
if(is_true(pfs)){ss.push_back("NO");continue;}
//校驗(yàn)pt中間字符
if(pts!="AA"&&pts!="A"){ss.push_back("NO");continue;}
//校驗(yàn)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、鄰接矩陣刪節(jié)點(diǎn)
題述
用鄰接矩陣存儲(chǔ)有n個(gè)結(jié)點(diǎn)(0,1,...,n)和e條邊的有向圖(0≤e≤n(n-1))。在鄰接矩陣中刪除結(jié)點(diǎn)i(0≤i≤n-1)的時(shí)間復(fù)雜度是（）
A. O(1)
B. O(n)
C. O(e)
D. O(n+e)
我的解析
答案選B.
刪除節(jié)點(diǎn)B時(shí)，在鄰接矩陣中需要把指向B的邊全部刪除，B指向的邊也全部刪除。
而鄰接矩陣表示法由一個(gè)頂點(diǎn)表（一維數(shù)組），一個(gè)邊集（鄰接矩陣，二維數(shù)組）組成。由頂點(diǎn)表查找i，復(fù)雜度為O(1)，然后查找二維數(shù)組i行i列，置i行i列均為0（即刪除i節(jié)點(diǎn)），復(fù)雜度為2*O（n）。
結(jié)果為O(n)，選擇 B。
int i，j，k，w;
scanf("%d%d"，&G->n，&G->e); //輸入頂點(diǎn)數(shù)和邊數(shù)
for(i = 0;i < G->n;i++) //讀入頂點(diǎn)信息，建立頂點(diǎn)表
{
G->vexs[i]=getchar();
}
for(i = 0;i < G->n;i++)
{
for(j = 0;j < G->n;j++)
{
G->edges[i][j] = 0; //鄰接矩陣初始化
}
}
//構(gòu)造鄰接矩陣
for(k = 0;k < G->e;k++)
{//讀入e條邊，建立鄰接矩陣
scanf("%d%d%d"，&i，&j，&w); //輸入邊(v i ,v j )上的權(quán)w
G->edges[i][j]=w;
}
}//CreateMGraph
7、插入排序
題述
具有 n 個(gè)整數(shù)的數(shù)組 A=[29,6,28,20,2,24] 使用插入排序（ Insertion Sort ）算法排序，算法偽代碼如下：
經(jīng)過三趟排序后，數(shù)組 A 的排列狀態(tài)將是（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條長(zhǎng)度均為M的有序鏈表進(jìn)行合并，合并以后的鏈表也保持有序，時(shí)間復(fù)雜度為()?
A. O(N * M * logN)
B. O(N*M)
C. O(N)
D. O(M)
我的解析
我的答案：A
M不確定，無法手動(dòng)取出M鏈表中每個(gè)的最小值然后比較。
可以將M個(gè)鏈表合并為無序的一個(gè)順序表，快速排序后輸出到鏈表中。
合并一個(gè)順序表O(M乘N),快排O(logN乘n)，輸出到鏈表中O(M乘N)，總共O(N * M * logN)
9、堆排序
題述
將整數(shù)數(shù)組（ 7-6-3-5-4-1-2 ）按照堆排序的方式進(jìn)行升序排列，請(qǐng)問在第一輪排序結(jié)束之后，數(shù)組的順序是（）
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
根據(jù)題意升序排列及堆排序排序時(shí)首尾交換原則，我們知道應(yīng)該調(diào)整堆為大根堆，這樣每次堆頂與末尾元素交換時(shí)總會(huì)將最大元素置于末尾構(gòu)成升序排列。所以本題解法如下：
首先調(diào)整為大根堆，然后排序，再調(diào)節(jié)成大根堆。因?yàn)橐笠惠喤判蚪Y(jié)束則查看結(jié)果，隱含步驟包括大根堆堆頂和數(shù)組末尾元素交換，然后重新生成大根堆。
10、最小調(diào)整有序
題述
有一個(gè)整數(shù)數(shù)組，請(qǐng)編寫一個(gè)函數(shù)，找出索引m和n，只要將m和n之間的元素排好序，整個(gè)數(shù)組就是有序的。注意：n-m應(yīng)該越小越好，也就是說，找出符合條件的最短序列。
給定一個(gè)int數(shù)組A和數(shù)組的大小n，請(qǐng)返回一個(gè)二元組，代表所求序列的起點(diǎn)和終點(diǎn)。(原序列位置從0開始標(biāo)號(hào),若原序列有序，返回[0,0])。保證A中元素均為正整數(shù)。
測(cè)試樣例：
[1,4,6,5,9,10],6
返回：[2,3]
我的解析
本題中n、m位置完全可以通過原數(shù)組A和排序后數(shù)組B對(duì)比得到，即當(dāng)A中元素與B中元素不同時(shí)則代表A中該元素需要排序，記錄最開始排序的位置和最末尾需要排序的位置，則得出答案
算法一覽
class Rearrange {
public:
vector<int> findSegment(vector<int> A, int n) {
// write code here
vector<int> com(A);
sort(com.begin(),com.end());//對(duì)結(jié)果排序
int start,end;start=end =0;//初始化start,end
for(int i=0;i<A.size();i++)//對(duì)比最小值無序點(diǎn)
{
if(A[i]!=com[i]){start = i;break;}
}
for(int i=A.size()-1;i>=0;i--)//對(duì)比最大值無序點(diǎn)
{
if(A[i]!=com[i]){end = i;break;}
}
//輸出結(jié)果
vector<int> ans;
ans.push_back(start);
ans.push_back(end);
return ans;
}
};
2020.05.06之后更新內(nèi)容詳見：數(shù)據(jù)結(jié)構(gòu)算法集錦
