头像

阿梁




离线:8小时前



阿梁
9小时前

二分递归版做法

时间复杂度:O(log(m+n))

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int tot=nums1.size()+nums2.size();
        if(tot%2==0){
            int left=find(nums1,0,nums2,0,tot/2);
            int right=find(nums1,0,nums2,0,tot/2+1);
            return (left+right)/2.0;
        }else{
            return find(nums1,0,nums2,0,tot/2+1);
        }
    }

    int find(vector<int>& nums1,int i,vector<int>& nums2,int j,int k){
        if(nums1.size()-i>nums2.size()-j) return find(nums2,j,nums1,i,k);

        if(k==1){
            if(nums1.size()==i) return nums2[j];
            else return min(nums1[i],nums2[j]);
        }
        if(nums1.size()==i) return nums2[j+k-1];

        int si=min((int)nums1.size(),i+k/2),sj=j+k-k/2;
        if(nums1[si-1]>nums2[sj-1]) return find(nums1,i,nums2,sj,k-sj+j);
        else return find(nums1,si,nums2,j,k-si+i);
    }
};

双指针做法

不知道为什么这个做法比二分递归版本更慢(在LeetCode)

  • 和合并两个有序链表类似
  • 时间复杂度为O(n+m)
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        vector<int> a;
        int n=nums1.size(),m=nums2.size();
        int i=0,j=0;
        while(i<n&&j<m){
            if(nums1[i]<=nums2[j]) a.push_back(nums1[i++]);
            else a.push_back(nums2[j++]); 
        }

        while(i<n) a.push_back(nums1[i++]);
        while(j<m) a.push_back(nums2[j++]);

        int l=0,r=a.size()-1;
        int len=a.size();

        double res=0.0;

        if(len%2==0) res=(double)(a[l+r>>1]+a[l+r+1>>1])/2.0;
        else res=(double) a[l+r>>1];

        return res; 
    }
};



阿梁
10小时前

双指针算法

  • 利用前指针的不会往前走做优化
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char,int> heap;
        int res=0;
        for(int i=0,j=0;i<s.size();i++)
        {
            heap[s[i]]++;
            while(heap[s[i]]>1) heap[s[j++]]--;
            res=max(res,i-j+1);
        }

        return res;
    }
};



阿梁
13小时前
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=510,INF=0x3f3f3f3f;

int n,m;
int g[N][N];
int dist[N];
bool st[N];

int prim()
{
    memset(dist,0x3f,sizeof dist);
    int res=0;

    for(int i=0;i<n;i++)
    {
        int t=-1;
        for(int j=1;j<=n;j++)
        {
            if(!st[j]&&(t==-1||dist[t]>dist[j]))
                t=j;
        }

        if(i&&dist[t]==INF) return INF;
        if(i) res+=dist[t];

        for(int j=1;j<=n;j++)
        {
            dist[j]=min(dist[j],g[t][j]);
        }

        st[t]=true;
    }

    return res;
}

int main()
{
    scanf("%d%d",&n,&m);

    memset(g,0x3f,sizeof g);

    while(m--)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);

        g[u][v]=g[v][u]=min(g[u][v],w);
    }

    int t=prim();

    if(t==INF) puts("impossible");
    else printf("%d",t);

    return 0;
}


活动打卡代码 AcWing 854. Floyd求最短路

阿梁
14小时前
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=210,INF=1e9;

int n,m,Q;
int d[N][N];

void floyd()
{
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}

int main()
{
    scanf("%d%d%d",&n,&m,&Q);

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i==j) d[i][j]=0;
            else d[i][j]=INF;

    while(m--)
    {
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);

        d[a][b]=min(d[a][b],w);
    }

    floyd();

    while(Q--)
    {
        int x,y;
        scanf("%d%d",&x,&y);

        if(d[x][y]>INF/2) puts("impossible");
        else printf("%d\n",d[x][y]);
    }

    return 0;
}


活动打卡代码 AcWing 852. spfa判断负环

阿梁
16小时前
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

const int N=100010;

int n,m;
int h[N],e[N],ne[N],w[N],idx;
int dist[N],cnt[N];
bool st[N];
queue<int> q;

void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

