【2025小白版】计算复试/保研机试模板（个人总结非GPT生成）附代码

一、编程语言选择

很多高校在机试中对编程语言都有明确规定，像复旦大学计算机学院就说明可选择 C、C++ 或 Java 语言答题，还支持 C11（gcc5.4），C++14（g++5.4），Java (openjdk1.8）等编译环境。这里强烈建议大家使用 C/C++，因为几乎所有高校都支持，通用性超强👍。

二、准备好模板是至关重要的

一般来说，机试都可以带书和纸质资料进入考场。所以提前把那些函数的用法和算法的模板准备好是很重要的，一方面是增加自己的信心，万一没记住还可以翻开来看一下。另外说不定考到原题或者类似的题，就可以直接秒杀了。
机试模板PDF详细代码自取

常见头文件

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
cout << abs(a);
memset(a,-1,sizeof(a));  #include <string.h>

int转字符串

string intToString(long long x){
	string s;
	while(x){
		s += (x % 10) + '0';
		x = x / 10;
	} 	
	reverse(s.begin(),s.end());
    return s;
}

日期模板

int daytab[2][13] = {
{0,31,28,31,30,31,30,31,31,30,31,30,31
},
{0,31,29,31,30,31,30,31,31,30,31,30,31,
}
};

bool IsLeapYear(int x){
    return (x % 4 == 0&& x % 100 != 0) || (x % 400 ==0);
}
=====================================================算天数
	while(cin >> y >> m >> d){
		int sum = 0;
		for(int i = 0;i < m ;i ++){
			sum += daytab[isLeapYear(y)][i];
		}
		sum += d;
		cout << sum << endl;
	}
======================================================
    scanf("%04d%02d%02d",&y1,&m1,&d1);
======================================================
// 第n天后是什么日期
        cin >> y >> m >> d >> n;
        n = n + d;
        d = 0;
        while(n >= daytab[IsLeapYear(y)][m]){
            n -= daytab[IsLeapYear(y)][m];
            if(m == 12){
                y ++;
                m = 1;
            }else{
                m ++;
            }
        }
        d = d + n;
        if(d == 0 && m != 1){
            m --;
            d = daytab[IsLeapYear(y)][m];
        }else if(d == 0 && m == 1){
            m = 12;
            d = daytab[IsLeapYear(y)][m];
        }
        printf("%04d-%02d-%02d\n",y,m,d);
    }

二分查找（在已经有序的情况下）

bool BinarySearch(int n,int x){
	int l = 0,r = n - 1;
	while(l <= r){
		int m = (r + l) / 2;
		if(a[m] < x){
			l = m + 1;
		}else if(a[m] > x){
			r = m - 1;
		}else{
			return true;
		}
	}
	return false;
}

sort排序，重写CMP函数

bool cmp(Student x,Student y){
	if(x.score == y.score){
		return x.num < y.num; 
	}else{
		return x.score < y.score;
	}
} 

stable_sort(&stu[0],&stu[n],cmp); //重点：sort是不稳定排序，stable_sort才是稳定排序 

快速排序

void quick_sort(int q[],int l,int r){
	if(l >= r)return ;
	int x = q[(l + r) >> 1], i = l - 1,j = r + 1;
	while(i < j){
		do i ++;while(q[i] < x);
		do j --;while(q[j] > x);
		if(i < j)swap(q[i],q[j]);
	} 
	quick_sort(q,l,j);
	quick_sort(q,j + 1,r);
}

归并排序 + 逆序数对

void merge_sort(int q[],int l,int r){
	if(l >= r)return ;
	int mid = (l + r) >> 1;
	merge_sort(q,l,mid);
	merge_sort(q,mid + 1,r);
	int i = l ,j = mid + 1,k = 0;
	
	// 左右指针进行比较 
	while(i <= mid && j <= r){
		if(q[i] < q[j])temp[k ++] = q[i ++];
		else temp[k ++] = q[j ++];
	}
	// 没有分完的 
	while(i <= mid)temp[k ++] = q[i ++];
	while(j <= r)temp[k ++] = q[j ++];
	
	for(int i = l,j = 0;i <= r;i ++,j ++)q[i] = temp[j];
}
============================================================
逆序数
while(i <= mid && j <= r){
		if(q[i] > q[j]){
			temp[k ++] = q[j ++];
			sum += mid - i + 1;
		}
		else temp[k ++] = q[i ++];
	}
