1子串个数
题目描述
给你若干个字符串，请编程输出每个字符串的子串个数
输入
若干个字符串，每个字符串占一行，字符串中不含空格，长度最大为1000。
输出
对应每一行的字符串，输出该字符串子串的个数。
样例输入
abc apple software
样例输出
7 16 37
代码
#include#include using namespace std; int countSubstrings(string s) { int n = s.length(); return n * (n + 1) / 2+1; } int main() { string s; while (getline(cin, s)) { cout << countSubstrings(s) << endl; } return 0; }
2模式串
题目描述
给你一个目标串，请查找在给目标串中是否存在模式串，存在就输出第一个模式串在目标串中出现的位置。
输入
占两行，第一行是目标串（长度小于1000）第二行为模式串（长度小于100）.
输入
输出模式串在目标事中出现的位置，即模式串匹配到目标串时第一个字符在目标串的位置（注意从1开始描述字符开始位置）不能匹配时输出0
样例输入
appleorange orange
样例输出
6
代码
#includeusing namespace std; int main() { string target, pattern; cin >> target; cin >> pattern; int n = target.length(), m = pattern.length(); for (int i = 0; i <= n - m; i++) { int j; for (j = 0; j < m; j++) { if (target[i+j] != pattern[j]) break; } if (j == m) { cout << i+1 << endl; return 0; } } cout << 0 << endl; return 0; }
3主对角线上的数据和
代码
#includeusing namespace std; const int MAXN = 100; int a[MAXN][MAXN]; int main() { int n; int cnt = 0; cin >> n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> a[i][j]; if (i == j) { cnt += a[i][j]; } } } cout << cnt; return 0; }
4顺时针排螺旋阵
代码
#includeusing namespace std; const int MAXN = 15; int a[MAXN][MAXN]; // 存放螺旋矩阵 void Spiral(int x, int y, int start, int n) // 递归创建螺旋矩阵 { if (n <= 0) return; // 递归结束条件 if (n == 1) // 矩阵大小为1时 { a[x][y] = start; return; } for (int j = x; j < x + n - 1; j++) // 上一行 { a[y][j] = start; start++; } for (int i = y; i < y + n - 1; i++) // 右一列 { a[i][x + n - 1] = start; start++; } for (int j = x + n - 1; j > x; j--) // 下一行 { a[y + n - 1][j] = start; start += 1; } for (int i = y + n - 1; i > y; i--) // 左一列 { a[i][x] = start; start++; } Spiral(x + 1, y + 1, start, n - 2); // 递归调用 } int main() { int n = 5; Spiral(0, 0, 1, n); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) printf("%3d", a[i][j]); printf("\n"); } return 0; }
5汉诺塔游戏中的移动
代码
#includeconst int MaxSize=100; //递归求解Hanoi问题 void Hanoi1(int n,char x,char y,char z) { if (n==1) cout << " 将第" << n << "个圆盘从" << x << "移动到" << z << endl; else { Hanoi1(n-1,x,z,y); cout << " 将第" << n << "个圆盘从" << x << "移动到" << z << endl; Hanoi1(n-1,y,x,z); } } //非递归求解Hanoi问题 struct SType //顺序栈中元素类型 { int n; char x,y,z; bool flag; //可直接移动时为true,否则为false }; class Stack //顺序栈类 { SType *data; //存放栈中元素 int top; //栈顶指针 public: Stack() //构造函数 { data=new SType[MaxSize]; //分配空间 top=-1; } ~Stack() //析构函数 { delete [] data; //释放空间 } bool StackEmpty() //判栈空否 { return(top==-1); } void Push(int n1,char x1,char y1,char z1,bool flag1) //进栈 { top++; data[top].n=n1; data[top].x=x1; data[top].y=y1; data[top].z=z1; data[top].flag=flag1; } void Pop(int &n1,char &x1,char &y1,char &z1,bool &flag1) //退栈 { n1=data[top].n; x1=data[top].x; y1=data[top].y; z1=data[top].z; flag1=data[top].flag; top--; } void GetTop(int &n1,char &x1,char &y1,char &z1,bool &flag1) //取栈顶元素 { n1=data[top].n; x1=data[top].x; y1=data[top].y; z1=data[top].z; flag1=data[top].flag; } }; void Hanoi2(int n, char x, char y, char z) { Stack st; //建立一个顺序栈 int n1; char x1,y1,z1; bool flag1; if (n<=0) return; //参数错误返回 else if (n==1) //只有一个圆盘的情况 cout << " 将第" << n << "个圆盘从" << x << "移动到" << z << endl; else { st.Push(n,x,y,z,false); //初值(n,x,y,z,false)进栈 while (!st.StackEmpty()) //栈不空循环 { st.GetTop(n1,x1,y1,z1,flag1); //取栈顶元素(n1,x1,y1,z1,flag1) if (flag1==false && n1>1) //当不能直接移时 { st.Pop(n1,x1,y1,z1,flag1); //退栈 if (n1-1==1) //只有一个盘片时可直接移动 st.Push(n1-1,y1,x1,z1,true); //将(n1-1,y1,x1,z1,true)进栈 else st.Push(n1-1,y1,x1,z1,false); //将(n1-1,y1,x1,z1,false)进栈 st.Push(n1,x1,y1,z1,true); //将第n1个圆盘从x1移到z1 if (n1-1==1) //再将(n1-1,x1,z1,y1)进栈 st.Push(n1-1,x1,z1,y1,true); else st.Push(n1-1,x1,z1,y1,false); } else if (flag1==true) //当可以直接移动时 { cout << " 将第" << n1 << "个圆盘从" << x1 << "移动到" << z1 << endl; st.Pop(n1,x1,y1,z1,flag1); //移动盘片后退栈 } } } } void main() { cout << "n=3的Hanoi问题递归求解如下:\n"; Hanoi1(3,'A','B','C'); cout << "n=3的Hanoi问题非递归求解如下:\n"; Hanoi2(3,'A','B','C'); }
6树的先根遍历
代码
#include#include #include #include const int MAXN = 26; std::vector tree[MAXN]; void preorder(int root) { std::stack s; s.push(root); while (!s.empty()) { int node = s.top(); s.pop(); std::cout << static_cast (node + 'A') << " "; for (int i = tree[node].size() - 1; i >= 0; i--) { s.push(tree[node][i]); } } } int main() { std::string str; while (std::getline(std::cin, str)) { std::istringstream iss(str); char parent, child; iss >> parent >> child; tree[parent - 'A'].push_back(child - 'A'); } preorder(0); return 0; }
7t树的后根遍历
代码
#include#include const int MAXN = 26; std::vector tree[MAXN]; bool visited[MAXN] = {false}; void postorder(char root) { visited[root - 'A'] = true; for (int i = 0; i < tree[root - 'A'].size(); i++) { char child = tree[root - 'A'][i] + 'A'; if (!visited[child - 'A']) { postorder(child); } } std::cout << root << " "; } int main() { char parent, child; while (std::cin >> parent >> child) { tree[parent - 'A'].push_back(child - 'A'); } postorder('A'); std::cout << std::endl; return 0; }