小景哥哥

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

强烈推荐

1008. 数组元素循环右移问题 (20)-浙大PAT乙级真题java实现

    1008. 数组元素循环右移问题 (20)
    一个数组A中存有N(N>0)个整数,在不允许使用另外数组的前提下,将每个整数循环向右移M(M>=0)个位置,即将A中的数据由(A0 A1……AN-1)变换为(AN-M …… AN-1 A0 A1……AN-M-1)(最后M个数循环移至最前面的M个位置)。如果需要考虑程序移动数据的次数尽量少,要如何设计移动
    的方法?
    输入格式:每个输入包含一个测试用例,第1行输入N ( 1<=N<=100)、M(M>=0);第2行输入N个整数,
    之间用空格分隔。
    输出格式:在一行中输出循环右移M位以后的整数序列,之间用空格分隔,序列结尾不能有多余空格。
    输入样例:
    6 2
    1 2 3 4 5 6
    输出样例:

    5 6 1 2 3 4


    阅读全文>>

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

2018-01-04

44.翻转单词顺序列

    44.翻转单词顺序列

    题目描述

    牛客最近来了一个新员工Fish,每天早晨总是会拿着一本英文杂志,写些句子在本子上。同事Cat对Fish写的内容颇感兴趣,有一天他向Fish借来翻看,但却读不懂它的意思。例如,“student. a am I”。后来才意识到,这家伙原来把句子单词的顺序翻转了,正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行,你能帮助他么?
     


    public class Solution {
        //利用java中String函数,简单明了
        public String ReverseSentence1(String str) {
            if(str.trim().isEmpty())
                return str;
            String[] temp = str.split(" ");
            String res = "";
            int i = temp.length - 1;
            for(; i > 0; i--){
                res = res + temp[i] + " ";
            }
            return res + temp[0];
        }
        //利用剑指offer上思想,两次反转字符串
        public String ReverseSentence(String str) {
            if(str.trim().isEmpty())
                return str;
            char[] c = str.toCharArray();
            Reverse(c, 0, c.length - 1);
            int pBegin = 0, pEnd = 0;
            while(pBegin < c.length){
                if(c[pBegin] == ' '){
                    pBegin++;
                    pEnd++;
                }else if(c[pEnd] == ' '){
                    Reverse(c, pBegin, pEnd - 1);
                    pBegin = ++pEnd;
                }else if(pEnd == c.length - 1){
                    Reverse(c, pBegin, pEnd);
                    pBegin = ++pEnd;
                }else
                    pEnd++;
            }
            return String.valueOf(c);
        }
        public static void Reverse(char[] c, int begin, int end){
            if(begin >= end)
                return;
            while(begin < end){
                char temp = c[begin];
                c[begin] = c[end];
                c[end] = temp;
                begin++;
                end--;
            }
        }
        
    }

    阅读全文>>

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

2018-08-24

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

2018-08-25

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

2018-08-23

1022. D进制的A+B (20)-浙大PAT乙级真题java实现

    1022. D进制的A+B (20) 
    输入两个非负10进制整数A和B(<=2^30-1),输出A+B的D (1 < D <= 10)进制数。 
    输入格式: 
    输入在一行中依次给出3个整数A、B和D。 
    输出格式: 
    输出A+B的D进制数。 
    输入样例: 
    123 456 8 
    输出样例: 
    1103


    阅读全文>>

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

2018-01-17