cout << sum << endl;

字符串处理

int index = str.find('a');

string newstr = str.substr(startIndex,count);

向量vector map queue stack

vector<int> vectore;

vectore.push_back('i');
vectore.pop_back();

for(int i = 0;i < vectore.size();i ++)

    // map自带对键排序，进行迭代
map<int,string>::iterator it;
for(it = str.begin();it != str.end();it ++){
    cout << it->second << endl;
}

queue<Animal> cats;
dogs.front().number

stack<int> s;
s.push(i);
s.pop();
s.top();
s.empty();

最大公约数、最小公倍数

int gcd(int a,int b){
    return b ? gcd(b,a % b):a;
}

// 最小公倍数
min =  (a * b) / gcd;

最长子序列和问题 + 最长公共序列

for(int i=1;i<n;i++){
            a[i]=max(a[i],a[i-1]+a[i]);
            answer=max(answer,a[i]);
        }
        cout<<answer<<endl;

for (int i = 1; i <= a.size(); i++) {
	for (int j = 1; j <= b.size(); j++) {
		if (a[i - 1] == b[j - 1]) {
			dp[i][j] = dp[i - 1][j - 1] + 1;
		}
		else {
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
		}
	}
}

背包问题

const int N = 1010;
int n,m;//物品数量和背包容积
int v[N],w[N];
int f[N];

int main(){
    cin >> n >> m;
    
    for(int i = 1;i <= n;i ++){
        cin >> v[i] >> w[i];
    }
    
    for(int i = 1;i <= n;i ++){
        for(int j = m;j >= v[i];j --){//2种情况
            f[j] = max(f[j],f[j - v[i]] + w[i]);//背包有空间
        }
    }
    
    cout << f[m] << endl;
    return 0;
}
// 完全
for(int i = 1;i <= n;i ++){
        for(int j = v[i];j <= m;j ++){
            f[j] = max(f[j],f[j - v[i]] + w[i]);
        }
    }

进制转化

======================================================================================
    数比较小
void convert(int n,int b){
	while(n){
		a[cnt ++] = n % b;
		n = n / b;
	}
}
	cin >> n >> b;
	convert(n,b);
	for(int i = cnt - 1;i >= 0;i --)cout << a[i];
=====================================================================================
    高精度:s原字符串，m是原进制，b是转换后的进制
string convert(string s, int m, int b) {
    string ans; 
    while (!s.empty()) {
        int k = 0; // 余数
        bool leadingZero = true; // 用于去除前导零
        string temp;
        for (int i = 0; i < s.size(); i++) {
        	// 如果是字母字符（用于大于10的进制），则转换为对应的值，如'A' -> 10, 'B' -> 11
            int digit = (isdigit(s[i]) ? s[i] - '0' : s[i] - 'A' + 10);
            int t = (k * m + digit) % b;
            int quotient = (k * m + digit) / b;
            k = t;
            if (quotient != 0 || !leadingZero) {
                temp += (quotient < 10 ? quotient + '0' : quotient - 10 + 'A');
                leadingZero = false;
            }
        }
        ans += (k < 10 ? k + '0' : k - 10 + 'A');
        s = temp;
    }
    reverse(ans.begin(), ans.end());
    return ans.empty() ? "0" : ans;
}
====================================================================================
    16进制到10进制
int CharToInt(char c){
    if(c >= '0' && c <= '9')    return c - '0';
    else return c - 'A' + 10;
}
int main() {
    string str;
    while (cin >> str) {
        int x = 0;
        for(int i = 2; i < str.length(); i ++){
            x = x * 16 + CharToInt(str[i]);
        }
        cout << x << endl;
    }
    return 0;
}

单词替换（字符串）

    getline(cin,s);
	
	cin >> a >> b;
	
	for(int i = 0;i < s.size();i ++){
		int j = i;
		string word;
		// s[j]不为空格时把他加到单词序列中，相当于split 
		while(j < s.size() && s[j] != ' ')word += s[j ++];
		i = j;
		
		if(word == a)cout << b << ' ';
		else cout << word << ' ';
	}

结构体应用

// 定义一个结构体 `point`，用来存储字符的相关信息
struct point {
    int num; // 记录字符在字符串中出现的次数
    vector<int> AA; // 记录字符在字符串中出现的位置（索引）
    bool flag = false; // 用来判断是不是该字符第一次被输出
};

