这几道题的技巧性比较强,需要大家静下心来思考和理解
6. 转移0元素
题目编号:Exp04-Basic05,GJBook3-06-06
题目名称:转移0元素
题目描述:编写程序,不使用其他辅助数组,把给定整型数组中所有0元素全部移到后面,且所有非0元素的顺序不变。
输入:第一行输入数组长度n(≤100),第二行依次从键盘随机输入n个整数作为数组元素值。
输出:已将所有0元素串到后面的整数数组,各元素间以一个西文空格间隔,最后一个元素后无字符。
样例1:
输入: 10 0 3 1 0 0 0 1 2 3 0输出: 3 1 1 2 3 0 0 0 0 0样例2:
输入: 10 0 0 0 0 0 0 1 2 3 4输出: 1 2 3 4 0 0 0 0 0 0
#include <iostream>
using namespace std;
int main()
{
int n = 0;
int arr[100];
cin >> n;
for (int i = 0;i < n;i++)
{
cin >> arr[i];
}
int cnt = 0;
for (int i = 0;i < n;i++)
{
if (arr[i] != 0)
{
cout << arr[i] << " ";
cnt++;
}
}
for (int i = cnt;i < n;i++)
{
cout << "0 ";
}
return 0;
}
如果题目没什么特别要求的话,改变数组中元素的输出顺序比改变数组简单,下一题也是如此
7. 循环右移
题目编号 :Exp04-Basic06,GJBook3-06-04
题目名称:循环右移
题目描述:编写程序,不使用其它辅助数组,把一维整型数组中的各个元素循环右移j位。
输入:
第一行输入两个整数,n表示数组长度(0<n<=100),j表示循环右移的位数(j>=0);
第二行依次从键盘随机输入n个整数作为数组元素值。
输出:
循环右移后的整数数组,各元素间以一个西文空格间隔,最后一个元素后无字符。
样例1:
输入: 10 2 1 2 3 4 5 6 7 8 9 0输出: 9 0 1 2 3 4 5 6 7 8样例2:
输入: 10 23 1 2 3 4 5 6 7 8 9 0输出: 8 9 0 1 2 3 4 5 6 7
第一种比较简单的方法,同上一题改变输出
#include <iostream>
using namespace std;
int main()
{
int n, m, * a;
cin >> n >> m;
a = new int[n];
for (int i = 0;i < n;i++)
{
cin >> a[i];
}
if (m > n)
{
m = m % n;
}
for (int i = n - m;i < n;i++)
{
cout << a[i] << " ";
}
for (int i = 0;i < n - m;i++)
{
cout << a[i] << " ";
}
return 0;
}
第二种方法是改变数组,把代码放在下面供大家参考
#include <iostream>
#include <vector>
using namespace std;
vector<int> a;
int main()
{
int n, m, x;
cin >> n >> m;
if (m > n)
m = m % n;
int cnt = n;
while (n > 0)//输入数组
{
cin >> x;
a.push_back(x);
n--;
}
for (int i = 0;i < m;i++)
{
int tmp = a[cnt - 1];//暂时储存vector中的最后一个元素
a.erase(a.end()-1);//将其删除
a.insert(a.begin(),tmp);//把原来vector中的最后一个元素插入到vector的开头
}
for (vector<int>::iterator it = a.begin();it != a.end();it++)//打印排序后的数组
{
cout << *it << " ";
}
return 0;
}
8. 括号匹配
题目编号:Exp04-Basic01,GJBook3例-06-13
题目名称:括号匹配
题目描述:编写程序,从终端读入以‘@’为结束符的字符序列,检查该字符序列中的 ( 与 )、 [ 与 ] 、{ 与 } 是否匹配(个数相等且位置不相交)。
输入:包含一串以‘@’为结束符的字符串,其间可能包含空白或其它非括号字符。
输出:如果字符串中三类括号匹配,则输出YES;否则输出NO。
样例1:
输入:
{a,a}b{c[cc]c} {a(bb[cc]dd)a}@输出: YES样例2:
输入: {a,a}b{c[cc]c] {a(bb[cc]dd)a}@输出: NO
#include <iostream>
#include <vector>
using namespace std;
vector<char> a;
int main()
{
char ch;
cin >> ch;
int cnt = 0;
while (ch != '@')
{
switch (ch)
{
case '(':a.push_back('(');break;
case '[':a.push_back('[');break;
case '{':a.push_back('{');break;
case ')':
{
if (a.back() == '(')
a.pop_back();//删除vector的最后一个元素
break;
}
case ']':
{
if (a.back() == '[')
a.pop_back();
break;
}
case '}':
{
if (a.back() == '{')
a.pop_back();
break;
}
}
cin >> ch;
}
cnt = a.size();
if (cnt == 0)
{
cout << "YES" << endl;
}
else
{
cout << "NO" << endl;
}
return 0;
}
熟悉的while循环和vector又来了,为我们提供了非常好的解题思路
此题的难点就是检查括号相等且不相交
输入一段以'@'结尾的字符串,遇到左括号时压入vector ,遇到右括号时判断是否与前面的左括号匹配,若匹配,则将对应的左括号删掉,随后继续读下一个字符
最后,若a.size()==0,则说明括号匹配,否则不匹配
9. 检验矩阵重复元素
题目编号:Exp04-Basic07,GJBook3-06-01
题目名称:检验矩阵重复元素
题目描述:编写程序判断任意给定n*n的两维整型数组中是否有相同元素。
输入:第一行输入数组行数n(≤10),第二行随机输入n*n个整数作为数组元素值。
输出:如果数组中有相同元素,则输出YES;否则,输出NO。
样例1:
输入: 3 1 2 3 4 5 6 7 8 9输出: NO样例2:
输入: 3 1 1 2 3 4 5 6 7 8输出: YES
#include <iostream>
using namespace std;
int main()
{
int n, * a;
cin >> n;
a = new int[n * n];
for (int i = 0;i < n * n;i++)
{
cin >> a[i];
}
int flag = 0;
for (int i = 0;i < n * n - 1;i++)
{
for (int j = i + 1;j < n * n;j++)
{
if (a[i] == a[j])
flag = 1;
}
}
if (flag == 1)cout << "YES" << endl;
else cout << "NO" << endl;
return 0;
}
判断重复的核心就在于中间的两个for循环嵌套,这种排序方式能保证在比较元素中不重不漏,不能只写一个for循环,否则容易漏掉某些元素之间的比较
10. 螺旋矩阵
题目编号:Exp04-Enhance05,freshman-1050,GJBook3-0622
题目名称:螺旋矩阵
题目描述:
螺旋矩阵指一个呈螺旋状的数字矩阵,它的数字由第一行开始到右边不断变大,向下变大,向左变大,向上变大,如此循环。如下所示为3阶螺旋矩阵。
输入:输入一个正整数 N (N<=30),标明矩阵阶数。
输出:按螺旋矩阵形式输出整数 1~N^2, 共 N 行N 列,每个数字输出占4个西文字符宽度,右对齐,最后一个数字后无多余字符。
样例:
输入: 15输出:
终于见到了终极大Boss,螺旋矩阵,据说很多大厂都爱考这个题,
主要解题思路有两个,
一是数组法:寻找每个递增元素的下标关系,利用循环输出
二是递归法:本题给出的是N*N阶方阵,所以用递归法也比较容易思考到
最终要归结到合理判断a[i][j]的元素
鉴于学校现在可能还没讲到递归算法,在此主要讲解数组法
1.首先要考虑到N为奇数或者N为偶数时候的情况
a00 | a01 | a03 | a04 | a05 |
a10 |
a11 | a12 | a13 | a14 |
a20 | a21 | a22 | a23 | a24 |
a30 | a31 | a32 | a33 | a34 |
a40 | a41 | a42 | a43 | a44 |
输出思路是,先输出外面的 N/2 层,再把中间的a[N/2][N/2]输出
a00 | a01 | a03 | a04 |
a10 |
a11 | a12 | a13 |
a20 | a21 | a22 | a23 |
a30 | a31 | a32 | a33 |
当N为偶数时就比较简单了,直接输出 N/2 层循环
2.观察两个表格上面颜色相同的元素,来确定每一个元素的输出顺序
每一层输出应写成四个循环,每一个循环输出N-1个元素,由外向内,依次输出
int k = 1;
for (i = 0;i < n / 2;i++)//判断循环层数
{
for (j = i;j < n - i - 1;j++)//上
a[i][j] = k++;
for (j = i;j < n - i - 1;j++)//右
a[j][n - i - 1] = k++;
for (j = n - i - 1;j > i;j--)//下
a[n - i - 1][j] = k++;
for (j = n - i - 1;j > i;j--)//左
a[j][i] = k++;
}
if (n % 2 == 1)//N为奇数时单独给中间剩下的元素赋值
a[n / 2][n / 2] = k;
最终的代码放在下边
#include <iostream>
#include <iomanip>
using namespace std;
int main()
{
//n阶螺旋矩阵
int n, m;
int i, k, j;
cin >> n;
int** a = new int* [n];
for (int i = 0;i < n;i++)
a[i] = new int[n];
k = 1;
for (i = 0;i < n / 2;i++)
{
for (j = i;j < n - i - 1;j++)
a[i][j] = k++;
for (j = i;j < n - i - 1;j++)
a[j][n - i - 1] = k++;
for (j = n - i - 1;j > i;j--)
a[n - i - 1][j] = k++;
for (j = n - i - 1;j > i;j--)
a[j][i] = k++;
}
if (n % 2 == 1)
a[n / 2][n / 2] = k;
for (int i = 0;i < n;i++)
{
for (int j = 0;j < n;j++)
{
cout << setfill(' ') << setw(4) << a[i][j];
}
cout << endl;
}
return 0;
}
最后别忘了用iomanip头文件来完成题目要求的输出格式
cout << setfill(' ') << setw(4) << a[i][j];//设置宽度为4,用空格补齐