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

语法

分割分号

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);

算法

二分查找

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）