1 查找第一個只出現一次的字符

#include <iostream> #include <cstring> #include <cstdio> using namespace std;bool findChar(char *str, char *ch);int main() {char str[100];while (cin.getline(str, 100)){char ch;if (findChar(str, &ch)){cout<<ch<<endl;}else{cout<<"."<<endl;}} }bool findChar(char *str, char *ch) {int c[256] = {0};for (int i = 0; i < strlen(str); i++){c[str[i]]++;}for (int i = 0; i < strlen(str); i++){if (c[str[i]] == 1){*ch = str[i];return true;}}return false; }

2 字符串排序

編寫一個程序，將輸入字符串中的字符按如下規則排序。
規則1：英文字母從A到Z排列，不區分大小寫。
如，輸入：Type 輸出：epTy
規則2：同一個英文字母的大小寫同時存在時，按照輸入順序排列。
如，輸入：BabA 輸出：aABb
規則3：非英文字母的其它字符保持原來的位置。
如，輸入：By?e 輸出：Be?y
樣例：
輸入：
A Famous Saying: Much Ado About Nothing(2012/8).
輸出：
A aaAAbc dFgghh: iimM nNn oooos Sttuuuy (2012/8).

解題思路就是冒泡排序。

#include <iostream> #include <cstring> #include <cstdio> using namespace std;void sort(char *str); bool isChar(char c);int main() {char str[100];while (cin.getline(str, 100)){sort(str);cout<<str<<endl;}return 0; }void sort(char *str) {for (int i = 0; i < strlen(str) - 1; i++){for (int j = 0; j < strlen(str) - i - 1; j++){int m = j;// 增加這兩個while是因為除字母外的其他字符要保持原位while (!isChar(str[m]) && m > 0){m--;}int n = j + 1;while (!isChar(str[n]) && n < strlen(str) - 1){n++;}int nm = str[m] >= 97 ? str[m] : str[m] + 32;int nn = str[n] >= 97 ? str[n] : str[n] + 32;if (isChar(str[m]) && isChar(str[n]) && nm > nn){char c = str[m];str[m] = str[n];str[n] = c;}}} }bool isChar(char c) {if ((c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z')){return true;}return false; }

3 DNA序列

輸入字符串和子串長度，得到CG比例最高的子串。
（建立一個長度為子串長度的窗口，然后向右移動窗口）

#include <iostream> #include <cstring> #include <cstdio> using namespace std;void fun(char *dest, const char *src, int n);int main() {char str[100];while (cin.getline(str, 100)){int n;cin>>n;char *dest = new char[n+1];fun(dest, str, n);cout<<dest<<endl;delete [] dest;}return 0; }void fun(char *dest, const char *src, int n) {int len = strlen(src);int i = 0;int max_count = 0;int max_left = 0;int count = 0;int left = 0;while (i < n){if (src[i] == 'C' || src[i] == 'G'){count++;}i++;}max_count = count;while (i < len){int b1 = (src[i] == 'C' || src[i] == 'G');int b2 = (src[i - n] == 'C' || src[i - n] == 'G');left = i - n + 1;count += b1 - b2;if (count > max_count){max_count = count;max_left = left;}i++;}while (n--){*dest++ = src[max_left++];}*dest = '\0'; }

4 整形數組合并

未排序的數組合并，合并時要去除重復值

