面经-刷题语法和一些经典算法题思路

语法

分割分号

stringstream ss(s);

while(getline(ss,t,’;’))

正则

​ string temp = t.substr(1);

​ if(regex_match(temp, regex(“[0-9]*”))){

}

cout输出格式

cout << setiosflags(ios::fixed);

cout.precision(2);

算法

归并排序

分割（Divide）

将数组递归地分成两半，直到每个子数组只包含一个元素

单个元素被认为是已排序的

合并（Merge）

将两个已排序的子数组合并成一个更大的有序数组

使用双指针法比较和合并

原始数组: [38, 27, 43, 3, 9, 82, 10]

分割过程：
[38, 27, 43, 3, 9, 82, 10]
↙                  ↘
[38, 27, 43, 3]    [9, 82, 10]
↙        ↘         ↙     ↘
[38, 27]  [43, 3]  [9]  [82, 10]
↙    ↘    ↙    ↘       ↙     ↘
[38] [27] [43] [3]     [82]  [10]

合并过程：
[27, 38]  [3, 43]  [9]  [10, 82]
   ↘        ↙         ↘     ↙
[3, 27, 38, 43]     [9, 10, 82]
         ↘              ↙
    [3, 9, 10, 27, 38, 43, 82]

时间复杂度

最好情况：O(n log n)

最坏情况：O(n log n)

平均情况：O(n log n)

空间复杂度

O(n) - 需要额外的临时数组

稳定性

稳定排序 - 相等元素的相对位置不变

二分查找

