小景哥哥

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

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--;
        }
    }
    
}

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;
    }
}

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

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;
    }
}

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

61.序列化二叉树

题目描述

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();
    }
}

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);
    }
}