头像

Rh.




离线:1天前


最近来访(8)
用户头像
spike_1
用户头像
RyanMoriarty
用户头像
妮可_
用户头像
yunyun117
用户头像
毓秀清风
用户头像
pfco


Rh.
16天前

思路

  • 首先制造一个虚拟节点hh,指向题中的头结点,为了防止样例2的特殊情况
  • 然后利用双指针查找重复元素的区间[i, j)(这里是包括j的,j是重复区间后第一个不重复的节点),然后设置一个新的指针ih,一直在i指针的前面。这样若存在重复区间,ih->next = j
  • 最后返回hh->next

Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplication(ListNode* head) {
        ListNode *hh = new ListNode(-1);
        ListNode *ih = hh;
        hh->next = head;
        for(auto i = head, j = head; i != NULL; )
        {
            while(j != NULL && j->val == i->val) j = j->next;
            if(i->next != j)//说明存在重复区间
            {
                ih->next = j;
                i = j;
            }
            else
            {
                i = j;
                ih = ih->next;
            }
        }
        return hh->next;
    }
};



Rh.
18天前

题目链接 AcWing 17

头结点的意思不应该是指向的下一个结点才是第一个结点吗,而头结点是不存元素的,为什么AC的代码,是先存头结点的元素

我的代码:

class Solution {
public:
    vector<int> printListReversingly(ListNode* head) {
        vector<int> res;
        while(head != NULL)
        {
            head = head->next;
            res.push_back(head->val);  
        }
        return vector<int>(res.rbegin(), res.rend());
    }
};


活动打卡代码 AcWing 2. 01背包问题

Rh.
8个月前

二维数组

import java.io.*;
public class Main{
    static int N=1010;
    static int n,m;
    static int []V=new int[N];
    static int []W=new int[N];
    static int [][]f=new int [N][N];
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String[]str=br.readLine().split(" ");
        n=Integer.parseInt(str[0]);
        m=Integer.parseInt(str[1]);
        for(int i=1;i<=n;i++){
            str=br.readLine().split(" ");
            V[i]=Integer.parseInt(str[0]);
            W[i]=Integer.parseInt(str[1]);
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(j<V[i])f[i][j]=f[i-1][j];
                else f[i][j]=Math.max(f[i-1][j],f[i-1][j-V[i]]+W[i]);
            }
        }
        System.out.println(f[n][m]);
        br.close();

    }
}

优化后一维数组

import java.io.*;
public class Main {
    static int N=1010;
    static int n,m;
    static int []v=new int [N];//体积
    static int []w=new int [N];//价值
    static int []f=new int [N];//状态f[j]定义:NN 件物品,背包容量j下的最优解。
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String[]str=br.readLine().split(" ");
        n=Integer.parseInt(str[0]);
        m=Integer.parseInt(str[1]);
        for(int i=1;i<=n;i++) {
            str=br.readLine().split(" ");
            v[i]=Integer.parseInt(str[0]);
            w[i]=Integer.parseInt(str[1]);
        }

        for(int i=1;i<=n;i++) {
            for(int j=m;j>=v[i];j--) {
                f[j]=Math.max(f[j],f[j-v[i]]+w[i]);
            }
        }
        System.out.println(f[m]);
        br.close();
    }
}



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

Rh.
8个月前
import java.io.*;
public class Main{
    static int N=210;
    static int n,m,k;
    static int max=0x3f3f3f3f;
    static int g[][]=new int [N][N];
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        String[]str=br.readLine().split(" ");
        n=Integer.parseInt(str[0]);
        m=Integer.parseInt(str[1]);
        k=Integer.parseInt(str[2]);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(i==j)g[i][j]=0;
                else g[i][j]=max;
            }
        }
        while(m-->0){
            str=br.readLine().split(" ");
            int a=Integer.parseInt(str[0]);
            int b=Integer.parseInt(str[1]);
            int c=Integer.parseInt(str[2]);
            g[a][b]=Math.min(g[a][b],c);
        }
        floyd();
        while(k-->0){
            str=br.readLine().split(" ");
            int x=Integer.parseInt(str[0]);
            int y=Integer.parseInt(str[1]);
            if(g[x][y]>max/2)bw.write("impossible\n");
            else bw.write(String.valueOf(g[x][y])+"\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
    public static void floyd(){
        for(int k=1;k<=n;k++){
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    g[i][j]=Math.min(g[i][j],g[i][k]+g[k][j]);
                }
            }
        }
    }
}


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

