小景哥哥

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

强烈推荐

1003. 我要通过!(20)-浙大PAT乙级真题Java实现

    1003. 我要通过!(20)
    “答案正确”是自动判题系统给出的最令人欢喜的回复。本题属于PAT的“答案正确”大派送 —— 只要读入的字符串满足下列条件,系统就输出“答案正确”,否则输出“答案错误”。
    得到“答案正确”的条件是:
    1. 字符串中必须仅有P, A, T这三种字符,不可以包含其它字符;
    2. 任意形如 xPATx 的字符串都可以获得“答案正确”,其中 x 或者是空字符串,或者是仅由字母 A 组成的字符串;
    3. 如果 aPbTc 是正确的,那么 aPbATca 也是正确的,其中 a, b, c 均或者是空字符串,或者是仅由字母 A 组成的字符串。
    现在就请你为PAT写一个自动裁判程序,判定哪些字符串是可以获得“答案正确”的。
    输入格式:
    每个测试输入包含1个测试用例。第1行给出一个自然数n (<10),是需要检测的字符串个数。接下来每个字符串占一行,字符串长度不超过100,且不包含空格。
    输出格式:
    每个字符串的检测结果占一行,如果该字符串可以获得“答案正确”,则输出YES,否则输出NO。

    输入样例:
    8
    PAT
    PAAT
    AAPATAA
    AAPAATAAAA
    xPATx
    PT
    Whatever
    APAAATAA
    输出样例:
    YES
    YES
    YES
    YES
    NO
    NO

    NO
    NO

    思路:

    条件一最基本,先忽略。条件二,xPATx 就是正确的形式;在此基础上,如果 aPbTc 是正确的,那么 aPbATca 也是正确的。如果二者放在一起考虑,就是中间每增加一个A,后面就增加一个a,似乎数学关系出来了。我们知道aPbTc中a b c 段都只能包含“A",其长度分别为len(a)、len(b)、len(c),则其关系满足len(a)*len(b) = len(c)!这完美的契合了条件二与条件三,xPATx 就是当len(b) = 1,(a=x,c=c,b=A)的情况,在此基础上演化到条件三B中每增加一个A,c中相应增加一段”a“以上的乘法关系式成立。


    阅读全文>>

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

2018-01-04

60.把二叉树打印成多行

    60.把二叉树打印成多行
    题目描述
    从上到下按层打印二叉树,同一层结点从左至右输出。每一层输出一行。
     
     
    import java.util.ArrayList;
    import java.util.Queue;
    import java.util.LinkedList;
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
        public TreeNode(int val) {
            this.val = val;
        }
    }
    public class Solution {
        public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
             ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
             if(pRoot == null)
                 return list;
             Queue<TreeNode> q = new LinkedList<TreeNode>();
             q.add(pRoot);
             while(!q.isEmpty()) {
            int l = 0, h = q.size();
            ArrayList<Integer> temp = new ArrayList<>();
            while(l++ < h) {
            TreeNode tn = q.poll();
                temp.add(tn.val);
                if(tn.left != null)
                q.add(tn.left);
                if(tn.right != null)
                q.add(tn.right);
            }
            list.add(temp);
             }
             return list;
         }
    }
    阅读全文>>

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

