VB.net 2010 视频教程 VB.net 2010 视频教程 python基础视频教程
SQL Server 2008 视频教程 c#入门经典教程 Visual Basic从门到精通视频教程
当前位置:
首页 > go语言 >
  • 有1、2、3、4个数字,能组成多少个互不相同 且无重复数字的三位数?都是多少

前言

今天看到一个超级简单的算法题,但是我当时思路往递归,逐级筛选里面想了。结果百度查查答案,超级简单。
真是惭愧惭愧,不过我还是坚持用递归实现了,因为用递归的方案,可以适用于任何给定数据和指定位数。

传统解法

如下所示,因为题目是找1、2、3、4组合的三位数,因此可以用三重循环,遍历所有组合,筛选不重复组合即可。
但是该方案,如果给定数据改变,组合位数改变,那代码就得大改,所以不是一个通用的好方法。


	
	
 
func useNormal() []int {
 
var ret []int
 
for i := 1; i < 5; i++ {
 
for j := 1; j < 5; j++ {
 
for k := 1; k < 5; k++ {
 
if i != j && j != k && i != k {
 
ret = append(ret, i*100+j*10+k)
 
}
 
}
 
}
 
}
 
return ret
 
}

递归求解

下面方案是通过递归,依次为某一位分配数字,并将剩余组合依次赋值下一位。 该方法只需要改变data数据,以及numLen的指定位数就可以灵活地计算所有组合。


	
	
 
func useRecursion() []int {
 
var (
 
data = []int{1, 2, 3, 4}
 
numLen = 3
 
tmp = make([]int, numLen)
 
ret []int
 
)
 
findNum(data, tmp, numLen, &ret)
 
return ret
 
}
 
 
 
func findNum(data, tmp []int, dep int, ret *[]int) {
 
for i, v := range data {
 
if dep--; dep < 0 {
 
sum := 0
 
for i := len(tmp) - 1; i >= 0; i-- {
 
sum = sum*10 + tmp[i]
 
}
 
*ret = append(*ret, sum)
 
return
 
}
 
tmp[dep] = v // 当前选择赋值
 
 
 
next := make([]int, 0, len(data))
 
next = append(next, data[:i]...)
 
next = append(next, data[i+1:]...)
 
findNum(next, tmp, dep, ret) // 剔除当前元素,进入下一级筛选
 
 
 
dep++
 
}
 
}

完整代码

执行结果如下,两种方案结果完全一致:

[123 124 132 134 142 143 213 214 231 234 241 243 312 314 321 324 341 342 412 413 421 423 431 432] 24 [123 124 132 134 142 143 213 214 231 234 241 243 312 314 321 324 341 342 412 413 421 423 431 432] 24


	
	
 
package main
 
 
 
import "fmt"
 
 
 
func main() {
 
ret0 := useNormal()
 
fmt.Println(ret0, len(ret0))
 
ret1 := useRecursion()
 
fmt.Println(ret1, len(ret1))
 
}
 
 
 
func useNormal() []int {
 
var ret []int
 
for i := 1; i < 5; i++ {
 
for j := 1; j < 5; j++ {
 
for k := 1; k < 5; k++ {
 
if i != j && j != k && i != k {
 
ret = append(ret, i*100+j*10+k)
 
}
 
}
 
}
 
}
 
return ret
 
}
 
 
 
func useRecursion() []int {
 
var (
 
data = []int{1, 2, 3, 4}
 
numLen = 3
 
tmp = make([]int, numLen)
 
ret []int
 
)
 
findNum(data, tmp, numLen, &ret)
 
return ret
 
}
 
 
 
func findNum(data, tmp []int, dep int, ret *[]int) {
 
for i, v := range data {
 
if dep--; dep < 0 {
 
sum := 0
 
for i := len(tmp) - 1; i >= 0; i-- {
 
sum = sum*10 + tmp[i]
 
}
 
*ret = append(*ret, sum)
 
return
 
}
 
tmp[dep] = v // 当前选择赋值
 
 
 
next := make([]int, 0, len(data))
 
next = append(next, data[:i]...)
 
next = append(next, data[i+1:]...)
 
findNum(next, tmp, dep, ret) // 剔除当前元素,进入下一级筛选
 
 
 
dep++
 
}
 
}

总结

凡事有简单方案,也有复杂方案,简单往往不能通用,多想想通用方案,尝试解决一类问题而不是某一个问题。

作者:janbar
出处:https://www.cnblogs.com/janbar
本文版权归作者和博客园所有,欢迎转载,转载请标明出处。喜欢我的文章请 [关注我] 吧。
如果您觉得本篇博文对您有所收获,可点击 [推荐]  [收藏] ,或到右侧 [打赏] 里请我喝杯咖啡,非常感谢。


相关教程