单词出现次数

难点在他妈的如何正确地输入, 以及处理输入.

int main() {
    int quesNum = 0;
    std::cin >> quesNum;
    std::cin.ignore();
    std::vector<int> result;
    for (int i = 0; i < quesNum; i++) {
        std::string tmp;
        std::string text;
        std::getline(std::cin, text);
        std::istringstream iss(text);
        std::string t;
        std::getline(std::cin, t);
        int count = 0;
        while (iss >> tmp) if (tmp == t) count++;
        result.push_back(count);
    }
    for (int i = 0; i < result.size(); i++) {
        std::cout << "case #" << i << ":" << std::endl;
        std::cout << result[i] << std::endl;
    }
    return 0;
}

细节:

输入第一个数字之后, 要用 std::cin.ignore(); 忽略换行符.

为什么需要 std::cin.ignore() ？(deepseek)
1. 输入流中的换行符问题：
  - 当你使用 std::cin >> T 读取整数 T 时，输入流中会留下一个换行符（\n），因为用户在输入整数后会按下回车键。
  - 如果直接使用 std::getline 读取下一行输入，std::getline 会立即读取到输入流中残留的换行符，导致它返回一个空字符串。
2. std::getline 的行为：
  - std::getline 会读取输入流中的内容，直到遇到换行符（\n），然后将换行符从输入流中移除。
  - 如果输入流中残留了一个换行符，std::getline 会立即读取到它，导致逻辑错误。
一个通用的处理一整行的字符串的手段是: 用 getline 获取整行, 然后用 istringstream 来一个个单词进行处理.

上面这两个细节非常非常重要.

Phone Number

看到记录次数首先就想到使用 map, 实际上思路很简单, 这题值得思考的点就是 map 容器的使用细节, 以及字符转数字的操作.

#include <iostream>
#include <vector>
#include <string>
#include <map>

void number(const std::string& p, std::map<std::vector<int>, int>& result) {
    std::vector<int> r;
    for (int i = 0; i < p.size(); i++) {
        if (isdigit(p[i])) r.push_back(p[i] - '0');
        if (p[i] >= 'A' && p[i] <= 'C') r.push_back(2);
        if (p[i] >= 'D' && p[i] <= 'F') r.push_back(3);
        if (p[i] >= 'G' && p[i] <= 'I') r.push_back(4);
        if (p[i] >= 'J' && p[i] <= 'L') r.push_back(5);
        if (p[i] >= 'M' && p[i] <= 'O') r.push_back(6);
        if (p[i] >= 'P' && p[i] <= 'S') r.push_back(7);
        if (p[i] >= 'T' && p[i] <= 'V') r.push_back(8);
        if (p[i] >= 'W' && p[i] <= 'Z') r.push_back(9);
    }

    if (result.find(r) != result.end()) result[r]++;
    else result[r] = 1;
}

int main() {
    int phoneNum = 0;
    std::cin >> phoneNum;
    std::cin.ignore();

    std::map<std::vector<int>, int> result;
    for (int i = 0; i < phoneNum; i++) {
        std::string phone;
        std::getline(std::cin, phone);
        number(phone, result);
    }
    for (auto i : result) {
        for (int j = 0; j < i.first.size(); j++) {
            if (j == 3) std::cout << i.first[j] << "-";
            else std::cout << i.first[j];
        }
        std::cout << " " << i.second << std::endl;
    }
    return 0;
}

首先是依旧使用了 std::cin.ignore();.
map 容器初始化的方法要注意, 然后就是遍历 map 容器中的元素并输出, 这里用的是范围 for 循环, 记得是用 first 和 second, map 容器会自动根据键对应的值进行排序. 那么问题来了, 默认情况下是降序排列的(符合题目要求)如果要升序排列呢?
实际上, 范围 for 循环是不支持倒序输出的. 所以想要倒序输出需要用正常 for 循环配合反向迭代器完成, 例如:
for (auto it = myMap.rbegin(); it != myMap.rend(); it++) {
std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl;
}
然后就是 map 容器内元素的操作. 直接使用下标运算符[]并配上键, 就能访问键对应的值了. 如果没有这个键, 我们就需要为这个键赋一个初始值; 如果已经存在, 我们就递增.
最后就是字符串转数字了, 这里用 p[i] - '0', 实际上是 int(p[i] - '0'), 只不过我将转换给省略了, 程序会自动执行. 所以我个人比较习惯的字符串转数字的通法是: 逐个访问字符串中的字符(使用下标运算符[]), 通过 int(p[i] - '0') 将它们 push 到一个 vector 中, 然后再对 vector 进行操作.

