剣指offer-java（1）

（1）二次元配列の中の検索は二次元配列の中で、各行は左から右にインクリメントされた順に並べられ、各列は上から下にインクリメントされた順に並べられます。このような二次元配列と整数を入力して、配列に整数が含まれているかどうかを判断する関数を完成してください。

public class Solution {
    public boolean Find(int [][] array,int target) {
        for(int i=0;i<array.length;i++){
            for(int j=0;j<array[0].length;j++){
                if(target==array[i][j])
                    return true;
            }
        }
        return false;
    }
}

（2）スペースを置換するには、関数を実行して、文字列の中のスペースを「%20」に置換してください。例えば、文字列がWe Aree Happyである場合、置換された文字列はWe%20 Aree%20 Happyである。

public class Solution {
    public String replaceSpace(StringBuffer str) {
        String s=str.toString().replaceAll(" ","\\%20");
        return s;
    }
}

（3）最後の端からチェーンテーブルを印刷して、最後の端からチェーンテーブルの各ノードの値を印刷します。入力説明：チェーンの出力説明として入力します。プリントが必要な「新しいチェーンテーブル」の出力先です。

*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
import java.util.*;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list=new ArrayList<Integer>();
        LinkedList<Integer> stack=new LinkedList<Integer>();
        ListNode p=listNode;
        if(listNode==null)
            return list;
        while(p!=null){
            stack.push(p.val);
            p=p.next;
        }
        while(!stack.isEmpty()){
            list.add(stack.pop());
        }
        return list;
    }
}

（4）二叉樹を再構築して、ある二叉樹の前の順序と中の順序を経た結果を入力して、二叉樹を再構築してください。入力された前の順序と中の順序を巡回した結果には重複した数字が含まれていないと仮定します。例えば、シーケンス｛1,2,4,7,3,5,6,8｝と中順序巡回シーケンス｛4,7,2,1,5,3,8,6｝を入力すると、二叉ツリーを再構築して戻ります。

/** 1. Definition for binary tree 2. public class TreeNode { 3. int val; 4. TreeNode left; 5. TreeNode right; 6. TreeNode(int x) { val = x; } 7. } */
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        TreeNode root=reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);
        return root;
    }
    public reConstructBinaryTree(int[] pre,int startp,int endp,int[] in, int startin, int endin ){
     //             
    //           ，      ，      
        if(startp>endp||startin>endin)
            return null;
        TreeNode root=new TreeNode(pre[startp]);
        for(int i=0;i<in.length;i++){
            if(in[i]==pre[startp])  {
                root.left=reConstructBinaryTree(pre,startp+1,i-startin+startp,in,startin,i-1);
                root.right=reConstructBinaryTree(pre,i-1-startin+1+startp,end,in,i+1,endin);
            }
        }
        return root;
    }
}

（5）2つのスタックでキューを2つのスタックで実現し、1つのキューを実現し、キューのPushおよびPop操作を完了する。キューの要素はintタイプです。

import java.util.Stack;
import java.util.*;
public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

    public void push(int node) {
        stack1.push(node);
    }
    //       ，
    //    “    ” 
    //        1 ，        2 ，       2   ， 
    //          

    //            
    //   1   2           ，   ，        
    public int pop() {
        int node=0;
        if(!stack2.isEmpty()){
            node=stack2.pop();

        }else{
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
            node=stack2.pop();

        }
        return node;

    }
}

（6）回転配列の最小数は、1つの配列の最初のいくつかの要素を配列の最後に移動します。これを配列の回転と呼びます。無逓減シーケンスの回転を入力して、回転配列の最小要素を出力します。例えば配列｛3,4,5,1,2｝は｛1,2,3,4,5｝の回転であり、この配列の最小値は1である。

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        int min=Integer.MAX_VALUE;
        if(array.length==0)
            return 0;
        for(int i=0;i<array.length;i++){
            if(min>=array[i])
                min=array[i];
        }
        return min;
    }
}

（7）フィボナッチの数列はフィボナッチの数列を知っています。今は整数nを入力してください。フィボナッチの数列の第n項目を出力してください。

