dfs

• 先做这道dfsLeetCode 40. 组合总和 II

var ans []string

func removeInvalidParentheses(s string) []string {
    ans = []string{}
    l, r := 0, 0
    for i := 0; i < len(s); i ++ {
        if s[i] == '(' {
            l ++
        } else if s[i] == ')' {
            if l == 0 {
                r ++
            } else {
                l --
            }
        }
    }

    dfs(s, "", 0, 0, l, r)
    return ans
}

func dfs(s, path string, u, cnt, l, r int) {
    if u == len(s) {
        if cnt == 0 {
            tmp := make([]byte, len(path))
            copy(tmp, path)
            ans = append(ans, string(tmp))
        }
        return
    }

    if s[u] != '(' && s[u] != ')' {
        dfs(s, path + string(s[u]), u + 1, cnt, l, r)
    } else {

        if (s[u] == '(') {
            k := u
            for k < len(s) && s[k] == '(' {
                k ++
            }
            l -= k - u
            for i := k - u; i >= 0; i -- {
                if l >= 0 {
                    dfs(s, path, k, cnt, l, r)
                }
                l ++
                cnt ++
                path += "("
            }

        } else {
            k := u
            for k < len(s) && s[k] == ')' {
                k ++
            }
            r -= k - u
            for i := k - u; i >= 0; i -- {
                if r >= 0 && cnt >= 0 {
                    dfs(s, path, k, cnt, l, r)
                } 
                r ++
                cnt --
                path += ")"
            }
        }
    }

}

dfs

• 每次dfs是一段一段枚举

var (
    ans [][]int
    path []int
)

func combinationSum2(cs []int, target int) [][]int {
    sort.Ints(cs[:])
    ans = [][]int{}
    path = []int{}

    dfs(cs, 0, target)
    return ans
}

func dfs(cs []int, u, target int) {
    if target == 0 {
        tmp := make([]int, len(path))
        copy(tmp, path)
        ans = append(ans, tmp)
        return
    }

    if u == len(cs) {
        return
    }


    k := u + 1
    for k < len(cs) && cs[k] == cs[u] {
        k ++
    }
    cnt := k - u

    i := 0
    for i = 0; cs[u] * i <= target && i <= cnt; i ++ {
        dfs(cs, k, target - cs[u] * i)
        path = append(path, cs[u])
    }

    path = path[:len(path) - i]
}

func modifyString(s string) string {
    res := ""
    for i := 0; i < len(s); i ++ {
        if s[i] != '?' {
            res += string(s[i])
            continue
        }

        c := int('a')
        for (i > 0 && res[i - 1] == byte(c)) || (i + 1 < len(s) && s[i + 1] == byte(c)) {
            c ++
        }
        res += string(byte(c))
    }

    return res
}

dp

• 先做lc152. 乘积最大子数组这题
• f[i], 以a[i]为结尾的乘积为正数最大长度；
• g[i], 以a[i]为结尾的乘积为负数最大长度；
• 边界情况，要处理g[i] == 0

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func getMaxLen(nums []int) int {
    n := len(nums)
    f := make([]int, n + 1)
    g := make([]int, n + 1)

    f[0], g[0] = 0, 0
    res := 0
    for i := 1; i <= n; i ++ {
        a := nums[i - 1]

        if a > 0 {
            if g[i - 1] == 0 {
                g[i] = 0
            } else {
                g[i] = g[i - 1] + 1
            }

            f[i] = f[i - 1] + 1

        } else if a < 0 {
            if g[i - 1] == 0 {
                f[i] = 0
            } else {
                f[i] = g[i - 1] + 1
            }

            g[i] = f[i - 1] + 1
        } else {
            f[i] = 0
            g[i] = 0
        }

        res = max(res, f[i])
    }

    return res
}

• 枚举每一个起点i,
• 以i为起点长度为m*k的子序列, 检查k段m长度是否一样（使用偏移量来对比）

func containsPattern(arr []int, m int, k int) bool {
    for i := 0; i + m * k <= len(arr); i ++ {
        flag := true
        for j := i; j < i + m * k; j ++ {
            if arr[j] != arr[(j - i) % m + i] {
                flag = false
                break
            }

        }
        if flag {
            return true
        }
    }
    return false
}

func thousandSeparator(n int) string {
    if n == 0 {
        return "0"
    }

    s := ""

    for i := 1; n > 0; i ++ {
        s += strconv.Itoa(n % 10)
        n /= 10
        if n > 0 && i % 3 == 0 {
            s += "."
        }
    }

    res := ""
    for i := len(s) - 1; i >= 0; i -- {
        res += string(s[i])
    }
    return res
}

dfs

• 枚举每个数，每个数选的数量（在递归内保证数量是有效），求和用减法，
• 由于要记录方案，path 需要拷贝否则会修改

var (
    ans [][]int
    path []int
)

