建站
咨詢
售后
建站咨詢
新聞中心
今天去網(wǎng)上看了一下09年的Java考研試題，看見(jiàn)該題目（圖片）：
成都創(chuàng)新互聯(lián)自2013年起，是專業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司，擁有項(xiàng)目成都做網(wǎng)站、網(wǎng)站建設(shè)、外貿(mào)營(yíng)銷網(wǎng)站建設(shè)網(wǎng)站策劃，項(xiàng)目實(shí)施與項(xiàng)目整合能力。我們以讓每一個(gè)夢(mèng)想脫穎而出為使命，1280元來(lái)賓做網(wǎng)站,已為上家服務(wù),為來(lái)賓各地企業(yè)和個(gè)人服務(wù),聯(lián)系電話:18980820575
先來(lái)定義結(jié)點(diǎn)（為了簡(jiǎn)便，省略set/get）：
- public class Node
- {
- public int data;
- public Node link;
- }
對(duì)于這個(gè)Java考研試題，我能想到的兩種解法，一個(gè)基于遞歸：
遞歸版的思路就是，基于當(dāng)前結(jié)點(diǎn)，如果后一個(gè)是倒數(shù)第K-1，那么當(dāng)前結(jié)點(diǎn)是所求，若不然，返回當(dāng)前是倒數(shù)第幾個(gè)。
- 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;
- }
對(duì)每個(gè)結(jié)點(diǎn)，該算法都只訪問(wèn)一次，因此復(fù)雜度O（N）。
第二解法，相對(duì)遞歸來(lái)說(shuō)，這種方法可以算是消除遞歸版，而且從某種意義上來(lái)說(shuō)比遞歸更高效，跟省空間，遞歸版實(shí)際上是把回溯的數(shù)據(jù)存在棧上，而版方法是自己存儲(chǔ)，且利用數(shù)組實(shí)現(xiàn)一個(gè)循環(huán)隊(duì)列，只存儲(chǔ)K個(gè)元素。
- 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() return 0;
- System.out.println("Got:"+queue.getButtom());
- return 1;
- }
本算法，都每個(gè)結(jié)點(diǎn)也只放一次，另外進(jìn)行一次入隊(duì)操作，該操作復(fù)雜度O(1),從而，整個(gè)算法復(fù)雜度仍是O(N).
對(duì)于此Java考研試題還有另外一種算法，該算法的空間復(fù)雜度為O（1），時(shí)間復(fù)雜度為O（n）。這在空間復(fù)雜度和時(shí)間復(fù)雜度上應(yīng)該是比較優(yōu)化了。
本算法的基本思想如下：既然是查找倒數(shù)第K個(gè)結(jié)點(diǎn)（注意，不是正數(shù)，否則就沒(méi)什么可討論的了），而且鏈表是單向的，還不能改變表結(jié)構(gòu)，這就意味著只能從前往后掃描結(jié)點(diǎn)。我們首先要知道這個(gè)鏈表有多少個(gè)結(jié)點(diǎn)（如果總結(jié)點(diǎn)數(shù)都不知道，何談倒數(shù)？），這個(gè)非常簡(jiǎn)單，只要從頭掃描一下鏈表，再計(jì)一下數(shù)即可。
在同一時(shí)間從事多項(xiàng)工作會(huì)大大提升效率，當(dāng)然，掃描鏈表也不例外，在掃描鏈表的同時(shí)，還需要做一些其他的工作。既然只能從前向后掃描鏈表，而且要求倒數(shù)第K個(gè)結(jié)點(diǎn)，那就讓我們把這個(gè)鏈表按長(zhǎng)度為K分成若干塊，而最后掃描的結(jié)果要么結(jié)點(diǎn)數(shù)是K的整數(shù)倍（模為0），要么余數(shù)（模）不為0（多出幾個(gè)結(jié)點(diǎn)，多出的結(jié)點(diǎn)數(shù)小于K）。
先看看第二種情況。
假設(shè)有12個(gè)結(jié)點(diǎn)的鏈表，每一個(gè)結(jié)點(diǎn)的值從前往后分別是1至12，如下所示：
1 2 3 4 5 6 7 8 9 10 11 12
假設(shè)我們要求倒數(shù)第5個(gè)結(jié)點(diǎn)，我們直接就可以看出結(jié)果是8.那么用程序如何處理呢？
先按長(zhǎng)度為5將上面的結(jié)點(diǎn)分成三個(gè)區(qū)域，如下：
1 2 3 4 5 6 7 8 9 10 11 12
注意，不是物理分，而是使用變量來(lái)保存區(qū)域的邊界（也就是區(qū)域最后一個(gè)結(jié)點(diǎn)的對(duì)象）。
從上面的分隔可以看出，最后剩下兩個(gè)結(jié)點(diǎn)，既然是求倒數(shù)第5個(gè)，而最后剩下了兩個(gè)，那么還缺5-2=3個(gè)，因此，只需要從倒數(shù)第二個(gè)塊（6 7 8 9 10）略過(guò)前兩個(gè)，第三個(gè)結(jié)點(diǎn)（8）就是我們要求的結(jié)果，而5就是題中的k，2就是結(jié)點(diǎn)數(shù)與k的模，因此，可以推出一個(gè)公式，倒數(shù)第k個(gè)結(jié)點(diǎn)就是按長(zhǎng)度為k按分成的若干塊中的第二塊的第（結(jié)點(diǎn)數(shù) % k+ 1）個(gè)結(jié)點(diǎn)。
下面來(lái)看看（結(jié)點(diǎn)數(shù) % k）為0的情況。假設(shè)上面的例子中的k為4，正確的輸出結(jié)果應(yīng)為9，分塊如下：
1 2 3 4 5 6 7 8 9 10 11 12
從上面的三個(gè)塊可以看出，結(jié)果正好是最后一個(gè)塊的第一個(gè)結(jié)點(diǎn)，這時(shí)mod為0（mod=結(jié)點(diǎn)數(shù) % k），因此，在這種情況也可以使用上面的公式，只是變成了最后一個(gè)塊。
根據(jù)上面的基本思想可以設(shè)兩個(gè)指針，p1和p2，其中p1最終指向倒數(shù)第2個(gè)完整塊，p2最終指向倒數(shù)第1個(gè)完整塊，對(duì)于第一種情況，p1指向5，p2指向10，這時(shí)可以使p1向后移動(dòng)（k - mod）個(gè)結(jié)點(diǎn)即可（從5移動(dòng)3個(gè)正好是8）。而對(duì)于第二種情況，p1指向8，p2指向12，而mod=0，這時(shí)的結(jié)果仍然是mod+1，也就是p1向后移動(dòng)1個(gè)結(jié)點(diǎn)就是所求的結(jié)果。 為了滿足（k=結(jié)點(diǎn)數(shù)）的情況，需要將p1的初始值設(shè)為頭結(jié)點(diǎn)，這樣如果（k=結(jié)點(diǎn)數(shù)），就直接從頭結(jié)點(diǎn)向后移動(dòng)一個(gè)結(jié)點(diǎn)就是最后的結(jié)果，如上面的例子求倒數(shù)第12個(gè)結(jié)點(diǎn)，也就是求正數(shù)第1個(gè)結(jié)點(diǎn)。
下面是這個(gè)算法的具體實(shí)現(xiàn)（包括核心算法、生成鏈表及調(diào)用核心算法的代碼）：
- public class Test
- {
- static class Node
- {
- public int data;
- public Node nextNode;
- }
- //////////////////////////////////////////
- // 核心算法
- private static int findNode(Node headNode, int k)
- {
- Node p = headNode, p1 = headNode, p2 = null;
- int count = 0; // 表示結(jié)點(diǎn)數(shù)
- while (p.nextNode != null)
- {
- p = p.nextNode;
- count++;
- // 遇到k的整數(shù)位個(gè)結(jié)點(diǎn)，進(jìn)行分塊
- if (count % k == 0)
- {
- if (p2 != null)
- p1 = p2;
- p2 = p;
- }
- }
- // k超過(guò)鏈表結(jié)點(diǎn)數(shù)，未找到，返回0
- // 此處也可以用k > count來(lái)判斷
- if (p2 == null)
- {
- return 0;
- }
- else
- {
- int mod = count % k;
- int offset = mod + 1; // 任何情況下，最終結(jié)果都是p1指向的結(jié)點(diǎn)向后移動(dòng)(mod + 1)個(gè)結(jié)點(diǎn)
- for (int i = 0; i < offset; i++)
- p1 = p1.nextNode;
- System.out.println(p1.data);
- return 1;
- }
- }
- ////////////////////////////////////////
- public static void main(String[] args) throws Exception
- {
- //產(chǎn)生一個(gè)包含1個(gè)頭結(jié)點(diǎn)和120個(gè)結(jié)點(diǎn)的鏈表
- Node headNode = new Node();
- Node p = headNode;
- for (int i = 0; i < 120; i++)
- {
- p.nextNode = new Node();
- p.nextNode.data = i + 1;
- p = p.nextNode;
- }
- p.nextNode = null;
- // 開(kāi)始查找倒數(shù)第k個(gè)結(jié)點(diǎn)，如果找到，返回1，并輸出結(jié)點(diǎn)的data值
- System.out.println(findNode(headNode, 12));
- }
- }
上面程序的輸出結(jié)果如下：
109
1
分享名稱：Java考研試題之?dāng)?shù)據(jù)結(jié)構(gòu)解法
文章路徑：http://m.fisionsoft.com.cn/article/djgjhsg.html
