机试day7

String Matching

String Matching_牛客题霸_牛客网 (nowcoder.com)

描述

Finding all occurrences of a pattern in a text is a problem that arises frequently in text-editing programs. Typically,the text is a document being edited,and the pattern searched for is a particular word supplied by the user. We assume that the text is an array T[1..n] of length n and that the pattern is an array P[1..m] of length m<=n.We further assume that the elements of P and T are all alphabets(∑={a,b...,z}).The character arrays P and T are often called strings of characters. We say that pattern P occurs with shift s in the text T if 0<=s<=n and T[s+1..s+m] = P1..m. If P occurs with shift s in T,then we call s a valid shift;otherwise,we calls a invalid shift. Your task is to calculate the number of vald shifts for the given text T and p attern P.

输入描述：

For each case, there are two strings T and P on a line,separated by a single space.You may assume both the length of T and P will not exceed 10^6.

输出描述：

You should output a number on a separate line,which indicates the number of valid shifts for the given text T and pattern P.

输入：
abababab abab
输出：
3

思路：就是在练习KMP算法编写

#include <iostream>
using namespace std;

int nextTable[1000];

void get_next(string pattern) {
    int i = -1, j = 0;
    nextTable[0] = -1;
    while (j < pattern.size()) {
        if (i == -1 || pattern[i] == pattern[j]) {
            i++;
            j++;
            nextTable[j] = i;
        } else {
            i = nextTable[i];
        }
    }
}

int KMP(string text, string pattern) {
    get_next(pattern);
    int number = 0;
    int i = 0, j = 0;
    while (i < text.size()) {
        if (j == -1 || text[i] == pattern[j]) {
            i++;
            j++;
        } else {
            j = nextTable[j];
        }
        if (j == pattern.size()) {
            number++;
            j = nextTable[j];
        }
    }
    return number;
}

int main() {
    string text, pattern;
    while (cin >> text >> pattern) {
        printf("%d\n", KMP(text, pattern));
    }
}

验证IP地址

描述

编写一个函数来验证输入的字符串是否是有效的 IPv4 或 IPv6 地址

IPv4 地址由十进制数和点来表示，每个地址包含4个十进制数，其范围为 0 - 255， 用(".")分割。比如，172.16.254.1；
同时，IPv4 地址内的数不会以 0 开头。比如，地址 172.16.254.01 是不合法的。

IPv6 地址由8组16进制的数字来表示，每组表示 16 比特。这些组数字通过 (":")分割。比如, 2001:0db8:85a3:0000:0000:8a2e:0370:7334 是一个有效的地址。而且，我们可以加入一些以 0 开头的数字，字母可以使用大写，也可以是小写。所以， 2001:db8:85a3:0:0:8A2E:0370:7334 也是一个有效的 IPv6 address地址 (即，忽略 0 开头，忽略大小写)。

然而，我们不能因为某个组的值为 0，而使用一个空的组，以至于出现 (::) 的情况。 比如， 2001:0db8:85a3::8A2E:0370:7334 是无效的 IPv6 地址。
同时，在 IPv6 地址中，多余的 0 也是不被允许的。比如， 02001:0db8:85a3:0000:0000:8a2e:0370:7334 是无效的。

说明: 你可以认为给定的字符串里没有空格或者其他特殊字符。

数据范围：字符串长度满足 $5\le n\le 50$

进阶：空间复杂度$O(n)$，时间复杂度 $O(n)$

法1：超极笨的不停if列举法【没脸看】

略

法2：正则-C++库

透露出一种清澈的愚蠢，谁考试能记得呢:cry:，而且还没有对开头为0的不标准ipv4进行判断

#include <iostream>
#include <regex>

bool is_ipv4(string IP) {
    regex pattern("((25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)\\.){3}(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)");
    smatch res;
    if (regex_match(IP, res, pattern))
        return true;
    else
        return false;
}