int main() {
    string s; // 用来存储输入的字符串
    map<char, point> mapp; // 定义一个映射，用来存储每个字符及其对应的 `point` 结构体

    while (cin >> s) { // 逐行读取输入的字符串
        // 第一次遍历字符串，统计每个字符的出现次数
        for (int i = 0; i < s.size(); i++) {
            mapp[s[i]].num++;
        }
        
        // 第二次遍历字符串，记录每个字符的出现位置（如果出现次数大于1）
        for (int i = 0; i < s.size(); i++) {
            if (mapp[s[i]].num > 1) {
                mapp[s[i]].AA.push_back(i);
            }
        }
        
        // 第三次遍历字符串，输出每个出现次数大于1且还未被输出的字符及其出现的位置
        for (int i = 0; i < s.size(); i++) {
            if (mapp[s[i]].num > 1 && mapp[s[i]].flag == false) {
                for (int j = 0; j < mapp[s[i]].AA.size(); j++) {
                    if (j == 0)
                        printf("%c:%d", s[i], mapp[s[i]].AA[j]);
                    else
                        printf(",%c:%d", s[i], mapp[s[i]].AA[j]);
                }
                cout << endl;
                mapp[s[i]].flag = true; // 标记该字符已被输出
            }
        }
    }
    return 0;
}

约瑟夫环问题

int main() {
    int n, p, m; // n多少人，p从哪里开始，m经过多少人淘汰 
    while (cin >> n >> p >> m && (n || p || m)) {
        queue<int> children;
        for (int i = 1; i <= n; ++i) {
            children.push(i);
        }
        
        // 将队列旋转到第p个小孩开始
        for (int i = 1; i < p; ++i) {
            children.push(children.front());
            children.pop();
        }
        
        while (!children.empty()) {
            // 报数到第m个
            for (int i = 1; i < m; ++i) {
                children.push(children.front());
                children.pop();
            }
            
            // 输出当前出圈的小孩编号
            cout << children.front();
            children.pop();
            if (!children.empty()) {
                cout << ",";
            }
        }
        cout << endl;
    }
    return 0;
}

素数

bool isPrime(int n)
{
    if(n == 1 || n == 0 || n < 0)return false;  
    for(int i = 2; i <= sqrt(n); i++) 
    {
        if(n % i ==0)
            return false;
    }
    return true;
}

埃氏筛法
const int maxn = 10000000;
int prime[maxn];
bool IsPrime[maxn] = {0};//0代表都是素数
void Find_Prime(){
    IsPrime[1] = 1;//1不是素数
    int pNum = 1;
    for(int i = 2; i <= maxn; i++){
        if(!IsPrime[i])
            prime[pNum++] = i;
        for(int j = i * i; j <= maxn; j += i){
            IsPrime[j] = true;
        }
    }
}

printf("%d\n", prime[k]);

质因数+约数

    int ret = 0;
    // 从 2 开始尝试每个可能的因数，直到 sqrt(n)
    for (int i = 2; i <= sqrt(n); i++) {
        // 如果 i 是 n 的一个因数
        while (n % i == 0) {
            ret++;  // 计数器加一
            n /= i;  // 用 i 除去 n 的这个因数
        }
        // 如果 n 已经被完全分解，提前退出循环
        if (n <= 1) break;
    }
    
    // 如果存在大于 sqrt(n) 的质因数，则它只能是 n 本身
    if (n > 1) ret++;
    
    return ret;
约数
int Counter(int x){
	int count = 0; 
	int i = 1;
	for(i = 1;i * i < x;i ++){
		if(x % i == 0)count += 2;
	}
	if(i * i == x) count ++;
	return count;
}

快速幂

typedef long long LL;
LL a,n;

LL ksm(LL a, LL n){
	LL ans = 1;
	while(n){
		if(n & 1)ans *= a;//如果n的最后一位是1 
		a *= a;
		n >>= 1; //二进制去掉最后一个1，*2 
	}
	return ans;
} 

int main(){
	cin >> a >> n;
	
	cout << ksm(a,n);

高精度加减乘除

// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B)
{
    if (A.size() < B.size()) return add(B, A);

    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i ++ )
    {
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }

    if (t) C.push_back(t);
    return C;
}

