习题6-7 简单计算器

模拟简单运算器的工作。假设计算器只能进行加减乘除运算，运算数和结果都是整数，四种运算符的优先级相同，按从左到右的顺序计算。
输入格式:
输入在一行中给出一个四则运算算式，没有空格，且至少有一个操作数。遇等号”=”说明输入结束。
输出格式:
在一行中输出算式的运算结果，或者如果除法分母为0或有非法运算符，则输出错误信息“ERROR”。
输入样例:

1+2*10-10/2=

输出样例:

10

解题思路：其实本例无优先级，就是找到这样的一个数：“操作符+操作数”，将所有表达式变成 1 +2 *10 -10 /2 然后将所有串联起来分别与前一个进行操作，因此需要人为在开头设置一个数字，即 0 作为火车头，累计求和即可。

1. 开头处理：由于本题可能开头是负数和正数，正数不带 + ，而负数带 -，为了统一处理，假设开头都是 + ，因此上述过程变为： +1 +2 *10 -10 /2
2. 关键问题就是如何知道一个组合结束，因此遇到第二个操作符就代表前一个结束，那么此时就可将前一个和 sum 进行操作并把结果保存在 sum 中，最后有一个尾巴问题。就是可能最后一个数后面没有操作符，一般就是单独最后处理（本例恰好存在 = 而方便处理）

   #include <stdio.h>
   int main () {
    char ch = getchar(), sign = '+';
    int num = 0, sum = 0;
    while ('\n' != ch) {  // '='
        if ('0' <= ch && ch <= '9') {
            num = num * 10 + (ch - '0');
        } else {  // 遇到第二个操作符
            switch (sign) {
                case '+':
                    sum += num;
                    break;
                case '-':
                    sum += -num;
                    break;
                case '*':
                    sum *= num;
                    break;
                case '/':
                    if (0 == num) {
                        printf("ERROR\n");
                        return 0;
                    }
                    sum /= num;
                    break;
                default:
                    printf("ERROR\n");
                    return 0;
            }
            sign = ch;
            num = 0;
        }
        ch = getchar();
    }
    printf("%d\n", sum);
    return 0;
   }

   运行结果：

习题6-8 统计一行文本的单词个数

本题目要求编写程序统计一行字符中单词的个数。所谓“单词”是指连续不含空格的字符串，各单词之间用空格分隔，空格数可以是多个。
输入格式:
输入给出一行字符。
输出格式:
在一行中输出单词个数。
输入样例:

Let's go to room 209.

输出样例:

5

解题思路：

1. IO输入：首先有空格的字符串需要使用正则 scanf 或者 gets （ fgets() 会把末尾的 \n 也带入！）收取
2. 每个单词是以空格作为分割，但是可能不是标注的单个空格分隔，可能含有很多很多，但都不影响我们判断，只要找到一个空格+非空格开始就是新单词开始；但是如果跳过在单词中的遍历，即需要将空格消除，（空格+非单词开始 = 一个单词）

   #include <stdio.h>
   #define MAXSIZE 1000
   int main () {
    char str[MAXSIZE];
    scanf("%[^\n]s", str);
    int words = 0, space = 1;  // 假设第一个就是空格
    for (int i = 0; '\0' != str[i]; i++) {
        if (' ' != str[i]) {
            if (1 == space) {  // 遇到非空格且之前有空格
                words++;
                space = 0;
            }
        } else {
            space = 1;
        }
    }
    printf("%d\n", words);
    return 0;
   }

   运行结果：

练习7-2 求最大值及其下标

本题要求编写程序，找出给定的n个数中的最大值及其对应的最小下标（下标从0开始）。
输入格式:
输入在第一行中给出一个正整数n（）。第二行输入n个整数，用空格分开。
输出格式:
在一行中输出最大值及最大值的最小下标，中间用一个空格分开。
输入样例:

6
2 8 10 1 9 10

输出样例:

10 2

解题思路：本题可以使用数组或者直接循环解决；使用循环需要先找到一个基准，可是第一个输入元素或者自定义一个非常小的数（哨兵）开始比较。

#include <stdio.h>
#include <limits.h>
int main () {
    int n, x, max = INT_MIN, idx = -1;
    scanf("%d", &n);
    for (int i = 0;i < n; i++) {
        scanf("%d", &x);
        if (x > max) {
            max = x;
            idx = i;
        }
    }
    printf("%d %d\n", max, idx);
    return 0;
}

运行结果：

练习7-3 将数组中的数逆序存放

本题要求编写程序，将给定的n个整数存入数组中，将数组中的这n个数逆序存放，再按顺序输出数组中的元素。
输入格式:
输入在第一行中给出一个正整数n（1≤n≤10）。第二行输入n个整数，用空格分开。
输出格式:
在一行中输出这n个整数的处理结果，相邻数字中间用一个空格分开，行末不得有多余空格。
输入样例:

