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

一. 报错原因总结

(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的最小交换次数，可以采用循环节分解的方法。以下是具体步骤和实现：

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

解决代码

#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;
}

代码解释

1. 映射构建：通过pos_map将nums1的元素与其索引关联，确定每个元素的目标位置。
2. 循环节检测：遍历nums2的元素，若未访问过，则追踪其应在的位置链，直到回到起点，形成一个循环节。每发现一个循环节，计数增加。
3. 计算交换次数：总交换次数为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;

结果：

​