// C = A - B, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    for (int i = 0, t = 0; i < A.size(); i ++ )
    {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

// C = A * b, A >= 0, b >= 0
vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;

    int t = 0;
    for (int i = 0; i < A.size() || t; i ++ )
    {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();

    return C;
}

// A / b = C ... r, A >= 0, b > 0
vector<int> div(vector<int> &A, int b, int &r)
{
    vector<int> C;
    r = 0;
    for (int i = A.size() - 1; i >= 0; i -- )
    {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

KMP

// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i ++ )
{
    while (j && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) j ++ ;
    ne[i] = j;
}

// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j ++ ;
    if (j == m)
    {
        j = ne[j];
        // 匹配成功后的逻辑
    }
}

BFS走迷宫

#include <iostream>
#include <queue>

#define x first
#define y second

using namespace std;

typedef pair<int,int> PII;

const int N = 1e3 + 10;

int n,m;
int g[N][N];
int d[N][N];
int dx[4] = {1,-1,0,0},dy[4] = {0,0,1,-1};

void bfs(int u){
    queue<int> q;
    q.push({1,1});
    memset(d,-1,sizeof(d));
    d[1][1] = 0;
    while(q.size()){
        PII t = q.front();
        q.pop();
        for(int i = 0;i < 4;i ++){
            int a = t.x +dx[i];
            int b = dy[i] + t.y;
            if(a < 1 || a > n || b < 1 || b > m)continue;
            if(g[a][b] == 1)continue;
            if(d[a][b] != -1)continue;
            d[a][b] = d[t.x][t.y] + 1;
            q.push({a,b});
        }
    }
}

int main(){
    cin >> n >> m;
    
    for(int i = 0;i < n;i ++){
        for(int j = 0;j < n;j ++){
            cin >> g[i][j];
        }
    }
    
    bfs();
    
    cout << d[n][m] << endl;
    return 0;
}

N皇后问题DFS

#include <iostream>

using namespace std;

const int N = 20; // 对角线元素2n-1取20防止越界
int n;
char g[N][N]; // 存储图
bool col[N],dg[N],udg[N]; // udg副对角线 diagonal  
int cnt;
 
void dfs(int x){
	if(x == n){ // 如果找到方案的话 
		for(int i = 0;i < n;i ++){
			puts(g[i]); // puts输出二维数组 输出每一行就会自动换行
		}
		puts("");
		cnt ++;
		return; // 返回调用函数进行执行 
	}
	
	// x : 行 y : 列
	for(int y = 0;y < n;y ++){
		// 按行枚举 因为每一行都需要放皇后 相当于剪枝 
		// 判断皇后是否放在这格
		if(!col[y] && !dg[x + y] && !udg[y - x + n]){
			g[x][y] = 'Q';
			col[y] = dg[x + y] = udg[y - x + n] = true;
		
			dfs(x + 1); // 找下一行
			
			// 回溯的时候恢复现场
			col[y] = dg[x + y] = udg[y - x + n] = false;
			g[x][y] = '.'; 
		} 
	} 
}
int main(){
	cin >> n;
	
	for(int i = 0;i < n;i ++){
		for(int j =0;j < n;j ++){
			g[i][j] = '.';
		}
	} 
	
	dfs(0); // 从第一行开始找[0:下标] 

	return 0;
}

链表类型

链表反转

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *cur = head, *pre = nullptr;
        while(cur != nullptr) {
            ListNode* tmp = cur->next; // 暂存后继节点 cur.next
            cur->next = pre;           // 修改 next 引用指向
            pre = cur;                 // pre 暂存 cur
            cur = tmp;                 // cur 访问下一节点
        }
        return pre;
    }
};

回文链表

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        vector<int> vals;
        while (head != nullptr) {
            vals.emplace_back(head->val);
            head = head->next;
        }
        for (int i = 0, j = (int)vals.size() - 1; i < j; ++i, --j) {
            if (vals[i] != vals[j]) {
                return false;
            }
        }
        return true;
    }
};

环形链表

public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> seen = new HashSet<ListNode>();
        while (head != null) {
            if (!seen.add(head)) {
                return true;
            }
            head = head.next;
        }
        return false;
    }
}

排序链表

class Solution {
public:
    ListNode* sortList(ListNode* head) { 
        return mergeSort(head);
    }