4
10 8 1 2

输出样例:

2 1 8 10

解题思路：本题直接使用递归（回溯）比使用数组方便，但是比较难理解，尤其是边界的处理（对应于格式化输出标准空格间隔）

// 1.递归处理
#include <stdio.h>
void reverse(int n) {
    int x;
    scanf("%d", &x);
    if (1 == n) {    // 递归终止，开始退栈
        printf("%d", x);
        return;
    }
    reverse(n - 1);
    printf("%d ", x);  // 开始打印第二个
}
int main () {
    int n;
    scanf("%d", &n);
    reverse(n);
    return 0;
}
// 2.逆序填入数组元素+最后一个单独处理
#include <stdio.h>
#define N 10
int main () {
    int arr[N], n;
    scanf("%d", &n);
    // 1.倒着填入数组
    for (int i = n - 1; i >= 0; i--) {
        scanf("%d", arr + i);
    }
    // 2.以"%d "输出前 n-1 个数字
    for (int i = 0; i < n - 1; i++) {
        printf("%d ", arr[i]);
    }
    // 3.最后单独输出 arr[n-1]
    printf("%d\n", arr[n-1]);
    return 0;
}
// 3.顺序填入数组元素+翻转处理+第一个单独处理
#include <stdio.h>
#define N 10
int main () {
    int arr[N], n;
    scanf("%d", &n);
    // 1.倒着填入数组
    for (int i = 0; i < n; i++) {
        scanf("%d", arr + i);
    }
    // 2.翻转数组
    for (int left = 0, right = n - 1; left < right; left++, right--) {
        int tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;
    }
    // 3.先输出 arr[0]
    printf("%d", arr[0]);
    // 3.以" %d"输出前 n-1 个数字
    for (int i = 1; i < n; i++) {
        printf(" %d", arr[i]);
    }
    return 0;
}

运行结果：

练习7-4 找出不是两个数组共有的元素

给定两个整型数组，本题要求找出不是两者共有的元素。
输入格式:
输入分别在两行中给出两个整型数组，每行先给出正整数N（≤20），随后是N个整数，其间以空格分隔。
输出格式:
在一行中按照数字给出的顺序输出不是两数组共有的元素，数字间以空格分隔，但行末不得有多余的空格。题目保证至少存在一个这样的数字。同一数字不重复输出。
输入样例:

10 3 -5 2 8 0 3 5 -15 9 100
11 6 4 8 2 6 -5 9 0 100 8 1

输出样例:

3 5 -15 6 4 1

解题思路：其实本题就是让求两个集合：，即两个集合的并集减去两者交集的元素。

>>> b
[6, 4, 8, 2, 6, -5, 9, 0, 100, 8, 1]
>>> a
[3, -5, 2, 8, 0, 3, 5, -15, 9, 100]
>>> set(b).symmetric_difference(set(a))
{1, 3, 5, 4, 6, -15}

没有 set 类型，数组进行手动暴力模拟。先算出 放入数组 ，然后再算 放入数组 ，最后就是最傻逼的去重操作，判题机器只认它的结果，也就是出现重复数字，要求按相对顺序输出第一个数字，而不是最后一个！ [3, 2, 3] 输出应该是 3 2 而不是 2 3 。

#include <stdio.h>
#define N 21
void symmetry_different(int *arr1, int idx1, int *arr2, int idx2, int *arr3, int *idx3) {
    for (int i = 0; i < idx1; i++) {
        int flag = 0;
        for (int j = 0; j < idx2; j++) {
            if (arr1[i] == arr2[j]) {
                flag = 1;
                break;
            }
        }
        if (0 == flag) {
            arr3[idx3[0]++] = arr1[i];
        }
    }
}
int main () {
    int arr1[N], arr2[N], arr3[N + N];
    int idx1, idx2, idx3 = 0;
    scanf("%d", &idx1);
    for (int i = 0; i < idx1; i++) {
        scanf("%d", arr1 + i);
    }
    scanf("%d", &idx2);
    for (int i = 0; i < idx2; i++) {
        scanf("%d", arr2 + i);
    }
    symmetry_different(arr1, idx1, arr2, idx2, arr3, &idx3);
    symmetry_different(arr2, idx2, arr1, idx1, arr3, &idx3);
    /* 向后看！即输出重复的最后一个
    for (int i = 0, cnt = 0; i < idx3; i++) {
        int j = i + 1;
        for (; j < idx3; j++) {
            if (arr3[i] == arr3[j]) {
                break;
            }
        }
        if (j >= idx3) {
            if (0 == cnt) {
                printf("%d", arr3[i]);  // 输出第一个
                cnt = 1;
            } else {
                printf(" %d", arr3[i]);
            }
        }
    }
    */
    // 向前看，才可AC
    printf("%d", arr3[0]);  // 输出第一个
    for (int i = 1, cnt = 0; i < idx3; i++) {
        int j = 0;
        for (; j < i; j++) {
            if (arr3[i] == arr3[j]) {
                break;
            }
        }
        if (j == i) {
            printf(" %d", arr3[i]);
        }
    }
    return 0;
}

