- 首页 > it技术 > >
leetcode 401 组合问题
func readBinaryWatch(turnedOn int) []string {
if turnedOn >= 9 {
//panic("不能正确表示")
return []string{}
}
maxHnum := 3
maxMnum := 5
returnData := make([]string, 0, 255)
for hourNum, minuteNum := 0, 0;
hourNum <= maxHnum;
hourNum++ {
minuteNum = turnedOn - hourNum
if (minuteNum < 0) {
break;
}
if minuteNum >maxMnum {
continue
}
hourList := getHour(hourNum)
minuteList := getMinute(minuteNum)for _, h := range hourList {
for _, m := range minuteList {
returnData = https://www.it610.com/article/append(returnData, h +":" + m)
}
} }
return returnData
}func getMinute(n int) []string {
if (n == 0) {
return []string{"00"}
}
cSet := []int{1, 2, 4, 8, 16, 32}
num := make([]string, 0, 60)list := sumNumItem(cSet, n)
for _, v := range list {
if v > 59 {
continue
}
num = append(num, fmt.Sprintf("%02d", v))
}
return num
}func getHour(n int) []string {
if (n == 0) {
return []string {"0"}
}
cSet := []int{1, 2, 4, 8}num := make([]string, 0, 60)
list := sumNumItem(cSet, n)for _, v := range list {
if v > 11 {
continue
}
num = append(num, fmt.Sprintf("%d", v))
}
return num
}func sumNumItem(list []int, num int) []int {
l := len(list)
if num > l {
//panic("求和数量异常")
return []int{}
}if num == 1 {
return list
}returnData := make([]int, 0, 60)
//使用位图对应方式，依次确认站位组合
indexList := make([]int, l)
for i := 0;
i < num;
i++ {
indexList[i] = 1
}
returnData = https://www.it610.com/article/append(returnData, sumIdxNum(list, indexList))
for {
find := false
for i := 0;
i < l - 1;
i++ {
if (indexList[i] == 1 && indexList[i + 1] == 0) {
find = true
indexList[i], indexList[i + 1] = 0, 1
if indexList[0] == 0 && i> 1 {
resetZeroIdx(indexList, i)
}
returnData = https://www.it610.com/article/append(returnData, sumIdxNum(list, indexList))
break
}}
if !find {
break
}
}
return returnData
}func sumIdxNum(list []int, idxSet []int) int {
num := 0
for idx, b := range idxSet {
if b == 1 {
num += list[idx]
}
}
return num
}func resetZeroIdx(idxList []int, k int) {
sum := 0
for i := 0;
i < k;
i++ {
if idxList[i] == 1 {
sum++
}
}
//将前sum个改为1，之后的改为0
for i := 0;
i < k;
i++ {
if i < sum {
idxList[i] = 1
} else {
idxList[i] = 0
}
}
}
推荐阅读
