真题集P115---2015年真题

• 第一题
• • 思路
  • 代码
• 第三题
• • 注
  • 思路
  • 代码
  • • 力扣版本
    • 吉大真题版本
• 第六题第一问

第一题

思路

注意scanf输入字符串写法

	char item[100];//用char输入保存字符串写法scanf("%s", item);

代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
void function_one() {char item[100];//用char输入保存字符串写法scanf("%s", item);int ans[200] = {};int i = 0;while (item[i] != '\0') {if (item[i] >= 'a'&&item[i] <= 'z') {ans[item[i]]++;}i++;//千万别忘了加}for (int i = 'a'; i <= 'z'; i++) {cout << ans[i] << ' ';}return;
}

第三题

注

本题思路同力扣54. 螺旋矩阵，只是最终结果略有不同

思路

抓住这个大思路：

1、每次都是按照<1><2><3><4>顺序遍历的，走完一轮就相当于外圈没了，重新按照这个顺序走小圈
2、u每次向下走(++),d每次向上走(–)，l每次向右走(++),r每次向左走(–)
3、只要 u > d || l > r 都发生了边界交错，说明完毕，退出循环，程序结束
4、因为只要边界一动，就可能造成出现推出情况，所以每次边界动完了必须判断退不退出

<1>绿色为u:上边界，每次从l到r，u++，看是否大于d
<2>红色为r:右边界，每次从u到d，r–，看是否小于l
<3>紫色为d:下边界，每次从r到l，d–，看是否小于u
<4>黄色为l:左边界，每次从d到u，l++，看是否大于l

代码

力扣版本

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
class Solution {
public:vector spiralOrder(vector>& matrix) {vector ans;int u = 0;//上边界int d = matrix.size() - 1;//下边界int l = 0;//左边界int r = matrix[0].size() - 1;//右边界while (true) {//(上下边界交错) || (左右边界交错) 出错退出//整体顺序:上边界(从左到右)，右边界(从上到下)，下边界(从右到左)，左边界(从下到上)//上边界(从左到右)for (int i = l; i <= r; i++) {ans.push_back(matrix[u][i]);}if (++u > d) {break;}//右边界(从上到下)for (int i = u; i <= d; i++) {ans.push_back(matrix[i][r]);}if (--r < l) {break;}//下边界(从右到左)for (int i = r; i >= l; i--) {ans.push_back(matrix[d][i]);}if (--d < u) {break;}//左边界(从下到上)for (int i = d; i >= u; i--) {ans.push_back(matrix[i][l]);}if (++l > r) {break;}}return ans;}
};

吉大真题版本

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
int ans[10][10] = {};
void function_three(int n, int m) {//nxm矩阵int u = 0;int d = n - 1;int l = 0;int r = m - 1;int num = 1;//这里有变化，就是把原来的加入答案数组，变成了往目标数组的特定位置赋值while (true) {for (int i = l; i <= r; i++) {ans[u][i] = num++;}if (++u > d) {break;}for (int i = u; i <= d; i++) {ans[i][r] = num++;}if (--r < l) {break;}for (int i = r; i >= l; i--) {ans[d][i] = num++;}if (--d < u) {break;}for (int i = d; i >= u; i--) {ans[i][l] = num++;}if (++l > r) {break;}}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cout << ans[i][j] << ' ';}cout << endl;}
}

第六题第一问

详见我的博客：
第五章–二叉树板子-第八部分，判断无向图是否是树