func combinationSum(cs []int, target int) [][]int {
    ans = [][]int{}
    path = []int{}
    dfs(cs, 0, target)
    return ans
}

func dfs(cs []int, u, target int) {
    if target == 0 {
        tmp := make([]int, len(path))
        copy(tmp, path)
        ans = append(ans, tmp)
        return
    }

    if u == len(cs) {
        return
    }

    i := 0
    for i = 0; cs[u] * i <= target; i ++ {
        dfs(cs, u + 1, target - cs[u] * i)
        path = append(path, cs[u])
    }

    // append了多少次就要pop出来多少次
    path = path[:len(path) - i]
}

dfs

• 回溯是，优先找到答案就要立刻回溯，其次找不到答案回溯；
• 比如下面两种写法：

  A）if check() return true
  B) if !check() 恢复现场继续递归

• 应该选写法A，A找到答案立刻回溯

func solveSudoku(board [][]byte)  {
    row := make([][]bool, 9)
    col := make([][]bool, 9)
    cell := make([][]bool, 9)

    for i := 0; i < 9; i ++ {
        row[i] = make([]bool, 9)
        col[i] = make([]bool, 9)
        cell[i] = make([]bool, 9)
    }

    for i := 0; i < 9; i ++ {
        for j := 0; j < 9; j ++ {
            if board[i][j] != '.' {
                u := int(board[i][j]) - 49
                row[i][u] = true
                col[j][u] = true
                idx := (i / 3 * 3) + (j / 3)
                cell[idx][u] = true
            }
        }
    }

    dfs(board, row, col, cell, 0, 0)
}

func dfs(board [][]byte, row, col, cell [][]bool, x, y int) bool {

    if y == 9 {
        x ++
        y = 0
    }

    if x == 9 {
        return true
    }

    if board[x][y] != '.' {
        return dfs(board, row, col, cell, x, y + 1)
    } 

    for i := 0; i < 9; i ++ {
        idx := (x / 3 * 3) + (y / 3)
        if !row[x][i] && !col[y][i] && !cell[idx][i] {
            board[x][y] = byte(i + 49)
            row[x][i] = true
            col[y][i] = true
            cell[idx][i] = true

            if dfs(board, row, col, cell, x, y + 1) {
                return true    
            }

            row[x][i] = false
            col[y][i] = false
            cell[idx][i] = false
            board[x][y] = '.'
        }
    }

    return false
}

区间DP

• 建议先看AcWing 282. 石子合并

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
func stoneGameV(st []int) int {

    n := len(st)
    f := make([][]int, n + 1)
    s := make([]int, n + 1)
    for i := 0; i <= n; i ++ {
        f[i] = make([]int, n + 1)
    }

    for i := 1; i <= n; i ++ {
        s[i] = s[i - 1] + st[i - 1]
    }

    for len := 2; len <= n; len ++ {
        for i := 1; i + len - 1 <= n; i ++ {
            j := i + len - 1

            for k := i; k < j; k ++ {
                left := s[k] - s[i - 1]
                right := s[j] - s[k]

                if left < right {
                    f[i][j] = max(f[i][j], left + f[i][k])
                } else if right < left {
                    f[i][j] = max(f[i][j], right + f[k + 1][j])
                } else {
                    f[i][j] = left + max(f[i][k], f[k + 1][j])
                }
            }
        }
    }

    return f[1][n]
}

类似题目

• lc1482. 制作 m 束花所需的最少天数
• lc352. 将数据流变为多个不相交区间

var (
    l []int
    r []int
)

func get(x int) int {
    return r[x] - x + 1
}

func findLatestStep(arr []int, m int) int {
    n := len(arr)
    l = make([]int, n + 2)
    r = make([]int, n + 2)

    cnt := 0
    res := -1
    for i := 0; i < n; i ++ {
        x := arr[i]

        if l[x - 1] > 0 && r[x + 1] > 0 {
            if get(l[x - 1]) == m {
                cnt --
            }

            if get(x + 1) == m {
                cnt --
            }

            r[l[x - 1]] = r[x + 1]
            l[r[x + 1]] = l[x - 1]

            if get(l[x - 1]) == m {
                cnt ++
            }

        } else if l[x - 1] > 0 {
            t := get(l[x - 1])
            if t == m {
                cnt --
            }
            r[l[x - 1]] = x
            l[x] = l[x - 1]
            t = get(l[x - 1])

            if t == m {
                cnt ++
            }
        } else if r[x + 1] > 0 {
            if get(x + 1) == m {
                cnt --
            }

            l[r[x + 1]] = x
            r[x] = r[x + 1]

            if get(x) == m {
                cnt ++ 
            }
        } else {
            l[x] = x
            r[x] = x
            if m == 1 {
                cnt ++
            }
        }

        if cnt > 0 {
            res = i + 1
        }
    }

    return res
}