算法其他笔记
分类：动态规划
Leetcode 1137 计算泰波那契数列
泰波那契序列定义如下:
, 且在
的条件下
，给你整数
，请返回第
个泰波那契数
的值。
思路一：dp(滚动数组)
重点：滚动数组思想
开大小为3的数组，依次迭代加和；递归则因为要计算的过多而时间复杂度过高(，最后也许会在
的数量级),总复杂度
# 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]
思路二：矩阵快速幂
寻找一个矩阵，乘以的列向量，可以得到
，则该矩阵多次幂后乘
，即可得到想要的结果
注意做时，每次
，为
则结果需乘此次快速幂结果，然后徐
，再让矩阵自乘一次即可。总复杂度
# 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 接雨水
给定 个非负整数表示每个宽度为
的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
思路一：动态规划
动态规划的核心思路：对于每一列，其能盛装的雨水量是左边最高、右边最高的柱子值的较小值。
故我们遍历三次，分别求出每一格对应左、右最高柱的高度、计算每一格对应列的盛装雨水量。时间复杂度，空间复杂度
。
# 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
空间复杂度优化：由于左最高单增，右最高单减，故可以利用双指针，从左、右分别向另一侧扫描，而左最高小于右最高时，左指针右移；反之右指针左移即可。可以将空间复杂度优化至并减少时间复杂度的常数，只遍历两次即可。
思路二：单调栈（写的不好 可以查题解）
采用单调递减栈，每次出栈都要累加面积。相较于动态规划中找左最高、右最高的做法，此做法的难点在于维护出栈时的雨水量增加值。特别需要注意的是，我们此次计算雨水量按照每块积水的宽来计算，即每根柱子右侧第一个比其高的柱子都可以存储[宽]为两者下标差的雨水，高度为两者较小值与弹元素的差
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
给你一个整数 ，求恰由
个节点组成且节点值从
到
互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
思路
给定个节点，则选定根为排序后第
大的节点后，共有整数
个节点组成的二叉搜索树的方案数，加上
对应的节点数组成的二叉搜索树的方案数。故
表示
个节点组成的二叉搜索树的方案。状态转移方程：
(此即卡特兰数的递推公式)
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 最大交换
给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。
思路
分析所求需要满足的条件：（依次满足）左边的数字大于右边的数字；左边的数字尽量靠左；右边的数字尽量大；右边的数字尽量靠右。依据此准则进行贪心。
贪心方法：从右向左扫描数组，记录最大值索引（相等时不更新，保证下标最靠右），扫描到小比当前记录小的数字时，记录交换位置。直至扫描到最左可得到结果。复杂度。
# 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
给你一个非负整数数组 ，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。假设你总是可以到达数组的最后一个位置。求最少的跳跃次数。
思路
采用贪心算法，每次值可达的最远距离，循环迭代至可达最远距离大于等于数组最大下标即可。复杂度为
。
# 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