#include <iostream> using namespace std;void CombineBySort(int* pArray1,int iArray1Num,int* pArray2,int iArray2Num,int* pOutputArray,int *iOutputNum); void sort(int *nums, int len); void print(int *nums, int len);int main() {int n1;while (cin>>n1){int *array1 = new int[n1];int i1 = 0;while(i1 < n1){cin>>array1[i1++];}int n2;cin>>n2;int *array2 = new int[n2];int i2 = 0;while(i2 < n2){cin>>array2[i2++];}int *array = new int[n1+n2];int n;CombineBySort(array1, n1, array2, n2, array, &n);print(array, n);delete [] array1;delete [] array2;delete [] array;}return 0; }void CombineBySort(int* pArray1,int iArray1Num,int* pArray2,int iArray2Num,int* pOutputArray,int* iOutputNum) {sort(pArray1, iArray1Num);sort(pArray2, iArray2Num);int i1 = 0;int i2 = 0;int index = 0;int n;if (pArray1[i1] < pArray2[i2]){n = pArray1[i1];i1++;pOutputArray[index++] = n;}else{n = pArray2[i2];i2++;pOutputArray[index++] = n;}while (i1 < iArray1Num && i2 < iArray2Num){if (pArray1[i1] <= pArray2[i2]){n = pArray1[i1];i1++;}else{n = pArray2[i2];i2++;}if (n != pOutputArray[index-1]){pOutputArray[index++] = n;}}while (i1 < iArray1Num){if (pArray1[i1] != pOutputArray[index-1]){pOutputArray[index++] = pArray1[i1];}i1++;}while (i2 < iArray2Num){if (pArray2[i2] != pOutputArray[index-1]){pOutputArray[index++] = pArray2[i2];}i2++;}*iOutputNum = index; }void sort(int *nums, int len) {for (int i = 0; i < len - 1; i++){for (int j = 0; j < len - i - 1; j++){if (nums[j] > nums[j+1]){int temp = nums[j];nums[j] = nums[j+1];nums[j+1] = temp;}}} }void print(int *nums, int len) {for (int i = 0; i < len; i++){cout<<nums[i];}cout<<endl; }

5 查找兩個字符串a,b中的最長公共子串

#include <iostream> #include <cstring> #include <cstdio> using namespace std;char* fun(char *str1, char *str2, char *str);int main() {char str1[100];char str2[100];while (gets(str1) && gets(str2)){char str[100] = {0};cout<<fun(str1,str2,str)<<endl;;} }char* fun(char *str1, char *str2, char *str) {int len1 = strlen(str1);int len2 = strlen(str2);int **c = new int*[len1 + 1];for (int i = 0; i < len1 + 1; i++){c[i] = new int[len2 + 1];}for (int i = 0; i < len1 + 1; i++){c[i][0] = 0;}for (int i = 0; i < len2 + 1; i++){c[0][i] = 0;}int max = 0;int maxi = 0;int maxj = 0;for (int i = 1; i < len1 + 1; i++){for (int j = 1; j < len2 + 1; j++){if (str1[i - 1] == str2[j - 1]){c[i][j] = c[i - 1][j - 1] + 1;if (c[i][j] > max){max = c[i][j];maxi = i;maxj = j;}}else{c[i][j] = 0;}}}char *temp = str;int i = maxi;int j = maxj;while (c[i][j] > 0){if (str1[i - 1] == str2[j - 1]){*temp++ = str1[i - 1];}i--;j--;}*temp = '\0';char *left = str;char *right = str + strlen(str) - 1;while (left < right){char c = *left;*left++ = *right;*right-- = c;}return str; }

6 成績排序

輸入數據組數，排序方式（升序或者降序），n組數據（由姓名和分數組成）。
輸出最后的排序結果。

#include <iostream> #include <cstring> #include <cstdio> using namespace std;struct User {char name[20];int val; };int main() {int n;while (cin>>n){int flag;cin>>flag;User *users = new User[n];int i = 0;while (i < n){cin>>users[i].name;cin>>users[i++].val;}for (int i = 0; i < n - 1; i++){int k = i;for (int j = i + 1; j < n; j++){if ((flag == 1 && users[j].val < users[k].val) || (flag == 0 && users[j].val > users[k].val)){k = j;}}if (k != i){User temp = users[k];users[k] = users[i];users[i] = temp;}}for (int i = 0; i < n; i++){cout<<users[i].name<<" "<<users[i].val<<endl;}} }

7 汽水瓶

用空瓶子換汽水，三個空瓶換一瓶汽水。輸入空瓶數目，輸出可以換到的汽水數目。輸入以0結束。

#include <iostream> #include <cstring> #include <cstdio> using namespace std;int main() {int n;while (cin>>n, n != 0){int sum = 0;while (n >= 3){sum += n / 3;n = n % 3 + n / 3;}if (n == 2){sum += 1;}cout<<sum<<endl;} }

8 記負均正

輸出負數的個數，以及正數的均值。均為為小數，則保留1位小數。

