math博客收藏
记录一些数学知识,方便以后忘记时回来
SVD:主要用途,解欠定、超定方程
OJ刷题总结 8
OJ刷题总结8——回溯——子集型回溯
OJ刷题总结 7
OJ刷题总结7——0-1背包 完全背包1. 0-1背包有 $n$ 个物品 第 $i$ 个物品的体积为 $w[i]$ ,价值为 $v[i]$每个物品至多选一个,求体积和不超过 capacity 时的最大价值和
回溯三问:
当前操作?枚举第i个物品选或不选
不选,剩余容量不变
选,剩余容量减少w[i]
子问题?在剩余容量为c时,从前i个物品中得到的最大价值和
下一个子问题?分类讨论:
不选:在剩余容量为c时,从前i-1个物品中得到的最大价值和
选:在剩余容量为c-w[i]时,从前i-1个物品中得到的最大价值和
dfs(i, c) = max(dfs(i - 1, c), dfs(i - 1, c - w[i]) + v[i])
Code:123456789101112def zero_one_bag(capacity, w, v): n = len(w) @cache def dfs(i, c): if i < 0: return 0 if c < w[i]: return d ...
OJ刷题总结 6
OJ刷题总结6——从记忆化搜索到递推198你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。
对于某一个i,要么拿,要么不拿
拿:dp[i] = dp[i - 2] + nums[i]
不拿:dp[i] = dp[i - 1]
dp[i + 2] = max(dp[i + 1], dp[i] + nums[i])
1234567class Solution: def rob(self, nums: List[int]) -> int: n = len(nums) dp = [0] * (n + 2) for i, x in enumerate(nums): dp[i + 2] = max(dp[i + 1], dp[i] + nums[i]) retu ...
OJ刷题总结 5
OJ刷题总结5——二叉树递归100给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
两颗树相同,意味着当前的两个节点相同,并且当前两个的左右子树相同。
那么结束条件呢?当递归到空节点时,判断两者是否相同即可。
1234567class Solution {public: bool isSameTree(TreeNode* p, TreeNode* q) { if (!q || !p) return p == q; return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right); }};
101给你一个二叉树的根节点 root , 检查它是否轴对称。
就是检查当前根节点的左右两颗子树,是否对称。
12345678910111213c ...
OJ刷题总结 4
OJ刷题总结4——二分许久尚未更新,我没摆烂,准备保研这段时间着实是有点小忙。。复现论文/oj/408。。
34给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target,返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
两次二分:
找target的开始位置,也就是说,左边部分=target,返回r即可
找target的结束为止,也就是说,左边部分<=target,右边部分>target,返回l即可
123456789101112131415161718192021222324class Solution {public: vector<int> searchRange(vector<int>& nums, int target) { if (nums.empty()) return {-1, -1}; int l ...
OJ刷题总结 3
b站链接:https://www.bilibili.com/video/BV1hd4y1r7Gq/?spm_id_from=333.999.0.0&vd_source=738644d63e97553d6e3dc1cd66a642d6
OJ刷题总结3
本期视频介绍了三类典型的滑动窗口题目:最短/最长/方案数,代表题目分别为209, 3, 713
Leetcode 209给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续 子数组
$[nums_l, nums_l+1, …, nums_r-1, nums_r]$ ,并返回其长度。如果不存在符合条件的子数组,返回 0 。
看到这题时,最的朴素的做法就是2层for循环,遍历去找答案。时间复杂度为$O(n^2)$.
但是,题目说,数组全部是由正整数组成的。这个性质很重要。这意味着什么呢??
我们先看一个例子,
target = 7, nums = [2, 3, 1, 2, 4, 3]
我们先用朴素的2层for循环看这个例子。固定右端点,移动左端点,寻找当前最 ...
nerf_3dgs博客收藏
记录一些nerf,3dgs的前置知识及讲解的博客和视频
知乎收藏夹:
https://www.zhihu.com/collection/949437601
nerf 解读:
原理:https://zhuanlan.zhihu.com/p/481275794
代码:https://zhuanlan.zhihu.com/p/482154458
相机参数与坐标系变换:https://zhuanlan.zhihu.com/p/593204605/
球协函数:
http://www.yindaheng98.top/%E5%9B%BE%E5%BD%A2%E5%AD%A6/%E7%90%83%E8%B0%90%E7%B3%BB%E6%95%B0.html#%E5%9F%BA%E5%87%BD%E6%95%B0
OJ刷题总结 2
OJ刷题总结 2来源于:https://www.bilibili.com/video/BV1Qg411q7ia/?spm_id_from=333.999.0.0&vd_source=738644d63e97553d6e3dc1cd66a642d6
上次更新还是上周。。不是摆烂了,是这周实在是太忙碌了。。。最近科研不是很顺畅,复现个3dgs,环境配不好。。很奇怪。。。稍微看了点代码理解了一下。。。工作到晚上9点。。剩下时间,在图书馆学习下算法,写个总结。
Leetcode 11盛最多水的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明:你不能倾斜容器。
借鉴一下leetcode的例图:
假设说,我们有两个指针,一左一右。分别指向红色的两个柱子。
这个时候,我们选中红色柱子中的一个柱子,和矮的的柱子构成容器(也就是右边的):
比如说第4个(从1数起),其高度为2。显然,它的高度 ...
图论模版
Leetcode 743 网络延迟时间遇到一个特别好的题目,以及特别的好的题解,借鉴一下,做个笔记
有 n 个网络节点,标记为 1 到 n。
给你一个列表 times,表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi),其中 ui 是源节点,vi 是目标节点, wi 是一个信号从源节点传递到目标节点的时间。
现在,从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号?如果不能使所有节点收到信号,返回 -1 。
题解:https://leetcode.cn/problems/network-delay-time/solutions/887186/wang-luo-yan-chi-shi-jian-dan-yuan-zui-d-m1m3/
dfs模版:
123456789101112void dfs(参数) { if (终止条件) { 存放结果; return; } for (选择:本节点所连接的其他节点) { 处理节点; dfs(图, ...