bool spfa()
{
    for(int i=1;i<=n;i++)
    {
        q.push(i);
        st[i]=true;
    }

    while(q.size())
    {
        int t=q.front();
        q.pop();
        st[t]=false;

        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[t]+w[i])
            {
                dist[j]=dist[t]+w[i];
                cnt[j]=cnt[t]+1;
                if(cnt[j]>=n) return true;
                if(!st[j])
                {
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }

    return false;
}

int main()
{

    scanf("%d%d",&n,&m);

    memset(h,-1,sizeof h);

    while(m--)
    {
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        add(a,b,w);
    }

    if(spfa()) puts("Yes");
    else puts("No");

    return 0;
}


活动打卡代码 AcWing 851. spfa求最短路

阿梁
17小时前
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

const int N=100010;

int n,m;
int h[N],e[N],ne[N],w[N],idx;
int dist[N];
bool st[N];
queue<int> q;

void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

int spfa()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    q.push(1);
    st[1]=true;

    while(q.size())
    {
        int t=q.front();
        q.pop();
        st[t]=false;

        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[t]+w[i])
            {
                dist[j]=dist[t]+w[i];
                if(!st[j])
                {
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }

    if(dist[n]==0x3f3f3f3f) return -1;
    else return dist[n];
}

int main()
{

    scanf("%d%d",&n,&m);

    memset(h,-1,sizeof h);

    while(m--)
    {
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        add(a,b,w);
    }

    int t=spfa();

    if(t==-1) puts("impossible");
    else printf("%d\n",t);

    return 0;
}


活动打卡代码 LeetCode 2. 两数相加

阿梁
1天前

解题思路:

  • 模拟手动加法的步骤,用一个数记一下每一位的进位
  • 从前往后遍历两个链表,直到所有链表遍历完并且进位为0
  • 用一个哑节点作为返回点
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        auto dummy=new ListNode(-1),cur=dummy;
        int t=0;
        while(l1||l2||t)
        {
            if(l1) t+=l1->val,l1=l1->next;
            if(l2) t+=l2->val,l2=l2->next;
            cur=cur->next=new ListNode(t%10);
            t/=10;
        }

        return dummy->next;
    }
};


活动打卡代码 LeetCode 1. 两数之和

阿梁
1天前

解题思路:
- 这个数组,在遍历的同时判断当前值前面是否有个一个数与自己相加等于target
- 历循环的时候判断一下hash表里面是否含有target-nums[i],如果有就直接返回,如果没有就把当前值放到hash表中

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> heap;
        for(int i=0;i<nums.size();i++)
        {
            int r=target-nums[i];
            if(heap.count(r)) return {heap[r],i};//count()  返回某一个数的个数
            heap[nums[i]]=i;
        }

        return {};
    }
};



阿梁
1天前
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=510,M=10010;

int n,m,k;

int dist[N],backup[N];

struct Edge
{
    int a,b,w;
}edge[M];

int Bellman_ford()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;

    for(int i=0;i<k;i++)
    {
        memcpy(backup,dist,sizeof dist);

        for(int j=0;j<m;j++)
        {
            int a=edge[j].a,b=edge[j].b,w=edge[j].w;
            dist[b]=min(dist[b],backup[a]+w);
        }
    }

    if(dist[n]>0x3f3f3f3f/2) return -1;
    else return dist[n];
}

int main()
{
    scanf("%d%d%d",&n,&m,&k);

    for(int i=0;i<m;i++)
    {
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        edge[i].a=a,edge[i].b=b,edge[i].w=w;
    }

    int t=Bellman_ford();

    if(t==-1) puts("impossible");
    else printf("%d\n",t);

    return 0;
}




阿梁
1天前
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>

using namespace std;

typedef pair<int,int> PII;

const int N=1000010;
int n,m;
int h[N],e[N],ne[N],w[N],idx;
int dist[N];
bool st[N];

void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

int dijkstra()
{
    memset(dist,0x3f,sizeof dist);

    priority_queue<PII,vector<PII>,greater<PII>> q;

    dist[1]=0;
    q.push({0,1});

    while(q.size())
    {
        auto t=q.top();
        q.pop();
        int ver=t.second,distance=t.first;

        if(st[ver]) continue;
        st[ver]=true;

        for(int i=h[ver];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>distance+w[i])
            {
                dist[j]=distance+w[i];
                q.push({dist[j],j});
            }
        }
    }

    if(dist[n]==0x3f3f3f3f) return -1;
    else return dist[n];
}

int main()
{
    scanf("%d%d",&n,&m);

    memset(h,-1,sizeof h);

    for(int i=0;i<m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }

    printf("%d\n",dijkstra());

    return 0;
}