运行结果：

| 3 ms | 296 KB | | 1 | 最大N，只有1个数字不同 | Accepted

| 3 ms | 384 KB | | 2 | 最小N，全不同 | Accepted

| 2 ms | 296 KB | | 3 | 输出中有0 | Accepted

| 2 ms | 256 KB |

350.两个数的交集2(简单)

练习7-7 矩阵运算

给定一个n×n的方阵，本题要求计算该矩阵除副对角线、最后一列和最后一行以外的所有元素之和。副对角线为从矩阵的右上角至左下角的连线。
输入格式:
输入第一行给出正整数n（1<_n_≤10）；随后_n_行，每行给出_n_个整数，其间以空格分隔。
输出格式:
在一行中给出该矩阵除副对角线、最后一列和最后一行以外的所有元素之和。
输入样例:

4
2 3 4 1
5 6 1 1
7 1 8 1
1 1 1 1

输出样例:

35

解题思路：找到规律即可。

1. 最后一行抛弃： row != n - 1
2. 最后一列抛弃： col != n - 1
3. 副对角线抛弃：由于副对角线和主对角线是对称关系，因而很容易发现规律 row != n - 1 - col 即可排除

代码1中没有使用二维数组，直接 scanf n-1 行，由于输入数据不可能抛弃最后一列，因此在列上面读取所有数字，但是最后一列不参入计算。
代码2中使用动态数组（指向一维数组的指针），其实因为题目给定的 n 范围，可以直接使用 define MAXSIZE 10 创建静态数组。

// 1.蛮力法
#include <stdio.h>
int main () {
    int n, x;
    scanf("%d", &n);
    int sum = 0;
    for (int row = 0; row < n - 1; row++) {  // 1.除去最后一行
        for (int col = 0; col < n; col++) {
            scanf("%d", &x);
            if (n - 1 != col && row != n - 1 - col) {  // 除去最后一列 + 除去副对角线
                sum += x;
            }
        }
    }
    printf("%d\n", sum);
    return 0;
}
// 2.动态内存分配二维数组
#include <stdio.h>
#include <stdlib.h>  // malloc
int main () {
    int n, x;
    scanf("%d", &n);
    // 1.定义指向含有n个元素数组的指针
    int (*arr)[n] = (int (*)[n])malloc(sizeof(int) * n * n);
    int sum = 0;
    for (int row = 0; row < n; row++) {
        for (int col = 0; col < n; col++) {
            scanf("%d", &arr[row][col]);  // arr[row]+col
        }
    }
    // 2.筛选求和
    for (int row = 0; row < n - 1; row++) {  // 除去最后一行
        for (int col = 0; col < n - 1; col++) {  // 除去最后一列
            if (row != n - 1 - col) {  // 除去副对角线
                sum += arr[row][col];
            }
        }
    }
    printf("%d\n", sum);
    // free(arr);
    return 0;
}

运行结果：

练习7-8 方阵循环右移

本题要求编写程序，将给定n×n方阵中的每个元素循环向右移m个位置，即将第0、1、⋯、n−1列变换为第n−m、n−m+1、⋯、n−1、0、1、⋯、n−m−1列。
输入格式：
输入第一行给出两个正整数m和n（1≤n≤6）。接下来一共n行，每行n个整数，表示一个n阶的方阵。
输出格式：
按照输入格式输出移动后的方阵：即输出n行，每行n个整数，每个整数后输出一个空格。
输入样例：

2 3
1 2 3
4 5 6
7 8 9

输出样例：

2 3 1 
5 6 4 
8 9 7

解题思路：本题就是数组循环右移的变形，只不过是二维数组而已，同样的道理，以列作为数组元素处理即可，非常实现上就多了内层多个元素的交换操作，没有本质变化。

#include <stdio.h>
#define MAXSIZE 6

void reverse(int matrix[][MAXSIZE], int n, int left, int right) {
    for (; left < right; left++, right--) {
        for (int row = 0; row < n; row++) {
            int tmp = matrix[row][left];
            matrix[row][left] = matrix[row][right];
            matrix[row][right] = tmp;
        }
    }
}

