摘要:再在前一種情況下繼續下一輪的遍歷,并將結果添加到隊列末尾。思路二遞歸其實,通過遞歸的方法我們也可以在前一輪的基礎上進行下一輪的計算。
題目要求
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n. For example, If n = 4 and k = 2, a solution is: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
有整數從1到n,問從中任選兩個數有多少排列組合的結果(順序無關)
思路一:利用鏈表(超時問題)這題其實是動態編碼的一個題目,可以通過鏈表實現隊列存儲前一種情況。再在前一種情況下繼續下一輪的遍歷,并將結果添加到隊列末尾。代碼如下:
public List> combine(int n, int k) { List
> result = new LinkedList
>(); if(k==0){ return result; } for(int i = 0 ; i+k<=n ; i++){ result.add(Arrays.asList(i+1)); } while(result.get(0).size() != k){ List
currentList = result.remove(0); for(int i = currentList.get(currentList.size()-1) + 1 ; i<=n ; i++){ List temp = new ArrayList (currentList); temp.add(i); result.add(temp); } } return result; }
但是在這里存在超時問題,歸根結底在于每一次都要創建新的數組用來保存臨時結果,既占用內存又影響效率。
思路二:遞歸其實,通過遞歸的方法我們也可以在前一輪的基礎上進行下一輪的計算。遞歸代碼如下:
public List> combine2(int n, int k){ List
> result = new ArrayList
>(); if(k==0) return result; combine2(result, new ArrayList
(), 1, n, k); return result; } public void combine2(List > currentResult, List
list, int start, int n, int k){ if(k==0){ currentResult.add(new ArrayList (list)); return; } while(start+k-1<=n){ list.add(start++); combine2(currentResult, list, start, n, k-1); list.remove(list.size()-1); } }
想要了解更多開發技術,面試教程以及互聯網公司內推,歡迎關注我的微信公眾號!將會不定期的發放福利哦~
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/67304.html
找出string里的單詞。 186. Reverse Words in a String II, 434. Number of Segments in a String combination類型題 77. Combinations 39. Combination Sum 40. Combination Sum II 216. Combination Sum III 494. Target S...
摘要:題目描述題目理解將一段字符廣度搜索截取,分別有種組合形式,添加限制條件,過濾掉不適合的組合元素。長度,大小,首字母應用如果進行字符串的子元素組合窮舉,可以應用。所有的循環,利用到前一個狀態,都可以理解為動態規劃的一種分支 題目描述:Given a string containing only digits, restore it by returning all possible va...
摘要:題目要求類似的題目有可以參考這篇博客可以參考這篇博客思路一遞歸還是利用遞歸的方式,在前一種情況的基礎上遍歷下一輪的組合情況。 題目要求 Given a set of distinct integers, nums, return all possible subsets. Note: The solution set must not contain duplicate subset...
摘要:本題與類似,都是用回溯法。求中個數的不同組合,很明顯我們需要注意的就是每個數字只能出現一次,這點與不同。 CombinationsGiven two integers n and k, return all possible combinations of k numbers out of 1 ... n. For example, If n = 4 and k = 2, a solu...
摘要:最新更新請見深度優先搜索復雜度時間空間遞歸棧空間思路首先建一個表,來映射號碼和字母的關系。然后對號碼進行深度優先搜索,對于每一位,從表中找出數字對應的字母,這些字母就是本輪搜索的幾種可能。 Letter Combinations of a Phone Number 最新更新請見:https://yanjia.me/zh/2019/01/... Given a digit string...
閱讀 2785·2021-10-14 09:42
閱讀 3608·2021-10-11 10:59
閱讀 2941·2019-08-30 11:25
閱讀 3074·2019-08-29 16:25
閱讀 3224·2019-08-26 17:40
閱讀 1225·2019-08-26 13:30
閱讀 1143·2019-08-26 11:46
閱讀 1329·2019-08-23 15:22