public class Solution {
    public int Fibonacci(int n) {
        if(n==0)return 0;
        int[] f=new int[n+2];
        f[0]=0;f[1]=1;
        for(int i=2;i<f.length;i++){
            f[i]=f[i-1]+f[i-2]; 
        }
        return f[n];
    }
}

（8）階段を跳ぶカエルは1回に1段の階段を上がることができます。2段の階段を上がることもできます。この蛙が1つのn段の階段に上がることを求めて、全部で何種類の踊り方がありますか？

public class Solution {
    public int JumpFloor(int target) {
        if(target==0)
            return 0;
        else if(target==1)
            return 1;
        else if(target==2)
            return 2;
        else
            return JumpFloor(target-1)+JumpFloor(target-2);

    }
}

（9）変態の階段をジャンプして、カエルが1回に1段の階段を飛び上がることができます。2段の階段を飛び上がることもできます。この蛙が1つのn段の階段に上がることを求めて、全部で何種類の踊り方がありますか？

public class Solution {
    public int JumpFloorII(int target) {
            return JumpFloor(target);
    }
    public int JumpFloor(int target){
        int sum=1;
        if(target==0)
            return 0;
        if(target==1)
            return 1;
        if(target==2)
            return 2;
        for(int i=0;i<target;i++){
            sum+=JumpFloor(i);
        }
        return sum;
    }
}

（10）長方形で覆われています。2*1の小さな長方形を横にしたり、縦にしたりして、より大きな長方形をカバーします。すみません、n個の2*1の小さい長方形を重複なく2*nの大きな長方形に上書きするには、いくつの方法がありますか？

public class Solution {
    public int RectCover(int target) {
    if(target==0)
        return 0;
    else if(target==1)
        return 1;
    else if(target==2)
        return 2;
    else
        return RectCover(target-1)+RectCover(target-2);
    }
}

（11）2進数のうち1の個数は1つの整数を入力し、その数は2進数表現のうち1の個数を出力します。負の数は補数で表します。

public class Solution {
    public int NumberOf1(int n) {
        int count=0;
        while(n!=0){
            n=n&(n-1);
            count++;
        }
        return count;
    }
}

（12）数値の整数乗は、ドット型の浮動小数点ベースとint型の整数exponentを与えます。baseのexponentの次の方を求めます。

public class Solution {
    public double Power(double base, int exponent) {
        double a=base;
        if(exponent>0){
            while((exponent--)>1){
                base=base*a;
            }
            return base;
        }else if(exponent<0){
            while((exponent++)<-1){
                base=base*a;
            }
            return 1.0/base;
        }
        else{
            return 1.00000;
        }
  }
}

（13）配列の順序を調整して、奇数を偶数の前に位置させて整数配列を入力し、奇数と奇数、偶数と偶数の間の相対的な位置が変わらないように、配列の前半部分にすべての奇数が配置されるように調整する関数を実現する。

import java.util.*;
public class Solution {
    public void reOrderArray(int [] array) {
        List<Integer> odd=new ArrayList<Integer>();
        List<Integer> oven=new ArrayList<Integer>();
        for(int i=0;i<array.length;i++){
            if(array[i]%2==1)        
                odd.add(array[i]);
            else
                oven.add(array[i]);
        }
        int m=0;
        for(int i=0;i<odd.size();i++){
            array[m++]=odd.get(i);
        }
        for(int i=0;i<oven.size();i++){
            array[m++]=oven.get(i);
        }
    }
}

（14）チェーンテーブルの最後からk番目の結点にチェーンテーブルを入力し、このチェーンテーブルの最後からk番目の結点を出力します。

/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(head==null)
            return head;
        if(k<=0)
            return null;
        ListNode p1=head;
        ListNode p2=head;
        while(p1!=null&&(--k)>0){
            p1=p1.next;
        }
        if(p1==null)
            return null;
        while(p1.next!=null){
            p1=p1.next;
            p2=p2.next;
        }
        return p2;
    }
}

