よくあるチェーンテーブルの反転、バイトのジャンプに条件をつけて、面接者は「私は難しい」と叫んでいます|図解アルゴリズム

本文は公衆番号「承香墨影(ID:cxmyDev)」から先発し、注目を歓迎する.
一.シーケンス
私はまたチェーンテーブルの問題を話しました.この問題はバイトの鼓動からの面接問題だそうです.
なぜ「聞く」と言うのですか?私も見たので、テーマは面白いと思いますが、原作者が出した案は、まだ最適化の余地があると思い、単独で出して話したいと思います.
本文のテーマが言ったように、これはチェーンテーブルの反転に関する問題です.チェーンテーブルの反転は、以前の文章でもたくさん話しました.例えば、チェーンテーブルの反転、チェーンテーブルの2つの反転、Kの1組の反転チェーンテーブルです.これらは実はleetcodeの標準問題ですが、通常、企業が与える面接問題は、多くの場合、いくつかの変種をしたり、特殊な条件を加えたりします.
例えば今日お話しするこの問題です.
単一チェーンテーブルのヘッダノードheadが与えられ、チェーンテーブルの調整関数が実現され、チェーンテーブルの末尾からK個のノードを一組として逆順序で反転され、ヘッダの残りのノードが一組未満の場合、反転する必要がない.(キューまたはスタックはサポートとして使用できません)
問題をよく読むと、私たちが前に話したleetcode第25題のように、K個の反転チェーンテーブルのセットがあります.
leetcode-25は、先頭ノードから始まり、K個のノードのセットで反転する.バイトのジャンプという問題は、終わりから始まります.
最後のノードからグループを分けて反転する条件が一つ増えただけで、この問題の難易度は増加した.
二.K個一組反転チェーンテーブル(トップ版)
2.1他の人の解題の考え方
前にも言いましたが、この問題は私が見たもので、当時は文章の形式で発表されていました.
文章はもう出しませんが、まず彼の解題の考え方を理解して、私たちの思考に役立ちます.
彼の考えははっきりしていて、この問題は彼が解けないが、leetcode-25という標準的なK個のチェーンテーブルを反転させる問題は彼はよく知っている.
では、元のチェーンテーブルを一度「チェーンテーブル反転」してから「K個一組反転チェーンテーブル」を行い、最後に「チェーンテーブル反転」してチェーンテーブルを復元すると、必要な結果が得られます.

ListNode revserseKGroupPlus(ListNode head, int k) {
  //     
  head = reverseList(head);
  // K        
  head = reverseKGroup(head, k);
  //     
  head = reverseList(head);
  return head;
}

よく知らない問題を、簡単な転換を経て、よく知っている問題になって解決するという考え方は間違っていない.
しかし、質問があります.
面接のシーンでは、通常、面接官のレベルが面接者より高いので、面接は絶えず挫折する過程であり、この過程はいつも私たちの知識の境界に聞かれてから止まることを簡単に理解することができます.
面接問題は起点にすぎず、面接の過程で深く掘り下げた問題こそ、私たちが給与帳を話す核心に触れることができる.もちろんこれは遠くなって、本文の内容に戻り続けます.
このとき、面接者がその場で解題コードを書いても、古典的な問題は避けられない.
面接官:「もっといい案はありますか?」
では、この問題は、もっと優れた案がありますか.答えはもちろんあります.
2.2より優れたシナリオ
チェーンテーブルを先に反転させてから処理し、反転させます.これは優雅ではありません.実際にはK個のグループでチェーンテーブルを反転させるだけでいいです.
leetcodeの25番の問題を思い出して、それはこの問題との違いで、主に1組未満のチェーンテーブルのノードに対する処理から来ています.leetcode-25は最初からノードから処理されるので、多く出たノードは末尾にあり、バイトのジャンプという問題は正反対で、残りのノードは頭にあります.
しかし、Kが1つずつグループ化される場合、ここのKはちょうど完全なグループ化が可能で、1つは多くなく、1つはNグループに多く分けられるという特殊な状況もあります.
チェーンテーブルのノード数がK*Nの場合、よく知られているleetcode-25に戻ります.
元のノードを先に処理して、Kの開始ノードoffsetをちょうど除去できることを見つけて、この開始ノードoffsetのサブチェーンテーブルをK個ずつ反転チェーンテーブルを行って、最後にそれを元のチェーンテーブルにつなぎ戻して、この問題を完成しました.
このプロセスでは、K個のパケット条件を満たすoffsetノードとoffsetの前駆ノードprevノードを追加的に定義する必要があります.prevノードは、主に反転後の2つのチェーンテーブルを接合し、チェーンテーブルの破断の問題が発生しないようにするために使用されます.
これらの関係は次のとおりです.
これには、チェーンテーブルの長さを求めるなど、簡単なチェーンテーブル演算も含まれています.ここでは、コアコードを展開しないで、論理は注釈の中にあります.まず、reverseKGroupPlus()の方法を定義します.