bool is_ipv6(string IP) {
    regex pattern("/^\s*((([0-9A-Fa-f]{1,4}:){7}([0-9A-Fa-f]{1,4}|:))|(([0-9A-Fa-f]{1,4}:){6}(:[0-9A-Fa-f]{1,4}|((25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)(\.(25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)){3})|:))|(([0-9A-Fa-f]{1,4}:){5}(((:[0-9A-Fa-f]{1,4}){1,2})|:((25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)(\.(25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)){3})|:))|(([0-9A-Fa-f]{1,4}:){4}(((:[0-9A-Fa-f]{1,4}){1,3})|((:[0-9A-Fa-f]{1,4})?:((25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)(\.(25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)){3}))|:))|(([0-9A-Fa-f]{1,4}:){3}(((:[0-9A-Fa-f]{1,4}){1,4})|((:[0-9A-Fa-f]{1,4}){0,2}:((25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)(\.(25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)){3}))|:))|(([0-9A-Fa-f]{1,4}:){2}(((:[0-9A-Fa-f]{1,4}){1,5})|((:[0-9A-Fa-f]{1,4}){0,3}:((25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)(\.(25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)){3}))|:))|(([0-9A-Fa-f]{1,4}:){1}(((:[0-9A-Fa-f]{1,4}){1,6})|((:[0-9A-Fa-f]{1,4}){0,4}:((25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)(\.(25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)){3}))|:))|(:(((:[0-9A-Fa-f]{1,4}){1,7})|((:[0-9A-Fa-f]{1,4}){0,5}:((25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)(\.(25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)){3}))|:)))(%.+)?\s*$/");
    smatch res;
    if (regex_match(IP, res, pattern))
        return true;
    else
        return false;
}

class Solution {
public:
    /**
     * 验证IP地址
     * @param IP string字符串 一个IP地址字符串
     * @return string字符串
     */
    string solve(string IP) {
        if (is_ipv4(IP)) 
            return "IPv4";
        else if (is_ipv6(IP))
            return "IPv6";
        else 
            return "Neither";
    }
};

二进制数

二进制数_牛客题霸_牛客网 (nowcoder.com)

描述

大家都知道，数据在计算机里中存储是以二进制的形式存储的。 有一天，小明学了C语言之后，他想知道一个类型为unsigned int 类型的数字，存储在计算机中的二进制串是什么样子的。 你能帮帮小明吗？并且，小明不想要二进制串中前面的没有意义的0串，即要去掉前导0。

输入描述：

多行，每一行表示要求的数字

输出描述：

输出共T行。每行输出求得的二进制串。

思路：vector之类的数据结构接收每次模2的结果，最后倒着输出

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    while (cin >> n) {
        vector<int> binary;
        while (n != 0) {
            binary.push_back(n % 2);
            n /= 2;
        }
        for (int i = binary.size() - 1; i >= 0; i--) {
            cout << binary[i];
        }
        cout << endl;
    }
}

进制转换

进制转换_牛客题霸_牛客网 (nowcoder.com)

描述

将一个长度最多为30位数字的十进制非负整数转换为二进制数输出。

输入描述：

多组数据，每行为一个长度不超过30位的十进制非负整数。 （注意是10进制数字的个数可能有30个，而非30bits的整数）

输出描述：

每行输出对应的二进制数。

思路：由于长度太长，肯定得用字符串来处理；模2余数好算，看最后一位即可；难点在于除以2后的结果

单独写了个chu2函数，从第一位开始遍历算起，如果除以2有余数，则下一位除以2前+10。特殊情况是第一位为1（1除外）的情况，需要最后去除第一位

#include <iostream>
#include <vector>
using namespace std;

string chu2(string n) {
    int num, yu = 0, flag = 0;
    for (int i = 0; i < n.size(); i++) {
        num = n[i] - '0';
        if (n[i] == '1' && i == 0 && n.size() != 1)
            flag = 1;
        else
            n[i] = (yu * 10 + num) / 2 + '0';
        yu = num % 2;
    }
    if (flag == 1)
        n.erase(0, 1);
    return n;
}

int main() {
    string n;
    while (cin >> n) {
        vector<int> binary;
        if (n == "0")
            binary.push_back(0);
        else {
            while (n != "0") {
                binary.push_back((n[n.size() - 1] - '0') % 2);
                n = chu2(n);
            }
        }
        for (int i = binary.size() - 1; i >= 0; i--) {
            cout << binary[i];
        }
        cout << endl;
    }
}

