头像

renqinghua




离线:4天前



题目思路

1、先将所有数据读入,并按照过期时间d从小到大排序
2、依次添加每个数据t到堆heap中,如果此时heap.size>t.d,则需要删除掉利益最低的那个数据
3、最后求出heap中数据的利益总和



import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class Main
{

    //将堆中的数据按照利益从小到大排序,删除时直接poll删除的就是最小那个
    static Comparator<node> cmp=new Comparator<node>()
    {
        @Override
        public int compare(node o1, node o2)
        {
            return o1.p-o2.p;
        }

    };

    public static void main(String[] args)
    {
        Scanner scan=new Scanner(System.in);

        while(scan.hasNextInt())
        {
            Queue<node> queue=new PriorityQueue<node>(cmp);

            int n=scan.nextInt();
            node[] nodes=new node[n];

            for(int i=0;i<n;i++)
            {
                int p=scan.nextInt();
                int d=scan.nextInt();
                nodes[i]=new node(p,d);

            }
            Arrays.sort(nodes);

            int ans=0;
            for(node t:nodes)
            {
                queue.offer(t);
                if(queue.size()>t.d)
                    queue.poll();
            }

            for(node t:queue)
            {
                ans+=t.p;
            }

            System.out.println(ans);
        }

        scan.close();

    }

    private static class node implements Comparable<node>
    {
        private int p;
        private int d;
        public node(int p,int d)
        {
            this.p=p;
            this.d=d;
        }
        @Override
        public int compareTo(node o)
        {
            return this.d-o.d;
        }
    }

}




思路

1、求出原字符串以及翻转后的字符串的最小字符串表示结果,所以有两种情况,
2、O(n)求出原字符串旋转后的所有情况,并得到最小的值,
3、最后结果判断,若set.size==n*2,证明所有雪花都不会相等,反之,至少有两片雪花是相等的。



import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;

public class Main
{
    private static int N=100010;
    private static int[][] num=new int[N][6];

    public static void main(String[] args)
    {
        Scanner scan=new Scanner(System.in);

        int n=scan.nextInt();
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<6;j++)
            {
                num[i][j]=scan.nextInt();
            }
        }

        Set<String> set=new HashSet<>();

        for(int i=0;i<n;i++)
        {
            String s1=get_min(num[i]);
            int[] temp=new int[6];
            for(int j=0,t=5;j<6;j++,t--)
                temp[j]=num[i][t];
            String s2=get_min(temp);
            set.add(s1);
            set.add(s2);
        }

        if(set.size()==n*2)
            System.out.println("No two snowflakes are alike.");
        else
            System.out.println("Twin snowflakes found.");
        scan.close();

    }

    private static String get_min(int[] a)
    {
        List<String> list=new ArrayList<>();

        int[] b=new int[12];
        for(int i=0;i<12;i++) b[i]=a[i%6];
        //截取长度为6
        for(int i=0;i<6;i++)
        {
            String s="";
            int t=6;
            int j=i;
            while(t--!=0)
            {
                s+=b[j];
                j++;
            }
            list.add(s);
        }
        Collections.sort(list);
        return list.get(0);
    }

}




思路

1、求前缀和
2、我们求解的是在以i结尾(i for 1-n),往前间隔在m范围的数j中,s[i]-s[j]的最大值
3、对于不在范围i-m中的j,直接删除
4、对于在范围i-m中的j,如果其值>=即将加入的数,直接删除

package _AcWing;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;

public class Main
{
    private static int N=300010;
    private static long[] s=new long[N];

    public static void main(String[] args)
    {
        Scanner scan=new Scanner(System.in);

        int n=scan.nextInt();
        int m=scan.nextInt();
        for(int i=1;i<=n;i++)
        {
            int t=scan.nextInt();
            s[i]=s[i-1]+t;
        }

        Deque<Integer> queue=new LinkedList<>();
        long ans=Long.MIN_VALUE;
        queue.offerLast(0);
        for(int i=1;i<=n;i++)
        {
            if(!queue.isEmpty()&&i-m>queue.peekFirst()) queue.pollFirst();
            ans=Math.max(ans, s[i]-s[queue.peekFirst()]);
            while(!queue.isEmpty()&&s[queue.peekLast()]>=s[i]) queue.pollLast();

            queue.offerLast(i);

        }

        System.out.println(ans);
        scan.close();

    }

}



活动打卡代码 AcWing 132. 小组队列



