LeetCode中级算法-回溯算法（2）
子集
[题目]
给定一个不包含重复元素的数组，返回该数组所有可能的子集
[输入]
[1,2,3][返回]
[[] [3] [2] [2 3] [1] [1 3] [1 2] [1 2 3]][解法]
这个题目的解点在于每个元素在子集中是否出现，一个元素在子集中只有两种状态：出现/不出现，所以我们在回溯index元素的时候，可以根据这两种状态分别进行回溯
[代码实现]
package main
import "fmt"
func main() {
input := []int {1,2,3}
result := computeResult(input)
fmt.Println("result:", result)
}
func computeResult(input []int) [][]int {
backtracking(input, 0, []int{})
return results
}
var results [][]int
// 元素是否在子集中的状态
var state = []int {0, 1}
func backtracking(input []int, index int, result []int) {
if index == len(input) {
results = append(results, result)
return
}
for i := 0; i < len(state); i++ {
if state[i] == 0 {
backtracking(input, index + 1, copy(result))
} else {
result = append(result, input[index])
backtracking(input, index + 1, copy(result))
}
}
}
func copy(input []int) []int {
result := make([]int, len(input))
for i := 0; i < len(input); i++ {
result[i] = input[i]
}
return result
}单词搜索
[题目]
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
[
["A","B","C","E"],
["S","F","C","S"],
["A","D","E","E"],
][输入1]
"ABCCED"[返回1]
true[输入2]
"ABCS"[返回2]
false[解法]
这个题目的解点是第i个元素的上下左右是不是下一个元素，遍历整个字符串，当遍历到第i个字符串的时候，需要在上一个字母的坐标周围(上下左右)找到第i个字母，要是可以找到，就遍历下一个字符，并让下一个字符以新的坐标进行检测，整个过程中只要发现有true的，就说明可以继续向下
[代码实现]
package main
import "fmt"
var board = [][]string {
{"A","B","C","E"},
{"S","F","C","S"},
{"A","D","E","E"},
}
func main() {
input := "ABCS"
result := computeResult(input)
fmt.Println("result:", result)
}
var position = [][]int{
{1, 0},
{-1, 0},
{0, 1},
{0, -1},
}
func computeResult(input string) bool {
rowCount := len(board)
colCount := len(board[0])
exists := false
for i := 0; i < rowCount; i++ {
if exists {
break
}
for j := 0; j < colCount; j++ {
if backtracking(input, 0, i, j) {
exists = true
break
}
}
}
return exists
}
func backtracking(input string, index int, x int, y int) bool {
if index == len(input) {
return true
}
existX, existY := -1, -1
if index == 0 {
if checkExist(x, y, string(input[index])) {
existX = x
existY = y
}
} else {
for i := 0; i < len(position); i++ {
newX, newY := x + position[i][0], y + position[i][1]
if index == 0 {
newX, newY = x, y
}
if checkExist(newX, newY, string(input[index])) {
existX = newX
existY = newY
break
}
}
}
if existX >= 0 && existY >= 0 {
return backtracking(input, index + 1, existX, existY)
}
return false
}
func checkExist(newX, newY int, item string) bool {
rowCount := len(board)
colCount := len(board[0])
if newX >= 0 && newX < rowCount && newY >= 0 && newY < colCount {
return board[newX][newY] == item
}
return false
}本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2021-01-05，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读