Rh.
8个月前
import java.io.*;
import java.util.*;
public class Main{
    static int N=2010,M=10010;
    static int n,m;
    static int dist[]=new int[N];
    static boolean[]st=new boolean[N];

    static int h[]=new int[N];
    static int e[]=new int [M];
    static int ne[]=new int [M];
    static int w[]=new int [M];
    static int idx;

    static int cnt[]=new int [N];
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String[]str=br.readLine().split(" ");
        n=Integer.parseInt(str[0]);
        m=Integer.parseInt(str[1]);
        Arrays.fill(h,-1);
        while(m-->0){
            str=br.readLine().split(" ");
            int a=Integer.parseInt(str[0]);
            int b=Integer.parseInt(str[1]);
            int c=Integer.parseInt(str[2]);
            add(a,b,c);
        }
        if(spfa())System.out.println("Yes");
        else System.out.println("No");
        br.close();
    }
    public static boolean spfa(){
       Queue<Integer>queue=new LinkedList<>();
       for(int i=1;i<=n;i++){
           queue.add(i);
           st[i]=true;
       }
       while(!queue.isEmpty()){
           int t=queue.poll();
           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]){
                       queue.add(j);
                       st[j]=true;
                   }
               }
           }
       }
       return false;
    }
    public static void add(int a,int b,int c){
        e[idx]=b;
        w[idx]=c;
        ne[idx]=h[a];
        h[a]=idx++;
    }
}


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

Rh.
8个月前
import java.io.*;
import java.util.*;
public class Main{
    static int N=100010;
    static int max=0x3f3f3f3f;
    static int n,m;
    static int q[]=new int[N];
    static int dist[]=new int [N];
    static boolean[]st=new boolean[N];

    static int []h=new int[N];
    static int []e=new int[N];
    static int []ne=new int [N];
    static int []w=new int [N];
    static int idx,hh,tt;
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String[]str=br.readLine().split(" ");
        n=Integer.parseInt(str[0]);
        m=Integer.parseInt(str[1]);
        Arrays.fill(h,-1);
        while(m-->0){
            str=br.readLine().split(" ");
            int a=Integer.parseInt(str[0]);
            int b=Integer.parseInt(str[1]);
            int c=Integer.parseInt(str[2]);
            add(a,b,c);
        }
        spfa();
        br.close();
    }
    public static void spfa(){
        hh=0;tt=-1;
        Arrays.fill(dist,max);
        q[++tt]=1;
        dist[1]=0;
        st[1]=true;
        while(hh<=tt){
            int t=q[hh++];
            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[++tt]=j;
                        st[j]=true;
                    }
                }
            }
        }
        if(dist[n]==max)System.out.println("impossible");
        else System.out.println(dist[n]);
    }
    public static void add(int a,int b,int c){
        e[idx]=b;
        w[idx]=c;
        ne[idx]=h[a];
        h[a]=idx++;
    }
}



Rh.
8个月前
import java.io.*;
import java.util.*;
public class Main{
    static int N=510,M=10010;
    static int dist[]=new int [N];
    static Node[]edgs=new Node[M];
    static int back[]=new int [N];
    static int n,m,k,max=0x3f3f3f3f;
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String[]str=br.readLine().split(" ");
        n=Integer.parseInt(str[0]);
        m=Integer.parseInt(str[1]);
        k=Integer.parseInt(str[2]);
        for(int i=0;i<m;i++){
            str=br.readLine().split(" ");
            int a=Integer.parseInt(str[0]);
            int b=Integer.parseInt(str[1]);
            int c=Integer.parseInt(str[2]);
            edgs[i]=new Node(a,b,c);
        }
        ballmen_ford();
        br.close();
    } 
    public static void ballmen_ford(){
        Arrays.fill(dist,max);
        dist[1]=0;
        while(k-->0){
            back=Arrays.copyOf(dist,n+1);
            for(int i=0;i<m;i++){
                Node edg=edgs[i];
                int a=edg.a;
                int b=edg.b;
                int c=edg.c;
                dist[b]=Math.min(dist[b],back[a]+c);
            }
        }
        if(dist[n]>max/2)System.out.println("impossible");
        else System.out.println(dist[n]);
    }
}