#include <iostream> #include <cstdio> using namespace std;int main() {int n;while (cin>>n){if (n == 0){cout<<"0 0";return 0;}int num;int c1 = 0;int c2 = 0;int sum = 0;int i = 0;while (i++ < n){cin>>num;if (num > 0){sum += num;c1++;}else if (num < 0){c2++;}}sum % c1 == 0 ? printf("%d %d\n", c2, sum / c1) : printf("%d %.1f\n", c2, float(sum) / c1);}return 0; }

9 字符串運用-密碼截取

輸入的字符為加入了前綴或者后綴字符的回文字符串，要求輸出最長回文子串的長度。
輸入：
ABBA
ABBA12
輸出
4
4

#include <iostream> #include <cstdio> #include <cstring> using namespace std;void reverse(const char *str1, char *str2); int fun(const char* str1, const char *str2);int main() {char str1[100];while (cin.getline(str1, 100)){char str2[100];reverse(str1, str2);cout<<fun(str1, str2)<<endl;}return 0; }void reverse(const char *str1, char *str2) {int index = strlen(str1) - 1;while (index >= 0){*str2++ = str1[index--];}*str2 = '\0'; }int fun(const char* str1, const char *str2) {int len1 = strlen(str1);int len2 = strlen(str2);int **c = new int*[len1 + 1];for (int i = 0; i <= len1; i++){c[i] = new int[len2 + 1];}for (int i = 0; i <= len1; i++){c[i][0] = 0;}for (int i = 0; i <= len2; i++){c[0][i] = 0;}int m = 0;for (int i = 0; i <= len1; i++){for (int j = 0; j <= len2; j++){if (str1[i - 1] == str2[j - 1]){c[i][j] = c[i - 1][j - 1] + 1;}else{c[i][j] = 0;}m = max(m, c[i][j]);}}return m; }

10 字符串分隔

輸入：
abc
123456789
輸出：
abc00000
12345678
90000000
（首先將字符串補成長度為8的倍數的字符串，然后輸出）

#include <iostream> #include <cstdio> #include <cstring> using namespace std;int main() {char str[108];while (cin.getline(str, 108)){int len = strlen(str);while (len % 8 != 0){str[len] = '0';str[len + 1] = '\0';len++;}int i = 0;while (str[i] != '\0'){if ((i + 1) % 8 == 0){cout<<str[i]<<endl;}else{cout<<str[i];}i++;}}return 0; }

11 撲克牌大小

輸入兩手牌，輸出較大的一手牌，若沒有大小關系，則輸出“ERROR”。
輸入：
3-8
2-A
3 3 3-7 7 7
J J-8
4 4 4 4-joker JOKER
輸出：
8
2
7 7 7
ERROR
joker JOKER
(對于每張牌，除J和JOKER外，比較第一個字符即可知道牌的大小)

#include <iostream> #include <cstdio> #include <cstring> #include <string> using namespace std;enum Type {GEZI = 1, DUIZI, SHUNZI, SANGE, ZHADAN, DUIWANG };char c[15][6] = {"3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K", "A", "2", "joker", "JOKER"}; int n[15] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};struct Cards {Type type;int val; };int getCardValue(char ch); int getCardNum(string str); void format(string str, int n[]); void nums2Card(int values[], int n, Cards& C); int cmp(Cards C1, Cards C2);int main() {char str[100];while (cin.getline(str, 100)){string str1 = "";string str2 = "";int i = 0;while (str[i] != '-'){str1 += str[i++];}i++;while (str[i] != '\0'){str2 += str[i++];}int cardNum1 = getCardNum(str1);int cardNum2 = getCardNum(str2);int nums1[5] = {0};int nums2[5] = {0};format(str1, nums1);format(str2, nums2);Cards hand1;Cards hand2;nums2Card(nums1, cardNum1, hand1);nums2Card(nums2, cardNum2, hand2);if (cmp(hand1, hand2) == 1){cout<<str1.c_str()<<endl;}else if (cmp(hand1, hand2) == -1){cout<<str2.c_str()<<endl;}else{cout<<"ERROR"<<endl;}}return 0; }int getCardValue(char ch) {for (int i = 0; i < 15; i++){if (ch == c[i][0]){return n[i];}}return -1; }int getCardNum(string str) {int count = 0;for (int i = 0; i < str.size(); i++){if (str[i] == ' '){count++;}}return count + 1; }void format(string str, int n[]) {int card_index = 0;int i = 0;while(i < str.size()){if (str[i] != ' '){int card_value;if (str[i] == 'J' && i + 1 < str.size() && str[i + 1] == 'O'){card_value = 15;}else{card_value = getCardValue(str[i]);}n[card_index++] = card_value;while(i < str.size() && str[i] != ' '){i++;}}else{i++;}} }void nums2Card(int values[], int n, Cards& C) {if (n == 1){C.type = (Type)1;C.val = values[0];}else if (n == 2){if (values[0] == values[1]){C.type = (Type)2;C.val = values[0];}else if (values[0] + values[1] == 29){C.type = (Type)6;C.val = 15;}}else if (n == 3 && values[0] == values[1] && values[1] == values[2]){C.type = (Type)4;C.val = values[0];}else if (n == 4 && values[0] == values[1] && values[1] == values[2] && values[2] == values[3]){C.type = (Type)5;C.val = values[0];}else if (n == 5){int diff = values[1] - values[0];if (values[2] - values[1] == diff && values[3] - values[2] == diff && values[4] - values[3] == diff)C.type = (Type)3;C.val = values[0];}else{C.type = (Type)0;C.val = 0;} }int cmp(Cards C1, Cards C2) {if (C1.type < 5 && C2.type < 5){if (C1.type == C2.type){return C1.val > C2.val ? 1 : -1;}}else{if (C1.type == C2.type){return C1.val > C2.val ? 1 : -1;}return C1.type > C2.type ? 1 : -1;}return 0; }

