leetcode如何解決全排列問題

這篇文章將為大家詳細(xì)講解有關(guān)leetcode如何解決全排列問題，小編覺得挺實(shí)用的，因此分享給大家做個(gè)參考，希望大家閱讀完這篇文章后可以有所收獲。

專注于為中小企業(yè)提供網(wǎng)站設(shè)計(jì)、成都網(wǎng)站設(shè)計(jì)服務(wù),電腦端+手機(jī)端+微信端的三站合一,更高效的管理,為中小企業(yè)翁牛特免費(fèi)做網(wǎng)站提供優(yōu)質(zhì)的服務(wù)。我們立足成都，凝聚了一批互聯(lián)網(wǎng)行業(yè)人才，有力地推動(dòng)了成百上千家企業(yè)的穩(wěn)健成長，幫助中小企業(yè)通過網(wǎng)站建設(shè)實(shí)現(xiàn)規(guī)模擴(kuò)充和轉(zhuǎn)變。

回溯法（探索與回溯法）是一種選優(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)”。

全排列問題，子集問題，組合和問題都是經(jīng)典的回溯問題。

給定一個(gè)沒有重復(fù)數(shù)字的序列，返回其所有可能的全排列。

示例:

輸入: [1,2,3]
輸出:
[
 [1,2,3],
 [1,3,2],
 [2,1,3],
 [2,3,1],
 [3,1,2],
 [3,2,1]
]

解題思路：

1，可以遞歸解

2，對于長度為n的全排列，對于任意一個(gè)元素，與長度為n-l的全排列拼接而成

3，注意golang slice append的坑

代碼：

func permute(nums []int) [][]int {    var a [][]int    if len(nums)==0{        return a    }    if len(nums)==1{        return append(a,nums)    }    for i:=0;i<len(nums);i++{        aa:=permute(rest(nums,i))        for j:=0;j<len(aa);j++{            a=append(a,append([]int{nums[i]},aa[j]...))        }    }    return a}
func rest(nums []int,i int)[]int{    if i==0{        return nums[1:]    }    if i==len(nums)-1{        return nums[:len(nums)-1]    }    return append(nums[0:i:i],nums[i+1:]...)}

給定一個(gè)可包含重復(fù)數(shù)字的序列，返回所有不重復(fù)的全排列。

示例:

輸入: [1,1,2]
輸出:
[
 [1,1,2],
 [1,2,1],
 [2,1,1]
]

解題思路類似，只是求并集的時(shí)候，對比如果有就不并入

func permuteUnique(nums []int) [][]int {  var a [][]int  if len(nums) == 0 {    return a  }  if len(nums) == 1 {    return merge(a, nums)  }  for i := 0; i < len(nums); i++ {    aa := permuteUnique(rest(nums, i))    for j := 0; j < len(aa); j++ {      b := append([]int{nums[i]}, aa[j]...)      a = merge(a, b)    }  }  return a}
func merge(a [][]int, b []int) [][]int {  l := len(a)  if l == 0 {    a = append(a, b)  } else {    m := false    for k := 0; k < l; k++ {      if match(b, a[k]) {        m = true      }    }    if !m {      a = append(a, b)    }  }  return a}func match(a, b []int) bool {  if len(a) == 0 {    return false  }  for i := 0; i < len(a); i++ {    if a[i] != b[i] {      return false    }  }  return true}
func rest(nums []int, i int) []int {  if i == 0 {    return nums[1:]  }  if i == len(nums)-1 {    return nums[:len(nums)-1]  }  return append(nums[0:i:i], nums[i+1:]...)}

關(guān)于“l(fā)eetcode如何解決全排列問題”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，使各位可以學(xué)到更多知識(shí)，如果覺得文章不錯(cuò)，請把它分享出去讓更多的人看到。

網(wǎng)頁名稱：leetcode如何解決全排列問題
本文來源：http://muchs.cn/article10/igeido.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供企業(yè)網(wǎng)站制作、小程序開發(fā)、做網(wǎng)站、微信公眾號(hào)、ChatGPT、靜態(tài)網(wǎng)站

廣告

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