int main () {
    int m, n, matrix[MAXSIZE][MAXSIZE];
    // 1.IO
    scanf("%d %d", &m, &n);
    m %= n;  // 注意要取模，否则爆炸移动！非法访问
    for (int row = 0; row < n; row++) {
        for (int col = 0; col < n; col++) {
            scanf("%d", &matrix[row][col]);
        }
    }
    // 2.以一列当作一个数组元素，向右移动 m 次
    reverse(matrix, n, 0, n - 1);  // (1) 整体翻转
    reverse(matrix, n, 0, m - 1);  // (2) 翻转 [0:m)
    reverse(matrix, n, m, n - 1);  // (3) 翻转 [m:n) 
    // 3.打印输出
    for (int row = 0; row < n; row++) {
        for (int col = 0; col < n; col++) {
            printf("%d ", matrix[row][col]);
        }
        printf("\n");
    }
    return 0;
}

运行结果：

练习7-9 计算天数

本题要求编写程序计算某年某月某日是该年中的第几天。
输入格式:
输入在一行中按照格式“yyyy/mm/dd”（即“年/月/日”）给出日期。注意：闰年的判别条件是该年年份能被4整除但不能被100整除、或者能被400整除。闰年的2月有29天。
输出格式:
在一行输出日期是该年中的第几天。
输入样例1:

2009/03/02

输出样例1:

61

输入样例2:

2000/03/02

输出样例2:

62

解题思路：本题主要是 IO 问题，可以使用字符串或者不使用直接开干；关键点就是判断闰年给 2 月份多算一天即可。

#include <stdio.h>
int Months[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int main () {
    int year, month, day;
    scanf("%d", &year);
    getchar();  // 吸收'/'
    scanf("%d", &month);
    getchar();  // 吸收'/'
    scanf("%d", &day);
    if ((0 == year % 4 && 0 != year % 100) || 0 == year % 400) {
        Months[2] += 1;
    }
    for (int i = 1; i < month; i++) {  // 取整个月
        day    += Months[i];
    }
    printf("%d\n", day);
    return 0;
}

运行结果：

练习7-10 查找指定字符

本题要求编写程序，从给定字符串中查找某指定的字符。
输入格式：
输入的第一行是一个待查找的字符。第二行是一个以回车结束的非空字符串（不超过80个字符）。
输出格式：
如果找到，在一行内按照格式“index = 下标”输出该字符在字符串中所对应的最大下标（下标从0开始）；否则输出”Not Found”。
输入样例1：

m
programming

输出样例1：

index = 7

输入样例2：

a
1234

输出样例2：

Not Found

解题思路：

1. 先输入 target 字符，注意要进行后面的 \n 吸收，否则错误。
2. 将字符串输入到字符数组中，由于存在空格，用正则表达式或者 gets(s) 函数解决。（其实可以不用进行数组存储，直接 while ((c = getchar()) != '\n') 判断即可）
3. 使用 idx = -1 假设先没有找到，如果找到相同的不断向后更新就是最大的。最后根据判断 -1 == idx 判断是否找到而得到结果。 ```c

   include

   define N 81

int main () { char s[N], target; scanf(“%c”, &target); getchar(); // 吸收换行 / getchar 循环读入 int idx = -1, i = 0; do { c = getchar(); if (c == target) { // 向右更新到最大值 idx = i; } i++; } while (c != ‘\n’); / scanf(“%[^\n]s”, s); // 字符串中有空格！ int idx = -1; for (int i = 0; s[i] != ‘\0’; i++) { if (s[i] == target) { // 向右更新到最大值 idx = i; } } if (-1 != idx) { printf(“index = %d”, idx); } else { printf(“Not Found”); } return 0; }

运行结果：

| Case | Hint | Result | Run Time | Memory |
| --- | --- | --- | --- | --- |
| 0 | sample1等价，不唯一，输出最大的下标 | Accepted

 | 3 ms | 296 KB |
| 1 | sample2, not found | Accepted

 | 2 ms | 296 KB |
| 2 | index = 0 | Accepted

 | 2 ms | 268 KB |
| 3 | index = max，字符串中有空格 | Accepted

 | 3 ms | 352 KB |
| 4 | 最小字符串 | Accepted

 | 2 ms | 380 KB |

<a name="GowN3"></a>
# [练习7-11 字符串逆序](https://pintia.cn/problem-sets/12/problems/323)
输入一个字符串，对该字符串进行逆序，输出逆序后的字符串。<br />**输入格式：**<br />输入在一行中给出一个不超过80个字符长度的、以回车结束的非空字符串。<br />**输出格式：**<br />在一行中输出逆序后的字符串。<br />**输入样例：**

Hello World!

**输出样例：**

!dlroW olleH

解题思路：

1. 输入字符串入数组：需要注意 `scanf("%s", s)` 是不能把含有空格的字符串整个读入，其会出现只读前部分。因为其设计就是遇到空白符就结束读取并在末尾添加上一个 `\0` ，但是不保证溢出！因此程序员必须直到预定字符串输入大小，且用正则表达式使其能够读取 `' '` 同时以 `\n` 作为结束符（此时的 `\n` 是否还留在缓冲区？）
1. 前后对转即可。即前后指针相向运动，当 `left < right` 成立就进行调换。
```c
#include <stdio.h>
#include <string.h>
#define N 81

int main () {
    char s[N];
    scanf("%[^\n]s", s);  // 读取空格
    for (int left = 0, right = strlen(s) - 1; left < right; left++, right--) {
        char tmp = s[left];
        s[left] = s[right];
        s[right] = tmp;
    }
    printf("%s", s);
    return 0;
}

运行结果：

| 4 ms | 256 KB | | 1 | 最短串 | Accepted

| 3 ms | 256 KB | | 2 | 最长串 | Accepted

| 2 ms | 256 KB |

习题7-1 选择法排序

本题要求将给定的n个整数从大到小排序后输出。
输入格式：
输入第一行给出一个不超过10的正整数n。第二行给出n个整数，其间以空格分隔。
输出格式：
在一行中输出从大到小有序的数列，相邻数字间有一个空格，行末不得有多余空格。
输入样例：

4
5 1 7 6

输出样例：

7 6 5 1

解题思路：

1. 输入数据入数组中存储。 1. 选择排序要挨个选出最大值共比较 n-1 趟，一趟中在剩余的淘汰局选最大值需要进行 n - i 次比较。但是为边排序边输出，即找到一个最大值就输出，那么可以改为走 n 趟或者单独在最后输出最后一个数字补上。 1. 格式化输出问题：第一次单独处理输出 printf("%d", nums[i]); ，其后输出数字前多加一个空格： printf(" %d", nums[i]);

#include <stdio.h>
#define N 11
int main () {
    int nums[N], n;
    // 1.输入数据
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", nums + i);
    }
    // 2.边逆向排序边输出
    for (int i = 0; i < n; i++) {  // 实际比较次数是 n-1，但为输出所有设置为 n
        int idx = i;  // 假设第 i 位是最大值，下面从 i+1 -> n 名选手中打出最大值来
        for (int j = i + 1; j < n; j++) {
            if (nums[j] > nums[idx]) {
                idx = j;
            }
        }
        // 看是否次数要进行交换？即保证此时 nums[i] 是最大的
        if (i != idx) {
            int tmp = nums[i];
            nums[i] = nums[idx];
            nums[idx] = tmp;
        }
        if (0 != i) {
            printf(" %d", nums[i]);
        } else {
            printf("%d", nums[i]);
        }
    }
    return 0;
}