    /**
     * 对给定的链表进行归并排序
    */
    ListNode* mergeSort(ListNode* head){
        // 如果链表为空或只有一个节点，无需排序直接返回
        if(!head || !head->next){
            return head;    
        }
        // 获取链表的中间节点，分别对左右子链表进行排序
        ListNode* mid = getMid(head);
        ListNode* rightSorted = mergeSort(mid->next);   // 排序右子链表
        if(mid)mid->next = nullptr;                     // 断开两段子链表
        ListNode* leftSorted = mergeSort(head);         // 排序左子链表
        return mergeTwoLists(leftSorted, rightSorted);  // 两个子链表必然有序，合并两个有序的链表
    }

    /**
     * 获取以head为头节点的链表中间节点
     * 如果链表长度为奇数，返回最中间的那个节点
     * 如果链表长度为偶数，返回中间靠左的那个节点
    */
    ListNode* getMid(ListNode* head){
        if(!head)return head;   
        ListNode* slow = head, *fast = head->next;          // 快慢指针，慢指针初始为
        while(fast != nullptr && fast->next != nullptr)     
        {
            fast = fast->next->next;    // 快指针每次移动两个节点
            slow = slow->next;          // 慢指针每次移动一个节点
        }
        return slow;    // 快指针到达链表尾部时，慢指针即指向中间节点
    }

    /**
     * 合并两个有序链表list1和list2
    */
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* dummy = new ListNode();   // 伪头节点，用于定位合并链表的头节点
        ListNode* node = dummy;             // 新链表当前的最后一个节点，初始为伪头节点
        // 直到两个链表都遍历完了，合并结束
        while(list1 != nullptr || list2 != nullptr){
            int val1 = list1 == nullptr ? 50001 : list1 -> val;   // 如果链表1已经遍历完，val1取最大值，保证链表2的节点被选择到       
            int val2 = list2 == nullptr ? 50001 : list2 -> val;   // 如果链表2已经遍历完，val2取最大值，保证链表1的节点被选择到 
            if(val1 < val2){
                // 链表1的节点值更小，加入到合并链表，并更新链表1指向的节点
                node -> next = list1;
                list1 = list1 -> next;
            }else{
                // 链表2的节点值更小，加入到合并链表，并更新链表2指向的节点
                node -> next = list2;
                list2 = list2 -> next;
            }
            node = node -> next;    // 更新合并链表当前的最后一个节点指向
        }
        return dummy -> next;       // 伪头节点的下一个节点即为合并链表的头节点
    }
};

合并两个有序链表

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == nullptr) {
            return l2;
        } else if (l2 == nullptr) {
            return l1;
        } else if (l1->val < l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

是否含有子链表

struct Link {
    int data;
    struct Link *next;
};
#include <stdio.h>
void subList(Link *a,Link *b) {
    struct Link *la = a ,*pA = la->next, *pB = b->next;
    while (pA&&pB) {
        if (pA->data==pB->data) {//相等继续对比下一个
            pA = pA->next;
            pB = pB->next;
        }
        else {
            pB = b->next;//pb从头开始与pa对比
            la = la->next;//失败一次，la往后移动一个节点
            pA = la->next;//pa从下一个节点又开始
        }
    }
    pB == NULL ? printf("true") : printf("false");//如果pb为NULL，说明已比对完成
}
int main() {
    struct Link *a, *b;
    Link *createLink(int);
    a = createLink(0);
    b = createLink(0);
    subList(a,b);
    return 0;
}

合并链表

    /*
        有两个循环单链表，链表头指针分别为h1和h2，编写一个函数将链表h2连接到h1之后，要求连接后的链表仍保持循环链表形式。
    */
    struct Link {
        int data;
        struct Link *next;
    };
    void linkTwoLists(Link *h1,Link *h2) {
        struct Link *p1 = h1->next, *p2 = h2->next;
        while (p1->next != h1) p1 = p1->next;//这里要去判断p1->next是否等于h1，进而判断出是否到达尾结点
        p1->next = p2;
        while (p2->next != h2) p2 = p2->next;
        p2->next = h1;
        free(h2);//释放h2
    }
    int main() {
        struct Link *h1, *h2,*p;
        Link *createSinLoopLink();
        h1 = createSinLoopLink();
        h2 = createSinLoopLink();
        linkTwoLists(h1,h2);
        p = h1->next;
        while (p!=h1) {
            printf("%d ",p->data);
            p = p->next;
        }
        return 0;
    }

输出链表倒数第K个结点

ListNode *findKthTail(ListNode *pHead, int K) {
	ListNode *p1(pHead), *p2(pHead);
	for(int i=0; i<K; ++i){
		p1 = p1-> next;
		if(!p1){
			return nullptr;
		}
	}

	while(p1){
		p1 = p1-> next;
		p2 = p2-> next;
	}
	return p2;
}

两数相加

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* first = new ListNode(0);  // 哑结点
        ListNode* last = first;
        int carry = 0;
        while(l1 or l2 or carry){
            // 相加
            int bitsum = 0;
            if(l1){
                bitsum += l1->val;
                l1 = l1->next;
            }
            if(l2){
                bitsum += l2->val;
                l2 = l2->next;
            }
            if(carry){
                bitsum += carry;
            }
            // 结果
            int digit = bitsum % 10;
            carry = bitsum / 10;
            // 链表存储
            ListNode* node = new ListNode(digit);
            last->next = node;
            last = node;
        }
        last = first->next;
        delete first;
        return last;
    }
};