12 輸入一行字符，分別統計出包含英文字母、空格、數字和其它字符的個數

#include <iostream> #include <cstdio> #include <cstring> using namespace std;int main() {char ch[100];while (cin.getline(ch, 100)){int en = 0;int blank = 0;int num = 0;int other = 0;for (int i = 0; i < strlen(ch); i++){if ((ch[i] >= 'A' && ch[i] <= 'Z') || (ch[i] >= 'a' && ch[i] <= 'z')){en++;}else if (ch[i] == ' '){blank++;}else if (ch[i] >= '0' && ch[i] <= '9'){num++;}else{other++;}}cout<<en<<endl<<blank<<endl<<num<<endl<<other<<endl;}return 0; }

13 統計每個月兔子的總數

第一個月—————–1
第二個月—————–1
第三個月—————–2
第四個月—————–3
第五個月—————–5
第六個月—————–8
第七個月—————–13

#include <iostream> using namespace std;int main() {int n;while (cin>>n){int a = 0;int b = 1;int c;int i = 2;while (i <= n){c = a + b;a = b;b = c;i++;}cout<<c<<endl;}return 0; }

14 質數因子

找出輸入整數的所有質數因子
輸入：180
輸出：2 2 3 3 5

#include <iostream> using namespace std;bool isPrime(int n);int main() {int n;while (cin>>n){int i = 2;while (n != 1){while (isPrime(i) && n % i == 0){cout<<i<<" ";n /= i;}i++;}}return 0; }bool isPrime(int n) {for (int i = 2; i <= n / 2; i++){if (n % i == 0){return false;}}return true; }

15 自守數

一個數的平方的尾數等于該自然數本身的數。（252=625）
輸入：
2000
輸出：8
思路：（625 - 25） % 100 == 0？

#include <iostream> using namespace std;int getBit(int n); int fun(int n);int main() {int n;while (cin>>n){cout<<fun(n)<<endl;}return 0; }int getBit(int n) {int b = 0;while (n / 10 != 0){b++;n /= 10;}int x = 10;for (int i = 0; i < b; i++){x *= 10;}return x; }int fun(int n) {int count = 0;for (int i = 0; i <= n; i++){int b = getBit(i);if ((i * i - i) % b == 0){count++;}}return count; }

16 iNOC產品部–完全數計算

完全數（Perfect number），又稱完美數或完備數，是一些特殊的自然數。
它所有的真因子（即除了自身以外的約數）的和（即因子函數），恰好等于它本身。
例如：28，它有約數1、2、4、7、14、28，除去它本身28外，其余5個數相加，1+2+4+7+14=28。
給定函數count(int n),用于計算n以內(含n)完全數的個數。計算范圍, 0 < n <= 500000
返回n以內完全數的個數。異常情況返回-1

