Hexo

在面试手撕代码时, 面对的代码环境常常不是类似于leetcode那样的核心代码填空, 而是需要你自己去搭建一个完整的代码框架, 处理输入输出, 以及边界条件等问题.

头文件

在使用ACM模式时, 需要知道常用的方法对应的头文件:

• <bits/stdc++.h>: 包含了几乎所有的标准C++库, 适合竞赛使用, 但编译速度较慢.
• : 定义了各种数据类型的极限值, 如 INT_MAX, INT_MIN
• : 提供字符处理函数, 如 isdigit()
• : 包含通用工具函数, 如 abs(), rand()
• : 还提供了 stoi()
• : 提供时间和日期函数, 如 time(), clock()
  • 一般与 一起使用, 用于生成随机数, 如 srand(time(0))

一般输入处理技巧

处理多组输入:

#include <iostream>
using namespace std;

int main() {
    int n;
    while (cin >> n) { // 处理多组输入
        // 处理输入数据
    }
}

这里的 while (cin >> n) 会持续读取输入直到没有更多数据, 适用于多组测试数据的情况.

整行读取, 可以消除换行符影响:

#include <iostream>
#include <string>
using namespace std;
int main() {
    string line;
    while (getline(cin, line)) { // 读取整行输入
        // 处理输入数据, 假如这里的数据是两个字符串

        
    }
}

使用 getline 可以读取整行输入, 避免换行符对输入处理的影响. 下次读取时会自动跳过换行符.

或者使用 cin.ignore() 来忽略换行符:

#include <iostream>
using namespace std;
int main() {
    int n;
    while (cin >> n) {
        cin.ignore(); // 忽略换行符, 下一轮循环会从新的一行开始读取
        // 处理输入数据
    }
}

处理多行输入:

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

创建链表

在处理链表输入时, 通常会以空格分隔的整数形式提供链表节点值. 一行输入表示一个链表. 下面是一个示例代码, 展示如何从输入中创建链表并传入到处理函数中:

#include<iostream>
#include<sstream>
#include<string>
using namespace std;

// 定义链表节点结构
struct ListNode{
    int val;            
    ListNode* next;     
    ListNode(int v) : val(v), next(nullptr) {} 
};

// 从输入的一行数字构建链表
ListNode* createList(){
    string line;
    getline(cin, line);           // 从标准输入读取一整行
    if(line.empty()) return nullptr; // 如果输入为空行，返回空链表

    stringstream ss(line);        // 用 stringstream 解析这一行
    int num;

    // 使用虚拟头结点（dummy），方便链表构建
    ListNode* dummy = new ListNode(-1);
    ListNode* tail = dummy;       // tail 指针始终指向链表的尾部

    // 按顺序读取数字并构建链表
    while(ss >> num){
        tail->next = new ListNode(num); // 新建节点并挂到尾部
        tail = tail->next;              // 移动尾指针
    }

    return dummy->next; // 返回真正的头结点
}

// 打印链表
void printList(ListNode* node){
    while(node){
        cout << node->val << ' '; 
        node = node->next;        
    }
    cout << endl;
}

// 主函数：处理单个链表
int main(){
    ListNode* head = createList();       // 从输入构建链表
    // 将链表传给核心函数，例如反转链表
    ListNode* ret = reverseList(head);   // reverseList 就是考核的核心函数
    printList(ret);                      // 打印处理后的链表
    return 0;
}

// 处理多个链表
int main(){
    ListNode* list1 = createList();     // 创建第一个链表
    ListNode* list2 = createList();     // 创建第二个链表
    // 传给核心函数, 例如合并两个有序链表
    ListNode* ret = mergeTwoLists(list1, list2);
    printList(ret);
    return 0;
}

创建二叉树

在处理二叉树输入时, 通常会以层序遍历的形式提供二叉树节点值, 使用空字符串或特定标记（如 null）表示空节点. 下面是一个示例代码, 展示如何从输入中创建二叉树并传入到处理函数中:

#include<iostream>
#include<sstream>
#include<queue>
using namespace std;

// 定义二叉树节点结构
struct TreeNode{
    int val;              
    TreeNode* left;       
    TreeNode* right;      
    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};

// 从输入的一行字符串构建二叉树（层序遍历格式，null 表示空节点）
TreeNode* createTree(){
    string line;
    getline(cin, line);               // 从标准输入读取一整行
    if(line.empty()) return nullptr; 

    stringstream ss(line);            // 用 stringstream 解析这一行
    string valstr;
    ss >> valstr; 
    if(valstr=="null") return nullptr;

    TreeNode* root = new TreeNode(stoi(valstr)); // 创建根节点
    queue<TreeNode*> q;                          // 队列用于层序构建
    q.push(root);

    // 层序遍历构建二叉树
    while(!q.empty()){
        TreeNode* cur = q.front();   // 取出队首节点
        q.pop();

        // 处理左子节点
        if(ss >> valstr){
            if(valstr!="null"){      // 如果不是 "null"，创建左子节点
                cur->left = new TreeNode(stoi(valstr));
                q.push(cur->left);   // 入队，后续继续处理
            }
        }

        // 处理右子节点
        if(ss >> valstr){
            if(valstr!="null"){      // 如果不是 "null"，创建右子节点
                cur->right = new TreeNode(stoi(valstr));
                q.push(cur->right);  // 入队
            }
        }
    }
    return root; // 返回构建好的树的根节点
}

// 创建单棵树并调用核心函数
int main(){
    TreeNode* root = createTree();   
    // 将树传递给核心函数，例如计算最大深度
    int depth = maxDepth(root);      
    cout << depth;                   
    return 0;
}

// 创建多棵树并调用核心函数
int main(){
    TreeNode* tree1 = createTree();  // 创建第一棵树
    TreeNode* tree2 = createTree();  // 创建第二棵树
    // 将两棵树传递给核心函数，例如判断是否相同
    bool isSame = isSameTree(tree1, tree2); 
    cout << (isSame ? "True" : "False");    
    return 0;
}