E81086713E446D36F62B2AA2A3502B5EB155

          Java雜家

          雜七雜八。。。一家之言

          BlogJava 首頁 新隨筆 聯(lián)系 聚合 管理
            40 Posts :: 1 Stories :: 174 Comments :: 0 Trackbacks

          公告

          所有文章和代碼除非特別說明, 均為本blog作者原創(chuàng),轉(zhuǎn)載請注明出處和原作者. 謝謝!

          常用鏈接

          留言簿(15)

          隨筆分類

          隨筆檔案

          相冊

          搜索

          積分與排名

          最新評論

          閱讀排行榜

          評論排行榜





          今天去網(wǎng)上看了一下09年的考研試題,看見該題目(圖片):



          先來定義結(jié)點(為了簡便,省略set/get):
          public class Node
          {
           
          public int data;
           
          public Node link;
          }
          我能想到的兩種解法,一個基于遞歸:

          遞歸版的思路就是,基于當(dāng)前結(jié)點,如果后一個是倒數(shù)第K-1,那么當(dāng)前結(jié)點是所求,若不然,返回當(dāng)前是倒數(shù)第幾個。
          public int printRKWithRecur(Node head,int k)
              {
                  
          if(k==0||head==null||head.link==null)return 0;
                  
          if(_recurFind(head.link,k)>=k)return 1;
                  
          return 0;
              }
              
          private final int _recurFind(Node node, int k) {
                  
          if(node.link==null)
                  {
                      
          return 1;
                  }
                  
          int sRet=_recurFind(node.link,k);
                  
          if(sRet==k-1)
                  {
                      System.out.println(
          "Got:"+node.data);
                      
          return k;
                  }
                  
          return sRet+1;
              }


          對每個結(jié)點,該算法都只訪問一次,因此復(fù)雜度O(N).

          第二解法,相對遞歸來說,這種方法可以算是消除遞歸版,而且從某種意義上來說比遞歸更高效,跟省空間,遞歸版實際上是把回溯的數(shù)據(jù)存在棧上,而版方法是自己存儲,且利用數(shù)組實現(xiàn)一個循環(huán)隊列,只存儲K個元素。

          public static class CycleIntQueue
              {
                  
          int[] datas;
                  
          int top=0;
                  
          int num=0;
                  
          public CycleIntQueue(int n)
                  {
                      datas
          =new int[n];
                  }
                  
                  
          public void push(int i)
                  {
                      datas[(top
          ++)%datas.length]=i;
                      num
          ++;
                      
                  }
                  
          public int numPushed()
                  {
                      
          return num;
                  }
                  
                  
                  
          public int getButtom()
                  {
                      
          return datas[top%datas.length];
                  }
              }
              
          public int printRKWithCycleQueue(Node head,int k)
              {
                  
          if(k==0||head==null)return 0;
                  CycleIntQueue queue
          =new CycleIntQueue(k);
                  Node cur
          =head.link;
                  
          while(cur!=null)
                  {
                      queue.push(cur.data);
                      cur
          =cur.link;
                  }
                  
          if(queue.numPushed()<k)return 0;
                  
                  System.out.println(
          "Got:"+queue.getButtom());
                  
          return 1;
              }

          本算法,都每個結(jié)點也只放一次,另外進(jìn)行一次入隊操作,該操作復(fù)雜度O(1),從而,整個算法復(fù)雜度仍是O(N).


          posted on 2009-01-17 13:56 DoubleH 閱讀(2290) 評論(5)  編輯  收藏

          Feedback

          # re: [算法]09考研數(shù)據(jù)結(jié)構(gòu)試題解法 2009-01-17 15:41 crtylr
          個人覺得根本就用不著那么,麻煩的方法
          兩個指針,第一個指向頭,另一個指向從頭開始的指向第K個
          然后兩個指針分別指向Next,
          直到第二個指針指向了Null,那第一個指針的元素就是所求的倒數(shù)第K個  回復(fù)  更多評論
            

          # re: [算法]09考研數(shù)據(jù)結(jié)構(gòu)試題解法 2009-01-17 20:53 銀河使者
          這是一個算法,詳細(xì)解釋見我的blog:
          http://www.aygfsteel.com/nokiaguy/archive/2009/01/17/251722.html

              private static int findNode(Node headNode, int k)
              {
                  Node p = headNode, p1 = headNode, p2 = null;
                  int count = 0;  //  表示結(jié)點數(shù)
                  while (p.nextNode != null)
                  {
                      p = p.nextNode;
                      count++;
                      //  遇到k的整數(shù)位個結(jié)點,進(jìn)行分塊
                      if (count % k == 0)
                      {                
                          if (p2 != null)
                              p1 = p2;
                          p2 = p;
                      }
                  }
                  //  k超過鏈表結(jié)點數(shù),未找到,返回0
                  if (p2 == null)
                  {
                      return 0;
                  }
                  else
                  {
                      int mod = count % k;
                      int offset = mod + 1;  // 任何情況下,最終結(jié)果都是p1指向的結(jié)點向后移動(mod + 1)個結(jié)點
                      for (int i = 0; i < offset; i++)
                          p1 = p1.nextNode;
                      System.out.println(p1.data);
                      return 1;
                  }
              }

            回復(fù)  更多評論
            

          # re: [算法]09考研數(shù)據(jù)結(jié)構(gòu)試題解法 2009-01-17 22:48 DoubleH
          @crtylr
          @銀河使者
          恩,二位的想法其實是一樣的,銀河使者其實就是crtylr的復(fù)雜版。crtylr的意思應(yīng)該是對頭K個元素,只移動一個指針,然后一起移動直到第一個指針沒法繼續(xù)。  回復(fù)  更多評論
            

          # re: [算法]09考研數(shù)據(jù)結(jié)構(gòu)試題解法 2009-01-18 10:39 銀河使者
          是的,@crtylr的算法比較好,下面的具體的實現(xiàn)代碼,很簡單:
              private static int findNode(Node headNode, int k)
              {       
                  Node p1 = headNode, p2 = headNode;
                  for(int i = 0; i < k && p2.nextNode != null; i++)
                      p2 = p2.nextNode;
                  if(p2.nextNode == null) return 0;
                  while(p2.nextNode != null)
                  {
                      p1 = p1.nextNode;
                      p2 = p2.nextNode;
                  }
                  System.out.println(p1.nextNode.data);
                  return 1;
              }   回復(fù)  更多評論
            

          # re: [算法]09考研數(shù)據(jù)結(jié)構(gòu)試題解法[未登錄] 2009-01-20 19:14 hehe
          這道題目好熟悉阿.. 呵呵
            回復(fù)  更多評論
            


          只有注冊用戶登錄后才能發(fā)表評論。


          網(wǎng)站導(dǎo)航:
           
          主站蜘蛛池模板: 灵武市| 孟州市| 浦东新区| 阿拉善左旗| 丹江口市| 仁怀市| 房山区| 晋州市| 营口市| 灵武市| 盘锦市| 舒城县| 洪江市| 东莞市| 延长县| 咸阳市| 乌鲁木齐市| 克什克腾旗| 罗山县| 始兴县| 松潘县| 巴南区| 罗源县| 读书| 马边| 元阳县| 绍兴县| 延川县| 宝丰县| 苏尼特右旗| 定西市| 简阳市| 铁岭县| 鄱阳县| 杂多县| 七台河市| 陆川县| 靖州| 肥西县| 谷城县| 隆回县|