#include <iostream> using namespace std;int fun(int n);int main() {int n;while (cin>>n){int count = 0;for (int j = 2; j <= n; j++){int sum = 0;for (int i = 1; i <= j / 2; i++){if (j % i == 0){sum += i;}}if (sum == j){count++;}}cout<<count<<endl;} }

17 人民幣轉換

#include <iostream> #include <cstdio> #include <cstring> #include <string> using namespace std;string big[10] = {"零","壹","貳","叁","肆","伍","陸","柒","捌","玖"};int dotIndex(string str); int atoi(string str, int i, int j); void toChinese(int n, string& str);int main() {string s;while (getline(cin,s)){int di = dotIndex(s);int left; //小數點左邊數字的大小int right; //小數點右邊數字的大小if (di != -1){left = atoi(s, 0, di - 1);right = atoi(s, di + 1, s.size() - 1);}else{left = atoi(s, 0, s.size() - 1);right = 0;}string str = "人民幣";toChinese(left, str);str += "元";if (right == 0){str += "整";}else{int jiao = right / 10;if (jiao != 0){str += big[jiao];str += "角";}else{str += "零";}int fen = right % 10;if (fen != 0){str += big[fen];str += "分";}}string temp = str.substr(6, 4);if (temp.compare("壹拾") == 0){str.replace(6,4,"拾");}cout<<str.c_str()<<endl;} }int dotIndex(string str) {for (int i = 0; i < str.size(); i++){if (str[i] == '.'){return i;}}return -1; }int atoi(string str, int i, int j) {int n = 0;for (int k = i; k <= j; k++){n = 10 * n + str[k] - '0';}return n; }void toChinese(int n, string& str) {int b[6] = {100000000,10000,1000,100,10,1};string c[6] = {"億","萬","仟","佰","拾",""};bool stat[6] = {false};for (int i = 0; i < sizeof(b)/sizeof(b[0]); i++){int temp = n / b[i];if (temp != 0){if (stat[i-1] && str.size() != 6){str += "零";}if (temp > 10){toChinese(temp, str);}else{str += big[temp];}str += c[i];}else{stat[i] = true;}n %= b[i];} }

18 矩陣乘法

#include <iostream> using namespace std;int main() {int x, y, z;while (cin>>x>>y>>z){int m1[100][100];int m2[100][100];int r[100][100] = {0};for (int i = 0; i < x; i++){for (int j = 0; j < y; j++){cin>>m1[i][j];}}for (int i = 0; i < y; i++){for (int j = 0; j < z; j++){cin>>m2[i][j];}}for (int i = 0; i < x; i++){for (int j = 0; j < z; j++){for (int k = 0; k < y; k++){r[i][j] += m1[i][k] * m2[k][j];}if (j == z - 1){cout<<r[i][j]<<endl;}else{cout<<r[i][j]<<" ";}}}} }

19 記負均正

輸入n個int數，輸出負數格式及整數的均值。

#include <iostream> #include <cstdio> using namespace std;int main() {int n;int zh = 0;int fu = 0;int sum = 0;while (cin>>n){if (n > 0){zh++;sum += n;}else{fu++;}}cout<<fu<<endl;printf("%.1f\n", zh == 0 ? zh : float(sum) / zh); }

20 查找組成一個偶數最接近的兩個素數

首先標記處素數（>=2），然后逐對判斷。判斷第一個數小于第二個數的即可（diff>0）。

#include <iostream> using namespace std;int main() {const int MAX = 10001;bool b[MAX];for (int i = 0; i < MAX; i++){if (i & 0x1){b[i] = true;}else{b[i] = false;}}b[2] = true;for (int i = 3; i < MAX; i++){for (int j = 2; j * i < MAX; j++){b[i * j] = false;}}int n;while (cin>>n){int min = 0x7fffffff;int x = 0, y = 0;int diff;for (int i = 2; i < n; i++){if (b[i] && b[n - i]){diff = n - 2 * i;if (diff > 0 && diff < min){min = diff;x = i;y = n - i;}}}cout<<x<<endl<<y<<endl;} }

總結

以上是生活随笔為你收集整理的[HW] OJ记录20题之二的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。