当前位置：首页 > backend >正文

leetcode报错原因总结需要背下来的程序片 [更新中]

backend 2025/5/19 7:49:56

一. 报错原因总结

(1) 越界错误

Line 1240: Char 9: runtime error: addition of unsigned offset to 0x7f6676300030 overflowed to 0x7f667630002f (basic_string.h)SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/13/../../../../include/c++/13/bits/basic_string.h:1249:9

C++13的string类型在使用.back()方法的时候不会考虑string是否为空，如果string为空的话会有越界错误
在这里插入图片描述

二. 需要背诵的程序片

(1) 排序算法 + lambda表达式

vector<int> v;
//需要对v从大到小排列
sort(v.begin(), v.end(), [](int a, int b){return a>b;})

(2) 整数转二进制字符串

string Binary(int x){sring result;while(x){result.push_back('0' + (x & 1));x >> 1;}reverse(result.begin(), result.end());return result;
}

(3) 阶乘factorial

Although there is no C function defined specifically for computing factorials, C math library lets you compute gamma function. Since Г(n) = (n-1)! for positive integers, using tgamma of i+1 yields i!.
在这里插入图片描述

(4) 最小交换次数问题

要计算将随机排列的nums2通过两两交换还原为nums1的最小交换次数，可以采用循环节分解的方法。以下是具体步骤和实现：

建立映射：记录nums1中每个元素的目标位置，因为nums1是最终要还原的顺序。
寻找循环节：遍历nums2中的元素，通过映射找到每个元素应在的位置，形成环（循环节）。每个环的长度为k，则需要交换k-1次。
计算总次数：所有环的交换次数之和等于总元素数减去循环节的数量。

解决代码

#include <vector>
#include <unordered_map>
using namespace std;int minSwapsToRestore(vector<int>& nums1, vector<int>& nums2) {int n = nums1.size();unordered_map<int, int> pos_map;  // 记录nums1中元素的目标位置for (int i = 0; i < n; ++i) {pos_map[nums1[i]] = i;}vector<bool> visited(n, false);int cycles = 0;for (int i = 0; i < n; ++i) {if (!visited[i]) {int j = i;while (!visited[j]) {visited[j] = true;// 当前元素在nums2中的位置j，其正确位置是pos_map[nums2[j]]j = pos_map[nums2[j]];}cycles++;}}return n - cycles;
}

代码解释

映射构建：通过pos_map将nums1的元素与其索引关联，确定每个元素的目标位置。
循环节检测：遍历nums2的元素，若未访问过，则追踪其应在的位置链，直到回到起点，形成一个循环节。每发现一个循环节，计数增加。
计算交换次数：总交换次数为n - cycles，其中n是元素总数，cycles是循环节数量。每个循环节需要k-1次交换，总次数即所有(k-1)之和，等价于n - cycles。

示例

若nums1 = [1,2,3,4]，nums2 = [4,3,2,1]：
- 循环节为4→3→1→0→4（索引0对应元素4，其正确位置是3，依此类推），形成1个循环节。
- 最小交换次数为4 - 1 = 3次。

该方法时间复杂度为O(n)，空间复杂度O(n)，高效解决最小交换次数问题。

三. 经常用到的常量认知

(1) int32,int64,long,long long,float,double对应的数据的最大和最小值分别是多大：

  std::cout << setiosflags(ios::scientific) << "INT32_MAX: " << (float)INT32_MAX<< std::endl;std::cout << setiosflags(ios::scientific) << "INT32_MIN: " << (float)INT32_MIN<< std::endl;std::cout << setiosflags(ios::scientific) << "INT64_MAX: " << (float)INT64_MAX<< setiosflags(ios::scientific) << std::endl;std::cout << setiosflags(ios::scientific) << "INT64_MIN: " << (float)INT64_MIN<< std::endl;std::cout << setiosflags(ios::scientific) << "LONG_MAX: " << (float)LONG_MAX<< std::endl;std::cout << setiosflags(ios::scientific) << "LONG_MIN: " << (float)LONG_MIN<< std::endl;std::cout << setiosflags(ios::scientific)<< "LONG_LONG_MAX: " << (float)LONG_LONG_MAX << std::endl;std::cout << setiosflags(ios::scientific)<< "LONG_LONG_MIN: " << (float)LONG_LONG_MIN << std::endl;std::cout << setiosflags(ios::scientific)<< "FLOAT_MAX: " << std::numeric_limits<float>::max() << std::endl;std::cout << setiosflags(ios::scientific)<< "FLOAT_MIN: " << std::numeric_limits<float>::min() << std::endl;std::cout << setiosflags(ios::scientific)<< "DOUBLE_MAX: " << std::numeric_limits<double>::max()<< std::endl;std::cout << setiosflags(ios::scientific)<< "DOUBLE_MIN: " << std::numeric_limits<double>::min()<< std::endl;std::cout << setiosflags(ios::scientific)<< "DOUBLE_T_MAX: " << std::numeric_limits<double_t>::max()<< std::endl;std::cout << setiosflags(ios::scientific)<< "DOUBLE_T_MIN: " << std::numeric_limits<double_t>::min()<< std::endl;