摘要:用變量和取模來判斷我們該取列表中的第幾個迭代器。同樣,由于每用完一個迭代器后都要移出一個,變量也要相應(yīng)的更新為該迭代器下標(biāo)的上一個下標(biāo)。如果迭代器列表為空,說明沒有下一個了。
Zigzag Iterator
雙迭代器 復(fù)雜度Given two 1d vectors, implement an iterator to return their elements alternately.
For example, given two 1d vectors:
v1 = [1, 2] v2 = [3, 4, 5, 6]By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1, 3, 2, 4, 5, 6].
Follow up: What if you are given k 1d vectors? How well can your code be extended to such cases?
Clarification for the follow up question - Update (2015-09-18): The "Zigzag" order is not clearly defined and is ambiguous for k > 2 cases. If "Zigzag" does not look right to you, replace "Zigzag" with "Cyclic". For example, given the following input:
[1,2,3] [4,5,6,7] [8,9]It should return [1,4,8,2,5,9,3,6,7].
時間 O(N) 空間 O(1)
思路該題實(shí)際上就是輪流取兩個列表的下一個元素。我們存下兩個列表的迭代器,然后用一個遞增的turns變量和取模的方法來判斷該取哪一個列表的元素。
代碼public class ZigzagIterator { Iterator后續(xù) Follow Upit1; Iterator it2; int turns; public ZigzagIterator(List v1, List v2) { this.it1 = v1.iterator(); this.it2 = v2.iterator(); turns = 0; } public int next() { // 如果沒有下一個則返回0 if(!hasNext()){ return 0; } turns++; // 如果是第奇數(shù)個,且第一個列表也有下一個元素時,返回第一個列表的下一個 // 如果第二個列表已經(jīng)沒有,返回第一個列表的下一個 if((turns % 2 == 1 && it1.hasNext()) || (!it2.hasNext())){ return it1.next(); // 如果是第偶數(shù)個,且第二個列表也有下一個元素時,返回第二個列表的下一個 // 如果第一個列表已經(jīng)沒有,返回第二個列表的下一個 } else if((turns % 2 == 0 && it2.hasNext()) || (!it1.hasNext())){ return it2.next(); } return 0; } public boolean hasNext() { return it1.hasNext() || it2.hasNext(); } }
Q:如果輸入是k個列表呢?
A:使用一個迭代器的列表來管理這些迭代器。用turns變量和取模來判斷我們該取列表中的第幾個迭代器。不同點(diǎn)在于,一個迭代器用完后,我們要將其從列表中移出,這樣我們下次就不用再找這個空的迭代器了。同樣,由于每用完一個迭代器后都要移出一個,turns變量也要相應(yīng)的更新為該迭代器下標(biāo)的上一個下標(biāo)。如果迭代器列表為空,說明沒有下一個了。
public class ZigzagIterator implements Iterator{ List > itlist; int turns; public ZigzagIterator(List > list) { this.itlist = new LinkedList >(); // 將非空迭代器加入列表 for(Iterator it : list){ if(it.hasNext()){ itlist.add(it); } } turns = 0; } public Integer next() { if(!hasNext()){ return 0; } Integer res = 0; // 算出本次使用的迭代器的下標(biāo) int pos = turns % itlist.size(); Iterator curr = itlist.get(pos); res = curr.next(); // 如果這個迭代器用完,就將其從列表中移出 if(!curr.hasNext()){ itlist.remove(turns % itlist.size()); // turns變量更新為上一個下標(biāo) turns = pos - 1; } turns++; return res; } public boolean hasNext() { return itlist.size() > 0; } }
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/64569.html
摘要:方法直接查找數(shù)組的位的迭代器,調(diào)用方法得到的整數(shù)即為要返回的元素。再寫迭代器的方法返回指針元素的并讓指針通過遞歸方法指向下一個元素。 Zigzag Iterator Problem Given two 1d vectors, implement an iterator to return their elements alternately. Example Given two 1d ...
摘要:有效三角形的個數(shù)雙指針最暴力的方法應(yīng)該是三重循環(huán)枚舉三個數(shù)字。總結(jié)本題和三數(shù)之和很像,都是三個數(shù)加和為某一個值。所以我們可以使用歸并排序來解決這個問題。注意因?yàn)闅w并排序需要遞歸,所以空間復(fù)雜度為 ...
摘要:題目鏈接這道題是說有兩個,來回返回兩個里面的值,要求用來做。所以可以用兩個來分別存這兩個的值,再用一個指針來表示現(xiàn)在應(yīng)該取哪個里面的值。這里用之后,如果一個循環(huán)結(jié)束,可以直接把它移除,然后就可以直接判斷是否是空。 Zigzag Iterator 題目鏈接:https://leetcode.com/problems... 這道題是說有兩個list,來回返回兩個list里面的值,要求用it...
摘要:看到這道題總覺得眼熟,做完之后恍然大悟,這不就是小學(xué)數(shù)學(xué)做的找規(guī)律一題目字形變換將一個給定字符串根據(jù)給定的行數(shù),以從上往下從左到右進(jìn)行字形排列。一當(dāng)然是因?yàn)樽罱鼘?shí)在太忙了捂臉,幾乎周周誰遭得住。 看到這道題總覺得眼熟,做完之后恍然大悟,這不就是小學(xué)數(shù)學(xué)做的找規(guī)律 一、題目 Z 字形變換: 將一個給定字符串根據(jù)給定的行數(shù),以從上往下、從左到右進(jìn)行 Z 字形排列。比如輸入字符串為 LEET...
摘要:返回的是表示是否走到了結(jié)尾。起到的就是緩存作用,因?yàn)檎{(diào)用之后馬上就走到下一個了。如果調(diào)用,返回用得到和最初的輸入相同的做相同的步驟存入不斷拆開得到結(jié)果。思想就是來自括號,后面也會跟進(jìn)的專題 Iterator其實(shí)就是一個單鏈表,無法回頭看。java里很多數(shù)據(jù)結(jié)構(gòu)都有這個接口,使用時需要initalize,得到一個iterator. 調(diào)用next()返回的是一個object, 指向的是下一...
閱讀 1039·2021-11-18 13:23
閱讀 746·2021-11-08 13:16
閱讀 856·2021-10-11 10:58
閱讀 3511·2021-09-22 15:26
閱讀 1732·2021-09-08 10:42
閱讀 1807·2021-09-04 16:45
閱讀 1734·2019-08-30 15:54
閱讀 2565·2019-08-30 13:45