小景哥哥

世界很大,而我们还需要再成长!

强烈推荐

1009. 说反话 (20)-浙大PAT乙级真题java实现

    1009. 说反话 (20)
    给定一句英语,要求你编写程序,将句中所有单词的顺序颠倒输出。
    输入格式:测试输入包含一个测试用例,在一行内给出总长度不超过80的字符串。字符串由若干单词和若干空格组成,其中单词是由英文字母(大小写有区分)组成的字符串,单词之间用1个空格分开,输入保证句子末尾没有多余的空格。
    输出格式:每个测试用例的输出占一行,输出倒序后的句子。
    输入样例:
    Hello World Here I Come
    输出样例:
    输入样例:
    Come I Here World Hello 


    阅读全文>>

作者:Jason分类:【pat浏览(397评论(0

2018-01-04

1028. 人口普查(20)-浙大PAT乙级真题java实现

    1028. 人口普查(20) 
    某城镇进行人口普查,得到了全体居民的生日。现请你写个程序,找出镇上最年长和最年轻的人。这里确保每个输入的日期都是合法的,但不一定是合理的——假设已知镇上没有超过200岁的老人,而今天是2014年9月6日,所以超过200岁的生日和未出生的生日都是不合理的,应该被过滤掉。 
    输入格式: 
    输入在第一行给出正整数N,取值在(0, 10^5];随后N行,每行给出1个人的姓名(由不超过5个英文字母组成的字符串)、以及按“yyyy/mm/dd”(即年/月/日)格式给出的生日。题目保证最年长和最年轻的人没有并列。 
    输出格式: 
    在一行中顺序输出有效生日的个数、最年长人和最年轻人的姓名,其间以空格分隔。 
    输入样例: 

    John 2001/05/12 
    Tom 1814/09/06 
    Ann 2121/01/30 
    James 1814/09/05 
    Steve 1967/11/20 
    输出样例: 
    3 Tom John


    阅读全文>>

作者:Jason分类:【pat浏览(428评论(0

2018-01-18

1005. 继续(3n+1)猜想 (25)-浙大PAT乙级真题java实现

    1005. 继续(3n+1)猜想 (25)

    卡拉兹(Callatz)猜想已经在1001中给出了描述。在这个题目里,情况稍微有些复杂。
    当我们验证卡拉兹猜想的时候,为了避免重复计算,可以记录下递推过程中遇到的每一个数。例如对n=3进行验证的时候,我们需要计算3、5、8、4、2、1,则当我们对n=5、8、4、2进行验证的时候,就可以直接判定卡拉兹猜想的真伪,而不需要重复计算,因为这4个数已经在验证3的时候遇到过了,我们称5、8、4、2是被3“覆盖”的数。我们称一个数列中的某个数n为“关键数”,如果n不能被数列中的其他数字所覆盖。
    现在给定一系列待验证的数字,我们只需要验证其中的几个关键数,就可以不必再重复验证余下的数字。你的任务就是找出这些关键数字,并按从大到小的顺序输出它们。
    输入格式:每个测试输入包含1个测试用例,第1行给出一个正整数K(<100),第2行给出K个互不相同的待验证的正整数n(1<n<=100)的值,数字间用空格隔开。
    输出格式:每个测试用例的输出占一行,按从大到小的顺序输出关键数字。数字间用1个空格隔开,但一行中最后一个数字后没有空格。
    输入样例:
    6
    3 5 6 7 8 11
    输出样例:
    7 6


    阅读全文>>

作者:Jason分类:【pat浏览(355评论(0

2018-01-04

1002. 写出这个数 (20)-浙大PAT乙级真题java实现

    1002. 写出这个数 (20)
    读入一个自然数n,计算其各位数字之和,用汉语拼音写出和的每一位数字。
    输入格式:每个测试输入包含1个测试用例,即给出自然数n的值。这里保证n小于10^100。
    输出格式:
    在一行内输出n的各位数字之和的每一位,拼音数字间有1 空格,但一行中最后一个拼音数字后没有空格。
    输入样例
    1234567890987654321123456789
    输出样例
    yi san wu

     

     

     
     
    阅读全文>>

作者:Jason分类:【pat浏览(400评论(0

2018-01-04

64.滑动窗口的最大值

    64.滑动窗口的最大值

    题目描述

    给定一个数组和滑动窗口的大小,找出所有滑动窗口里数值的最大值。例如,如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3,那么一共存在6个滑动窗口,他们的最大值分别为{4,4,6,6,6,5}; 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个: {[2,3,4],2,6,2,5,1}, {2,[3,4,2],6,2,5,1}, {2,3,[4,2,6],2,5,1}, {2,3,4,[2,6,2],5,1}, {2,3,4,2,[6,2,5],1}, {2,3,4,2,6,[2,5,1]}。

    import java.util.ArrayList;
    import java.util.ArrayDeque;
    public class Solution {
        /**
        用一个双端队列,队列第一个位置保存当前窗口的最大值,当窗口滑动一次
        1.判断当前最大值是否过期
        2.新增加的值从队尾开始比较,把所有比他小的值丢掉
        */
        public ArrayList<Integer> maxInWindows(int [] num, int size)
        {
            ArrayList<Integer> res = new ArrayList<>();
            if(size == 0) return res;
            int begin; 
            ArrayDeque<Integer> q = new ArrayDeque<>();
            for(int i = 0; i < num.length; i++){
                begin = i - size + 1;
                if(q.isEmpty())
                    q.add(i);
                else if(begin > q.peekFirst())
                    q.pollFirst();
             
                while((!q.isEmpty()) && num[q.peekLast()] <= num[i])
                    q.pollLast();
                q.add(i);  
                if(begin >= 0)
                    res.add(num[q.peekFirst()]);
            }
            return res;
        }
    }
    阅读全文>>

作者:Jason分类:【offer浏览(327评论(0

2018-08-25

1007. 素数对猜想 (20)-浙大PAT乙级真题java实现

    1007. 素数对猜想 (20)
    让我们定义 dn 为:dn = pn+1 – pn,其中 pi 是第i个素数。显然有 d1=1 且对于n>1有 dn 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。
    现给定任意正整数N (< 105),请计算不超过N的满足猜想的素数对的个数。
    输入格式:每个测试输入包含1个测试用例,给出正整数N。
    输出格式:每个测试用例的输出占一行,不超过N的满足猜想的素数对的个数。
    输入样例:
    20
    输出样例:

    4


    阅读全文>>

作者:Jason分类:【pat浏览(406评论(0

2018-01-04

1069. 微博转发抽奖(20)–PAT乙级真题java实现

    1069. 微博转发抽奖(20)–PAT乙级真题java实现
     
    小明PAT考了满分,高兴之余决定发起微博转发抽奖活动,从转发的网友中按顺序每隔N个人就发出一个红包。请你编写程序帮助他确定中奖名单。 
    输入格式: 
    输入第一行给出三个正整数M(<= 1000)、N和S,分别是转发的总量、小明决定的中奖间隔、以及第一位中奖者的序号(编号从1开始)。随后M行,顺序给出转发微博的网友的昵称(不超过20个字符、不包含空格回车的非空字符串)。 
    注意:可能有人转发多次,但不能中奖多次。所以如果处于当前中奖位置的网友已经中过奖,则跳过他顺次取下一位。 
    输出格式: 
    按照输入的顺序输出中奖名单,每个昵称占一行。如果没有人中奖,则输出“Keep going…”。 
    输入样例1: 
    9 3 2 
    Imgonnawin! 
    PickMe 
    PickMeMeMeee 
    LookHere 
    Imgonnawin! 
    TryAgainAgain 
    TryAgainAgain 
    Imgonnawin! 
    TryAgainAgain 
    输出样例1: 
    PickMe 
    Imgonnawin! 
    TryAgainAgain 
    输入样例2: 
    2 3 5 
    Imgonnawin! 
    PickMe 
    输出样例2: 
    Keep going…
     
     
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.ArrayList;
    import java.util.List;
    public class Main {
        public static void main(String[] args) throws IOException{
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            String[] s = br.readLine().split(" ");
            int total = Integer.parseInt(s[0]);
            int interval = Integer.parseInt(s[1]);
            int prize = Integer.parseInt(s[2]);
            List<String> list = new ArrayList<>();
            boolean flag = false;
            for(int i = 1; i <= total; i++) {
                String user = br.readLine();
                if(list.contains(user))
                    prize++;
                if(i == prize) {
                    System.out.println(user);
                    list.add(user);
                    flag = true;
                    prize += interval;
                }
            }
            if(!flag)
                System.out.println("Keep going...");
        }
    }
    阅读全文>>

作者:小景哥哥分类:【pat浏览(482评论(0

2018-09-09

1052. 卖个萌 (20)-PAT乙级真题java实现

    1052. 卖个萌 (20)-PAT乙级真题java实现

    萌萌哒表情符号通常由“手”、“眼”、“口”三个主要部分组成。简单起见,我们假设一个表情符号是按下列格式输出的: 
    [左手] ([左眼][口][右眼])[右手] 
    现给出可选用的符号集合,请你按用户的要求输出表情。 
    输入格式: 
    输入首先在前三行顺序对应给出手、眼、口的可选符号集。每个符号括在一对方括号[]内。题目保证每个集合都至少有一个符号,并不超过10个符号;每个符号包含1到4个非空字符。 
    之后一行给出一个正整数K,为用户请求的个数。随后K行,每行给出一个用户的符号选择,顺序为左手、左眼、口、右眼、右手——这里只给出符号在相应集合中的序号(从1开始),数字间以空格分隔。 
    输出格式: 
    对每个用户请求,在一行中输出生成的表情。若用户选择的序号不存在,则输出“Are you kidding me? @\/@”。 
    输入样例: 
    [╮][╭][o][~][/~] [<][>] 
    [╯][╰][^][-][=][>][<][@][⊙] 
    [Д][▽][_][ε][^] … 

    1 1 2 2 2 
    6 8 1 5 5 
    3 3 4 3 3 
    2 10 3 9 3 
    输出样例: 
    ╮(╯▽╰)╭ 
    <(@Д=)/~ 
    o(^ε^)o 
    Are you kidding me? @\/@

     

     
    import java.util.Scanner;
    public class Main {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            String h = sc.nextLine().trim();
            String[] hands = h.substring(h.indexOf("[") + 1, h.lastIndexOf(']')).split("\\]\\s*\\[");
            String e = sc.nextLine().trim();
            String[] eyes = e.substring(h.indexOf("[") + 1, e.lastIndexOf(']')).split("\\]\\s*\\[");
            String m = sc.nextLine().trim();
            String[] mouths = m.substring(h.indexOf("[") + 1, m.lastIndexOf(']')).split("\\]\\s*\\[");
     
            int n = Integer.parseInt(sc.nextLine());
            for (int i = 0; i < n; i++) {
                String[] in = sc.nextLine().split("\\s+");
                String temp = "";
                boolean flag = true;
                if (Integer.parseInt(in[0]) <= hands.length) {
                    temp = temp + hands[Integer.parseInt(in[0]) - 1] + "(";
                } else {
                    System.out.println("Are you kidding me? @\\/@");
                    flag = false;
                    continue;
                }           
                if (Integer.parseInt(in[1]) <= eyes.length) {
                    temp = temp + eyes[Integer.parseInt(in[1]) - 1];
                } else {
                    System.out.println("Are you kidding me? @\\/@");
                    flag = false;
                    continue;
                }            
                if (Integer.parseInt(in[2]) <= mouths.length) {
                    temp = temp + mouths[Integer.parseInt(in[2]) - 1];
                } else {
                    System.out.println("Are you kidding me? @\\/@");
                    flag = false;
                    continue;
                }            
                if (Integer.parseInt(in[3]) <= eyes.length) {
                    temp = temp + eyes[Integer.parseInt(in[3]) - 1];
                } else {
                    System.out.println("Are you kidding me? @\\/@");
                    flag = false;
                    continue;
                }          
                if (Integer.parseInt(in[4]) <= hands.length) {
                    temp = temp + ")" + hands[Integer.parseInt(in[4]) - 1];
                } else {
                    System.out.println("Are you kidding me? @\\/@");
                    flag = false;
                    continue;
                }
                if (flag) {
                    System.out.println(temp);
                }              
            }
        }
    }

     

    阅读全文>>

作者:小景分类:【pat浏览(360评论(0

2018-09-07

28.数组中出现次数超过一半的数字

    28.数组中出现次数超过一半的数字

    题目描述

    数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。



    import java.util.Arrays;
    public class Solution {
        public int MoreThanHalfNum_Solution(int [] array) {
            if(array.length <= 0)
                return 0;
            if(array.length == 1)
                return array[0];
            Arrays.sort(array);
            int length = array.length;
            if(length % 2 == 0 && array[length / 2 - 1] == array[length / 2]){
                return array[length / 2];
            }else if(length % 2 == 1 && array[length / 2] == array[length / 2 + 1])
                return array[length / 2];
            else 
                return 0;
        }
    }

    //方法二,基于快速排序算法思想

        public int MoreThanHalfNum_Solution(int[] array) {

            if (array == null || array.length == 0)

                return 0;

            int middle = array.length >> 1;

            int start = 0;

            int end = array.length - 1;

            int index = Partition(array, start, end);

     

            while (index != middle) {

                if (index > middle) {

                    end = index - 1;

                    index = Partition(array, start, end);

                } else {

                    start = index + 1;

                    index = Partition(array, start, end);

                }

            }

            int result = array[middle];

            if (!CheckMoreThanHalf(array, result))

                result = 0;

            return result;

        }

     

        public static boolean CheckMoreThanHalf(int array[], int number) {

            int times = 0;

            for (int i = 0; i < array.length; ++i) {

                if (array[i] == number)

                    times++;

            }

            boolean isMoreThanHalf = true;

            if (times * 2 <= array.length) {

                isMoreThanHalf = false;

            }

            return isMoreThanHalf;

        }

     

        public static int Partition(int array[], int start, int end) {

            int pivotkey = (int) start + (int) Math.random() * (end - start);

            while (start < end) {

                while (start < end && array[end] >= array[pivotkey])

                    end--;

                int temp = array[start];

                array[start] = array[end];

                array[end] = temp;

                while (start < end && array[start] <= array[pivotkey])

                    start++;

                temp = array[start];

                array[start] = array[end];

                array[end] = temp;

            }

            return start;

        }

    阅读全文>>

作者:Jason分类:【offer浏览(394评论(0

2018-08-23

1025. 反转链表 (25)-浙大PAT乙级真题java实现

    1025. 反转链表 (25) 
    给定一个常数K以及一个单链表L,请编写程序将L中每K个结点反转。例如:给定L为1→2→3→4→5→6,K为3,则输出应该为3→2→1→6→5→4;如果K为4,则输出应该为4→3→2→1→5→6,即最后不到K个元素不反转。 
    输入格式: 
    每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址、结点总个数正整数N(<= 10^5)、以及正整数K(<=N),即要求反转的子链结点的个数。结点的地址是5位非负整数,NULL地址用-1表示。 
    接下来有N行,每行格式为:Address Data Next 
    其中Address是结点地址,Data是该结点保存的整数数据,Next是下一结点的地址。 
    输出格式: 
    对每个测试用例,顺序输出反转后的链表,其上每个结点占一行,格式与输入相同。 
    输入样例: 
    00100 6 4 
    00000 4 99999 
    00100 1 12309 
    68237 6 -1 
    33218 3 00000 
    99999 5 68237 
    12309 2 33218 
    输出样例: 
    00000 4 33218 
    33218 3 12309 
    12309 2 00100 
    00100 1 99999 
    99999 5 68237 
    68237 6 -1


    阅读全文>>

作者:Jason分类:【pat浏览(371评论(0

2018-01-18