int Binary(vector<int> ary, int target){
    int n = ary.size();
    if(n==0) return -1;
    int left = 0, right = n - 1;
    int mid;
    while(left<=right){
        mid = (left + right) / 2;
        int m = ary[mid];
        if(m==target) return mid;
        else if(m<target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

快排

#include<iostream>
using namespace std;
int n,a[1000001];
void qsort(int l,int r)//应用二分思想
{
    int mid=a[(l+r)/2];//中间数
    int i=l,j=r;
    do{
        while(a[i]<mid) i++;//查找左半部分比中间数大的数
        while(a[j]>mid) j--;//查找右半部分比中间数小的数
        if(i<=j)//如果有一组不满足排序条件（左小右大）的数
        {
            swap(a[i],a[j]);//交换
            i++;
            j--;
        }
    }while(i<=j);//这里注意要有=
    if(l<j) qsort(l,j);//递归搜索左半部分
    if(i<r) qsort(i,r);//递归搜索右半部分
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    qsort(1,n);
    for(int i=1;i<=n;i++) cout<<a[i]<<" ";
}

椭球公式

x2 / a2+y2 / b2+z2 / c2=1。

当x^2/a^2+y^2/b^2+z^2/c^2<1时　则点(x,y,z)在内部

反转链表

删除导数第N个数

总体很简单，有两个特殊的需要注意，第一是只有一个数或者零个数，第二个是需要删除的是第一个数

if(!head || !head -> next) return NULL;//判断是否只有一个数或者零个数
ListNode* first = head;
ListNode* second = head;
for(int i = 0;i<n;i++) second = second->next;
if(!second) return head->next; //判断是否要删的是第一个数，因为你要是走完发现走到了尽头就说明倒数第N个数是开头，那么久直接返回head->next就行，用源代码会有bug

高精度加法

一个很妙的不用判断进位并且前面0的处理方法

while(n1>=0 || n2>=0 || jw){
    int x = n1 >= 0 ? num1[n1] - '0' : 0;
    int y = n2 >= 0 ? num2[n2] - '0' : 0;

n变成1

n如果是奇数就变成n-1或者n+1，如果是偶数就变成n/2

用动态规划

vector<int> dp;
dp[0] = 0;
dp[1] = 0;
for(int i = 2;i<n;i++){
    if(i%2==0) dp[i] = dp[i/2] +1;
    else dp[i] = min(dp[i-1],dp[i+1]) + 1;
}
return dp[n];

寻找第k大

（1）基于快排，每轮划分选择一个基准值，把比它小的数放在左边，大的放在右边，函数返回基准值的位置，如果该位置恰好是K，就说明了这是第K小的数，所以从0-基准值位置的数是序列中的前K小数。若返回基准值的位置小于或者大于K，再进行相应调整：如果返回的基准值大于k，在基准值左边序列查找，如果小于，在基准值右边进行查找。递归地进行快排，直到返回的结果=K；时间复杂度为O(n)。

（2）基于堆排序，求前K个最小的数用最大顶堆，求前K个最大的数用最小顶堆。以最大顶堆为例，要维护一个大小为K的顶堆，就是先将K个数插入堆中，随后，对每一个数，与堆顶的最大元素比较，若该数比堆顶元素小，则替换掉堆顶元素，然后调整堆，若大于堆顶元素，则不管，那么将所有元素比较和插入后，该堆维护的就是最小的K个数。求前k小的数用最大顶堆的目的(原理）：这是一种局部淘汰的思想，尽量的把小的数都放在堆中，最后使得即使堆中最大的数，也比外界的所有数都小，就达到了目的。

洗牌算法

遍历1到n，生成一个随机数，然后把当前位置的和生成位置的交换，复杂度O（n）

二叉树镜像

图如何判断是否有环

DFS

DFS方法的核心思想是：如果在DFS遍历过程中，遇到一个正在访问的节点，就说明存在环。

拓扑排序

不断删掉入度为0的顶点，删的时候记得减掉对应顶点的入度，加入能全部删完，就说明没有环，如果删不完，就说明肯定有环

示例图（有环）：
0 → 1 → 2
    ↑   ↓
    └── 3

每个顶点的初始入度：
0: 0 (没有边指向0)
1: 2 (0和3指向1)
2: 1 (1指向2)
3: 1 (2指向3)

1. 初始状态：
入度数组：[0, 2, 1, 1]
将入度为0的顶点(0)加入队列

2. 处理顶点0：
- 访问0，计数=1
- 减少其指向的顶点的入度：
  1的入度减1：[0, 1, 1, 1]
- 没有新的入度为0的顶点

3. 队列为空，但是：
- 还有未访问的顶点(1,2,3)
- 它们的入度都不为0
- 访问计数(1) < 顶点总数(4)

结果：存在环！

抛硬币决定输赢

谁先正面就赢，求先手赢的概率

做法一

无穷级数求和：sum(0-n) :[(1/4)^ n * 1/2]

取巧

设赢的概率是x，那么后者赢的概率是x*0.5，所以(x + 0.5x) = 1

可以得到x = 2/3

实现一个共享指针类

#include <iostream>

template <typename T>
class SharedPtr {
private:
    T* res;               // 指向资源的原始指针
    int* refCount;        // 引用计数指针

public:
    // 构造函数
    explicit SharedPtr(T* ptr = nullptr) : res(ptr), refCount(new int(1)) {
        if (ptr == nullptr) {
            *refCount = 0;
        }
    }

    // 拷贝构造函数
    SharedPtr(const SharedPtr<T>& other) : res(other.res), refCount(other.refCount) {
        ++(*refCount);  // 增加引用计数
    }

    // 赋值运算符
    SharedPtr<T>& operator=(const SharedPtr<T>& other) {
        if (this != &other) {  // 防止自我赋值
            // 先减少原有引用计数
            if (--(*refCount) == 0) {
                delete res;
                delete refCount;
            }

            // 复制新的资源
            res = other.res;
            refCount = other.refCount;
            ++(*refCount);  // 增加引用计数
        }
        return *this;
    }

    // 析构函数
    ~SharedPtr() {
        if (--(*refCount) == 0) {
            delete res;
            delete refCount;
        }
    }

    // 获取底层资源
    T* get() const {
        return res;
    }

    // 解引用操作符
    T& operator*() const {
        return *res;
    }

    // 箭头操作符
    T* operator->() const {
        return res;
    }

    // 返回引用计数
    int use_count() const {
        return *refCount;
    }

    // 检查是否为空
    bool is_null() const {
        return res == nullptr;
    }
};

class Resource {
public:
    void show() {
        std::cout << "Resource in use!" << std::endl;
    }
};

int main() {
    // 创建一个SharedPtr指向Resource对象
    SharedPtr<Resource> p(new Resource());  // 1
    std::cout << "Reference count after p creation: " << p.use_count() << std::endl;

    // 拷贝构造，p2指向与p相同的资源
    SharedPtr<Resource> p2 = p;  // 2
    std::cout << "Reference count after p2 creation: " << p.use_count() << std::endl;

    // 使用共享的资源
    p->show();
    p2->show();

    // 由于p2和p共享同一个资源，引用计数会在析构时自动减少
    return 0;  // 当p和p2超出作用域时，资源会被释放
}

实现一个吃鸡空投算法

要求平均，概率均等，每个点都能去到

如何均匀分布点？

为了保证点在整个圆形区域内均匀分布，我们必须确保面积上是均匀的，而不是在半径上直接均匀分布。这样做可以避免靠近圆心的地方密度过高，靠近边缘的地方密度过低。

均匀分布的正确方法

为了确保在圆内均匀分布，应该使用以下方法生成随机半径：

生成随机数 𝑢 在 0 到 1 之间。

计算实际半径 𝑟 为 根号u * radius。这样可以确保在圆内的每个区域都有相同的概率被选中。