import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main
{
    private static int N=1010;
    private static int M=1000010;
    private static int[] teamid=new int[M]; 

    public static void main(String[] args)
    {
        Scanner scan=new Scanner(System.in);
        int c=1;
        while(scan.hasNextInt())
        {
            int num=scan.nextInt();
            if(num==0)
                break;

            System.out.println("Scenario #"+(c++));
            Queue<Integer> team=new LinkedList<>();
            Queue<Integer>[] people=new Queue[N];
            for(int i=0;i<N;i++)
                people[i]=new LinkedList<>();
            for(int i=0;i<num;i++)
            {
                int t=scan.nextInt();
                for(int j=0;j<t;j++)
                {
                    int x=scan.nextInt();
                    teamid[x]=i;
                }

            }

            String command="";
            while(scan.hasNext())
            {
                command=scan.next();
                if(command.equals("STOP"))
                    break;
                if(command.equals("ENQUEUE"))
                {
                    int x=scan.nextInt();
                    int tid=teamid[x];

                    if(people[tid].isEmpty())
                        team.offer(tid);
                    people[tid].offer(x);
                }
                else
                {

                    int tid=team.peek();
                    System.out.println(people[tid].poll());
                    if(people[tid].isEmpty())
                        team.poll();

                }

            }
            System.out.println();
        }


        scan.close();

    }

}






import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main
{
    private static int N=1010;
    private static int M=1000010;
    private static int[] teamid=new int[M]; 

    public static void main(String[] args)
    {
        Scanner scan=new Scanner(System.in);
        int c=1;
        while(scan.hasNextInt())
        {
            int num=scan.nextInt();
            if(num==0)
                break;

            System.out.println("Scenario #"+(c++));
            Queue<Integer> team=new LinkedList<>();
            Queue<Integer>[] people=new Queue[N];
            for(int i=0;i<N;i++)
                people[i]=new LinkedList<>();
            for(int i=0;i<num;i++)
            {
                int t=scan.nextInt();
                for(int j=0;j<t;j++)
                {
                    int x=scan.nextInt();
                    teamid[x]=i;
                }

            }

            String command="";
            while(scan.hasNext())
            {
                command=scan.next();
                if(command.equals("STOP"))
                    break;
                if(command.equals("ENQUEUE"))
                {
                    int x=scan.nextInt();
                    int tid=teamid[x];

                    if(people[tid].isEmpty())
                        team.offer(tid);
                    people[tid].offer(x);
                }
                else
                {

                    int tid=team.peek();
                    System.out.println(people[tid].poll());
                    if(people[tid].isEmpty())
                        team.poll();

                }

            }
            System.out.println();
        }


        scan.close();

    }

}




知识点

1、首先可以看到这是一道模拟题,我们按题意模拟出来就行
2、java中如何去表示出二维的不定长数组
3、split函数的使用



import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main
{
    private static int N=14;
    //定义二维不定长数组
    private static List<Integer>[] list=new ArrayList[14];
    private static int[] up=new int[N];

    public static void main(String[] args)
    {
        Scanner scan=new Scanner(System.in);

        //进行初始化
        for(int i=0;i<14;i++)
            list[i]=new ArrayList<>();

        for(int i=1;i<=13;i++)
        {
            String str=scan.nextLine();
            //数据一行读取,因为不清楚数据中间或结尾是否只存在一个空格
            String[] ts=str.split("\\s+");
            for(int j=0;j<ts.length;j++)
                list[i].add(change(ts[j]));

        }

        for(int i=0;i<4;i++)
        {
            int t=list[13].get(i);
            while(t!=13)
            {
                up[t]++;
                int num=list[t].get(list[t].size()-1);
                list[t].remove(list[t].size()-1);
                t=num;
            }
        }
        int ans=0;
        for(int i=1;i<14;i++)
        {
            ans+=(up[i]==4?1:0);
        }
        System.out.println(ans);

        scan.close();

    }

    private static Integer change(String ts)
    {
        char ch=ts.charAt(0);
        if(ch=='A')  return 1;
        else if(ch>='2'&&ch<='9') return ch-'0';
        else if(ch=='0') return 10;
        else if(ch=='J') return 11;
        else if(ch=='Q') return 12;
        else return 13;

    }

}




在视频中yxc用到的位运算的知识,代码看起来也比较简洁,但是在改变x,y所在行列状态时的位运算我还比较懵懂,并且我觉得如果是在考场中可能想不到这种简洁的做法。所以记录下我自己的思路吧

题目思路

1、首先一个二维数组state记录下初始状态
2、枚举从0–1<<16所有的可能,若当前位置为1,则操作下
3、最后判断state是否满足,并更新结果。