55.链表中环的入口结点

    55.链表中环的入口结点

    题目描述

    给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。
     

     


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

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

    public class Solution {

        //solution one
        /**
        假设fast每次走两步,slow每次走一步,当二者相遇时,假设slow走了s步,fast走了2s步。二者相遇时,slow指针肯定没有遍历完链表,而fast指针也在环内循环了n圈(n >= 1),则2s= s + nr.从而s=nr.
        设整个链表长L,入口环与相遇点设x,起始点到环入口距离为a,则a+x = nr,故a+x = (n-1)r + L-a,从而 a=(n-1)r+)(L-a-x).
        (L-a-x)为相遇点到环入口点的距离,从链表头到环入口点等于(n-1)环内循环+相遇点到环入口点,于是在链表头与相遇点分别设一个指针,每次各走一步,两者必定相遇,且相遇第一点为环入口点。
        */
        public ListNode EntryNodeOfLoop1(ListNode pHead)
        {
            ListNode slow = pHead, fast = pHead;
            
            while(fast != null && fast.next != null){
                slow = slow.next;
                fast = fast.next.next;
                if(slow == fast)
                    break;
            }
            
            if(fast == null || fast.next == null)
                return null;
            slow = pHead;
            while(slow != fast){
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
        
        //solution two
        //找到一快一满指针相遇处的节点,相遇的节点一定是在环中
        public static ListNode meetingNode(ListNode head) {
            if(head==null)
                return null;
             
            ListNode slow = head.next;
            if(slow==null)
                return null;
             
            ListNode fast = slow.next;
            while (slow != null && fast != null) {
                if(slow==fast){
                    return fast;
                }
                slow=slow.next;
                fast=fast.next;
                 
                if(fast!=slow){
                    fast=fast.next;
                }
            }
            return null;
        }
        /**
            如果链表中环 有n个结点,指针P1在链表上向前移动n步,然后两个指针以相同的速度向前移动。当第二个指针指向环的入口结点时,第一个指针已经围绕着环走了一圈又回到了入口结点。所以首先要得到环中结点的数目。
        */
        public ListNode EntryNodeOfLoop(ListNode pHead) {
            ListNode meetingNode=meetingNode(pHead);
            if(meetingNode==null)
                return null;
            //得到环中的节点个数
            int nodesInLoop=1;
            ListNode p1=meetingNode;
            while(p1.next!=meetingNode){
                p1=p1.next;
                ++nodesInLoop;
            }
            //移动p1
            p1=pHead;
            for(int i=0;i<nodesInLoop;i++){
                p1=p1.next;
            }
            //移动p1,p2
            ListNode p2=pHead;
            while(p1!=p2){
                p1=p1.next;
                p2=p2.next;
            }
            return p1;
        }
    }

    阅读全文>>

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

2018-08-24

1036. 跟奥巴马一起编程(15)-浙大PAT乙级真题java实现

    1036.跟奥巴马一起编程(15) 
    美国总统奥巴马不仅呼吁所有人都学习编程,甚至以身作则编写代码,成为美国历史上首位编写计算机代码的总统。2014年底,为庆祝“计算机科学教育周”正式启动,奥巴马编写了很简单的计算机代码:在屏幕上画一个正方形。现在你也跟他一起画吧! 
    输入格式: 
    输入在一行中给出正方形边长N(3<=N<=20)和组成正方形边的某种字符C,间隔一个空格。 
    输出格式: 
    输出由给定字符C画出的正方形。但是注意到行间距比列间距大,所以为了让结果看上去更像正方形,我们输出的行数实际上是列数的50%(四舍五入取整)。 
    输入样例: 
    10 a 
    输出样例: 
    aaaaaaaaaa 
    a               a 
    a               a 
    a               a 
    aaaaaaaaaa


    阅读全文>>

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

2018-01-23

61.序列化二叉树

    61.序列化二叉树

    题目描述

    请实现两个函数,分别用来序列化和反序列化二叉树
    算法思想:根据前序遍历规则完成序列化与反序列化。所谓序列化指的是遍历二叉树为字符串;所谓反序列化指的是依据字符串重新构造成二叉树。依据前序遍历序列来序列化二叉树,因为前序遍历序列是从根结点开始的。当在遍历二叉树时碰到Null指针时,这些Null指针被序列化为一个特殊的字符“#”。另外,结点之间的数值用逗号隔开。


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

    public class Solution {
        public int index = -1;
        public String Serialize(TreeNode root) {
            StringBuffer sb = new StringBuffer();
            if(root == null){
                sb.append("#,");
                return sb.toString();
            }
            sb.append(root.val + ",");
            sb.append(Serialize(root.left));
            sb.append(Serialize(root.right));
            return sb.toString();
            
       }
        public TreeNode Deserialize(String str) {
            index++;
            int len = str.length();
            if(index >= len)
                return null;
            String[] strr = str.split(",");
            TreeNode node = null;
            if(!strr[index].equals("#")){
                node = new TreeNode(Integer.valueOf(strr[index]));
                node.left = Deserialize(str);
                node.right = Deserialize(str);
            }
            return node;
       }
    }
    阅读全文>>

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

2018-08-25

栈的压入、弹出序列

    21.栈的压入、弹出序列

    题目描述

    输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。(注意:这两个序列的长度是相等的)

    import java.util.ArrayList;
    import java.util.Stack;
    public class Solution {
        public boolean IsPopOrder(int [] pushA,int [] popA) {
            if(pushA.length == 0 || popA.length == 0)
                return false;
            Stack<Integer> s = new Stack<Integer>();
            int popIndex = 0;
            for(int i = 0; i < pushA.length; i++){
                s.push(pushA[i]);
                while(!s.empty() && s.peek() == popA[popIndex]){
                    s.pop();
                    popIndex++;
                }
            }
            return s.empty();
        }
    }

    阅读全文>>

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

2018-08-14

树的子结构

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

2018-08-13