算法其他筆記

分類：動態(tài)規(guī)劃

Leetcode 1137 計算泰波那契數(shù)列

泰波那契序列定義如下:, 且在 的條件下 朋鞍，給你整數(shù)亭饵，請返回第 個泰波那契數(shù) 的值。

思路一：dp(滾動數(shù)組)

重點：滾動數(shù)組思想

開大小為3的數(shù)組劲厌，依次迭代加和懊渡；遞歸則因為要計算的過多而時間復雜度過高(刽射，最后也許會在的數(shù)量級),總復雜度

# https://leetcode.cn/problems/n-th-tribonacci-number/
class Solution:    
        dp = [0, 1, 1]
        cnt = n
        while cnt >= 3:
            dp.append((dp[0] + dp[1] + dp[2]))
            del dp[0]
            cnt -= 1
        return dp[cnt]

思路二：矩陣快速冪

尋找一個矩陣军拟，乘以的列向量，可以得到誓禁，則該矩陣多次冪后乘懈息，即可得到想要的結(jié)果

注意做時，每次摹恰，為則結(jié)果需乘此次快速冪結(jié)果漓拾，然后徐，再讓矩陣自乘一次即可戒祠『Я剑總復雜度

# https://leetcode.cn/problems/n-th-tribonacci-number/
class Solution:    
    def tribonacci(self, n):
        if n == 0:
            return 0
        if n == 1:
            return 1
        if n == 2:
            return 1

        pow_tm, martix, final_mtx =\
            n - 2, [[1, 1, 1], [1, 0, 0], [0, 1, 0]], [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
        while pow_tm != 0:
            if (pow_tm & 1) == 1:
                    final_mtx = self.martix_mult(martix, final_mtx)
            martix = self.martix_mult(martix, martix)
            pow_tm = pow_tm >> 1
        return final_mtx[0][0] + final_mtx[0][1]

    def martix_mult(self, mrtx1, mrtx2):
        rows = len(mrtx1)
        res = [[0 for _ in range(rows)] for __ in range(rows)]
        for i in range(rows):
            for j in range(rows):
                tmp = 0
                for k in range(rows):
                   tmp += mrtx1[i][k] * mrtx2[k][j]
                res[i][j] = tmp
        return res

Leetcode 42 接雨水

給定 個非負整數(shù)表示每個寬度為 的柱子的高度圖，計算按此排列的柱子姜盈，下雨之后能接多少雨水低千。

思路一：動態(tài)規(guī)劃

動態(tài)規(guī)劃的核心思路：對于每一列，其能盛裝的雨水量是左邊最高馏颂、右邊最高的柱子值的較小值示血。

故我們遍歷三次，分別求出每一格對應左救拉、右最高柱的高度难审、計算每一格對應列的盛裝雨水量。時間復雜度亿絮，空間復雜度告喊。

# https://leetcode.cn/problems/trapping-rain-water/
class Solution:
    def trap(self, height):
        l_h, r_h, cur_max = [0 for _ in range(len(height))], [None for _ in range(len(height))], height[0]
        for i in range(1, len(height)):
            cur_max = max(cur_max, height[i-1])
            l_h[i] = cur_max
        cur_max = height[-1]
        for i in range(len(height) - 2, -1, -1):
            cur_max = max(cur_max, height[i+1])
            r_h[i] = cur_max
        ans = 0
        for i in range(1,len(height)-1):
            ans += max(min(l_h[i], r_h[i]) - height[i], 0)
        return ans

空間復雜度優(yōu)化：由于左最高單增，右最高單減派昧，故可以利用雙指針黔姜，從左、右分別向另一側(cè)掃描蒂萎，而左最高小于右最高時秆吵，左指針右移；反之右指針左移即可五慈∧杉牛可以將空間復雜度優(yōu)化至并減少時間復雜度的常數(shù)，只遍歷兩次即可泻拦。

思路二：單調(diào)棧（寫的不好 可以查題解）

采用單調(diào)遞減棧毙芜，每次出棧都要累加面積。相較于動態(tài)規(guī)劃中找左最高聪轿、右最高的做法爷肝，此做法的難點在于維護出棧時的雨水量增加值猾浦。特別需要注意的是陆错，我們此次計算雨水量按照每塊積水的寬來計算灯抛，即每根柱子右側(cè)第一個比其高的柱子都可以存儲[寬]為兩者下標差的雨水，高度為兩者較小值與彈元素的差

class Solution:
    def trap(self, height):
        ans, stack = 0, []
        for i in range(len(height)):
            if len(stack) == 0 or height[i] < height[stack[-1]]:
                stack.append(i)
                continue
            while height[i] > height[stack[-1]] and len(stack) != 0:
                cur = stack.pop()
                if len(stack) == 0:
                    break
                height_ = min(height[stack[-1]], height[i]) - height[cur]
                width = i - stack[-1] - 1
                ans += height_ * width
            stack.append(i)
        return ans

Leetcode 96

給你一個整數(shù) 音瓷，求恰由 個節(jié)點組成且節(jié)點值從 到 互不相同的 二叉搜索樹 有多少種对嚼？返回滿足題意的二叉搜索樹的種數(shù)。

思路

給定個節(jié)點绳慎，則選定根為排序后第大的節(jié)點后纵竖，共有整數(shù)個節(jié)點組成的二叉搜索樹的方案數(shù)，加上對應的節(jié)點數(shù)組成的二叉搜索樹的方案數(shù)杏愤。故表示個節(jié)點組成的二叉搜索樹的方案靡砌。狀態(tài)轉(zhuǎn)移方程：

(此即卡特蘭數(shù)的遞推公式)

class Solution:
    def numTrees(self, n):
        dp = [0 for _ in range(n+1)]
        dp[0] = 1
        for i in range(1, n+1):
            tmp = 0
            for j in range(0, i // 2):
                tmp += dp[j] * dp[i-j-1]
            tmp = tmp << 1
            if i & 1 == 1:
                tmp += dp[(i//2)] ** 2
            dp[i] = tmp
        return dp[-1]

分類：貪心

Leetcode 670 最大交換

給定一個非負整數(shù)，你至多可以交換一次數(shù)字中的任意兩位珊楼。返回你能得到的最大值通殃。

思路

分析所求需要滿足的條件：（依次滿足）左邊的數(shù)字大于右邊的數(shù)字；左邊的數(shù)字盡量靠左厕宗；右邊的數(shù)字盡量大画舌；右邊的數(shù)字盡量靠右。依據(jù)此準則進行貪心已慢。

貪心方法：從右向左掃描數(shù)組曲聂，記錄最大值索引（相等時不更新，保證下標最靠右）佑惠，掃描到小比當前記錄小的數(shù)字時朋腋，記錄交換位置。直至掃描到最左可得到結(jié)果膜楷。復雜度乍丈。

# https://leetcode.cn/problems/maximum-swap/
class Solution:
    def maximumSwap(self, num):
        nums = str(num)
        cur_max, cur_max_i, cur_min_ans_i, cur_max_ans_i = nums[-1], len(nums) - 1, None, None
        for i in range(len(nums)-2, -1, -1):
            if nums[i] > cur_max:
               cur_max_i, cur_max = i, nums[i]
            elif nums[i] < cur_max:
                cur_min_ans_i, cur_max_ans_i = i, cur_max_i
        return int(nums[0: cur_min_ans_i] + nums[cur_max_ans_i] +
                   nums[cur_min_ans_i + 1: cur_max_ans_i] + nums[cur_min_ans_i] +
                   nums[cur_max_ans_i+1: len(nums)]) if cur_min_ans_i is not None else num

Leetcode 45 跳躍游戲II

給你一個非負整數(shù)數(shù)組 ，你最初位于數(shù)組的第一個位置把将。數(shù)組中的每個元素代表你在該位置可以跳躍的最大長度轻专。你的目標是使用最少的跳躍次數(shù)到達數(shù)組的最后一個位置。假設(shè)你總是可以到達數(shù)組的最后一個位置察蹲。求最少的跳躍次數(shù)请垛。

思路

采用貪心算法，每次值可達的最遠距離洽议，循環(huán)迭代至可達最遠距離大于等于數(shù)組最大下標即可宗收。復雜度為。

# https://leetcode.cn/problems/jump-game-ii
class Solution:
    def jump(self, nums):
        if len(nums) == 1:
            return 0
        begin_i, end_i, step = 0, 0, 0
        while True:
            nxt_begin_i, cur_max = end_i + 1, begin_i + nums[begin_i]
            if cur_max >= len(nums) - 1:
                return step + 1
            for i in range(begin_i + 1, end_i + 1):
                nxt = i + nums[i]
                if nxt >= len(nums) - 1:
                    return step + 1
                cur_max = nxt if nxt > cur_max else cur_max
            begin_i = nxt_begin_i
            end_i = cur_max
            step += 1