import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main
{
    private static int[][] state=new int[4][4];

    public static void main(String[] args)
    {
        Scanner scan=new Scanner(System.in);

        for(int i=0;i<4;i++)
        {
            String str=scan.nextLine();
            for(int j=0;j<4;j++)
            {
                if(str.charAt(j)=='+')
                {
                    state[i][j]=1;
                }

            }
        }

        List<Node> ans=new ArrayList<>();
        for(int k=0;k<1<<16;k++)
        {
            //先要保存一下state
            int[][] temp=new int[4][4];
            for(int i=0;i<4;i++)
                for(int j=0;j<4;j++)
                    temp[i][j]=state[i][j];

            List<Node> list=new ArrayList<>();
            for(int j=0;j<16;j++)
            {
                //所在位置为1就要操作一下
                if((k>>j&1)==1)
                {
                    int x=j/4,y=j%4;
                    change(temp,x,y);
                    list.add(new Node(x,y));
                }
            }
            //如果当前temp满足要求,并且最终答案数组ans为空,或者有更短的方案,则要更新
            if(get_sum(temp)&&(ans.isEmpty()||ans.size()>list.size()))
                ans=list;

        }

        System.out.println(ans.size());
        for(Node t:ans)
        {
            System.out.println((t.x+1)+" "+(t.y+1));
        }

        scan.close();

    }

    private static boolean get_sum(int[][] temp)
    {
        int sum=0;
        for(int i=0;i<4;i++)
            for(int j=0;j<4;j++)
                sum+=temp[i][j];
        return sum==0;
    }

    //更改x,y所在行列数值的状态
    private static void change(int[][] temp,int x, int y)
    {
        temp[x][y]^=1;
        //上
        int tx=x-1,ty=y;
        while(tx>=0&&tx<4&&ty>=0&&ty<4)
        {
            temp[tx][ty]^=1;
            tx--;
        }
        //下
        tx=x+1;
        ty=y;
        while(tx>=0&&tx<4&&ty>=0&&ty<4)
        {
            temp[tx][ty]^=1;
            tx++;
        }

        //左
        tx=x;
        ty=y-1;
        while(tx>=0&&tx<4&&ty>=0&&ty<4)
        {
            temp[tx][ty]^=1;
            ty--;
        }

        //右
        tx=x;
        ty=y+1;
        while(tx>=0&&tx<4&&ty>=0&&ty<4)
        {
            temp[tx][ty]^=1;
            ty++;
        }



    }

    private static class Node
    {
        private int x;
        private int y;
        public Node(int x,int y)
        {
            this.x=x;
            this.y=y;
        }
    }

}




题目知识点

1、本题使用到了差分,因为要求的有牛可能的最大值,所以每头牛初始化为h,a,b之间要互相看得见,所以对中间的值都-1
2、是要对数据进行判重,yxc这边用到了set< pair< int,int> >来存储两个值并判重,但java里面就只能是转化成set里存储对象在判断,这样是不好判断的。我这边转化成set< String>,String=”“+a+b,这样String存储的值是不会重复的。

C++ 代码



import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main
{
    private static int N=10010;
    private static int[] height=new int[N];

    public static void main(String[] args)
    {
        Scanner scan=new Scanner(System.in);

        Set<String> set=new HashSet<>();

        int n=scan.nextInt();
        int p=scan.nextInt();
        int h=scan.nextInt();
        int m=scan.nextInt();

        height[1]=h;

        for(int i=0;i<m;i++)
        {
            int a=scan.nextInt();
            int b=scan.nextInt();
            if(a>b) 
            {
                int t=a;
                a=b;
                b=t;
            }
            String ts=""+a+b;
           if(!set.contains(ts))
           {
               set.add(ts);
               height[a+1]--;
               height[b]++;
           }

        }

        for(int i=1;i<=n;i++)
        {
            height[i]+=height[i-1];
            System.out.println(height[i]);
        }



        scan.close();

    }


}




renqinghua
1个月前

知识点

1、split函数的使用

class Solution {
    public String reverseWords(String str) {
        //String[] s=str.split("\\s+");//中间有多个空格进行分隔
        String[] s=str.split(" ");
        String ans="";
        for(int i=s.length-1;i>=0;i--)
            ans+=s[i]+" ";
        ans=ans.trim();
        return ans;

    }
}



renqinghua
1个月前

知识点

1、相同两个数异或为0,例如2^2==0
2、判断二进制数num中第k位是1或0, num>>k&1==1即1 ==0即0

class Solution {
    public int[] findNumsAppearOnce(int[] list) {
        int sum=0;//x^y  1^1==0
        for(int x:list)
            sum^=x;

        int k=0;
        //找到二进制中任意第k位为1
        while((sum>>k&1)==0) k++;

        int first=0;
        for(int x:list)
        {
            if((x>>k&1)==1)
                first^=x;
        }
        int[] ans= {first,first^sum};
        return ans;

    }
}