计算循环链表中环的长度

int getLoopLength(ListNode *pHead) {
    ListNode *fast(pHead), *slow(pHead);
    while (fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow) {
            break;
        }
    }
    if (!fast || !fast->next) return -1;

    int length = 1;  // 从1开始
    while (slow->next != fast) {
        slow = slow->next;
        length++;
    }
    return length;
}

先序遍历

void preorder(TreeNode *root, vector<int> &res) {
        if (root == nullptr) {
            return;
        }
        res.push_back(root->val);
        preorder(root->left, res);
        preorder(root->right, res);
    }

    vector<int> preorderTraversal(TreeNode *root) {
        vector<int> res;
        preorder(root, res);
        return res;
    }

层序遍历

vector<vector<int>> levelOrder(TreeNode* root) {
        vector <vector <int>> ret;
        if (!root) {
            return ret;
        }

        queue <TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int currentLevelSize = q.size();
            ret.push_back(vector <int> ());
            for (int i = 1; i <= currentLevelSize; ++i) {
                auto node = q.front(); q.pop();
                ret.back().push_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }
        
        return ret;

完全二叉树的节点个数

int countNodes(TreeNode* root) {
        if(!root)return 0;
        return countNodes(root -> left) + countNodes(root -> right) + 1;
    }

每个人戴不同帽子的方案数

using LL = long long;

class Solution {
private:
    static constexpr int mod = 1000000007;
    
public:
    int numberWays(vector<vector<int>>& hats) {
        int n = hats.size();
        // 找到帽子编号的最大值，这样我们只需要求出 $f[maxhatid][2^n - 1]$ 作为答案
        int maxHatId = 0;
        for (int i = 0; i < n; ++i) {
            for (int h: hats[i]) {
                maxHatId = max(maxHatId, h);
            }
        }
        
        // 对于每一顶帽子 h，hatToPerson[h] 中存储了喜欢这顶帽子的所有人，方便进行动态规划
        vector<vector<int>> hatToPerson(maxHatId + 1);
        for (int i = 0; i < n; ++i) {
            for (int h: hats[i]) {
                hatToPerson[h].push_back(i);
            }
        }
        
        vector<vector<int>> f(maxHatId + 1, vector<int>(1 << n));
        // 边界条件
        f[0][0] = 1;
        for (int i = 1; i <= maxHatId; ++i) {
            for (int mask = 0; mask < (1 << n); ++mask) {
                f[i][mask] = f[i - 1][mask];
                for (int j: hatToPerson[i]) {
                    if (mask & (1 << j)) {
                        f[i][mask] += f[i - 1][mask ^ (1 << j)];
                        f[i][mask] %= mod;
                    }
                }
            }
        }
        
        return f[maxHatId][(1 << n) - 1];
    }
};

同构字符串

bool isIsomorphic(string s, string t) {
        if(s.size() != t.size())return false;
        unordered_map<char,char> s1;
        unordered_map<char,char> s2;
        for(int i = 0;i < s.size();i ++){
            char x = s[i],y = t[i];
            if((s1.count(x) && s1[x] != y) || (s2.count(y) && s2[y] != x))return false;
            s1[x] = y;
            s2[y] = x;
        }
        return true;
    }

因篇幅受限，如需查看完整版内容，请点击“上述的link”.