跳转至

leetcode 其他

手搓快排

int Partition(vector<int> &a,int l,int r)
{
    int pivot = a[r];
    int i=l;
    for(int j=l;j<r;j++) // 把所有比基准值小的数全部往前扔
    {
        if(a[j]<pivot)
        {
            swap(a[i],a[j]);
            i++;
        }
    }
    swap(a[i],a[r]); // 把基准值换到对应的位置
    return i;
}

void QuickSort(vector<int> &a,int l,int r)
{
    if(l>=r)return;
    int index=Partition(a,l,r);
    cout<<"index="<<index<<endl;
    QuickSort(a,l,index-1);
    QuickSort(a,index+1,r);
}

手搓堆排

先写堆移动和建堆函数 注意堆移动是从堆顶往下递归 因为上下两个元素互换 下面这个元素可能不满足堆的特性 上面这个元素肯定是满足的

void heapify(vector<int> &a,int n,int i)
{
    int largest=i;
    int l=2*i+1;
    int r=2*i+2;
    if(l<n && a[l]>a[largest])
        largest=l;
    if(r<n && a[r]>a[largest])
        largest=r;
    if(largest!=i)
    {
        swap(a[i],a[largest]);
        heapify(a,n,largest);
    }
}

void buildHeap(vector<int> &a)
{
    for(int i=(a.size()-1)/2;i>=0;i--)
    {
        heapify(a,a.size()-1,i);
    }
}

void heapSort(vector<int> &a)
{
    buildHeap(a);
    for(int i=a.size()-1;i>0;i--)
    {
        swap(a[0],a[i]);
        heapify(a,i,0);
    }
}

链表

反转链表II-92

k个一组反转链表的简单版 注意找到head和tail（反转对象的前一个和后一个） 然后反转的时候记得最后要连head和新链表的第一个 （pre一开始=tail就连上了新链表的最后一个和tail）

动态规划

买卖股票的最佳时机II-122

  • dp做法 保留有股票状态和没股票状态（dp[i][0]和dp[i][1]）
dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]);
dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]);
  • 可以理解成画个折线图 所有上升的都是利润 直接加
if(prices[i]>prices[i-1])
profit+=prices[i]-prices[i-1];

买卖股票的最佳时机III-123

dp做法 保留买一个 买1卖1 买2卖1 买2卖2四个状态（没买不用保存 利润肯定是0）

买卖股票的最佳时机IV-188

保留k+1个有股票状态和没股票状态

最长回文子序列-516

  • 直接dp 注意遍历顺序的问题 想要的是dp[0][n-1] i就从n-1开始 j从0开始 然后从[i+1] [j-1]取信息
int n=s.size();
vector<vector<int>> dp(n,vector<int>(n));
for(int i=n-1;i>=0;i--)
{
    dp[i][i]=1;
}
for(int i=n-1;i>=0;i--)
{
    for(int j=i+1;j<n;j++)
    {
        if(s[i]==s[j])
        {
            dp[i][j]=dp[i+1][j-1]+2;
        }
        else{
            dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
        }
    }
}
return dp[0][n-1];
  • 或者求原字符串和翻转后的字符串的最长公共子序列 还真就是这么回事

回溯

组合-77

放进help 然后进Back 拿出来 再进Back 就实现了放当前和不放当前

vector<vector<int>> keep;

void Back(int cur,int n,int k,vector<int> &help)
{
    if(cur>n+1)return;
    if(help.size()==k)
    {
        keep.push_back(help);
        return;
    }
    help.push_back(cur);
    Back(cur+1,n,k,help);
    help.pop_back();
    Back(cur+1,n,k,help);
}

vector<vector<int>> combine(int n, int k) {
    vector<int> help;
    Back(1,n,k,help);
    return keep;
}

二叉树

二叉树的序列化和反序列化-297

近似于层序遍历 需要给null留位置 把字符串转成树的时候也是 还有通过stringstream把string转成vector

其他

字符串转换整数(atoi)-8

注意溢出判断，前面消去前导0和判断符号

数组中重复的数据-442

  • 原地hash 尝试将每个元素放到对应的位置
vector<int> ans;
int n=nums.size();
for(int i=0;i<n;i++)
{
    while(nums[i]!=nums[nums[i]-1])
    {
        swap(nums[i],nums[nums[i]-1]);
    }
}
for(int i=0;i<n;i++)
{
    if(nums[i]-1!=i)
    {
        ans.push_back(nums[i]);
    }
}
return ans;
  • 使用正负号作标记

遍历过程中，取出当前数字，取绝对值 去下标-1找 如果是负数 说明已出现过 如果是正数 则将下标-1的数据调成负数

vector<int> ans;
int n=nums.size();
for(int i=0;i<n;i++)
{
    int x=abs(nums[i]);
    if(nums[x-1]>0)
    {
        nums[x-1]=-nums[x-1];
    }
    else{
        ans.push_back(x);
    }
}
return ans;

字符串相乘-43

  • 可以用数组来存储每一个对应位上的乘积 最后统一处理进位 注意这个题要处理前导0和乘积为0的情况
int n=num1.size();
int m=num2.size();
vector<int> v(n+m);
for(int i=0;i<n;i++)
{
    for(int j=0;j<m;j++)
    {
        int a=num1[n-i-1]-'0';
        int b=num2[m-j-1]-'0';
        v[n+m-1-(i+j)]+=a*b;
    }
}
int carry=0;
for(int i=n+m-1;i>=0;i--)
{
    v[i]+=carry;
    carry=v[i]/10;
    v[i]=v[i]%10;
}
string s="";
for(int i=0;i<n+m;i++)
{
    if(s.empty()&&v[i]==0)continue;
    s+=v[i]+'0';
}
if(s=="")s="0";
return s;