判断合法 IP

2022-08-12

technology

约 441 字预计阅读 1 分钟

题目描述：

现在IPV4下用一个32位无符号整数来表示，一般用点分方式来显示，点将IP地址分成4个部分，每个部分为8位，表示成一个无符号整数（因此不需要用正号出现），如10.137.17.1，是我们非常熟悉的IP地址，一个IP地址串中没有空格出现（因为要表示成一个32数字）。

现在需要你用程序来判断IP是否合法。

注意本题有多组样例输入。

输入描述：

输入一个ip地址，保证是xx.xx.xx.xx的形式（xx为整数）

输出描述：

返回判断的结果YES or NO

示例：

输入：

10.138.15.1
255.0.0.255
255.255.255.1000

输出：

YES
YES
NO

解题思路：

1、地址分四段，且必须有四段
2、dot 有三个，且必须三个
3、每段数字在 0 - 255 之间
4、每段数字长度大于 0，少于 3

测试用例：

10.128.1.156.1
10.128.1.
10.128.1.156.
256.0.0.0
10.1111.1.1
1..0.122
12.a.89.1
255.255.255.255
0.0.0.0

题解 - C 语言

int main()
{
    char ip[20];
    while (scanf("%s", ip) != EOF) {
        int len = strlen(ip);
        int seg = 0;
        int dot = 0;
        int seg_len = 0;
        for (int i=0; i<len; i++) {
            if (ip[i] >= '0' && ip[i] <= '9') {
                seg_len++;
                seg = seg*10 + ip[i]-'0';
            } else if (ip[i] == '.') {
                if (seg > 255 || seg_len == 0 || seg_len > 3 || (seg==0 && seg_len>1)) {
                    printf("NO");
                    break;
                }
                seg = 0;
                seg_len = 0;
                dot++;
            } else {
                printf("NO");
                break;
            }
        }
        if (seg > 255 || seg_len == 0 || seg_len > 3 || (seg==0 && seg_len>1)) {
            printf("NO");
            break;
        }
        if (dot == 3) {
            printf("YES");
        } else {
            printf("NO");
        }
    }
    return 0;
}

阅读全文

学生方阵

2022-07-19

technology

约 610 字预计阅读 2 分钟

题目描述

学校组织活动，将学生排成一个矩形方阵。请在矩形方阵中找到最大的位置相连的男生数量。这个相连位置在一个直线上，方向可以是水平的、垂直的、呈对角线的或者反对角线的。注：学生个数不会超过10000.

输入描述:

输入的第一行为矩阵的行数和列数，接下来的n行为矩阵元素，元素间用“,”分隔。

输出描述:

输出一个整数，表示矩阵中最长的位置相连的男生个数。

示例1

输入
3,4
F,M,M,F
F,M,M,F
F,F,F,M

输出
3

测试用例

4,5
H,M,H,M,H
H,M,H,M,H
H,M,H,M,H
H,M,H,M,H
4

4,5
M,M,M,M,M
H,M,H,M,H
H,M,H,M,H
H,M,H,M,H
5

4,5
M,M,H,M,H
H,M,H,M,H
H,H,M,H,H
H,M,H,M,H
4

4,5
M,M,H,M,M
H,H,H,M,H
H,H,M,H,H
H,M,H,M,H
4

4,5
M,M,H,M,M
H,H,H,H,M
H,H,M,M,H
H,M,M,H,H
3

C语言题解：

