130. 被围绕的区域 Surrounded Regions
给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
示例 1：
输入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
示例 2：
输入：board = [["X"]]
输出：[["X"]]
提示：
m == board.lengthn == board[i].length1 <= m, n <= 200board[i][j]为'X'或'O'
代码1：DFS
package main import ( "fmt" ) func solve(board [][]byte) { if len(board) == 0 || len(board[0]) == 0 { return } m, n := len(board), len(board[0]) // 从边界的'O'出发，将与其相连的'O'标记为'A' for i := 0; i < m; i++ { dfs(board, i, 0) dfs(board, i, n-1) } for j := 0; j < n; j++ { dfs(board, 0, j) dfs(board, m-1, j) } // 将未被标记的'O'填充为'X'，将标记为'A'的'O'恢复为'O' for i := 0; i < m; i++ { for j := 0; j < n; j++ { if board[i][j] == 'O' { board[i][j] = 'X' } else if board[i][j] == 'A' { board[i][j] = 'O' } } } } func dfs(board [][]byte, i, j int) { if i < 0 || i >= len(board) || j < 0 || j >= len(board[0]) || board[i][j] != 'O' { return } board[i][j] = 'A' dfs(board, i-1, j) dfs(board, i+1, j) dfs(board, i, j-1) dfs(board, i, j+1) } func ArrayToString(arr []byte) string { res := "[" for i := 0; i < len(arr); i++ { res += string(arr[i]) if i != len(arr)-1 { res += "," } } return res + "]" } func main() { board := [][]byte{ {'X', 'X', 'X', 'X'}, {'X', 'O', 'O', 'X'}, {'X', 'X', 'O', 'X'}, {'X', 'O', 'X', 'X'}} solve(board) for _, row := range board { fmt.Println(ArrayToString(row)) } }
输出：
[X,X,X,X]
[X,X,X,X]
[X,X,X,X]
[X,O,X,X]
代码2： BFS
package main import ( "fmt" ) func solve(board [][]byte) { if len(board) == 0 || len(board[0]) == 0 { return } m, n := len(board), len(board[0]) // 从边界的'O'出发，将与其相连的'O'标记为'A' queue := make([][2]int, 0) for i := 0; i < m; i++ { if board[i][0] == 'O' { queue = append(queue, [2]int{i, 0}) } if board[i][n-1] == 'O' { queue = append(queue, [2]int{i, n - 1}) } } for j := 0; j < n; j++ { if board[0][j] == 'O' { queue = append(queue, [2]int{0, j}) } if board[m-1][j] == 'O' { queue = append(queue, [2]int{m - 1, j}) } } for len(queue) > 0 { i, j := queue[0][0], queue[0][1] queue = queue[1:] board[i][j] = 'A' if i > 0 && board[i-1][j] == 'O' { queue = append(queue, [2]int{i - 1, j}) } if i < m-1 && board[i+1][j] == 'O' { queue = append(queue, [2]int{i + 1, j}) } if j > 0 && board[i][j-1] == 'O' { queue = append(queue, [2]int{i, j - 1}) } if j < n-1 && board[i][j+1] == 'O' { queue = append(queue, [2]int{i, j + 1}) } } // 将未被标记的'O'填充为'X'，将标记为'A'的'O'恢复为'O' for i := 0; i < m; i++ { for j := 0; j < n; j++ { if board[i][j] == 'O' { board[i][j] = 'X' } else if board[i][j] == 'A' { board[i][j] = 'O' } } } } func ArrayToString(arr []byte) string { res := "[" for i := 0; i < len(arr); i++ { res += string(arr[i]) if i != len(arr)-1 { res += "," } } return res + "]" } func main() { board := [][]byte{ {'X', 'X', 'X', 'X'}, {'X', 'O', 'O', 'X'}, {'X', 'X', 'O', 'X'}, {'X', 'O', 'X', 'X'}} solve(board) for _, row := range board { fmt.Println(ArrayToString(row)) } }
131. 分割回文串 Palindrome Partitioning
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
示例 2：
输入：s = "a"
输出：[["a"]]
提示：
1 <= s.length <= 16s仅由小写英文字母组成
代码1： 动态规划
package main import ( "fmt" "strings" ) func partition(s string) [][]string { n := len(s) dp := make([][]bool, n) for i := range dp { dp[i] = make([]bool, n) } for j := 0; j < n; j++ { for i := 0; i <= j; i++ { if s[i] == s[j] && (j-i <= 2 || dp[i+1][j-1]) { dp[i][j] = true } } } res := make([][]string, 0) path := make([]string, 0) dfs(s, 0, dp, path, &res) return res } func dfs(s string, start int, dp [][]bool, path []string, res *[][]string) { if start == len(s) { tmp := make([]string, len(path)) copy(tmp, path) *res = append(*res, tmp) return } for i := start; i < len(s); i++ { if dp[start][i] { path = append(path, s[start:i+1]) dfs(s, i+1, dp, path, res) path = path[:len(path)-1] } } } func ArrayToString(arr []string) string { res := "[" for i := 0; i < len(arr); i++ { res += arr[i] if i != len(arr)-1 { res += "," } } return res + "]" } func main() { str := "aab" fmt.Println(strings.Join(strings.Fields(fmt.Sprint(partition(str))), ",")) str = "a" fmt.Println(strings.Join(strings.Fields(fmt.Sprint(partition(str))), ",")) }
输出：
[[a,a,b],[aa,b]]
[[a]]
代码2： 回溯
package main import ( "fmt" "strings" ) func partition(s string) [][]string { res := make([][]string, 0) path := make([]string, 0) backtrack(s, 0, path, &res) return res } func backtrack(s string, start int, path []string, res *[][]string) { if start == len(s) { tmp := make([]string, len(path)) copy(tmp, path) *res = append(*res, tmp) return } for i := start; i < len(s); i++ { if isPalindrome(s, start, i) { path = append(path, s[start:i+1]) backtrack(s, i+1, path, res) path = path[:len(path)-1] } } } func isPalindrome(s string, start, end int) bool { for start < end { if s[start] != s[end] { return false } start++ end-- } return true } func ArrayToString(arr []string) string { res := "[" for i := 0; i < len(arr); i++ { res += arr[i] if i != len(arr)-1 { res += "," } } return res + "]" } func main() { str := "aab" fmt.Println(strings.Join(strings.Fields(fmt.Sprint(partition(str))), ",")) str = "a" fmt.Println(strings.Join(strings.Fields(fmt.Sprint(partition(str))), ",")) }
132. 分割回文串 II Palindrome Partitioning II
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。
返回符合要求的 最少分割次数 。
示例 1：
输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
示例 2：
输入：s = "a"
输出：0
示例 3：
输入：s = "ab"
输出：1
提示：
1 <= s.length <= 2000s仅由小写英文字母组成
代码1： 动态规划
package main import ( "fmt" ) func minCut(s string) int { n := len(s) dp := make([][]bool, n) for i := range dp { dp[i] = make([]bool, n) } for j := 0; j < n; j++ { for i := 0; i <= j; i++ { if s[i] == s[j] && (j-i <= 2 || dp[i+1][j-1]) { dp[i][j] = true } } } cut := make([]int, n) for i := 0; i < n; i++ { if dp[0][i] { cut[i] = 0 continue } cut[i] = i for j := 0; j < i; j++ { if dp[j+1][i] { cut[i] = min(cut[i], cut[j]+1) } } } return cut[n-1] } func min(a, b int) int { if a < b { return a } return b } func main() { str := "aab" fmt.Println(minCut(str)) str = "a" fmt.Println(minCut(str)) str = "ab" fmt.Println(minCut(str)) }
输出：
1
0
1
代码2： 动态规划
package main import ( "fmt" ) func minCut(s string) int { n := len(s) cut := make([]int, n) for i := range cut { cut[i] = i } for i := 0; i < n; i++ { expand(s, i, i, &cut) expand(s, i, i+1, &cut) } return cut[n-1] } func expand(s string, left, right int, cut *[]int) { for left >= 0 && right < len(s) && s[left] == s[right] { if left == 0 { (*cut)[right] = 0 } else { (*cut)[right] = min((*cut)[right], (*cut)[left-1]+1) } left-- right++ } } func min(a, b int) int { if a < b { return a } return b } func main() { str := "aab" fmt.Println(minCut(str)) str = "a" fmt.Println(minCut(str)) str = "ab" fmt.Println(minCut(str)) }
🌟 每日一练刷题专栏 🌟
✨持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
☸ 主页：https://hannyang.blog.csdn.net/
