/// 1.机器人走格子 m 行数 、 n 列数
func uniquePaths(_ m: Int, _ n: Int) -> Int {
// dp[1][n]、dp[m][1] 最外层的横竖排，每格只有一种走法，所以用1初始化
var H = [Int].init(repeating: 1, count: n-1)
let V = [Int].init(repeating: 1, count: m-1)
// 处理异常
if(m == 1 || n == 1){
return 1
}
// 按行遍历，dp[i][j] 的必由上面的格或左边的格走到，由 dp[i-1][j] + dp[i][j-1]的和来计算当前格的不同走法
for _ in 0...V.count-1 {
for j in 0...H.count - 1 {
let top = H[j]
var left = 0
if(j == 0){
left = 1
}else {
left = H[j - 1]
}
H[j] = top + left
}
}
return H.last!
}
/// 2.最小路径和，每个格子一个值，也是只能向右或向下
/// - Parameter grid: <#grid description#>
/// - Returns: <#description#>
func minPathSum(_ grid: [[Int]]) -> Int {
// 因为数组元素是基础数据类型，赋值会产生copy，用新数组来记录处理后的元素
var resArr = [[Int]]()
// 处理异常
if(grid.count == 0){
return 0
}else if(grid.count == 1){
let numbers = grid.first!
let sum = numbers.reduce(0, +)
return sum
}
for i in 0...grid.count-1 {
var nums = grid[i]
// 遍历每个数，将每个元素的值都替换成走到当前步数最少的累加和
for j in 0...nums.count-1 {
// 如过上面没有元素， 0
var numTop = 0
if(i > 0){
// 这里注意，上面的值需要对接的是新数组 resArr，旧的数组值没有发生变化
let topNums = resArr[i-1];
numTop = topNums[j]
}
// 如果左边没有元素， 0
var numLeft = 0
if(j > 0){
numLeft = nums[j-1];
}
// 如果上面没有元素，那就必须加左边的元素，同理，如果左边没有元素，必须加上面的元素，因为必须有一个路径
if(i == 0 && j == 0){
}else if (i == 0){
nums[j] = nums[j] + numLeft
continue
}else if (j == 0){
nums[j] = nums[j] + numTop
continue
}
// 当前值 = 取上左的最小值 + 当前值
nums[j] = nums[j]+(min(numTop, numLeft))
}
resArr.append(nums)
}
let lastLine = resArr.last!
return lastLine.last!
}
/// 3.机器人走格子plus，数组元素为1时，代表障碍物，机器人依旧每次只能向右或者向下一步
/// - Parameter obstacleGrid: <#obstacleGrid description#>
/// - Returns: <#description#>
func uniquePathsWithObstacles(_ obstacleGrid: [[Int]]) -> Int {
if (obstacleGrid.count == 0){
return 0
}else if (obstacleGrid.count == 1){
let lineOne = obstacleGrid.first!
if lineOne.contains(1){
// 如果单行中包含障碍物
return 0
}
}
// count >= 2
var res = [Int]() // res存储的是不同的方法数
for i in 0...obstacleGrid.count - 1 {
let line = obstacleGrid[i]
var obstacle = false
for j in 0...line.count - 1 {
// 第一行，如果num = 0 （空格）, 那就是1种，如果num == 1 （障碍物），那么后面的都是 0
if (i == 0){
if line[j] == 0 && obstacle == false{
res.append(1)
}else {
res.append(0)
obstacle = true
}
}else {
if(line[j] == 1){
// 如果当前格子是障碍物，那么通过方法数就是0
res[j] = 0
}else {
if(j == 0){
res[j] = res[j] // 直接用上面的值
}else {
res[j] = res[j - 1] + res[j] // 左 + 上
}
}
}
}
}
return res.last!
}
/*
2
3 4
6 5 7
4 1 8 3
*/
/// 4.三角形阶梯,向下只能走一步，只能走下标相同，或者下标 + 1
/// - Parameter triangle: <#triangle description#>
/// - Returns: <#description#>
func minimumTotal(_ triangle: [[Int]]) -> Int {
if(triangle.count == 0){
return 0
}else if (triangle.count == 1){
let res = triangle.first!
return res.min()!
}
var res = [Int]()
// res初始值就是第一行
res = triangle.first!
for lineNum in 0...triangle.count - 1{
var nums = triangle[lineNum]
for i in 0...nums.count - 1 {
if lineNum > 0 {
// 如果是第二行，那么要和上面的那行数字进行比较,上一行应该为res，res存储的才是累加值
if(i == 0){
// 第一个元素，只有一种到达方式，就是上面的同位元素
nums[i] = nums[i] + res.first!
}else if(i > res.count - 1){
// 最后一个元素，只有一种到达方式，就是上面的最后一个元素
nums[i] = res.last! + nums[i]
}else{
// 其他位置有两个元素，要取最小值
nums[i] = min(res[i-1], res[i]) + nums[i]
}
}else {
// 第一行不用处理
}
}
// 更新res，res存储累加值
res = nums
}
return res.min()!
}
/// 5.方形矩阵，下降路径最小和，可以从第一行的任意位置开始下降，可以直接下降也可以下降到相邻行，但不能跨行下降
/// - Parameter matrix: <#matrix description#>
/// - Returns: <#description#>
func minFallingPathSum(_ matrix: [[Int]]) -> Int {
if(matrix.count == 0){
return 0
}else if (matrix.count == 1){
let res = matrix.first!
return res.min()!
}
var res = [Int]()
// res初始值就是第一行
res = matrix.first!
for lineNum in 0...matrix.count - 1{
var nums = matrix[lineNum]
for i in 0...nums.count - 1 {
// 从第二行开始处理
if lineNum > 0 {
// 如果是第二行，那么要和上面的那行数字进行比较,上一行应该为res，res存储的才是累加值
if(i == 0){
// 第一个元素，只有两种到达方式，就是上面的同位元素，和上面的 i + 1
if(nums.count > 1){
nums[i] = nums[i] + min(res[0], res[1]);
}else {
nums[i] = nums[i] + res[0]
}
}else if(i == res.count - 1){
// 最后一个元素，只有一种到达方式，就是上面的最后一个元素
if(nums.count > 1){
nums[i] = nums[i] + min(res[i - 1], res[i])
}else {
nums[i] = nums[i] + res[i]
}
}else{
// 其他位置有两个元素，要取最小值
nums[i] = min(res[i-1], res[i], res[i + 1]) + nums[i]
}
}
}
// 更新res，res存储累加值
res = nums
}
return res.min()!
}
/// 6.最大正方形
/// - Parameter matrix: <#matrix description#>
/// - Returns: <#description#>
func maximalSquare(_ matrix: [[Character]]) -> Int {
// 每个元素值，换成当前元素为右下角的最大正方形的面积
if matrix.count == 0 { return 0}
// 上一行的运算结果
var topLineResult = [Int](repeating: 1, count: matrix.first!.count)
// 保存当前行计算结果的临时数组
var tempResult = [Int](repeating: 1, count: matrix.first!.count)
var max = 0
for lineNum in 0...matrix.count-1{
let chars = matrix[lineNum]
// 遍历当前行中的元素
for i in 0...chars.count-1 {
let unitChar = chars[i]
let intChar = Int(String(unitChar))!
// 处理最小值为0的情况，从1开始
if(max == 0 && intChar == 1){
max = 1
continue
}
if(intChar == 0){
tempResult[i] = 0
continue;
}
// 当前格子为1
tempResult[i] = 1;
// 当前格子可作为右下角的格子，左、上都还有位置
if(lineNum - 1 >= 0 && i - 1 >= 0){
let leftTopInt = topLineResult[i - 1]
// 左上角的格子大于0
if(leftTopInt > 0){
/**
左上角格子开平方取边长
比如 左上角格子 = 4，说明左上角是一个边长为2的正方形
*/
let sideLength = sqrt(Double(leftTopInt))
// 这里应该来一个最长边到最小边，而不是不满足最长就false
for j in 1...Int(sideLength) {
if (lineNum - j >= 0 && i - j >= 0){
let topChart = matrix[lineNum - j][i]
let leftChart = matrix[lineNum][i - j]
// 边长以当前格子为原点，x轴往左，y轴往上，逐步延伸
if (Int(String(topChart))! > 0 && Int(String(leftChart))! > 0){
// 每成功延伸一条，就把当前格子的正方形的最大面积替换
// 这里无法优化，因为当前边长即便不超过最大值，也可能需要作为下个方形的判断依据
tempResult[i] = (j + 1) * (j + 1)
if(tempResult[i] > max){
max = tempResult[i]
}
}else {
break
}
}else{
break
}
}
}
}
}
topLineResult = tempResult
}
return max
}
//func maximalSquare(_ matrix: [[Character]]) -> Int {
// if matrix.isEmpty || matrix[0].isEmpty { return 0 }
// let m = matrix.count, n = matrix[0].count
// var dp = [Int](repeating: 0, count: n)
// var maxLength = 0, prev = 0
// for i in 0..<m {
// for j in 0..<n {
// let temp = dp[j]
// if i == 0 || j == 0 || matrix[i][j] == "0" {
// dp[j] = Int(String(matrix[i][j]))!
// } else {
// dp[j] = min(dp[j], dp[j-1], prev) + 1
// }
// maxLength = max(maxLength, dp[j])
// prev = temp
// }
// }
// return maxLength * maxLength
//}
网友评论