欧美一区二区三区老妇人-欧美做爰猛烈大尺度电-99久久夜色精品国产亚洲a-亚洲福利视频一区二区

leetcode回溯題目golang語(yǔ)言-創(chuàng)新互聯(lián)

回溯算法實(shí)際上一個(gè)類似枚舉的搜索嘗試過(guò)程，主要是在搜索嘗試過(guò)程中尋找問(wèn)題的解，當(dāng)發(fā)現(xiàn)已不滿足求解條件時(shí)，就 “回溯” 返回，嘗試別的路徑。回溯法是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達(dá)到目標(biāo)。但當(dāng)探索到某一步時(shí)，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)，就退回一步重新選擇，這種走不通就退回再走的技術(shù)為回溯法，而滿足回溯條件的某個(gè)狀態(tài)的點(diǎn)稱為 “回溯點(diǎn)”。許多復(fù)雜的，規(guī)模較大的問(wèn)題都可以使用回溯法，有“通用解題方法”的美稱。
回溯算法的基本思想是：從一條路往前走，能進(jìn)則進(jìn)，不能進(jìn)則退回來(lái)，換一條路再試。

成都創(chuàng)新互聯(lián)公司服務(wù)項(xiàng)目包括婁煩網(wǎng)站建設(shè)、婁煩網(wǎng)站制作、婁煩網(wǎng)頁(yè)制作以及婁煩網(wǎng)絡(luò)營(yíng)銷策劃等。多年來(lái)，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢(shì)、行業(yè)經(jīng)驗(yàn)、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機(jī)構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，婁煩網(wǎng)站推廣取得了明顯的社會(huì)效益與經(jīng)濟(jì)效益。目前，我們服務(wù)的客戶以成都為中心已經(jīng)輻射到婁煩省份的部分城市，未來(lái)相信會(huì)繼續(xù)擴(kuò)大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任！
鏈接：https://leetcode-cn.com/tag/backtracking/
 來(lái)源：力扣（LeetCode）
 著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

本文主要總結(jié)一下回溯算法的一些題目。語(yǔ)言主要是Golang。

78.子集，不含重復(fù)元素

第一種是比較常規(guī)的回溯解法。

func subsets(nums []int) [][]int {
    result := make([][]int, 0)
    subsetsBT(&result, nums, []int{}, 0)
    return result
}
func subsetsBT(result *[][]int, nums []int, temp []int, start int) {
    //此處深拷貝temp，避免回溯的時(shí)候temp被修改后會(huì)影響之前保存的結(jié)果
    c := make([]int, len(temp))
    copy(c, temp)
    *result = append(*result, c)

    for i := start; i < len(nums); i++ {
        temp = append(temp, nums[i])
        subsetsBT(result, nums, temp, i+1)//不包含重復(fù)值
        temp = temp[:len(temp)-1]
    }
}

第二章方法就比較牛逼了，具體解釋參考此處。用二進(jìn)制位的0，1表示是否選中當(dāng)前位置的數(shù)。

func subsets(nums []int) [][]int {
    result := make([][]int, 0)
    n := 1 << uint(len(nums))
    for i := 0; i < n; i++ {
        temp := make([]int, 0)
        for j := 0; j < len(nums); j++ {
            if uint(i)>>uint(j)&1 == 1 {
                temp = append(temp, nums[j])
            }
        }
        result = append(result, temp)
    }

    return result
}

77.組合

常規(guī)解法。當(dāng)temp里的元素個(gè)數(shù)等于給定的K時(shí)，找到一個(gè)滿足條件的解。

func combine(n int, k int) [][]int {
    var result = make([][]int, 0)
    combineBT(n, k, 1, []int{}, &result)
    return result
}
func combineBT(n, k, start int, temp []int, result *[][]int) {
    if len(temp) == k {
        c := make([]int, len(temp))
        copy(c, temp)
        *result = append(*result, c)
        return
    }

    for i := start; i <= n; i++ {
        temp = append(temp, i)
        combineBT(n, k, i+1, temp, result)
        temp = temp[0 : len(temp)-1]
    }
}

39. 組合總和，不包含重復(fù)元素，可多次使用

常規(guī)解法，要先排序一下。每次先嘗試減去當(dāng)前元素，要是減去后還大于0，則表示可以繼續(xù)往下走。然后因?yàn)榭梢灾貜?fù)使用元素，所以回溯的時(shí)候從i開(kāi)始繼續(xù)下一次。直到目標(biāo)值減到0后，找到一個(gè)滿足條件的解空間。

func combinationSum(candidates []int, target int) [][]int {
    var result = make([][]int, 0)
    sort.Ints(candidates)
    combinationSumBT(&result, candidates, []int{}, target, 0)
    return result
}
func combinationSumBT(result *[][]int, candidates []int, temp []int, target int, start int) {
    if target == 0 {
        c := make([]int, len(temp))
        copy(c, temp)
        *result = append(*result, c)
        return
    }
    for i := start; i < len(candidates); i++ {
        if target-candidates[i] >= 0 {
            target -= candidates[i]
            temp = append(temp, candidates[i])
            combinationSumBT(result, candidates, temp, target, i)//可以包含已經(jīng)用過(guò)的值，所以從i開(kāi)始，
            temp = temp[0 : len(temp)-1]//回溯
            target += candidates[i]//得把當(dāng)前用過(guò)的值再加回去。
        } else {
            return
        }
    }
}

40. 組合總和2，只能使用一次且解空間不能包含重復(fù)

和第一個(gè)很像，但是每個(gè)數(shù)字只能用一次且解空間不能包含重復(fù)解。