10进制 VS 2进制

10进制 VS 2进制_牛客题霸_牛客网 (nowcoder.com)

描述

对于一个十进制数A，将A转换为二进制数，然后按位逆序排列，再转换为十进制数B，我们称B为A的二进制逆序数。 例如对于十进制数173，它的二进制形式为10101101，逆序排列得到10110101，其十进制数为181，181即为173的二进制逆序数。

输入描述：

一个1000位(即10^999)以内的十进制数。

输出描述：

输入的十进制数的二进制逆序数。

输入：
173
输出：
181

思路：这题很难，对于十进制转二进制就上一题的方法，但是二进制也要转换为十进制，需要再写个字符串乘法和加法函数

直接照抄书上的了，模板题【做的脑CPU都快烧了】

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

string Divide(string str, int x) {
    int remainder = 0;
    for (int i = 0; i < str.size(); i++) {
        int current = remainder * 10 + str[i] - '0';
        str[i] = current / x + '0';
        remainder = current % x;
    }
    int pos = 0;
    while (str[pos] == '0')
        pos++;
    return str.substr(pos);
}

string Multiple(string str, int x) {
    int carry = 0;
    for (int i = str.size() - 1; i >= 0; i--) {
        int current = x * (str[i] - '0') + carry;
        str[i] = current % 10 + '0';
        carry = current / 10;
    }
    if (carry != 0)
        str = "1" + str;
    return str;
}

string Add(string str, int x) {
    int carry = x;
    for (int i = str.size() - 1; i >= 0; i--) {
        int current = (str[i] - '0') + carry;
        str[i] = current % 10 + '0';
        carry = current / 10;
    }
    if (carry != 0)
        str = "1" + str;
    return str;
}

int main() {
    string str;
    while (cin >> str) {
        vector<int> binary;
        while (str.size() != 0) {
            int last = str[str.size() - 1] - '0';
            binary.push_back(last % 2);
            str = Divide(str, 2);
        }
        string answer = "0";
        for (int i = 0; i < binary.size(); i++) {
            answer = Multiple(answer, 2);
            answer = Add(answer, binary[i]);
        }
        cout << answer << endl;
    }
    return 0;
}

进制转换2

进制转换2_牛客题霸_牛客网 (nowcoder.com)

描述

将M进制的数X转换为N进制的数输出。

输入描述：

输入的第一行包括两个整数：M和N(2<=M,N<=36)。
下面的一行输入一个数X，X是M进制的数，现在要求你将M进制的数X转换成N进制的数输出。

输出描述：

输出X的N进制表示的数。

输入：
10 2
11
输出：
1011

【注意输入时如有字母，则字母为大写，输出时如有字母，则字母为小写。】

思路：先转为10进制再转为N进制，要考虑大于10进制的字母形式【难点】

需要注意的是int溢出！！！所以用long long

#include <iostream>
#include <vector>
using namespace std;

int ch2int(char c) {
    if (c <= '9' && c >= '0') 
        return c - '0';
    else
        return c - 'A' + 10;
}

char int2ch(int x) {
    if (x < 10)
        return char(x + '0');
    else {
        return char(x - 10 + 'a');
    }
}

int main() {
    int M, N;
    cin >> M >> N;
    string x;
    cin >> x;
    long long dec = 0;
    for (int i = 0; i < x.size(); i++) {
        dec = M * dec + ch2int(x[i]);
    }
    vector<char> n_num;
    while (dec != 0) {
        n_num.push_back(int2ch(dec % N));
        dec /= N;
    }
    for (int i = n_num.size() - 1; i >= 0; i--) {
        cout << n_num[i];
    }
    cout << endl;
}

八进制

八进制_牛客题霸_牛客网 (nowcoder.com)

输入一个整数转为八进制，做了前面的题目此题1min就敲完了

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N;
    while (cin >> N) {
        vector<int> oct;
        while (N != 0) {
            oct.push_back(N % 8);
            N /= 8;
        }
        for (int i = oct.size() - 1; i >= 0; i--) {
            cout << oct[i];
        }
        cout << endl;
    }
}

