蚂蚁笔试go 9-22
蚂蚁前两道笔试题送分题，很快就ac了，
但第三道不知道怎么优化，只会很笨的回溯方法，把n*n的数字填满之后然后判断是不是符合规定，当n很大的时候肯定跑不过
中间也尝试过不等n*n二维数组填满的时候就判断是否符合要求，但折腾了折腾白折腾
附上第三题题目，之前力扣上也刷过类似于解数独的题目 [37. 解数独]
小红构造n行n列矩阵，2*2的举矩阵之和都为奇数示例1：
输入
3
输出
1 3 2
7 4 6
9 5 8示例2：
输入
2
输出
-1
package main
import (
"fmt"
)
func main() {
test003()
}
//数字是 1到 n*n
//每个 2*2 矩阵中四个元素之和为 奇数
//有多解时候，输出一个就好
func test003() {
var n int
fmt.Scan(&n)
//保存结果
result := make([][]int, n)
for i := 0; i < n; i++ {
result[i] = make([]int, n)
}
used := make([]bool, n*n+1)
//每个 2*2 矩阵中四个元素之和为 奇数 则返回true
check := func() bool {
for i := 0; i < n-1; i++ {
var temp int
for j := 0; j < n-1; j++ {
temp = 0
for k := j; k < j+2; k++ {
temp += result[i][k]
temp += result[i+1][k]
}
if temp%2 == 0 {
return false
}
}
}
return true
}
var backtrack func(index int) bool
backtrack = func(index int) bool {
if index == n*n && check() { //当n*n数组填满时，去判断是否符合要求
return true
}
// i,j 表示待填充二维矩阵中的横坐标和纵坐标
i, j := index/n, index%n
//选择列表
for k := 1; k <= n*n; k++ {
if used[k] {
continue
} else {
used[k] = true
result[i][j] = k
//继续填充下一个
if backtrack(index + 1) {
return true
}
//回溯
used[k] = false
result[i][j] = 0
}
}
return false
}
if backtrack(0) {
//存在解则打印解
for i := 0; i < n; i++ {
fmt.Print(result[i][0])
for j := 1; j < n; j++ {
fmt.Print(" ", result[i][j])
}
fmt.Print("\n")
}
} else {
fmt.Println(-1)
}
} 第二题可能大家的题目不太一样，反正我的题目如下： 小红拿到数字串，截取一段小于k，求几种截取方案
样例1：
输入
1234
23
输出
5
然后我就随便写了代码也没优化 多个if可以优化一下...
package main
import (
"fmt"
"strconv"
"strings"
)
func main() {
test002()
}
func test002() {
var str string
var k int
fmt.Scan(&str)
fmt.Scan(&k)
ans := 0
strk := strconv.Itoa(k)
for i := 0; i < len(str); i++ {
for j := i; j < len(str); j++ {
temp := str[i : j+1]
if len(temp) < len(strk) {
ans++
continue
}
if len(temp) == len(strk) && strings.Compare(temp, strk) < 0 {
ans++
continue
}
if len(temp) > len(strk) {
break
}
}
}
fmt.Println(ans)
}