运行结果：

| 7 ms | 268 KB | | 1 | 最大n，逆序，有负数 | Accepted

| 4 ms | 256 KB | | 2 | 最大n，顺序，有重复数 | Accepted

| 4 ms | 256 KB | | 3 | 最小n | Accepted

| 4 ms | 256 KB |

习题7-2 求一批整数中出现最多的个位数字

给定一批整数，分析每个整数的每一位数字，求出现次数最多的个位数字。例如给定3个整数1234、2345、3456，其中出现最多次数的数字是3和4，均出现了3次。
输入格式：
输入在第1行中给出正整数N（≤1000），在第二行中给出N个不超过整型范围的非负整数，数字间以空格分隔。
输出格式：
在一行中按格式“M: n1 n2 …”输出，其中M是最大次数，n1、n2、……为出现次数最多的个位数字，按从小到大的顺序排列。数字间以空格分隔，但末尾不得有多余空格。
输入样例：

3
1234 2345 3456

输出样例：

3: 3 4

解题思路：

1. 需要进行输入，在第一行输入整数后需要吸收回车吗？答案是无需！因为 %d 会自动跳过所有的非数字直到最后。
2. 整数拆分：此处 do-while 虽然输入测试用例不存在 0 这个用例，可以使用 while 进行。同时使用 cnt[10] 计数器进行统计每个数位的个数，在这个过程中也同时进行位数出现最大次数的统计 max 的更新。
3. 遍历计数器，将等于 cnt[i] = max 的 i 值进行输出。依然是格式问题，首先单独处理第一个输出即可不会在最后残留空格问题 。 ```c

   include

   define N 1001

   int arr[N]; int cnt[10]; // 计数器

int main () { int n; scanf(“%d”, &n); // getchar(); // 吸收空格 int max = 0; // 1.IO拆分数字+计数最大值统计 for (int i = 0; i < n; i++) { scanf(“%d”, arr + i); int x = arr[i]; do { int remainder = x % 10; cnt[remainder]++; max = max > cnt[remainder] ? max : cnt[remainder]; x /= 10; } while (x); } // 2.输出格式 printf(“%d: “, max); for (int i = 0, isFirst = 0; i < 10; i++) { if (cnt[i] == max) { if (0 == isFirst) { printf(“%d”, i); isFirst = 1; } else { printf(“ %d”, i); } } } return 0; }

**运行结果：**

| Case | Hint | Result | Run Time | Memory |
| --- | --- | --- | --- | --- |
| 0 | sample 不唯一，但有序 | Accepted

 | 2 ms | 256 KB |
| 1 | 最小N，唯一 | Accepted

 | 3 ms | 228 KB |
| 2 | 最大N，不唯一，乱序 | Accepted

 | 3 ms | 384 KB |
| 3 | 每个数字都出现1次 | Accepted

 | 3 ms | 296 KB |

<a name="n0Vpx"></a>
# [习题7-3 判断上三角矩](https://pintia.cn/problem-sets/12/problems/326)
上三角矩阵指主对角线以下的元素都为0的矩阵；主对角线为从矩阵的左上角至右下角的连线。<br />本题要求编写程序，判断一个给定的方阵是否上三角矩阵。<br />**输入格式：**<br />输入第一行给出一个正整数_T_，为待测矩阵的个数。接下来给出_T_个矩阵的信息：每个矩阵信息的第一行给出一个不超过10的正整数_n_。随后_n_行，每行给出_n_个整数，其间以空格分隔。<br />**输出格式：**<br />每个矩阵的判断结果占一行。如果输入的矩阵是上三角矩阵，输出“YES”，否则输出“NO”。<br />**输入样例：**

2 3 1 2 3 0 4 5 0 0 6 2 1 0 -8 2

**输出样例：**

YES NO

**解题思路**：处于同一主对角线上的点有  性质，而主对角线下方的点都有  的性质，因此根据输入判断当前坐标是否满足且是否都为 `0` 。
```c
#include <stdio.h>