又一版 A+B

又一版 A+B_牛客题霸_牛客网 (nowcoder.com)

描述

输入两个不超过整型定义的非负10进制整数A和B($\le 2^{31}-1$)，输出A+B的m ($1\lt m\lt 10$)进制数。

输入描述：

输入格式：测试输入包含若干测试用例。每个测试用例占一行，给出m和A，B的值。 当m为0时输入结束。

输出描述：

输出格式：每个测试用例的输出占一行，输出A+B的m进制数。

法1：字符串处理

思路：如果A+B不溢出，那就很好做，直接按照正常数字进制转换即可；但是测试案例里有A+B很大溢出的情况，因此需要多加考虑

我的想法是既然十进制加起来可能会溢出，那就先不相加，先转为对应的m进制后再相加，此时就好做多了；我是使用的字符串形式来计算，看起来有些麻烦；此种方法的好处是不用再去写转换字符串进制转换了（除法）

#include <iostream>
#include <algorithm>
using namespace std;

string Add(string a, string b, int m) {
    int carry = 0;
    if (a.size() > b.size()) {    // 判断哪个长就用哪个接收最终相加结果
        int current = 0;
        for (int i = 0; i < a.size(); i++) {
            if (i < b.size()) {
                current = (a[i] - '0') + (b[i] - '0') + carry; 
                a[i] = current % m  + '0';
                carry = current / m;
            }
            else {    // 超过短的长度后，不用取值，否则数组溢出
                current = (a[i] - '0') + carry; 
                a[i] = current % m  + '0';
                carry = current / m;
            }
        }
        if (carry != 0)    // 最后还要在判断下，防止进位超出最大长度
            a.push_back(carry + '0');
        return a;
    } else {
        int current = 0;
        for (int i = 0; i < b.size(); i++) {
            if (i < a.size()) {
                current = (b[i] - '0') + (a[i] - '0') + carry; 
                b[i] = current % m  + '0';
                carry = current / m;
            }
            else {
                current = (b[i] - '0') + carry; 
                b[i] = current % m  + '0';
                carry = current / m;
            }
        }
        if (carry != 0)
            b.push_back(carry + '0');
        return b;
    }
}

int main() {
    int m, a, b;
    while (cin >> m >> a >> b) {
        if (m == 0)
            break;  
        string oct_a;
        while (a != 0) {
            oct_a.push_back(a % m + '0');    // 每次添加一个字符
            a /= m;
        }
        string oct_b;
        while (b != 0) {
            oct_b.push_back(b % m + '0');
            b /= m;
        }
        if (oct_a.size() == 0 && oct_b.size() == 0)    //如果a、b都是0，直接输出0
            cout << 0 << endl;
        else {
            string result = Add(oct_a, oct_b, m);    // 字符串结果还要逆向一下才是正确的顺序
            reverse(result.begin(), result.end());
            cout << result << endl;
        }
    }
}

改进：

  • 数字进制转换写成了函数，这样增加代码可读性
  • 字符串相加函数中，使用while给较短字符串补0（参考其他人题解），使得长度相等，这样不用重复两遍代码了
#include <iostream>
#include <algorithm>
using namespace std;

string Add(string a, string b, int m) {
    while (a.size() > b.size()) 
        b.push_back('0');
    while (a.size() < b.size()) 
        a.push_back('0');
    int carry = 0;
    int current = 0;
    for (int i = 0; i < a.size(); i++) {
        current = (a[i] - '0') + (b[i] - '0') + carry; 
        a[i] = current % m  + '0';
        carry = current / m;
    }
    if (carry != 0)
        a.push_back(carry + '0');
    return a;
}

string dec2m(int x, int m) {
    string s;
    while (x != 0) {
        s.push_back(x % m + '0');
        x /= m;
    } 
    return s;
}

int main() {
    int m, a, b;
    while (cin >> m >> a >> b) {
        if (m == 0)
            break;  
        string oct_a = dec2m(a, m);
        string oct_b = dec2m(b, m);
        if (oct_a.size() == 0 && oct_b.size() == 0)
            cout << 0 << endl;
        else {
            string result = Add(oct_a, oct_b, m);
            reverse(result.begin(), result.end());
            cout << result << endl;
        }
    }
}