func combinationSum2(candidates []int, target int) [][]int {
    sort.Ints(candidates)
    var result = make([][]int, 0)
    combinationSumBT2(&result, candidates, []int{}, target, 0)
    return result
}
func combinationSumBT2(result *[][]int, candidates []int, temp []int, target int, start int) {
    if target == 0 {
        c := make([]int, len(temp))
        copy(c, temp)
        *result = append(*result, c)
        return
    }
    for i := start; i < len(candidates); i++ {
        if target-candidates[i] >= 0 {
        //比如[10,1,2,7,6,1,5], target = 8
        //排好序后[1,1,2,5,6,7,10]
        //在第一個(gè)for循環(huán)里，先遍歷到第一個(gè)1，經(jīng)過(guò)一系列操作，得到解集[1,7]
        //然后還是第一個(gè)for循環(huán)里，又遍歷到后面的1，現(xiàn)在是不需要[第二個(gè)1,7]這個(gè)解集了，所以跳過(guò)。
            if i != start && candidates[i] == candidates[i-1] { //因?yàn)榻饪臻g不能有重復(fù)
                continue
            }
            target -= candidates[i]
            temp = append(temp, candidates[i])
            combinationSumBT2(result, candidates, temp, target, i+1)//因?yàn)椴荒苤貜?fù)使用，所以從i+1開(kāi)始
            temp = temp[0 : len(temp)-1]
            target += candidates[i]
        } else {
            return
        }
    }
}

216. 組合總和3,只有1-9，且每個(gè)組合中不能有重復(fù)且最后的解空間不能包含重復(fù)

func combinationSum3(k int, n int) [][]int {
    var result = make([][]int, 0)
    combinationSumBT3(&result, []int{}, k, n, 1)
    return result
}
func combinationSumBT3(result *[][]int, temp []int, k int, target int, start int) {
    //和第一個(gè)很像，在target的基礎(chǔ)上增加了一個(gè)k的限制。
    if target == 0 && k == 0 {
        c := make([]int, len(temp))
        copy(c, temp)
        *result = append(*result, c)
        return
    }
    for i := start; i <= 9; i++ {
        if target-i >= 0 {
            target -= i
            k--
            temp = append(temp, i)
            combinationSumBT3(result, temp, k, target, i+1)//每個(gè)組合不能有重復(fù)
            temp = temp[0 : len(temp)-1]
            target += i
            k++
        } else {
            return
        }
    }
}

17.電話號(hào)碼的字母組合

方法一是常規(guī)的回溯。

var wordsMap = map[int]string{2: "abc", 3: "def", 4: "ghi", 5: "jkl", 6: "mno", 7: "pqrs", 8: "tuv", 9: "wxyz"}
func letterCombinations(digits string) []string {
    if len(digits) == 0 {
        return []string{}
    }
    answer := make([]string, 0)
    letterCombinationsBT(&answer, digits, "", 0)
    return answer
}
func letterCombinationsBT(answer *[]string, digits string, temp string, index int) {
    if len(temp) == len(digits) {
        *answer = append(*answer, temp)
        return
    }

    char := digits[index] - '0'
    letter := wordsMap[int(char)]
    //fmt.Println(int(char), letter)
    for i := 0; i < len(letter); i++ {
        letterCombinationsBT(answer, digits, temp+string(letter[i]), index+1)
    }

    return
}

方法二就比較牛逼了，把按的數(shù)字對(duì)應(yīng)的字母依次放到隊(duì)列中，然后和下一個(gè)數(shù)字的字母挨個(gè)拼，拼完再扔到隊(duì)尾。
比如我按了 "23" 對(duì)應(yīng) abc 和 def
我先在隊(duì)列[從左到右表示隊(duì)首到隊(duì)尾]初始化一個(gè)空字符串。
" "
然后遍歷第一個(gè)數(shù)字 2 ，對(duì)應(yīng)的字母是 abc，然后用隊(duì)列頭部的空字符串 "" 依次和abc做拼接，得到 "a", "b", "c",
然后依次從隊(duì)尾扔到隊(duì)列，現(xiàn)在隊(duì)列是
a b c
遍歷完2對(duì)應(yīng)的字母再繼續(xù)遍歷3的。3對(duì)應(yīng)def。取出隊(duì)首的"a",依次和后面的def拼接，得到 "ad", "ae", "af",然后扔到隊(duì)尾，現(xiàn)在隊(duì)列里是
b c ad ae af
繼續(xù)重復(fù)這個(gè)操作即可完成最后的遍歷，很方便。

c ad ae af bd be bf

ad ae af bd be bf cd ce cf

func letterCombinations(digits string) []string {
    if len(digits) == 0 {
        return []string{}
    }
    var words = [8]string{"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
    queue := make([]string, 0)
    queue = append(queue, "")
    for i := 0; i < len(digits); i++ {
        n := digits[i] - '2'
        size := len(queue)
        for j := 0; j < size; j++ {
            st := queue[0]
            queue = queue[1:]
            for _, ch := range words[n] {
                temp := st + string(ch)
                queue = append(queue, temp)
            }
        }
    }
    return queue
}

創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國(guó)云服務(wù)器，動(dòng)態(tài)BGP最優(yōu)骨干路由自動(dòng)選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證， 機(jī)房獨(dú)有T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確進(jìn)行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動(dòng)現(xiàn)已開(kāi)啟，新人活動(dòng)云服務(wù)器買多久送多久。

本文題目：leetcode回溯題目golang語(yǔ)言-創(chuàng)新互聯(lián)
當(dāng)前鏈接：http://www.chinadenli.net/article34/dciise.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站營(yíng)銷、域名注冊(cè)、網(wǎng)站排名、網(wǎng)站策劃、動(dòng)態(tài)網(wǎng)站、網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)

綿陽(yáng)服務(wù)器托管