每日LeetCode力扣（36~40） _Leetcode

知是行的主意,行是知的功夫。这篇文章主要讲述每日LeetCode力扣（36~40）相关的知识，希望能为你提供帮助。
36. 有效的数独

判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
上图是一个部分填充的有效的数独。
数独部分空格内已填入了数字，空白格用 . 表示。
示例 1:
输入:
[
["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
输出: true
示例 2:
输入:
[
["8","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
输出: false
解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与示例1 相同。
但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
说明:
一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
给定数独序列只包含数字 1-9 和字符 . 。
给定数独永远是 9x9 形式的。

解题

fun _0036_isValidSudoku()
println("--------_0036_isValidSudoku-------")
println(
isValidSudoku(
arrayOf(
charArrayOf(8, 3, ., ., 7, ., ., ., .),
charArrayOf(6, ., ., 1, 9, 5, ., ., .),
charArrayOf(., 9, 5, ., ., ., ., 6, .),
charArrayOf(8, ., ., ., 6, ., ., ., 3),
charArrayOf(4, ., ., 8, ., 3, ., ., 1),
charArrayOf(7, ., ., ., 2, ., ., ., 6),
charArrayOf(., 6, ., ., ., ., 2, 8, .),
charArrayOf(., ., ., 4, 1, 9, ., ., 5),
charArrayOf(., ., ., ., 8, ., ., 7, 9),
)
)
)
println(
isValidSudoku(
arrayOf(
charArrayOf(8, 3, ., ., 7, ., ., ., .),
charArrayOf(6, ., ., 1, 9, 5, ., ., .),
charArrayOf(., 9, 8, ., ., ., ., 6, .),
charArrayOf(8, ., ., ., 6, ., ., ., 3),
charArrayOf(4, ., ., 8, ., 3, ., ., 1),
charArrayOf(7, ., ., ., 2, ., ., ., 6),
charArrayOf(., 6, ., ., ., ., 2, 8, .),
charArrayOf(., ., ., 4, 1, 9, ., ., 5),
charArrayOf(., ., ., ., 8, ., ., 7, 9),
)
)
)

/**
想必数独游戏我们都玩过，就是给一个 9x9 大小的矩阵，可以分为9个 3x3 大小的矩阵，
要求是每个小矩阵内必须都是1到9的数字不能有重复，同时大矩阵的横纵列也不能有重复数字
在遍历每个数字的时候，就看看包含当前位置的行和列以及 3x3 小方阵中是否已经出现该数字，
这里需要三个 boolean 型矩阵，大小跟原数组相同，分别记录各行，各列，各小方阵是否出现某个数字，
其中行和列标志下标很好对应，就是小方阵的下标需要稍稍转换一下
其中一维下标 n 对于3个二维数组分别表示：第 n 行，第 n 列，第 n 个子九宫格
其中二维下标 m 对于3个二维数组分别表示：在当前行、列、子九宫格的数字m
二维数组中的值则表示：该数字是否出现过
*/
fun isValidSudoku(board: Array< CharArray> ): Boolean
val rows = Array(9)BooleanArray(9)
val cols = Array(9)BooleanArray(9)
val boxs = Array(9)BooleanArray(9)
for (i in board.indices)
for (j in board[i].indices)
if (board[i][j] != .)
val num = board[i][j] - 0 - 1
val k = i / 3 * 3 + j / 3
if (rows[i][num] || cols[j][num] || boxs[k][num]) return false
rows[i][num] = cols[j][num]
cols[j][num] = boxs[k][num]
boxs[k][num] = true

return true

37. 解数独

编写一个程序，通过填充空格来解决数独问题。
一个数独的解法需遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 . 表示。
提示：
给定的数独序列只包含数字 1-9 和字符 . 。
你可以假设给定的数独只有唯一解。
给定数独永远是 9x9 形式的。

解题

fun _0037_solveSudoku()
println("--------_0037_solveSudoku-------")
solveSudoku(
arrayOf(
charArrayOf(5, 3, ., ., 7, ., ., ., .),
charArrayOf(6, ., ., 1, 9, 5, ., ., .),
charArrayOf(., 9, 8, ., ., ., ., 6, .),
charArrayOf(8, ., ., ., 6, ., ., ., 3),
charArrayOf(4, ., ., 8, ., 3, ., ., 1),
charArrayOf(7, ., ., ., 2, ., ., ., 6),
charArrayOf(., 6, ., ., ., ., 2, 8, .),
charArrayOf(., ., ., 4, 1, 9, ., ., 5),
charArrayOf(., ., ., ., 8, ., ., 7, 9),
)
)

fun solveSudoku(board: Array< CharArray> )
helper(board)
for (cs in board)
println(cs.contentToString())

fun helper(board: Array< CharArray> ): Boolean
for (i in board.indices)
for (j in board[i].indices)
if (board[i][j] != .) continue
for (c in 1..9)
if (!isValidSK(board, i, j, c)) continue
board[i][j] = c
if (helper(board)) return true
board[i][j] = .

return false

return true

fun isValidSK(board: Array< CharArray> , i: Int, j: Int, c: Char): Boolean
for (k in 0..8)
if (board[k][j] != . & & board[k][j] == c) return false
if (board[i][k] != . & & board[i][k] == c) return false
val row = i / 3 * 3 + k / 3
val col = j / 3 * 3 + k % 3
if (board[row][col] != . & & board[row][col] == c) return false

return true

38. 外观数列

给定一个正整数 n ，输出外观数列的第 n 项。
「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。
你可以将其视作是由递归公式定义的数字字符串序列：
countAndSay(1) = "1"
countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。
前五项如下：
1.1
2.11
3.21
4.1211
5.111221
第一项是数字 1
描述前一项，这个数是 1 即 “ 一个 1 ”，记作 "11"
描述前一项，这个数是 11 即 “ 二个 1 ” ，记作 "21"
描述前一项，这个数是 21 即 “ 一个 2 + 一个 1 ” ，记作 "1211"
描述前一项，这个数是 1211 即 “ 一个 1 + 一个 2 + 二个 1 ” ，记作 "111221"
要描述一个数字字符串，首先要将字符串分割为最小数量的组，每个组都由连续的最多相同字符组成。
然后对于每个组，先描述字符的数量，然后描述字符，形成一个描述组。
要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。
示例 1：
输入：n = 1
输出："1"
解释：这是一个基本样例。
示例 2：
输入：n = 4
输出："1211"
解释：
countAndSay(1) = "1"
countAndSay(2) = 读 "1" = 一个 1 = "11"
countAndSay(3) = 读 "11" = 二个 1 = "21"
countAndSay(4) = 读 "21" = 一个 2 + 一个 1 = "12" + "11" = "1211"
提示：
1 < = n < = 30

解题

fun _0038_countAndSay()
println("--------_0038_countAndSay-------")
println(countAndSay(1))
println(countAndSay(2))
println(countAndSay(3))
println(countAndSay(4))
println(countAndSay(5))
println(countAndSay(6))
println(countAndSay(7))
println(countAndSay(8))
println(countAndSay(9))

/**
对于前一个数，找出相同元素的个数，把个数和该元素存到新的 string 里
1
1 1
2 1
1 2 1 1
1 1 1 2 2 1
3 1 2 2 1 1
1 3 1 1 2 2 2 1
1 1 1 3 2 1 3 2 1 1
3 1 1 3 1 2 1 1 1 3 1 2 2 1
*/
fun countAndSay(n: Int): String
println("countAndSay_$n:")
if (n < = 0) return ""
var res = "1"
var n = n
while (--n > 0)
var cur = ""
var i = 0
while (i < res.length)
var cnt = 1
while (i + 1 < res.length & & res[i] == res[i + 1])
++cnt
++i

cur += cnt.toString() + res[i]
i++

res = cur

return res

39. 组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
示例 1：
输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
[7],
[2,2,3]
]
示例 2：
输入：candidates = [2,3,5], target = 8,
所求解集为：
[
[2,2,2,2],
[2,3,3],
[3,5]
]
提示：
1 < = candidates.length < = 30
1 < = candidates[i] < = 200
candidate 中的每个元素都是独一无二的。
1 < = target < = 500

解题

fun _0039_combinationSum()
println("--------_0039_combinationSum-------")
println(combinationSum(intArrayOf(2, 3, 6, 7), 7))
println(combinationSum(intArrayOf(2, 3, 5), 8))

/**
在一个函数中完成递归，要先给数组排序，然后遍历，如果当前数字大于 target，说明肯定无法组成 target，
由于排过序，之后的也无法组成 target，直接 break 掉。如果当前数字正好等于 target，则当前单个数字就是一个解，
组成一个数组然后放到结果 res 中。然后将当前位置之后的数组取出来，调用递归函数，注意此时的 target 要减去当前的数字，
然后遍历递归结果返回的二维数组，将当前数字加到每一个数组最前面，然后再将每个数组加入结果 res 即可
*/
fun combinationSum(candidates: IntArray, target: Int): ArrayList< ArrayList< Int> >
Arrays.sort(candidates)
val res = ArrayList< ArrayList< Int> > ();
for (i in candidates.indices)
if (candidates[i] > target) break
if (candidates[i] == target)
res.add(arrayListOf(candidates[i]))
break

val vec = candidates.copyOfRange(i, candidates.size)
val tmp = combinationSum(vec, target - candidates[i])
for (a in tmp)
a.add(0, candidates[i])
res.add(a)

return res

40. 组合总和 II

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
[1,2,2],
[5]
]

解题

fun _0040_combinationSum2()
println("--------_0040_combinationSum2-------")
println(combinationSum2(intArrayOf(10, 1, 2, 7, 6, 1, 5), 8))
println(combinationSum2(intArrayOf(2, 5, 2, 1, 2), 5))

/**
* 与上题类似，只是candidates 中的每个数字在每个组合中只能使用一次
* 所以在获取vec时，将i换成i+1即可，即用过i，则从i的下一个开始递归
*/
fun combinationSum2(candidates: IntArray, target: Int): ArrayList< ArrayList< Int> >
Arrays.sort(candidates)
val res = ArrayList< ArrayList< Int> > ();
for (i in candidates.indices)
if (i > 0 & & candidates[i] == candidates[i - 1]) continue
if (candidates[i] > target) break
if (candidates[i] == target)
res.add(arrayListOf(candidates[i]))
break

val vec = candidates.copyOfRange(i + 1, candidates.size)
val tmp = combinationSum2(vec, target - candidates[i])
for (a in tmp)
a.add(0, candidates[i])
res.add(a)

return res