129. 求根節(jié)點到葉節(jié)點數字之和-中等

題目描述：
給你一個二叉樹的根節(jié)點 root ，樹中每個節(jié)點都存放有一個 0 到 9 之間的數字。
每條從根節(jié)點到葉節(jié)點的路徑都代表一個數字：
例如，從根節(jié)點到葉節(jié)點的路徑 1 -> 2 -> 3 表示數字 123 。
計算從根節(jié)點到葉節(jié)點生成的 所有數字之和 。
葉節(jié)點 是指沒有子節(jié)點的節(jié)點。

題解：
簡單的深度優(yōu)先搜索就可以解決

代碼（Go）：

func sumNumbers(root *TreeNode) int {
    return dfs(root,0)
}

func dfs(root *TreeNode,sum int) int {
    if root == nil {
        return sum
    }
    sum = sum * 10 + root.Val
    NewSum := 0
    if root.Left == nil && root.Right == nil{
        return sum
    }
    if root.Left != nil{
        NewSum += dfs(root.Left,sum)
    }
    if root.Right != nil{
        NewSum += dfs(root.Right,sum)
    }
    return NewSum
}

130. 被圍繞的區(qū)域-中等

題目描述：
給你一個 m x n 的矩陣 board ，由若干字符 ‘X’ 和 ‘O’ ，找到所有被 ‘X’ 圍繞的區(qū)域，并將這些區(qū)域里所有的 ‘O’ 用 ‘X’ 填充。

題解：
沒有被包圍的O一定與邊界上的O相連，所以可以反過來從邊界上的O開始找到所有相連的O并標記，最后遍歷矩陣，被標記的O變回O，沒有被標記的O改為X

代碼（Go）：

func solve(board [][]byte)  {
    for i := 0;i < len(board);i++{
        for j := 0;j < len(board[0]);j++{
            if (i == 0 || j == 0 || i == len(board) - 1 || j == len(board[0]) - 1) && board[i][j] == 'O'{
                checkout(board,i,j)
                board[i][j] = '1'
            }
        }
    }
    for i := 0;i < len(board);i++{
        for j := 0;j < len(board[0]);j++{
            if board[i][j] == '1'{
                board[i][j] = 'O'
            }else{
                board[i][j] = 'X'
            }
        }
    }
    return
}

func checkout(board [][]byte,x int,y int) {
    if x - 1 >= 0 && board[x - 1][y] == 'O'{
        board[x - 1][y] = '1'
        checkout(board,x - 1,y)
    }
    if y - 1 >= 0 &&board[x][y - 1] == 'O'{
        board[x][y - 1] = '1'
        checkout(board,x,y - 1)
    }
    if x + 1 < len(board) && board[x + 1][y] == 'O'{
        board[x + 1][y] = '1'
        checkout(board,x + 1,y)
    }
    if y + 1 < len(board[0]) && board[x][y + 1] == 'O'{
        board[x][y + 1] = '1'
        checkout(board,x,y + 1)
    }
    return
}

437. 路徑總和 III-中等

題目描述：
給定一個二叉樹的根節(jié)點 root ，和一個整數 targetSum ，求該二叉樹里節(jié)點值之和等于 targetSum 的 路徑 的數目。
路徑 不需要從根節(jié)點開始，也不需要在葉子節(jié)點結束，但是路徑方向必須是向下的（只能從父節(jié)點到子節(jié)點）。

題解：
代碼寫麻煩了，官方題解更容易懂。我的思路是用一個flag變量標記此節(jié)點是否必選，如果此節(jié)點的父節(jié)點已經被選中到路徑中則該節(jié)點必須被選擇，然后就是常規(guī)的深度優(yōu)先搜索統(tǒng)計即可

代碼（Go）：

func pathSum(root *TreeNode, targetSum int) int {
    return search(root,targetSum,0)
}

