目录

130. 被围绕的区域 Surrounded Regions  🌟🌟

131. 分割回文串 Palindrome Partitioning  🌟🌟

132. 分割回文串 II Palindrome Partitioning II  🌟🌟🌟

🌟 每日一练刷题专栏 🌟

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏

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.length
• n == board[i].length
• 1 <= m, n <= 200
• board[i][j] 为 'X' 或 'O'

代码1： DFS

package mainimport ("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 mainimport ("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 <= 16
• s 仅由小写英文字母组成

代码1： 动态规划

package mainimport ("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 mainimport ("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 <= 2000
• s 仅由小写英文字母组成

代码1： 动态规划

package mainimport ("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] = 0continue}cut[i] = ifor 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 mainimport ("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/ 

	Golang每日一练 专栏
	Python每日一练 专栏
	C/C++每日一练 专栏
	Java每日一练 专栏