1.找到字符串中出現次數最少的字符
?
題目描寫敘述
給定一個字符串（長度小于50）
找到該字符串出現次數最少的字符
假設有兩個字符出現次數同樣，并且均出現最少。那么ASCII碼小的字符優先
?
輸入
輸入為一行字符串。不含空格
輸出
輸出出現次數最少的字符
例子輸入
rra3
333444abcd
例子輸出
3
a
解題思路：
先將字符串內部依據字符順序排序，然后遍歷一遍。記錄出現次數最小的（假設有多個次數最小的。選排序在最前的）。
代碼：
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;char a[105];int main()
{int len,i;while(cin>>a){len=strlen(a);sort(a,a+len);//cout<<a<<endl;int min=105; //字符出現的最少次數賦初值char res;int p=1;for(i=len-2; i>=0; i--){if(a[i]==a[i+1]) //統計a[i+1]出現的次數p++;else{if(p<=min) //更新出現次數最少的{min=p;res=a[i+1];}p=1;}}if(p<=min) //推斷a[0]{min=p;res=a[0];}cout<<res<<endl;}
}/*
rra3
333444abcd
1112234
11223344
*/
2.歸并兩個已排序的數組（數組長度在1-20之間）。將其歸并成一個順序的數組
?
注意：在輸出時。最后一個數字后邊要打印一個空格
?
輸入
第一行給定測試用例的個數N。接下來兩行數據為一組，每行的第一個數是一個整數，表示的是該行數組的大小。
輸出
輸出每一個測試用例的結果。每行數據為一行。注意：在輸出時，最后一個數字后邊要打印一個空格
?
例子輸入
2
4?1?3?5?7
3?2?4?6
2?3?5
3?-1?2?3
例子輸出
1?2?3?4?5?6?7?
-1?2?3?3?5
解題思路：
用兩個指針遍歷兩個數組。每次輸出小的。
代碼：
#include<iostream>
using namespace std;int a[105];
int b[105];int main()
{int tes;int m,n;int i,j;while(cin>>tes){while(tes--){cin>>m;for(i=0; i<m; i++)cin>>a[i];cin>>n;for(i=0; i<n; i++)cin>>b[i];i=0,j=0;while(i<m&&j<n) //兩個數組里面用指針選小的{if(a[i]<b[j]){cout<<a[i]<<" ";i++;}else{cout<<b[j]<<" ";j++;}}while(i<m) //a數組還有剩余{cout<<a[i]<<" ";i++;}while(j<n) //b數組還有剩余{cout<<b[j]<<" ";j++;}cout<<endl;}}return 0;
}/*
2
4 1 3 5 7
3 2 4 6
2 3 5
3 -1 2 3
*/3.推斷二叉樹的先序遍歷序列
?
題目描寫敘述
一種線性表示二叉樹的方式是使用先序遍歷序列，假設遇到非空節點。我們記錄它的值，假設遇到空節點，我們用固定字符或者數字表示。比如用數字0表示
?
比如上邊這樣一顆二叉樹，其先序遍歷序列為“9?3?4?0?0?1?0 0 2?0?6?0?0”，當中0表示空節點。給出一個線性序列，推斷這個序列是否為一個二叉樹的先序遍歷序列。
序列中每一個非空節點的值均為非0整數，0表示空節點。節點之間用空格隔開，節點個數不超過20個
?
輸入
輸入一行序列。序列中每一個數字表示一個節點的值，非空節點的值均為非0整數，0代表空節點，節點之間用空格隔開，節點個數不超過20個。
?
輸出
假設該序列是一個二叉樹的先序遍歷序列。輸出一行“True”,否則輸出“False”
?
例子輸入
9?3?4?0?0?1?0?0?2?0?6?0?0
1?0
9?0?0?1
例子輸出
True
False
False
解題思路：
首先一個二叉樹必須是葉子節點個數等于枝干節點數+1。
即數組里面0的個數等于非0個數+1。假設不滿足。直接輸出False。
然后依照先序建立二叉樹的方法。記錄建立二叉樹總共用的節點。
假設
1）建立二叉樹使用的節點數index等于數組里數的個數n，
2）數組里面0的個數等于非0個數+1。
那么輸出True，否則輸出False。
代碼：
#include<iostream>
#include<cstring>
#define maxn 1005
using namespace std;char str[maxn];
int a[maxn];
int index;typedef struct node
{node *l;node *r;int val;
}*root;void createBiTree(root T) //先序建立二叉樹
{if(a[index] == 0){T = NULL;index++;}else{T = new node;T->val = a[index++];createBiTree(T->l);createBiTree(T->r);}
}int main()
{int len,i,n;while(gets(str)){n=0;int tmp,flag;tmp=flag=0;len=strlen(str);int cnt=0; //記錄葉子節點個數for(i=0; i<len; i++) //將字符串處理成int數組保存在數組a中{if(str[i]=='-'){flag=1;}else if(str[i]==' '){if(flag)tmp=0-tmp;a[n]=tmp;if(a[n]==0)cnt++;n++;flag=0;tmp=0;}elsetmp=tmp*10+(str[i]-'0');}if(flag)tmp=0-tmp;a[n]=tmp;if(a[n]==0) cnt++;n++;if(cnt!=n-cnt+1) //葉子節點必須等于枝干節點+1{cout<<"False"<<endl;continue;}index=0;root T;createBiTree(T);if(n==index)cout<<"True"<<endl;elsecout<<"False"<<endl;}return 0;
}/*
9 3 4 0 0 1 0 0 2 0 6 0 0
1 0
9 0 0 19 2 0 0 5 6 0 0 0
9 2 0 0 5 0 6 0 0
*/4.最短路徑和
?
題目描寫敘述
輸出一個大小為M×N的方格，每一個方格填滿了非負整數。找到一條從左上角到右下角的路徑，使得路徑經過的全部方格內的值相加和最小
1?2?3
1?1?1
比如如上方格，從左上角開始先向下走，再向右走。得到的路徑和最短。最短為1+1+1+1=4
?
注意：在隨意時刻。你僅僅有向下移動或者向右移動。
?
輸入
輸入第一行為該方格的行數和列數。行數和列數不超過1000。
接著輸入數字矩陣
輸出
輸出最短路徑和
例子輸出
2?3
1?2?3
1?1?1
1?1
3
例子輸出
4
3
解題思路：
在隨意時刻。你僅僅有向下移動或者向右移動。
不論什么一個狀態僅僅能從上方或者左方得到。
用二維數組a存儲該方格。用dp[i][j]表示到達第i行第j列這個數的最小值。
1）dp[1][j]僅僅能從左方得到。dp[1][j]=dp[1][j-1]+a[1][j];
2) dp[i][1]僅僅能從上方得到。dp[i][1]=dp[i-1][1]+a[i][1];
3) dp[i][j](i>1,j>1)能夠從左方和上方得到。狀態轉移方程為
dp[i][j] = min(dp[i-1][j] , dp[i][j-1]) +a[i][j]
最后輸出dp[m][n]即為結果
代碼：
#include<iostream>
#define maxn 1005
using namespace std;int a[maxn][maxn];
int dp[maxn][maxn];int mi(int p1,int p2)
{if(p1<p2) return p1;return p2;
}int main()
{int m,n;int i,j;while(cin>>m>>n){for(i=1; i<=m; i++)for(j=1; j<=n; j++)cin>>a[i][j];dp[0][1]=0;dp[1][0]=0;for(i=1; i<=m; i++)dp[i][1]=a[i][1]+dp[i-1][1];for(i=1; i<=n; i++)dp[1][i]=a[1][i]+dp[1][i-1];for(i=2; i<=m; i++){for(j=2; j<=n; j++){dp[i][j]=mi(dp[i-1][j],dp[i][j-1])+a[i][j];}}/*for(i=1;i<=m;i++){for(j=1;j<=n;j++){cout<<dp[i][j]<<" ";}cout<<endl;}*/cout<<dp[m][n]<<endl;}
}5.找出一個缺失的正整數
描寫敘述
給定一個未排序的數組，找出一個缺失的正整數
比如
數組?1?2?0
有正整數1和2。缺失的第一個正整數是3
?
輸入
輸入為一個未排序的整數數組。數組長度不超過1000000
輸出
輸出為整數數組中第一個缺失的正整數
?
例子輸入
1?2?0
3?4?-1?1
例子輸出
3
2
解題思路：
把全部的正正整數都映射到map里面。
然后從最小的正整數1開始找，假設沒有被映射。便輸出。然后結束。
代碼：
#include<iostream>
#include<cstring>
#include<map>
using namespace std;char str[1005];
map <int,int> mq;int main()
{int len,i;while(gets(str)){mq.clear();int tmp,flag;tmp=flag=0;len=strlen(str);for(i=0; i<len; i++) //將字符串處理成int數組保存在數組a中{if(str[i]=='-'){flag=1;}else if(str[i]==' '){if(!flag) //負數不須要處理{mq[tmp]=1;}flag=0;tmp=0;}elsetmp=tmp*10+(str[i]-'0');}if(!flag)mq[tmp]=1;for(i=1;; i++){if(!mq[i]){cout<<i<<endl;break;}}}return 0;
}