public ListNode reverseKGroupPlus(ListNode head, int k) {
    if (head == null || k <= 1) return head;
    //         
    int length = linkedLength(head);
      if (length < k) 
        return head;
  
    //    offset
    int offsetIndex = length % k;

      //           K    N  ，     
    if (offsetIndex == 0) {
        return reverseKGroup(head, k);
    }

    //       prev   offset
    ListNode prev = head, offset = head;
    while (offsetIndex > 0) {
        prev = offset;
        offset = offset.next;
        offsetIndex--;
    }
    //   offset              ，       
    prev.next = reverseKGroup(offset, k);
    return head;
}

チェーンテーブルの長さがKでちょうどNグループに分けられる場合,我々は直接処理し,否定者は後続の複雑な論理を必要とすることに注意する.
コードの注釈は十分にはっきりしていて、頭の中でコードの実行の流れを1回通って理解することができるべきで、みんなの理解を助けるために、私はまた概略図を描きました.
ヘッドノードのチェーンテーブル長が10,Kが4であると仮定するとoffset Indexは2である.
prevとoffsetノードが見つかったら、offsetノードをヘッダノードとするサブチェーンテーブルをK個ずつチェーンテーブルを反転させる操作を行うことができます.
このときheadノードが開始するチェーンテーブルは,我々が計算した結果である.
2.3追加のコードを追加する
この問題は、他にも多くの小さなアルゴリズムに関連しており、自身leetcode-25が「困難」に格付けされ、バイトがこの問題にジャンプした上で、難易度が増加した.
問題の完全性を保証するために、ここでは関連コードを追加します.
1.チェーンテーブルの長さを計算する

private int linkedLength(ListNode head) {
    int count = 0;
    while (head != null) {
        count++;
        head = head.next;
    }
    return count;
}

何も言うことはありません.whileサイクルで終わります.
2.チェーンテーブルをK個ずつ反転
この問題は前の文章で詳しく説明したので、ここに直接コードを貼りました.

public ListNode reverseKGroup(ListNode head, int k) {
    //        
    ListNode dummy = new ListNode(0);
    dummy.next = head;

    //    prev   end   
    ListNode prev = dummy;
    ListNode end = dummy;

    while(end.next != null) {
      //   k       ，     
      for (int i = 0; i < k && end != null; i++)
        end = end.next;
      //    K      
      if (end == null)
        break;
      //      
      ListNode start = prev.next;
      ListNode next = end.next;
      end.next = null;
      //      
      prev.next = reverseList(start);
      //          
      start.next = next;
      prev = start;
      end = prev;
    }
    return dummy.next;
}

//          
private ListNode reverseList(ListNode head) {
    if (head == null || head.next == null)
      return head;
    ListNode p = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return p;
}

leetcode-25という問題については、まだよく知られていない前の文章「K個一組反転チェーンテーブル」を見ることができます.
三.小結時刻
以上が私がこの問題を解く構想で、最も効率的ではないかもしれませんが、比較的はっきりしています.
面接の過程で、チェーンテーブルに関する問題は高周波問題と言える.企業は出題の際、難易度を上げるために変種をすることもあるが、面接者としてはどうしても練習したり考えたりすることは避けられない.
もっといい案はありますか.面接で何か変なアルゴリズムの問題に遭遇しましたか.伝言エリアでの討論を歓迎します.
本文はあなたに役に立ちますか?メッセージ、転送、コレクションは最大のサポートです.ありがとうございます.
公式アカウントのバックグラウンドで成長を回復する『
成长』は、私が准备した学习资料を手に入れ、『
一緒に勉強して進歩する.