2018-08-25

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浏览(367评论(0

2018-09-09

微醺的忧伤

    华灯初上,夜未央,皎月之下,花未眠。

    每天晚上踩着皎洁的月光回家,清风徐来,心荡漾。

    夜色朦胧,凉风轻抚,正是喝酒的好时光。

    很多人喜欢巴黎的浪漫,不是因为法国人天生具有爱情的细胞,不是因为法语的音调具有抑扬顿挫的美感,也不是因为埃菲尔凝聚了爱的浓密,而是法国具有美味醇香的红酒。我喜欢法国,喜欢波尔多,没有原因,纯属爱好。我也喜欢张裕解百纳,名字中就散发着一股浓郁的浪漫气息,也因为我也在烟台待过几年,这里有失去的青春美好,在最美好的年华里,这里藏着年轻的记忆。

    土直男本身就有一种违和感,总在某些时候与世界显得格格不入,而直男作为爱情难民,情商也许会低到尘埃里,总在不经意间冒出一句梗,然后整段垮掉。所以为了排解内心的忧伤,可能绝大多数人都会喜欢上微醺的感觉,我记得乔欣说活一句话,喜欢晚上喝完红酒微醺的感觉,简简单单的一句话,深深的刻进我的心中,这种感同身受的感觉,无法真真切切的表达到位。

    每一颗心承载的悲伤都有容量,微醺的忧伤,忧伤的暗伤,再多的不快总会在微醺的酒意下显得那么的微不足道,可以轻松地放空自己,让内心即使再澎湃的忧伤都可以在一杯红酒之后烟消云散,潇洒本洒,就是这种感觉。抛开生活中的种种不快和烦恼,幸福的种子在心里就会慢慢冒花子。

    给我一个不爱喝酒的理由,不好意思,我没有。我喜欢干红的苦涩中夹杂的微甜,喜欢原浆浓烈的麦芽香,喜欢干白透露出的绿葡萄的清香,喜欢白兰地强烈的温暖,喜欢江小白文艺的带有温度的文字,喜欢干红充盈的甜爽,喜欢威士忌贯彻心扉的干烈。我喜欢酒,我喜欢酒的种种清香。

    ​喝酒就是在一个陌生的城市,发现一种久违的感动。夜深人静的晚上,打开一盏灯,醒一瓶红酒,看着醒酒瓶中的红酒被一点点氧化变得更加醇香,再配一盘小龙虾,在微光陆离的小桌前,思绪在漫无目的的游荡,幸福的感觉总在一刹那间溢满全身,我是世界上最幸福的人,没有之一,人生最美是酒欢。

    我喜欢李白,可以在人生中与酒结缘,在酩酊大醉之后还能写出流芳百世的佳句。想做一个有情怀的人,如果有来生,我愿做李白,与酒为伴,陪伴月光,对影成三人,挥洒心中豪情万丈,萌萌地醉一生。

    五花马,千金裘,呼儿将出换美酒,与尔同消万古愁,但不舍爱与自由。

    人生得意须尽欢,人生失意需排难,酒在我们生命中的大起大落之时,陪我们欢笑陪我们忧伤,在欢聚时刻助兴,在伤心时刻排忧解难。

    以酒会友,可以和好哥们敞开心扉交谈,特别喜欢和兄弟们一起喝到微醺的时刻,交流各自的悲和喜,有时兴起也会彻夜长谈,即使提不出建设性的意见,但你认真的倾听,会让对方倾吐之后忧伤骤减。分享快乐,快乐加倍;分享痛苦,痛苦减半。

    凌晨一点半,海棠花未眠,正是喝酒的好时间,将进酒,杯莫停,雪花不飘我不飘,青岛不倒我不倒。来,cheers!

    阅读全文>>

作者:小景哥哥分类:【品酒浏览(497评论(0

2019-06-13

树的子结构

    17.树的子结构

    题目描述

    输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)
    解题思路:

    比较两棵树当前根节点是否相等,相等的话再递归分别比较左右子树是否包含相同结构。

     


    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
        public TreeNode(int val) {
            this.val = val;
        }
    }

    public class Solution {
        public boolean HasSubtree(TreeNode root1,TreeNode root2) {
            boolean result = false;
            if(root1 != null && root2 != null){
                if(root1.val == root2.val)
                    result = DoesTree1HaveTree2(root1, root2);
                if(!result)
                    result = HasSubtree(root1.left, root2);
                if(!result)
                    result = HasSubtree(root1.right, root2);
            }
            return result;
        }
        
        public boolean DoesTree1HaveTree2(TreeNode root1, TreeNode root2){
            if(root2 == null)
                return true;
            if(root1 == null)
                return false;
            
            if(root1.val != root2.val)
                return false;
            return DoesTree1HaveTree2(root1.left, root2.left) && DoesTree1HaveTree2(root1.right, root2.right);
        }
    }

    阅读全文>>

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

2018-08-13

43.左旋转字符串

    43.左旋转字符串

    题目描述

    汇编语言中有一种移位指令叫做循环左移(ROL),现在有个简单的任务,就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S,请你把其循环左移K位后的序列输出。例如,字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果,即“XYZdefabc”。是不是很简单?OK,搞定它!
     


    public class Solution {
        public String LeftRotateString(String str,int n) {
            if(n > str.toCharArray().length)
                return "";
            return str.substring(n) + str.substring(0,n);
        }
    }

    阅读全文>>

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

2018-08-24

56.删除链表中重复的结点

    56.删除链表中重复的结点

    题目描述

    在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1->2->5
     



    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }

    public class Solution {
        public ListNode deleteDuplication(ListNode pHead)
        {
            if(pHead == null)
                return null;
            if(pHead != null && pHead.next == null)
                return pHead;
            ListNode current;
            if(pHead.next.val == pHead.val){
                current = pHead.next.next;
                while(current != null && current.val == pHead.val)
                    current = current.next;
                return deleteDuplication(current);
            }else{
                current = pHead.next;
                pHead.next = deleteDuplication(current);
                return pHead;
            }
            
        }
        
    }

     

     

     

    阅读全文>>

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

2018-08-25

1045. 快速排序(25)-浙大PAT乙级真题java实现

    1045. 快速排序(25) 
    著名的快速排序算法里有一个经典的划分过程:我们通常采用某种方法取一个元素作为主元,通过交换,把比主元小的元素放到它的左边,比主元大的元素放到它的右边。 给定划分后的N个互不相同的正整数的排列,请问有多少个元素可能是划分前选取的主元? 
    例如给定N = 5, 排列是1、3、2、4、5。则: 
    1的左边没有元素,右边的元素都比它大,所以它可能是主元; 
    尽管3的左边元素都比它小,但是它右边的2它小,所以它不能是主元; 
    尽管2的右边元素都比它大,但其左边的3比它大,所以它不能是主元; 
    类似原因,4和5都可能是主元。 
    因此,有3个元素可能是主元。 
    输入格式: 
    输入在第1行中给出一个正整数N(<= 105); 第2行是空格分隔的N个不同的正整数,每个数不超过109。 
    输出格式: 
    在第1行中输出有可能是主元的元素个数;在第2行中按递增顺序输出这些元素,其间以1个空格分隔,行末不得有多余空格。 
    输入样例: 

    1 3 2 4 5 
    输出样例: 

    1 4 5


    分析:对原序列sort排序,逐个比较,排序前后元素没有变化,并且它左边的所有值的最大值都比它小的时候它一定是主元。


    阅读全文>>

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

2018-01-24

36.两个链表的第一个公共结点

    36.两个链表的第一个公共结点

    题目描述

    输入两个链表,找出它们的第一个公共结点。

    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }
    public class Solution {
        public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
            int len1 = 0, len2 = 0;
            ListNode lp1 = pHead1;
            ListNode lp2 = pHead2;
            ListNode pHeadLong = pHead1;
            ListNode pHeadShort = pHead2;
            int nLengthDif = 0;
            while(lp1 != null){
                len1++;
                lp1 = lp1.next;
            }
            while(lp2 != null){
                len2++;
                lp2 = lp2.next;
            }
            if(len2 > len1){
                pHeadLong = pHead2;
                pHeadShort = pHead1;
                nLengthDif = len2 - len1;
            }else{
                nLengthDif = len1 - len2;
            }
            
            for(int i = 0; i < nLengthDif; ++i)
                pHeadLong = pHeadLong.next;
            
            while(pHeadLong != null && pHeadShort != null && pHeadLong != pHeadShort){
                pHeadLong = pHeadLong.next;
                pHeadShort = pHeadShort.next;
            }
            ListNode res = pHeadLong;
            return res;
        }
    }

     

     

     

     

     

    阅读全文>>

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

2018-08-23

38.二叉树的深度

    38.二叉树的深度

    题目描述

    输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。


    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
        public TreeNode(int val) {
            this.val = val;
        }
    }

    public class Solution {
        public int TreeDepth(TreeNode root) {
            if(root == null)
                return 0;
            if(root != null && root.left == null && root.right == null)
                return 1;
            int leftLen = TreeDepth(root.left);
            int rightLen = TreeDepth(root.right);
            return leftLen > rightLen? leftLen + 1: rightLen + 1;
        }
    }

    阅读全文>>

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

2018-08-23