いくつかの面白い問題とその解法

ブログを見ていたら、いいですね.回ってきました.原作者:ゼロから無限大
単一チェーンテーブルの最後からK番目のノードを見つけるアルゴリズムを実現する.
1つの比較的効率的な解法は、チェーンテーブル内のK個のノードから離れた2つのノードをそれぞれ指す2つのポインタを使用することである.次に、チェーンテーブルに沿って2つのポインタを同時に移動し、そのうちの1つが最初にチェーンテーブルの末端に到達したとき、もう1つのポインタは最後からK番目のノードを指します.アルゴリズムの時間的複雑さはO(n)であることが明らかになった.

public ListNode kthToLast(ListNode head, int k) {
    if (K <= 0) return null;

    ListNode fast = head;
    ListNode slow = head;

    // fast      k   
    for (int i = 1; i <= k; i++) {
        if (slow == null) return null;
        fast = fast.next;
    }
    if (fast == null) return null;

    // fast     ，slow       K   
    while (fast.next != null) {
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}

チェーンテーブルにループがあるかどうかを検出します.
クイックポインタ針法を使用して、クイックポインタは一度に2ステップ、スローポインタは一度に1ステップ移動します.チェーンテーブルにループが存在する場合、2つのポインタは必ず出会う.このようなスローポインタの使用方法は、2倍速のクイックポインタを使用してチェーンテーブルの中間位置にスローポインタを位置決めすることができ、3倍速のクイックポインタをチェーンテーブルの3分の1の位置にスローポインタを位置決めすることができるなど、多くのチェーンテーブルの問題を解決するための考え方を提供することができる.
コード(n&(n-1)==0はどういう意味ですか?
このコードは、nが0または2であるかどうかを確認するために使用することができる.同じn=n&(n−1)はnの最低有効ビットをクリアする.
一時変数を使用せずに2つの数を直接交換する方法を実現します.
方法1:

public static void swap(int a, int b) {
    a = a - b;
    b = a + b;
    a = b - a;  
}

方法2:

public static void swap(int a, int b) {
    a = a^b;
    b = a^b;
    a = a^b;
}

バイナリに変換する場合、2ビットビットを正しく交換できればよい.
「+」または他の演算子を使用できない2つの数値を加算する方法を実装します.
この問題を解く鍵は、「加算」と「キャリー」の2つの操作を別々に行うことであり、バイナリについては、キャリーを考慮せずに2つの数を加算することであり、すなわち異或操作を行うことに相当する.しかし、キャリーのみを考慮すると、また、ビット毎とシフト加算操作に相当する.したがって、コードは次のように実装できます.

public static int add(int a, int b) {
    if (b == 0) return a;

    //       
    int sum = a ^ b;
    //    
    int carry = (a & b) << 1;
    //     
    return add(sum, carry);
}

20本の錠剤があり、そのうち19本は1グラム/粒の錠剤が入っており、残りの1本は1.1グラム/粒の錠剤が入っている.正確な天秤をあげます.どうやって重い丸薬を見つけますか?天秤は一度しか使えません.
20本の錠剤に対して1から20番まで、各錠剤から対応する番号の錠剤を取り出し、例えば1番の錠剤から1本、2番の錠剤から2本......を取り出し、これらを取り出した錠剤を一緒に天秤にかけて秤量します.各錠剤が1グラム重い場合、総重量は(1+2+3+4+......+19+20)=210グラムであるべきであるため、実際の重量が210グラムより大きい場合、多くの重量は0.1グラム未満の錠剤から来ているに違いない.そのため、より多く出た重量を0.1グラムで割ったものが瓶の番号です.
2本のロープを与えて、1本のロープが燃え尽きるのにちょうど1時間かかります.どうやってこの2本のロープで正確に15分計量しますか?ロープ密度が不均一である.
この問題の鍵は、ロープの密度が不均一であるが、両端から同時にロープに火をつけると、1本のロープが燃え上がるのにちょうど30分かかることだ.だから、この2本のロープのうちの1本を片方から火をつけ、もう1本を同時に両端から火をつけ、両端に火をつけたロープが燃え上がるのを待つと、ちょうど30分が過ぎます.この時、片方から火をつけたロープはさらに30分焼くことができ、このロープのもう片方に火をつけ、時間を計り始め、焼き終わったら、ちょうど15分計量します.
1つの方法isSubString()を指定すると、1つの文字列が他の文字列のサブ列であるかどうかを確認し、2つの文字列s 1およびs 2を指定することができる.1つの方法を実装し、s 2がs 1回転であるかどうかを確認し、isSubString()メソッドを1回しか呼び出せない.
例を挙げると、s 2=colinwangはs 1=wangcolinで回転するので、s 1を2つの部分に分けることができます.すなわち、s 1=xy、x=wang、y=colinです.このときyxは必ずxyxyのサブストリングであること,すなわちs 2は必ずs 1 s 1のサブストリングであるためisSubString(s 1 s 1,s 2)を呼び出すだけでよい.
0から4の間の整数乱数を生成できる方法rand 5()が与えられ、0から6の間の整数乱数を生成できる方法rand 7()が実現される.
rand 7()は、0から6の間の整数を返し、各整数を返す確率は7分の1であるべきである.whileサイクルを用いて,各数値が現れる確率が同じ範囲の数値(少なくとも7要素を含む)を生成することができる.このように,その中の7より大きい倍数の部分を捨て,最後に7で割って余りをとり,0から6の範囲の乱数を得,各値が現れる確率は7分の1であった.次のコードを参照してください.

public static int rand7() {
    while(true) {
        //  rand   0 24  ，            ，
        //    21、22、23、24，        0 3        
        int rand = 5*rand5() + rand5();
        if (rand < 21) {
            return rand % 7;
        }
    }
}

上のコードでrand=5*rand 5()+rand 5()を選択した理由は、0から24の間の数字を均一に生成できるため、0から24の間の数字が現れる確率が同じであることを保証しているからです.rand=2*rand 5()+rand 5()を選択すると、これらの値が均一に分布していないため、例えば6を取得するには2つの方式(6=2*1+4と6=2*2+2)があり、0を取得するには1つの方式(0=2*0+0)しかないため、値ごとに出現する確率が等しくない.この問題の鍵は範囲を見つけ,その中の各値が現れる確率を同じにすることにある.