class Node{
    int a,b,c;
    public Node(int a,int b,int c){
        this.a=a;
        this.b=b;
        this.c=c;
    }
}



Rh.
8个月前
import java.io.*;
import java.util.*;
public class Main{
    static int N=510;
    static int g[][]=new int [N][N];
    static int dist[]=new int [N];
    static boolean st[]=new boolean[N];
    static int n,m;
    static int max=50000000;
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String[]str=br.readLine().split(" ");
        n=Integer.parseInt(str[0]);
        m=Integer.parseInt(str[1]);
        for(int i=1;i<=n;i++)Arrays.fill(g[i],max);
        while(m-->0){
            str=br.readLine().split(" ");
            int a=Integer.parseInt(str[0]);
            int b=Integer.parseInt(str[1]);
            int c=Integer.parseInt(str[2]);
            g[a][b]=Math.min(g[a][b],c);
        }
        System.out.println(dijkstra());
        br.close();
    }
    public static int  dijkstra(){
        Arrays.fill(dist,max);
        dist[1]=0;
        for(int i=1;i<n;i++){
            int t=-1;
            for(int j=1;j<=n;j++){
                if(!st[j]){
                    if(t==-1||dist[j]<dist[t]){
                        t=j;
                    }
                }
            }
            st[t]=true;
            for(int j=1;j<=n;j++){
                if(dist[j]>dist[t]+g[t][j])dist[j]=dist[t]+g[t][j];
            }
        }
        if(dist[n]==max)return -1;
        else return dist[n];
    }
}



Rh.
8个月前
import java.io.*;
public class Main{
    static int N=100010;
    static int q[]=new int [N];
    static int d[]=new int [N];//入度
    static int hh,tt;
    static int h[]=new int [N];
    static int e[]=new int [N];
    static int ne[]=new int [N];
    static int idx,n,m;
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        String[]str=br.readLine().split(" ");
        n=Integer.parseInt(str[0]);
        m=Integer.parseInt(str[1]);
        for(int i=1;i<=n;i++)h[i]=-1;
        while(m-->0) {
            str=br.readLine().split(" ");
            add(Integer.parseInt(str[0]),Integer.parseInt(str[1]));
            d[Integer.parseInt(str[1])]++;
        }
        if(bfs()) {
            for(int i=0;i<n;i++)bw.write(q[i]+" ");
        }else {
            bw.write("-1");
        }
        bw.flush();
        bw.close();
        br.close();
    }
    public static boolean bfs() {
        hh=0;tt=-1;
        for(int i=1;i<=n;i++) {
            if(d[i]==0) {
                q[++tt]=i;
            }
        }
        while(hh<=tt) {
            int t=q[hh++];
            for(int i=h[t];i!=-1;i=ne[i]) {
                int j=e[i];
                d[j]--;
                if(d[j]==0) {
                    q[++tt]=j;
                }
            }
        }
        return tt==n-1;
    }
    public static void add(int a,int b) {
        e[idx]=b;
        ne[idx]=h[a];
        h[a]=idx++;
    }
}


活动打卡代码 AcWing 847. 图中点的层次

Rh.
8个月前
import java.io.*;
public class Main{
    static int N=100010;
    static int d[]=new int [N];
    static int q[]=new int [N];
    static int n,m,hh,tt;
    static int h[]=new int [N];
    static int e[]=new int [N];
    static int ne[]=new int [N];
    static int idx;
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String []str=br.readLine().split(" ");
        n=Integer.parseInt(str[0]);
        m=Integer.parseInt(str[1]);
        for(int i=1;i<=n;i++){
            h[i]=-1;
            d[i]=-1;
        }
        while(m-->0){
            str=br.readLine().split(" ");
            int a=Integer.parseInt(str[0]);
            int b=Integer.parseInt(str[1]);
            add(a,b);
        }
        System.out.println(bfs());
        br.close();
    }
    public static void add(int a,int b){
        e[idx]=b;
        ne[idx]=h[a];
        h[a]=idx++;
    }
    public static int bfs(){
        hh=0;tt=-1;
        d[1]=0;
        q[++tt]=1;
        while(hh<=tt){
            int t=q[hh++];
            for(int i=h[t];i!=-1;i=ne[i]){
                int s=e[i];
                if(d[s]==-1){
                    d[s]=d[t]+1;
                    q[++tt]=s;
                }
            }
        }
        return d[n];
    }
}