（15）チェーンテーブルを反転させ、チェーンテーブルを反転させ、チェーンテーブルのすべての要素を出力します。

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head==null||head.next==null)
            return head;
        ListNode newHead=null;
        ListNode pre=null;
        ListNode pnext=null;
        ListNode p=head;
        while(p!=null){
            pnext=p.next;
            if(pnext==null) 
                newHead=p;
            p.next=pre;
            pre=p;
            p=pnext;
        }
        return newHead;
    }
}

（16）二つの並べ替えられたチェーンを結合して、二つの単調に増分されたチェーンを入力し、二つのチェーンを合成した後のチェーンを出力します。もちろん、合成後のチェーンは単調な規則を満足させる必要があります。

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1==null)
            return list2;
        else if(list2==null)
            return list1;
        ListNode MergeList=null;
        if(list1.val<list2.val){
            MergeList=list1;
            MergeList.next=Merge(list1.next,list2);
        }else{
            MergeList=list2;
            MergeList.next= Merge(list1,list2.next);
        }
        return MergeList;
    }
}

（17）ツリーのサブ構造は、二叉樹A、Bを2本入力し、BがAのサブ構造であるかどうかを判断する。

/** 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)return false;
        if(root2==null&&root1!=null)
            return true;
    if(root1!=null&&root2!=null){
        if(root1.val==root.val){
            result=DoesRoot1HasRoot2(root1,root2)   ;
        }
        if(!result){
            result=HasSubtree(root1.left,root2);
        }
        if(!result){
        result=HasSubtree(root1.right,root2);
        }
    }
    return result;
    }
    public boolean DoesRoot1HasRoot2(TreeNode root1,TreeNode root2)  {
        if(root1==null&&root2!=null)
            return false;
        if(root2==null)
            return true;
        if(root1.val!=root2.val)
            return false;
        return DoesRoot1HasRoot2(root1.left,root2.left)&DoesRoot1HasRoot2(root1.right,root2.right);
    }
}

（18）二叉樹の鏡像は、与えられた二叉樹を操作し、ソース二叉樹の鏡像に変換する。

/** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */
public class Solution {
    public void Mirror(TreeNode root) {
        if(root==null)
            return null;
    TreeNode rootLeft=root.left;
    TreeNode rootRight=root.right;
    root.left=rootRight;
    root.right=rootLeft;
    Mirror(root.left);
    Mirror(root.right);
    }
}

（19）時計回りの印刷行列に行列を入力し、外向から時計回りの順に各数字を順次印刷します。たとえば、行列を入力すると、1 2 3 4 5 5 6 6、7 7、10 11、12、3、4、8、16、15、14、13、9、5、6、7、11、10が順次印刷されます。

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printMatrix(int [][] matrix) {
       ArrayList<Integer> list=new ArrayList<Integer>();
       int row=matrix.length;
       int col=matrix[0].length;
       int top=0,bottom=row-1,left=0,right=col-1;
       while(left<=right&&top<=bottom){
           for(int i=left;i<=right;i++){
               list.add(matrix[0][i]);
           }
           for(int i=top+1;i<=bottom;i++){
               list.add(matrix[i][right]);
           }
           if(top!=bottom)
               for(int i=right-1;i>=left;i--){
                   list.add(matrix[bottom][i]);
               }
           if(left!=right)
               for(int i=bottom-1;i>top;i--){
                   list.add(matrix[i][left]);
               }
           top++;left++;right--;bottom--;
       }
       return list;
    }
}

（20）min関数を含むスタック定義スタックのデータ構造は、スタックの最小要素を得ることができるmin関数をこのタイプで実現してください。

import java.util.Stack;
import java.util.*;
public class Solution {
    LinkedList<Integer> stack=new LinkedList<Integer>();

    public void push(int node) {
        stack.push(node);
    }

    public void pop() {
        stack.pop();
    }

    public int top() {
        int i=stack.peek();
        return i;
    }

    public int min() {
        int min=stack.peek();
        int tmp=0;
        Iterator<Integer> it=stack.iterator();
        while(it.hasNext()){
            tmp=it.next();
            if(min>tmp)        
                min=tmp;
        }
        return min;
    }
}