int main () {
    int m, n, x;
    scanf("%d", &m);
    for (int i = 0; i < m; ++i) {
        scanf("%d", &n);
        int flag = 1;  // yes
        for (int r = 0; r < n; ++r) {
            for (int c = 0; c < n; ++c) {
                scanf("%d", &x);
                // 即使知道不满足，也不能 break，因为要读取完当前数据集，不然会影响下一个判断
                if (r - c > 0 && 0 != x) flag = 0;  
            }
        }
        if (flag) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

输出结果：

习题7-4 求矩阵各行元素之和

本题要求编写程序，求一个给定的m×n矩阵各行元素之和。
输入格式：
输入第一行给出两个正整数m和n（1≤m,n≤6）。随后m行，每行给出n个整数，其间
以空格分隔。
输出格式：
每行输出对应矩阵行元素之和。
输入样例：

3 2
6 3
1 -8
3 12

输出样例：

9
-7
15

解题思路：每行进行输入，对每列进行统计。

#include <stdio.h>
#define N 6
int matrix[N][N];
int main () {
    int m, n;
    scanf("%d %d", &m, &n);
    for (int row = 0; row < m; row++) {
        int sum = 0;
        for (int col = 0; col < n; col++) {
            scanf("%d", &matrix[row][col]);
            sum += matrix[row][col];
        }
        printf("%d\n", sum);
    }
    return 0;
}

运行结果：

| 2 ms | 364 KB | | 1 | m小于n | Accepted

| 2 ms | 360 KB | | 2 | 最大规模 | Accepted

| 2 ms | 368 KB | | 3 | 最小规模 | Accepted

| 2 ms | 368 KB |

习题7-5 找鞍点

一个矩阵元素的“鞍点”是指该位置上的元素值在该行上最大、在该列上最小。
本题要求编写程序，求一个给定的n阶方阵的鞍点。
输入格式：
输入第一行给出一个正整数n（1≤n≤6）。随后n行，每行给出n个整数，其间以空格分隔。
输出格式：
输出在一行中按照“行下标 列下标”（下标从0开始）的格式输出鞍点的位置。如果鞍点不存在，则输出“NONE”。题目保证给出的矩阵至多存在一个鞍点。
输入样例1：

4
1 7 4 1
4 8 3 6
1 6 1 2
0 7 8 9

输出样例1：

2 1

输入样例2：

2
1 7
4 1

输出样例2：

NONE

解题思路：

1. 暴力查找 ，对于每个元素 matrix[row][col] 向水平和垂直方向进行查找看是否满足题意。但是这会导致很多重复的比较
2. 预处理优化 ：即是说 rowMax[row] 只有一个最大值， colMin[col] 只有一个最小值，为什么不可以先求出这两个方向的最值呢？最后再判断 matrix[row][col] = rowMax[row] = colMin[col] 即可。
3. 判断有无鞍点，按题意理解，最多有 n 个（因为互斥条件，使得最多满足每行一个），最少就是没有要输出 NONE ，因此不得不使用一个 flag=0 进行标记。 ```c // 1.暴力判断

   include

   include

   include

   define N 6

int main () { int n, matrix[N][N]; // 1.输入数据 scanf(“%d”, &n); for (int row = 0; row < n; row++) { for (int col = 0; col < n; col++) { scanf(“%d”, matrix[row] + col); // &matrix[row][col] } } // 对每个元素进行扫描，暴力判断 int flag = 0; for (int row = 0; row < n; row++) { for (int col = 0; col < n; col++) { / 纯暴力：没有一丝优化 int x, y, rowMax = INT_MIN, colMin = INT_MAX; for (y = 0; y < n; y++) { rowMax = fmax(matrix[row][y], rowMax); } for (x = 0; x < n; x++) { colMin = fmin(matrix[x][col], colMin); } if (matrix[row][col] == rowMax && matrix[row][col] == colMin) { // 判断 flag = 1; // 标记存在鞍点 printf(“%d %d\n”, row, col); } / int x, y, rowMax = INT_MIN, colMin = INT_MAX; for (y = 0; y < n; y++) { rowMax = fmax(matrix[row][y], rowMax); } if (rowMax != matrix[row][col]) continue; // 小优化：跳过比较列最小值 for (x = 0; x < n; x++) { colMin = fmin(matrix[x][col], colMin); } if (matrix[row][col] == colMin) { // 能到此：肯定行满足，只需判断列 flag = 1; // 标记存在鞍点 printf(“%d %d\n”, row, col); } } } if (0 == flag) { printf(“NONE\n”); } return 0; }

// 2.预处理优化

include

define N 6

define Max(a, b) ((a > b) ? (a) : (b))

define Min(a, b) ((a > b) ? (b) : (a))

int main () { int n, matrix[N][N], rowMax[N], colMin[N]; // 1.输入数据 scanf(“%d”, &n); for (int row = 0; row < n; row++) { for (int col = 0; col < n; col++) { scanf(“%d”, matrix[row] + col); // &matrix[row][col] } } // 2.初始化行最大值为每行第一个原始，列最小值为每列第一个元素 for (int i = 0; i < n; i++) { rowMax[i] = matrix[i][0]; colMin[i] = matrix[0][i]; } // 3.进行预处理每行每列最值 for (int row = 0; row < n; row++) { for (int col = 0; col < n; col++) { rowMax[row] = Max(matrix[row][col], rowMax[row]); colMin[col] = Min(matrix[row][col], colMin[col]); } } // 4.对每个元素进行扫描，判断 matrix[row][col]=rowMax[row]=colMin[col] 成立 int flag = 0; for (int row = 0; row < n; row++) { for (int col = 0; col < n; col++) { if (matrix[row][col] == rowMax[row] && matrix[row][col] == colMin[col]) { flag = 1; // 标记存在鞍点 printf(“%d %d\n”, row, col); } } } if (0 == flag) { printf(“NONE\n”); } return 0; }

**运行结果**：

| Case | Hint | Result | Run Time | Memory |
| --- | --- | --- | --- | --- |
| 0 | sample1等价，存在鞍点 | Accepted | 3 ms | 296 KB |
| 1 | sample2等价，不存在 | Accepted | 3 ms | 256 KB |
| 2 | 最大规模，有并列极值元素，最后一个是鞍点 | Accepted | 2 ms | 256 KB |
| 3 | 最小规模 | Accepted | 3 ms | 256 KB |


<br />**错误想法**：遍历每行`row`，找到最大元素所在列`col`，然后再验证该列上`matrix[row][col]`是否是最小的。当数组中不存在重复数字时是没问题，但是若存在并列极值，那么都要把这些极值考虑入内。

| 3 | 6 | 4 | 7 |
| --- | --- | --- | --- |
| 4 | 7 | 5 | 8 |
| 6 | 4 | 7 | 6 |
| 0 | **5** | 3 | 5 |

例如如下代码中判断极值时未加等号将会在上面标红的`5`上，而这个点不是鞍点。这个问题出在寻找某行最大值时，当出现多个最大值，只会取**最左侧**为最大值所在索引，因此可能忽视其它列最大值的情况。如上表最后一个元素才是鞍点
```c
#include <stdio.h>
#include <limits.h>
#include <math.h>
#define N 6

int main () {
    int n, matrix[N][N];
    // 1.输入数据
    scanf("%d", &n);
    for (int row = 0; row < n; row++) {
        for (int col = 0; col < n; col++) {
            scanf("%d", matrix[row] + col);  // &matrix[row][col]
        }
    }
    // 对每个元素进行扫描，暴力判断
    int flag = 0;
    for (int row = 0; row < n; row++) {
        // (1) 寻找 row 行最大元素所在列
        int colIdx = 0;
        for (int col = 0; col < n; col++) {
            if (matrix[row][col] > matrix[row][colIdx]) {  // 更新最大值所在列（万一相等呢？）
                colIdx = col;
            }
        }
        // (2) 验证 matrix[row][colIdx] 是否是 colIdx 列最小值
        int rowIdx = 0;
        for (int r = 0; r < n; ++r) {
            if (matrix[r][colIdx] < matrix[rowIdx][colIdx]) {  // 更新最小值所在行（万一相等呢？）
                rowIdx = r;
            }
        }
        if (rowIdx == row) {  // 判断
            flag = 1;  // 标记存在鞍点
            printf("%d %d\n", rowIdx, colIdx);
        } else {
            flag = 0;
        }
    }
    if (0 == flag) {
        printf("NONE\n");
    }
    return 0;
}

你可能会说加上等号不就完事了，但是此时最大值所在列就是在最右侧，假设现在将上面最右侧列交换一下，那么代码依然不对。

因此最佳的解决办法就是考虑所有并列最大值的情况，也就说非要使用这个方式就不得不用数组额外记录并列最值。

习题7-6 统计大写辅音字母

英文辅音字母是除A、E、I、O、U以外的字母。本题要求编写程序，统计给定字符串中大写辅音字母的个数。
输入格式：
输入在一行中给出一个不超过80个字符、并以回车结束的字符串。
输出格式：
输出在一行中给出字符串中大写辅音字母的个数。
输入样例：

HELLO World!

输出样例：

4

解题思路：本题主要是筛选大写字母，然后再在大写字母中筛去元音字母即可得到答案。

#include <stdio.h>
int main () {
    int cnt = 0;
    char ch = getchar();
    while ('\n' != ch) {
        if ('A' <= ch && ch <= 'Z') {
            cnt++;
            switch (ch) {
                case 'A':
                case 'E':
                case 'I':
                case 'O':
                case 'U':
                    cnt--;
            }
        }
        ch = getchar();
    }
    printf("%d", cnt);
    return 0;
}

运行结果：

习题7-7 字符串替换

本题要求编写程序，将给定字符串中的大写英文字母按以下对应规则替换：

输入格式：
输入在一行中给出一个不超过 80 个字符、并以回车结束的字符串。
输出格式：
输出在一行中给出替换完成后的字符串。
输入样例：

Only the 11 CAPItaL LeTtERS are replaced.

输出样例：

Lnly the 11 XZKRtaO OeGtVIH are replaced.

解题思路：规律很容易发现，就是首字母对尾字母，即是一个加，一个减，两者和不变，即有 永远成立，因此编码实现很简单。

#include <stdio.h>
int main () {
    char x = getchar(), y;
    while ('\n' != x) {
        if ('A' <= x && x <= 'Z') {  // 大写
            y = 'A' + 25 + 'A' - x;
            putchar(y);
        } else {
            putchar(x);
        }
        x = getchar();
    }
    return 0;
}

运行结果：

习题7-8 字符串转换成十进制整数

输入一个以#结束的字符串，本题要求滤去所有的非十六进制字符（不分大小写），组成一个新的表示十六进制数字的字符串，然后将其转换为十进制数后输出。如果在第一个十六进制字符之前存在字符“-”，则代表该数是负数。
输入格式：
输入在一行中给出一个以#结束的非空字符串。
输出格式：
在一行中输出转换后的十进制数。题目保证输出在长整型范围内。
输入样例：

+-P-xf4+-1!#

输出样例：

-3905

解题思路：

1. 进行字符串的消除处理，由于需要离有效数字最近的符号位，因此不得不使用 flag 来标记防止在有效数字后出现的垃圾符号。
2. 将所有非法字符剔除，注意 0-9a-fA-F 的范围即可。
3. 使用秦九算法进行高位到低位相乘。

   #include <stdio.h>
   #define MAXSIZE 12
   int main () {
    char hex[MAXSIZE] = {'\0'};
    int sign = 1, flag = 0, idx = 0;
    // 1.字符串处理
    char tmp = getchar();
    while (tmp != '\n') {
        if ('+' == tmp) {
            if (0 == flag) {
                sign = 1;
            }
        } else if ('-' == tmp) {
            if (0 == flag) {
                sign = -1;
            }
        } else if (('0' <= tmp && tmp <= '9') || ('a' <= tmp && tmp <= 'f') || ('A' <= tmp && tmp <= 'F')) {
            hex[idx++] = tmp;
            flag = 1;
        }
        tmp = getchar();
    }
    // 2.转换
    int num = 0;
    for (int i = 0; i < idx; i++) {
        if ('0' <= hex[i] && hex[i] <= '9') {
            num = num * 16 + hex[i] - '0';
        } else if ('a' <= hex[i] && hex[i] <= 'f') {
            num = num * 16 + hex[i] - 'a' + 10;
        } else {
            num = num * 16 + hex[i] - 'A' + 10;
        }
    }
    printf("%d\n", sign * num);
    return 0;
   }
   

   运行结果：