剣指Offerプログラミング整理(三)

1、二叉探索木の後順遍歴シーケンス
2、二叉木とある値の経路
3、複雑なチェーンテーブルのコピー
4、二叉検索ツリーと双方向チェーンテーブル
5、文字列の配列
6、配列の出現回数が半分を超える数字
7、最小のk個数
8、連続サブ配列の最大和
9、整数のうち1の出現回数(1からnのうち1の出現回数)
10、配列を最小にする
11、ブス数
1、二叉探索木の後順遍歴シーケンス
(1)問題の説明:
整数配列を入力し、その配列が二叉探索ツリーの後順に遍歴した結果であるかどうかを判断します.もしそうであればYesを出力し、そうでなければNoを出力します.入力された配列の任意の2つの数字が互いに異なると仮定します.
(2)問題を解く構想:
二叉検索ツリー:すなわち、二叉ソートツリー、または空のツリー、または次の性質を持つ二叉ツリーです.左のサブツリーが空でない場合、左のサブツリー上のすべてのノードの値は、そのルートノードの値よりも小さくなります.その右に
サブツリーが空でない場合、右サブツリー上のすべてのノードの値は、そのルートノードの値よりも大きくなります.その左、右のサブツリーもそれぞれ二叉探索ツリーである.
後順遍歴:左右のルート;
以上から、配列の最後の要素はルートノードであることがわかる.
配列の前のn-1要素は2つの部分に分けることができ、左の値は右の値より小さい.
再帰的に左右の木が1本もないと判断した.
(3)コード実装:

 public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence==null||sequence.length==0)
            return false;
        boolean res=getRes(sequence,0,sequence.length-1);
        return res;
    }
    public boolean getRes(int[] s,int start,int end){
        int i=0;
        int j=0;
        if(end-start<=1)
            return true;
        for(i=start;is[end])
                break;
        }
        for(j=i;j0){
            left=getRes(s,start,i-1);
        }
        if(i

補足:
Arrays.copyOfRange(T[]original,int from,int to)元の配列originalを、小標fromからコピーし、小標toにコピーし、下標fromを含む新しい配列を生成します.
下付きtoは含まれず,効率はcloneとほぼ一致し,いずれもnative methodであり,ループレプリケーション配列を利用するよりもはるかに効率的である.
2、二叉木とある値の経路
(1)問題の説明:
ツリーと整数を入力し、ツリー内のノード値と入力整数のすべてのパスを印刷します.パスは、ツリーのルートノードからリーフノードまで続くノードがパスを形成するように定義されます.
ツリーノードの定義:

public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}

(2)問題を解く構想:
深さは遍歴し,遍歴しながら累加する.
(3)コード実装:

public class Solution {
    ArrayList> result=new ArrayList>();
    ArrayList arr=new ArrayList();
    int num=0;
    public ArrayList> FindPath(TreeNode root,int target) {
        if(root==null)
            return result;
        boolean isLeaf=root.left==null&&root.right==null;
        num+=root.val;
        arr.add(root.val);
        if(num==target&&isLeaf){
            ArrayList path=new ArrayList();
            for(int i=0;i

3、複雑なチェーンテーブルのコピー
(1)問題の説明:
複雑なチェーンテーブル(各ノードにノード値と2つのポインタがあり、1つは次のノードを指し、もう1つの特殊なポインタは任意のノードを指す)を入力し、コピー後の複雑なチェーンテーブルのheadを返します.(注)
なお、出力結果ではパラメータのノード参照を返さないでください.そうしないと、問題判定プログラムは直接空に戻ります)
(2)問題を解く構想:
法一:レプリケーションプロセスを2つのステップに分け、最初のステップは元のチェーンテーブルの各ノードをレプリケーションし、nextでリンクします.第2のステップでは、各ノードを位置決めするrandomは、チェーンテーブルのヘッダノードから開始する必要があります.
法2:空間を時間に変えて、最初のステップは元のチェーンテーブルの各ノードNをコピーしてN’を新しくして、それからこれらの新しくできたノードをnextでリンクします.同時にペアリング情報をハッシュテーブルに配置します.ステップ2
元のチェーンテーブルにおけるノードNのrandomポインタがSを指す場合、複製チェーンテーブルにおいて、対応するN’がS’を指す場合、ハッシュテーブルを用いてSに基づいてS’を見つけることができる.
法3:最初のステップは、元のチェーンテーブル上の各ノードNをコピーして、対応するN’を作成し、N’をNの後に置く.ステップ2:各ノードのrandomを設定する 針.元のチェーンテーブル上のノードNのrandomがSを指す場合、対応する複製ノードN’のrandomはS’を指す. 第三歩:長鎖表を二つの鎖表に分ける:奇数位置の結点をnextで接続すると元の鎖表であり、偶数位置の結点をnextで接続すると複製された鎖表である.
(3)コード実装:法三:

/*
public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}
*/
public class Solution {
    public RandomListNode Clone(RandomListNode pHead)
    {
        if(pHead==null)
            return null;
        RandomListNode pCur=pHead;
        while(pCur!=null){
            RandomListNode node=new RandomListNode(pCur.label);
            node.next=pCur.next;
            pCur.next=node;
            pCur=node.next;
        }
        pCur=pHead;
        while(pCur!=null){
            if(pCur.random!=null)
                pCur.next.random=pCur.random.next;
            pCur=pCur.next.next;
        }
        RandomListNode head=pHead.next;
        RandomListNode cur=head;
        pCur=pHead;
        while(pCur!=null){
            pCur.next=pCur.next.next;
            if(cur.next!=null)
                cur.next=cur.next.next;
            cur=cur.next;
            pCur=pCur.next;
        }
        return head;
    }
}

4、二叉検索ツリーと双方向チェーンテーブル
(1)問題の説明:
ツリーを入力し、ツリーを並べ替えた双方向チェーンテーブルに変換します.新しいノードを作成できない必要があります.ツリー内のノードポインタの方向を調整するしかありません.
(2)問題を解く構想:
左サブツリーを2つのチェーンテーブルに構築し、チェーンテーブルヘッダノードに戻ります.
左サブツリーの二重チェーンテーブルの最後のノードにナビゲートします.
左サブツリーチェーンテーブルが空でない場合は、現在のrootを左サブツリーチェーンテーブルに追加します.
右サブツリーを二重チェーンテーブルに作成し、チェーンテーブルヘッダノードに戻ります.
右サブツリーチェーンテーブルが空でない場合は、そのチェーンテーブルをrootノードの後に追加します.左サブツリーチェーンテーブルが空であるかどうかに基づいて、返されるノードを決定します.
(3)コード実装:

public TreeNode Convert(TreeNode root) {
        if(root==null)
            return null;
        if(root.left==null&&root.right==null)
            return root;
        // 1.          ，        
        TreeNode left = Convert(root.left);
        TreeNode p = left;
        // 2.               
        while(p!=null&&p.right!=null){
            p = p.right;
        }
        // 3.            ，   root        
        if(left!=null){
            p.right = root;
            root.left = p;
        }
        // 4.          ，        
        TreeNode right = Convert(root.right);
        // 5.            ，       root    
        if(right!=null){
            right.left = root;
            root.right = right;
        }
        return left!=null?left:root;       
    }

5、文字列の配列
(1)問題の説明:
文字列を入力し、その文字列のすべての配列を辞書順に印刷します.例えば文字列abcを入力すると、文字a,b,cで並べられるすべての文字列abc,acb,bac,bca,cab,cbaが印刷される.
(2)問題を解く構想:
1番目の可能性のあるすべての状況をリストし、後のビットを再帰します.
1位と各位を交換する.再帰的な終了条件は、1番目と最後の交換が完了することである.
(3)コード実装:

import java.util.ArrayList;
import java.util.Collections;
public class Solution
{
    public ArrayList Permutation(String str)
    {
        ArrayList res=new ArrayList();
        if(str.length()==0||str==null)return res;
        int n= str.length();
        helper(res,0,str.toCharArray());
        Collections.sort(res);//    ，         ， sort    
        return res;
         
    }
    public void helper( ArrayList res,int index,char []s)
    {
        if(index==s.length-1)res.add(new String(s));         ，            
        for(int i=index;i//          
        {
            if(i==index||s[index]!=s[i])//             ，     
            {
                swap(s,index,i);
                helper(res,index+1,s);  ，      ，      ，         。
                swap(s,index,i);//         ，       
            }
        }
         
    }
     
    public void swap(char[]t,int i,int j)
     {
        char c=t[i];
        t[i]=t[j];
        t[j]=c;
    }
}

6、配列の出現回数が半分を超える数字
(1)問題の説明:
配列の1つの数字が配列の長さの半分を超える回数がある場合は、この数字を見つけてください.例えば、長さ9の配列{1,2,3,2,2,5,4,2}を入力します.数字2は配列中に5回出現し,配列長の半分を超えるため,2を出力する.存在しない場合は0を出力します.
(2)問題を解く構想:
配列の数が配列の長さの半分を超える場合、並べ替え後、その数は配列の真ん中にあるに違いない.
まず速い列を行って、それから配列の最も中間の数を取ります;
この配列を巡って、最も中間の数が配列の長さの半分を超えると、この数が出力されます.
(3)コード実装:

public int MoreThanHalfNum_Solution(int [] array) {
        int len=array.length;
        if(len<1){
            return 0;
        }
        int count=0;
        Arrays.sort(array);
        int num=array[len/2];
        for(int i=0;i

7、最小のK個数
(1)問題の説明:
n個の整数を入力し、その中で最も小さいK個の数を見つけます.例えば4,5,1,6,2,7,3,8の8つの数字を入力すると、最小の4つの数字は1,2,3,4である.
(2)問題を解く構想:
法一:配列を速く並べます;早い列の後ろのK個の数を取る.
法二:配列の前のk個の数を1つのcopyを1つの配列int[]tempに置く.temp配列を速く並べます.元の配列のk番目の要素から始め、temp配列の中で最大の要素temp[k-1]と1つずつ比較する.temp[k-1]
元の配列より小さい場合は、元の配列を1つ取り外し、temp[k-1]が元の配列の要素より大きい場合は、2つの数を交換し、temp配列を速く並べます.最後にtemp配列を出力します.
(3)コード実装:
法一:略
法二:

public static ArrayList getLastKnum(int[] input,int k){
        ArrayList list = new ArrayList();
        int[] temp = new int[k];
        temp = Arrays.copyOfRange(input,0,k);
        Arrays.sort(temp);
        for (int i = k ;i input[i]){
                int a = temp[k-1];
                temp[k-1] = input[i];
                input[i] = a;
                Arrays.sort(temp);
            }
        }
        for (int i : temp){
            list.add(i);
        }
        return list;
    }

8、連続サブ配列の最大和
(1)問題の説明:
HZはたまに専門的な問題を持って非コンピュータ専門の同級生をからかっている.今日のテストグループの会議が終わった後、彼はまた話をしました:古い1次元モードの識別の中で、いつも連続するサブベクトルの最大和を計算する必要があって、ベクトルがすべて正数の時、問題はとてもよく解決します.しかし、ベクトルに負の数が含まれている場合、ある負の数を含んで、隣の正の数が補うことを期待しますか?例えば,{6,−3,−2,7,−15,1,2,2},連続サブベクトルの最大和は8(0番目から3番目まで)である.彼にだまされるの?(サブベクトルの長さは少なくとも1)
(2)問題を解く構想:
法一:蛮力法、すべてのサブ配列を見つける;
法二:計算されたサブ配列の和を繰り返し利用する.
法三:動的計画:
currSumを現在の要素で終わる最大連続サブ配列の和にします.
maxSumはグローバルで最も大きなサブ配列の和である.
後でスキャンすると、j番目の要素には2つの選択があり、前に見つかったサブ配列を入れるか、最新のサブ配列の最初の要素を入れるかのいずれかです.
currSum>0の場合、currSumにa[j]を加算する.
currSum<0の場合、currSumは現在の要素として設定されます.すなわちcurrSum=a[j];
(3)コード実装:
法一:略
法二:

public int FindGreatestSumOfSubArray(int[] array) {
        int max=array[0];
        for(int i=0;imax)
                    max=sum;
            }
        }
        return max;
    }

法3:

public static int FindGreatestSumOfSubArray(int[] array) {
        if (array.length == 0 ){
            return 0;
        }
        int currSum = 0;
        int maxSum = array[0];
        for (int j=0 ;j= 0){
                currSum += array[j];
            }else {
                currSum = array[j];
            }

            if (currSum > maxSum){
                maxSum = currSum;
            }
        }

        return maxSum;
    }

9、整数のうち1が現れる回数(1からnまでの整数のうち1が現れる回数)
(1)問題の説明:
1~13の整数のうち1が出現する回数を求め、100~1300の整数のうち1が出現する回数を算出する.そのため、1~13に含まれる1の数字を1、10、11、12、13と特別に数えて6回も現れたが、後の問題には仕方がない.ACMerはあなたたちが彼を助けることを望んで、そして問題をもっと普遍化して、すぐに任意の非負の整数区間の中で1の出現の回数を求めることができます.
(2)問題を解く構想:
法一:文字配列;
法二:数学の方法.
(3)コード実装:
法一:

public int NumberOf1Between1AndN_Solution(int n) {
    
        int count=0;
        while(n>0){
            String str=String.valueOf(n);
            char[] chars=str.toCharArray();
            for(int i=0;i

法二:

public static int NumberOf1Between1AndN_Solution(int n) {
        int count = 0;
        for (long m = 1; m <= n; m *= 10)
            count += (n/m + 8) / 10 * m + (n/m % 10 == 1 ? n%m + 1 : 0);
        return count;
    }

10、配列を最小にする
(1)問題の説明:
正の整数配列を入力し、配列内のすべての数字をつなぎ合わせて1つの数に並べ、つなぎ合わせることができるすべての数字の中で最小の1つを印刷します.例えば配列{3,32321}を入力すると、この3つの数字が並べられる最小数字は321323となる.
(2)問題を解く構想:
「3」と「32」は直接「3」.compareTo(「32」)の演算を行うことができない.2つの文字列をつなぎ合わせて「332」.compareTo(「323」)を比較するのです
(3)コード実装:

 public String PrintMinNumber(int [] numbers) {

        if(numbers==null||numbers.length==0)
            return "";
        int len=numbers.length;
        String[] str=new String[len];
        StringBuilder sb=new StringBuilder();
        for(int i=0;i(){
            public int compare(String s1,String s2){
                String c1=s1+s2;
                String c2=s2+s1;
                return c1.compareTo(c2);
            }
        });
        for(int i=0;i

11、ブス数
(1)問題の説明:
因子2,3,5のみを含む数をブス数(Ugly Number)と呼ぶ.例えば、6、8はすべて丑数であるが、14は因子7を含むためではない.習慣的に私たちは1を最初の醜数と見なしています.小さいから大きい順のN番目の丑数を求めます.
(2)問題を解く構想:
法一:各整数が丑数であるかどうかを逐一判断し、丑数の定義によると、丑数は2,3,5でしか除かれない.つまり、1つの数が2で割り切れると、私たちはそれを連続的に2で割ることができます.3で割り切れるなら、連続して3で割る.5で割り切れるなら、5で割る.もし最後に私たちが得たのが1であれば、この数は醜い数で、そうでなければそうではありません.
法二:配列を作成して見つかったブス数を保存し、空間で時間を変え、ブス数の定義によると、ブス数は別のブス数に2,3,5を乗じた結果、配列を作成し、中の数字はソートされたブス数であり、それぞれのブス数は前のブス数に2,3,5を乗じたものである.
(3)コード実装:
法一:略;
法二;

public int GetUglyNumber_Solution(int index) {
        if(index<=0)
            return 0;
        int[] result=new int[index];
        int count=0;
        int i2=0;
        int i3=0;
        int i5=0;
        result[0]=1;
        int tmp=0;
        while(countb)?b:a;
    }