法2：直接long long接收A、B（感觉有些作弊？）

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int m;
    long long A, B;
    while (cin >> m) {
        if (m == 0) break;
        cin >> A;
        cin >> B;
        long long val = A + B;
        vector<int> res;
        if (val == 0) res.push_back(0);
        while (val != 0) {
            res.push_back(val % m);
            val = val / m;
        }
        for (int i = res.size()-1; i >= 0; i--) {
            cout << res[i];
        }
        cout << endl;
    }
    return 0;
}

进制转换

进制转换_牛客题霸_牛客网 (nowcoder.com)

描述

写出一个程序，接受一个十六进制的数值字符串，输出该数值的十进制字符串(注意可能存在的一个测试用例里的多组数据)。

输入描述：

输入一个十六进制的数值字符串。

输出描述：

输出该数值的十进制字符串。

法1：16进制字符转10进制

#include <iostream>
using namespace std;

int hex2dec(char ch) {
    if (ch <= '9' && ch >= '0') 
        return ch - '0';
    else
        return ch - 'A' + 10;
}

int main() {
    string hex;
    while (cin >> hex) {
        int dec = 0;
        for (int i = 2; i < hex.size(); i++) {
            dec = dec * 16 + hex2dec(hex[i]);
        }
        cout << dec << endl;
    }

}

法2：超级简单，直接格式化输入和输出

C的写法：

#include <stdio.h>

int main() {
    int num = 0;
    while (~scanf ("%x", &num))
        printf("%d\n",  num);
    return 0;
}

C++的写法：

#include <iostream>
using namespace std;

int main() {
    int num = 0;
    while (cin >> hex >> num)
        cout << dec << num << endl;
    return 0;
}

数制转换

数制转换_牛客题霸_牛客网 (nowcoder.com)

描述

求任意两个不同进制非负整数的转换（2进制～16进制），所给整数在long所能表达的范围之内。 不同进制的表示符号为（0，1，...，9，a，b，...，f）或者（0，1，...，9，A，B，...，F）。

输入描述：

输入只有一行，包含三个整数a，n，b。a表示其后的n 是a进制整数，b表示欲将a进制整数n转换成b进制整数。a，b是十进制整数，2 =< a，b <= 16。 数据可能存在包含前导零的情况。

输出描述：

可能有多组测试数据，对于每组数据，输出包含一行，该行有一个整数为转换后的b进制数。输出时字母符号全部用大写表示，即（0，1，...，9，A，B，...，F）。

思路：

  1. 首先a进制字符串转为十进制数字（a2dec），其中设置flag位为0，直到遇到开头不为'0'的字符，即去除开头的0
  2. 十进制数字转为b进制字符串（dec2b），需要注意dec % b如果大于等于10，要改为字母，因此做一个条件判断
  3. 如果b=10，第一步完可以直接输出，不用再去dec2b里转为字符串了
#include <iostream>
#include <algorithm>
using namespace std;

int a2dec(string num, int a) {
    int dec = 0, n, flag = 0;
    for (int i = 0; i < num.size(); i++) {
        if (num[i] != '0')
            flag = 1;
        if (flag) {
            if (num[i] <= '9' && num[i] >= '0') 
                n = num[i] - '0';
            else if (num[i] <= 'z' && num[i] >= 'a')
                n = num[i] - 'a' + 10;
            else 
                n = num[i] - 'A' + 10;
            dec = dec * a + n;
        }
    }
    return dec;
}

string dec2b(int dec, int b) {
    string num;
    while (dec != 0) {
        if (dec % b >= 10)
            num.push_back(dec % b + 'A' - 10);
        else
            num.push_back(dec % b + '0');
        dec /= b;
    }
    reverse(num.begin(), num.end());    //得逆转下顺序
    return num;
}

int main() {
    int a, b;
    string num;
    while (cin >> a >> num >> b) {
        int dec = a2dec(num, a);
        if (b != 10)
            cout << dec2b(dec, b) << endl;
        else
            cout << dec << endl;
    }
}
最后修改：2023 年 06 月 10 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