todo
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <stdlib.h>
#define MAX 105
int n,m;
int g[MAX][MAX] = {0};
int main()
{
    scanf("%d,%d", &n, &m);//printf("%d %d\n", n, m);
    char s[500] = {0};
    for (int i=0; i<n; i++) {    
        scanf("%s", s);//printf("%s\n", s);
        for (int j=0; j<m; j++) {
            //printf("%c", s[j*2]);
            if (s[j*2] == 'M') {
                g[i][j] = 1;
            }
        }
    }

    int max = 0;
    for (int i=0; i<n; i++) { // 从左到右
        int k = 0;
        int cnt = 0;
        while (k<m) {
            //printf("%d ", g[i][k]);
            if (g[i][k] == 1) {
                cnt++;
                if (cnt > max) {
                    max = cnt;
                }
            } else {
                cnt = 0;
            }
            k++;
        }
    }

    for (int i=0; i<n; i++) { // 左上到右下
        int k = 0;
        int cnt = 0;
        int x = i;
        while (k<m && x<n) {//printf("%d ", g[x][k]);
            if (g[x][k] == 1) {
                cnt++;
                if (cnt > max) {
                    max = cnt;
                }
            } else {
                cnt = 0;
            }
            k++;
            x++;
        }
    }
    
    for (int j=0; j<m; j++) { // 从上到下
        int k = 0;
        int cnt = 0;
        while (k<n) {
            if (g[k][j] == 1) {
                cnt++;
                if (cnt > max) {
                    max = cnt;
                }
            } else {
                cnt = 0;
            }
            k++;
        }
    }
    for (int j=0; j<m; j++) { // 左上到右下
        int k = 0;
        int cnt = 0;
        int y = j;
        while (k<n && y<m) {
            if (g[k][y] == 1) {
                cnt++;
                if (cnt > max) {
                    max = cnt;
                }
            } else {
                cnt = 0;
            }
            k++;
            y++;
        }
    }
    for (int j=0; j<m; j++) { // 右上到左下
        int k = 0;
        int cnt = 0;
        int y = j;
        while (k<n && y>=0) {
            if (g[k][y] == 1) {
                cnt++;
                if (cnt > max) {
                    max = cnt;
                }
            } else {
                cnt = 0;
            }
            k++;
            y--;
        }
    }
    for (int i=0; i<n; i++) { // 右上到左下
        int k = m-1;
        int cnt = 0;
        int x = i;
        while (k>=0) {
            if (g[x][k] == 1) {
                cnt++;
                if (cnt > max) {
                    max = cnt;
                }
            } else {
                cnt = 0;
            }
            x++;
            k--;
        }
    }     
    printf("%d\n", max);
    return 0;
}

阅读全文

判断字符串子序列

2022-07-18

technology

约 522 字预计阅读 2 分钟

题目描述

给定字符串 target和 source, 判断 target 是否为 source 的子序列。
你可以认为 target 和 source 中仅包含英文小写字母。
字符串 source可能会很长（长度 ~= 500,000），而 target 是个短字符串（长度 <=100）。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。
（例如，“abc"是"aebycd"的一个子序列，而"ayb"不是）。
请找出最后一个子序列的起始位置。

输入描述:

第一行为target，短字符串（长度 <=100）
第二行为source，长字符串（长度 ~= 500,000）

输出描述:

最后一个子序列的起始位置，即最后一个子序列首字母的下标

示例1

输入
abc
abcaybec
输出
3

说明
这里有两个abc的子序列满足，取下标较大的，故返回3
备注:
若在source中找不到target，则输出-1

测试用例

abc
cabdef
-1

abc
afegbdefsec
0

abc
dfsabcdefahibjkic
9

C语言题解：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX_SOURCE 600000
#define MAX_TARGET 110
int main()
{
    char target[105] = {0};
    char source[MAX_SOURCE] = {0};
    scanf("%s", target);
    scanf("%s", source);
    const int t_len = strlen(target);
    const int s_len = strlen(source);
    int i = t_len - 1;
    int j = s_len - 1;
    int idx = 0;
    while (i>=0 && j>=0) { // 从尾部到头部开始比较
        if (target[i] == source[j]) {
            if (i == 0) { // 当到达 target 头部时，找到位置，返回索引
                printf("%d", j);
                return 0;
            }
            i--;
        }
        j--;
    }
    printf("-1");
    return 0;
}

时间复杂度：O(n)

阅读全文