进制转换

老朋友了. 可以借此回顾一下十进制转其他进制的算法. 一直除然后取余数, 倒过来就是答案. 至于为什么倒过来, 可以直观上理解为: 除以的次数越多, 说明这个数越大, 所以越到后面的余数对应的次数就越大.

另外就是"数字转字符串"的问题, 这里用的是 std::to_string. 容易忘, 要记住.

List 的插入, 查找和删除

/**
 * 【线性表查找操作】
 * @param  x   [目标元素的值 x]
 * @return     [存在值为 x 的元素则返回其第一次出现的下标，否则返回 NIL]
 */
Position List::search(ElemType x)
{
    for (int i = 0; i <= _last; i++) if (_data[i] == x) return i;
    return NIL;
}

/**
 * 【线性表插入操作】
 * @param  idx [插入元素的位置（以下标表示） idx]
 * @param  x   [被插入的元素值 x] 
 * @return     [返回是否成功执行插入操作]
 */
bool List::insert(Position idx, ElemType x)
{
    if (idx < 0 || _last + 1 == _max_size || idx > _last + 1) return false;
    for (int i = _last; i >= idx; i--) _data[i + 1] = _data[i];
    _data[idx] = x;
    _last += 1;
    return true;
}

/**
 * 【线性表删除操作】
 * @param  idx [被删除的元素下标 idx]
 * @return     [成功执行则返回被删除的元素的值，否则返回 NIL]
 */
ElemType List::remove(Position idx)
{
    if (idx > _last || idx < 0) return NIL;
    ElemType value = _data[idx];
    for (int i = idx; i < _last; i++) _data[i] = _data[i + 1];
    _last -= 1;
    return value;
}

看代码感觉很简单, 写之前觉得没问题, 一写就全是问题了. 主要是边界的处理, insert 的, 其他的倒是没啥问题哈.

if (idx < 0 || _last + 1 == _max_size || idx > _last + 1) return false;

还有就是这里的 remove 用的是惰性删除. 我也不知道怎么进行主动删除. 我记得好像没办法, 这个内存是由程序自行配置的.

多项式插入操作

要求: 给定一个指数, 一个系数, 将其插入一个多项式中, 按照降幂排列.

题目思路很简单, 实际上要考虑的情况巨多, 闹斯特麻麻.

首先是系数为 0 的情况, 排除.

然后就是空多项式的情况, 单独处理

接着就是程序的主要部分: 在循环内分情况推进.

这里要用双指针法, 方便访问前一个元素. 并且快指针 p 必须从 head 开始, 慢指针 slow 从 NULL 开始, 这样才能覆盖所有情况(比如仅有 head 一个节点的特殊情况, 妈的).

void Polynomial::insert(int c, int e) {
    if (c == 0) return;
    if (head == NULL) {
        head = new node{ c, e }; 
        return;
    } 
    node* newNode = new node{ c, e };
    node* p = head;
    node* slow = NULL;
    while (p != NULL) {
        if (p->e > e) {
            slow = p;
            p = p->next;
            if (p == NULL) {
                slow->next = newNode;
                return;
            }
            continue;
        }
        else if (p->e == e) {
            p->c += c;
            if (p->c == 0) {
                if (slow == NULL) head = p->next;
                else slow->next = p->next;
                delete p;
            } 
            return;
        }
        else {
            newNode->next = p;
            if (slow == NULL) head = newNode;
            else slow->next = newNode;
            return;
        }
    }
}

可以看到这里对 slow == NULL 的情况做了单独处理, 这就是只有 head 一个节点的情况.

‍