func search(root *TreeNode,targetSum int,flag int) int {
    if root == nil{
        return 0
    }
    if root.Val == targetSum && flag == 0{
        return 1 + search(root.Left,0,1) + search(root.Right,0,1) + search(root.Left,targetSum,0) + search(root.Right,targetSum,0)
    }else if root.Val == targetSum && flag == 1{
        return 1 + search(root.Left,0,1) + search(root.Right,0,1)
    }else if flag == 0{
        return search(root.Left,targetSum,0) + search(root.Right,targetSum,0) + search(root.Left,targetSum - root.Val,1) + search(root.Right,targetSum - root.Val,1)
    }else{
        return search(root.Left,targetSum - root.Val,1) + search(root.Right,targetSum - root.Val,1)
    }
}

376. 擺動序列-中等

題目描述：
如果連續(xù)數字之間的差嚴格地在正數和負數之間交替，則數字序列稱為 擺動序列 。第一個差（如果存在的話）可能是正數或負數。僅有一個元素或者含兩個不等元素的序列也視作擺動序列。
例如， [1, 7, 4, 9, 2, 5] 是一個 擺動序列 ，因為差值 (6, -3, 5, -7, 3) 是正負交替出現(xiàn)的。
相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是擺動序列，第一個序列是因為它的前兩個差值都是正數，第二個序列是因為它的最后一個差值為零。
子序列 可以通過從原始序列中刪除一些（也可以不刪除）元素來獲得，剩下的元素保持其原始順序。
給你一個整數數組 nums ，返回 nums 中作為 擺動序列 的 最長子序列的長度 。

題解：
子序列問題直接想到動態(tài)規(guī)劃，整體思路和最長遞增子序列問題基本一致，但是因為每次判斷dp[i]時都需要和前面所有的位置依次對比，所以時間復雜度是O（n2），官方題解使用了兩個dp數組分別表示最后一個元素是上升狀態(tài)的上升數組和最后一個元素是下降狀態(tài)的下降數組，兩個數組的第n個狀態(tài)都可以通過兩個數組的n-1個狀態(tài)共同得出，這樣既使時間復雜度降到了O（n），也使空間復雜度降到了O（1），具體可以看下官方題解

代碼（Go）：

func wiggleMaxLength(nums []int) int {
    dp := make([]int,len(nums))
    sign := make([]int,len(nums))
    for i := 0;i < len(nums);i++{
        if i == 0{
            dp[i] = 1
            sign[i] = 0
        }else if i == 1{
            if nums[i] > nums[0]{
                sign[i] = 1
                dp[i] = 2
            }else if nums[i] < nums[0]{
                sign[i] = -1
                dp[i] = 2
            }else{
                sign[i] = 0
                dp[i] = 1
            }
        }else{
            max := 0
            for j := 0;j < i;j++{
                if sign[j] == 1 && nums[i] < nums[j]{
                    if dp[j] + 1 > max{
                        max = dp[j] + 1
                        sign[i] = -1
                    }
                }else if sign[j] == -1 && nums[i] > nums[j]{
                    if dp[j] + 1 > max{
                        max = dp[j] + 1
                        sign[i] = 1
                    }
                }else if sign[j] == 0{
                    if dp[j] + 1 > max && nums[i] > nums[j]{
                        max = dp[j] + 1
                        sign[i] = 1
                    }else if dp[j] + 1 > max && nums[i] < nums[j]{
                        max = dp[j] + 1
                        sign[i] = -1
                    }
                }
            }
            dp[i] = max
        }
    }
    max := 0
    for i := 0;i < len(nums);i++{
        if dp[i] > max{
            max = dp[i]
        }
    }
    return max
}

總結

終于忙完了一個大階段，正式回歸！但是因為現(xiàn)在還要上課而且兩道簡單兩道中等現(xiàn)在變成了四道中等，所以不一定能保證每天全靠自己做完四道題了，只能說盡量完成，如果時間不夠的話就只能把沒解出來看了題解的題也搬上來了文章來源地址http://www.zghlxwxcb.cn/news/detail-727299.html

到了這里，關于從零開始的力扣刷題記錄-第八十七天的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！