头像

Haisu


访客:571

离线:3天前



Haisu
5天前

//三路快速排序O(nlogn)

template <typename T>
void __quickSort3Ways(T arr[], int l, int r){
    if(l>=r) return;
    swap(arr[l],arr[rand()%(r-l)+l])
    T v=arr[l];
    int lt=l; //arr[l+1,lt]<v
    int gt=r+1; //arr[gt,r]>v
    int i=l; //arr[lt+1,i]==v
    while(i<gt)
    {
        if(arr[i]<v)
        {
            swap(arr[i],arr[lt+1]);//小于v和等于v部分的元素交换位置
            lt++;
            i++;
        }
        else if(arr[i]>v)
        {
            swap(arr[i],arr[gt-1]);
            gt--;//i依然是未处理的元素,不动
        }
        else
        {
            i++
        }
    }
    swap(arr[l],arr[lt])
    __quickSort3Ways(arrr,l,lt-1);
    __quickSort3Ways(arr,gt,r);

}

template <typename T>
void quickSort3Ways(T arr[], int n){

    srand(time(NULL));
    __quickSort3Ways( arr, 0, n-1);
}



Haisu
6天前

//归并排序O(nlogn)

// 将arr[l...mid]和arr[mid+1...r]两部分进行归并
template<typename  T>
void __merge(T arr[], int l, int mid, int r){

    T aux[r-l+1];
    for( int i = l ; i <= r; i ++ )
        aux[i-l] = arr[i];

    int i = l, j = mid+1;
    for( int k = l ; k <= r; k ++ ){

        if( i > mid )   { arr[k] = aux[j-l]; j ++;}
        else if( j > r ){ arr[k] = aux[i-l]; i ++;}
        else if( aux[i-l] < aux[j-l] ){ arr[k] = aux[i-l]; i ++;}
        else                          { arr[k] = aux[j-l]; j ++;}
    }
}

// 递归使用归并排序,对arr[l...r]的范围进行排序
template<typename T>
void __mergeSort(T arr[], int l, int r){

    if( l >= r )
        return;

    int mid =l+ (r-l)/2;
    __mergeSort(arr, l, mid);
    __mergeSort(arr, mid+1, r);
    // 对于arr[mid] <= arr[mid+1]的情况,不进行merge
    // 对于近乎有序的数组非常有效,但是对于一般情况,有一定的性能损失
    if( arr[mid] > arr[mid+1] )
        __merge(arr, l, mid, r);
}

template<typename T>
void mergeSort(T arr[], int n){

    __mergeSort( arr , 0 , n-1 );
}



Haisu
6天前

//冒泡排序O(n^2)

template<typename T>
void bubbleSort(vector<T>& a)
{
    int n=a.size();
    for(int i=n-1;i>=0;i--)
        for(int j=0;j<i;j++)
            if(a[j+1]<a[j]) swap(a[j+1],a[j]);//冒泡,每次将最大值沉入水底
}

//选择排序O(n^2),选择排序没有提前终止的机会
template<typename T>
void selectSort(vector<T>& a)
{
    int n=a.size();
    for(int i=0;i<n;i++)
    {
        int minIndex=i;//存放最小值索引
        for(int j=i+1;j<n;j++)
            if(a[j]<a[minIndex]) minIndex=j;//寻找[i,n)区间的最小值索引
        swap(a[i],a[minIndex]);
    }
}

//插入排序O(n^2),插入排序可以提前终止,对于近乎有序的数据非常实用
template<typename T>
void insertSort(vector<T>& a)
{
    int n=a.size();
    for(int i=1;i<n;i++)
    {
        T e=a[i];
        int j;
        for(j=i;j>0&&a[j-1]>e;j--)
        {
            a[j]=a[j-1];//通过赋值来代替交换操作,可以优化代码。一个交换操作包含三次赋值操作,很花费时间
        }
        a[j]=e;

    }
}


活动打卡代码 AcWing 1048. 鸡蛋的硬度

