国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

[Leetcode] Combinations 組合數(shù)

omgdog / 2173人閱讀

摘要：回溯法復(fù)雜度時(shí)間空間思路通過(guò)深度優(yōu)先搜索，回溯出所有可能性即可。而遞歸的條件是當(dāng)或者時(shí)，返回一個(gè)空列表。注意當(dāng)返回的是空列表時(shí)，要加一個(gè)空列表進(jìn)去，否則循環(huán)會(huì)被跳過(guò)代碼加入一個(gè)空列表，防止跳過(guò)循環(huán)

Combinations 
Given two integers n and k, return all possible ombinations 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],
]
回溯法 復(fù)雜度

時(shí)間 O(N) 空間 O(K)

思路

通過(guò)深度優(yōu)先搜索，回溯出所有可能性即可。

代碼 
public class Solution {
    
    List> res = new ArrayList>();
    
    public List> combine(int n, int k) {
        dfs(1, k, n, new ArrayList());
        return res;
    }
    
    private void dfs(int start, int k, int n, List tmp){
        // 當(dāng)已經(jīng)選擇足夠數(shù)字時(shí)，將tmp加入結(jié)果
        if(k == 0){
            res.add(new ArrayList(tmp));
        }
        // 每一種選擇數(shù)字的可能
        for(int i = start; i <= n; i++){
            tmp.add(i);
            dfs(i + 1, k - 1, n, tmp);
            tmp.remove(tmp.size() - 1);
        }
    }
}
公式法 復(fù)雜度

時(shí)間 O(N) 空間 O(N)

思路

在數(shù)學(xué)中，組合數(shù)有這么一個(gè)性質(zhì)
$$ C_{n}^{k}=C_{n-1}^{k-1}cup n+C_{n-1}^{k}$$
所以，我們可以分別求出C(n-1,k-1)和C(n-1,k)，并將前者都加上n，最后將兩個(gè)結(jié)果和到一起，就是C(n,k)。而遞歸的Base條件是當(dāng)n=0,k=0或者n 注意

當(dāng)C(n-1,k-1)返回的是空列表時(shí)，要加一個(gè)空列表進(jìn)去，否則for循環(huán)會(huì)被跳過(guò)

代碼 
public class Solution {
    public List> combine(int n, int k) {
        // Recursion: C(n, k) = C(n-1, k-1) U n + C(n-1, k)
        // Base: C(0, k) C(n, 0) n < k ---> empty
        List> res = new LinkedList>();
        if(n < k || n == 0 || k == 0){
            return res;
        }
        // C(n-1, k-1) U n
        List> temp = combine(n-1, k-1);
        List> part1 = new LinkedList>();
        // 加入一個(gè)空列表，防止跳過(guò)for循環(huán)
        if(temp.isEmpty()){
            List list = new LinkedList();
            temp.add(list);
        }
        for(List list : temp){
            list.add(n);
            part1.add(list);
        }
        // C(n-1, k)
        List> part2 = combine(n-1, k);
        res.addAll(part1);
        res.addAll(part2);
        return res;
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.specialneedsforspecialkids.com/yun/64529.html

相關(guān)文章

  • [Leetcode] Combination Sum 組合數(shù)之和

    摘要：深度優(yōu)先搜索復(fù)雜度時(shí)間空間遞歸?？臻g思路因?yàn)槲覀兛梢匀我饨M合任意多個(gè)數(shù)，看其和是否是目標(biāo)數(shù)，而且還要返回所有可能的組合，所以我們必須遍歷所有可能性才能求解。這題是非常基本且典型的深度優(yōu)先搜索并返回路徑的題。本質(zhì)上是有限深度優(yōu)先搜索。 Combination Sum I Given a set of candidate numbers (C) and a target number (...

    GitCafe 評(píng)論0 收藏0

  • [LintCode/LeetCode] Combination Sum I & II

    摘要：和唯一的不同是組合中不能存在重復(fù)的元素，因此，在遞歸時(shí)將初始位即可。 Combination Sum I Problem Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T...

    ThreeWords 評(píng)論0 收藏0

  • leetcode77. Combinations

    摘要：再在前一種情況下繼續(xù)下一輪的遍歷，并將結(jié)果添加到隊(duì)列末尾。思路二遞歸其實(shí)，通過(guò)遞歸的方法我們也可以在前一輪的基礎(chǔ)上進(jìn)行下一輪的計(jì)算。 題目要求 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...

    garfileo 評(píng)論0 收藏0

  • leetcode-93-Restore IP Addresses

    摘要：題目描述題目理解將一段字符廣度搜索截取，分別有種組合形式，添加限制條件，過(guò)濾掉不適合的組合元素。長(zhǎng)度，大小，首字母應(yīng)用如果進(jìn)行字符串的子元素組合窮舉，可以應(yīng)用。所有的循環(huán)，利用到前一個(gè)狀態(tài)，都可以理解為動(dòng)態(tài)規(guī)劃的一種分支 題目描述：Given a string containing only digits, restore it by returning all possible va...

    wmui 評(píng)論0 收藏0

  • leetcode 17 Letter Combinations of a Phone Number

    摘要：而按鍵和字母的對(duì)應(yīng)關(guān)系如上圖。這將成為下一次操作的前序字符串。對(duì)于每一個(gè)不同的前序字符串，我們都要在其后面分別加上當(dāng)前鍵所表示的不同字符，再將獲得的結(jié)果字符串加入里面。 題目詳情 Given a digit string, return all possible letter combinations that the number could represent. mapping o...

    sean 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<