Haisu
15天前
class Solution {
public:

    int superEggDrop(int K, int N) {
        vector<vector<int>> dp(N+1,vector<int>(K+1,0));
        for(int i=1;i<=N;i++)
            for(int j=1;j<=K;j++)
            {
                dp[i][j]=dp[i-1][j-1]+dp[i-1][j]+1;
                if(dp[i][j]>=N) return i;
            }
        return 0;
    }
};



Haisu
16天前
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> res;
        if(words.empty()) return res;
        int n=s.size(),m=words.size(),w=words[0].size();
        unordered_map<string,int> tot;
        for(auto& word:words) tot[word]++;
        for(int i=0;i<w;i++)
        {
            unordered_map<string,int> wd;
            int cnt=0;
            for(int j=i;j+w<=n;j+=w)//终点是j+w-1<n-->j+w<=n
            {
                if(j>=i+m*w)//维护窗口大小为m
                {
                    auto word=s.substr(j-m*w,w);
                    wd[word]--;
                    if(wd[word]<tot[word]) cnt--;
                }
                auto word=s.substr(j,w);
                wd[word]++;
                if(wd[word]<=tot[word]) cnt++;
                if(cnt==m) res.push_back(j-(m-1)*w);//j-m*w+w
            }
        }
        return res;
    }
};


活动打卡代码 LeetCode 29. 两数相除

Haisu
16天前
class Solution {
public:
    int divide(int x, int y) {
        typedef long long LL;
        vector<LL>exp;
        bool is_minus=false;
        if(x<0&&y>0||x>0&&y<0) is_minus=true;
        LL a=abs(x),b=abs(y);
        for(LL i=b;i<=a;i=i+i) exp.push_back(i);
        // b 2b 4b 8b
        LL res=0;
        for(int i=exp.size()-1;i>=0;i--)
        {
            if(a>=exp[i])
            {
                a-=exp[i];
                cout<<exp[i]<<endl;
                cout<<i<<endl;
                cout<<(1LL<<i)<<" ";
                res+=1LL<<i;
            }
        }
        if(is_minus) res=-res;
        if(res>INT_MAX||res<INT_MIN) res=INT_MAX;
        return res;
    }
};


活动打卡代码 LeetCode 28. 实现 strStr()

Haisu
17天前
class Solution {
public:
    int strStr(string s, string p) {
        if(p.empty()) return 0;
        int n=s.size(), m=p.size();
        s=' '+s,p=' '+p;
        vector<int> next(m+1);
        for(int i=2,j=0;i<=m;i++)
        {
            while(j&&p[i]!=p[j+1]) j=next[j];
            if(p[i]==p[j+1]) j++;
            next[i]=j;
        }
        for(int i=1,j=0;i<=n;i++)
        {
            while(j&&s[i]!=p[j+1]) j=next[j];
            if(s[i]==p[j+1]) j++;
            if(j==m) return (i-m);
        }
        return -1;
    }
};


活动打卡代码 LeetCode 27. 移除元素

Haisu
17天前
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int k=0;
        for(int i=0;i<nums.size();i++)
        {
            if(nums[i]!=val) nums[k++]=nums[i];
        }
        return k;

    }
};



Haisu
17天前
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int k=0;
        for(int i=0;i<nums.size();i++)
        {
            if(!i||nums[i]!=nums[i-1]) nums[k++]=nums[i];
        }
        return k;

    }
};



Haisu
17天前
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        auto dummy=new ListNode(-1);
        dummy->next=head;
        for(auto p=dummy;;)
        {
            auto q=p;
            for(int i=0;i<k&&q;i++) q=q->next;
            if(!q) break;
            auto a=p->next,b=a->next;
            for(int i=0;i<k-1;i++)
            {
                auto c=b->next;
                b->next=a;
                a=b,b=c;
            }
            auto c=p->next;
            p->next=a,c->next=b;
            p=c;
        }
        return dummy->next;

    }
};