- 博客(74)
- 收藏
- 关注
RSS订阅原创 music transciption 思路
例如Audeo: Audio Generation for a Silent Performance Video 这篇文章，通过视频输出midi 伴奏，然后再生成音乐。可以参考：Online Audio-Visual Source Association for Chamber Music Performances 这篇文章。第三阶段：真人伴奏，可以参考AR pianoist 的思路，直接正确的弹奏。1. 图像和声音联合检测可以帮助更好的进行声音的识别；第二阶段：通过动作生成伴奏音乐，AIGC 方向。
2023-03-16 10:20:23
59
原创 test1
## 1.1$$E_{o t e}\left(\mathfrak{L}_{a} | X, f\right)=\sum_{h} \sum_{\boldsymbol{x} \in \mathcal{X}-X} P(\boldsymbol{x}) \mathbb{I}(h(\boldsymbol{x}) \neq f(\boldsymbol{x})) P\left(h | X, \mathfrak{L}_{a}\right)$$[解析]：参见公式(1.2)## 1.2$$\begin{aligned}
2020-05-21 10:45:06
133
原创 109. 有序链表转换二叉搜索树
找中点然后采用分治法。classSolution{public:TreeNode*sortedListToBST(ListNode*head){if(head==NULL)returnNULL;if(head->next==NULL)returnnewTreeNode(head->val);...
2020-03-29 13:22:00
99
原创 105. 从前序与中序遍历序列构造二叉树
这道题按照下面的思路进行的。直接复制思路：**C++**。首先要知道一个结论，前序/后序+中序序列可以唯一确定一棵二叉树，所以自然而然可以用来建树。看一下前序和中序有什么特点，前序1,2,4,7,3,5,6,8，中序4,7,2,1,5,3,8,6；有如下特征：前序中左起第一位1肯定是根结点，我们可以据此找到中序中根结点的位置rootin； 中序中根结点左边就是左子树结点，右...
2020-03-29 11:37:06
117
原创 114. Flatten Binary Tree to Linked List
先序遍历，用一个stack 来存储节点。然后用一个dummyHead 来存储头结点。classSolution{public:voidflatten(TreeNode*root){if(root==NULL)return;TreeNode*dummyHead=newTreeNode(0);...
2020-03-29 09:50:57
82
原创 面试题 04.05. 合法二叉搜索树
这个就是一个分治法+寻找最小最大值。二叉搜索树根节点要比左子树的最大值大，比右子树的最小值小。classSolution{private:public:boolisValidBST(TreeNode*root){if(root==NULL)returntrue;TreeNode*max_left=root-&g...
2020-03-22 14:23:44
127
原创 300. 最长上升子序列
用dp 的方法，注意的是，F[I] 这个状态是以i作为结尾的最长的子序列。最后是取所有状态的最大值。classSolution{public:intlengthOfLIS(vector<int>&nums){intm(nums.size());if(!m)return0;vector...
2020-03-18 21:26:00
71
原创 63. 不同路径 II
经典的dp , 只是障碍物要单独处理下。classSolution{public:intuniquePathsWithObstacles(vector<vector<int>>&obstacleGrid){intm(obstacleGrid.size()),n(obstacleGrid[0].size());...
2020-03-17 23:59:28
99
原创 120. 三角形最小路径和
这个应该是一个典型的dp问题，用一个和输入相同的二维数组进行到达此节点时的最小路径。注意两个在每一行的边界条件。以及row<=2时的处理，否则容易overflow.classSolution{public:intminimumTotal(vector<vector<int>>&triangle){vecto...
2020-03-17 14:14:04
81
原创 138. 复制带随机指针的链表
就是用回溯法。用一个hash_map来存储访问过的节点。classSolution{private:unordered_map<Node*,Node*>all;public:Node*copyRandomList(Node*head){if(head==NULL)returnNULL;if...
2020-03-15 20:42:23
85
原创 142. Linked List Cycle II
两种解法，一种是通过hash将访问过的存储起来，当遇到环的时候，break; 另一种是快慢指针，floyd解法。下面是hash_map解法：classSolution{public:ListNode*detectCycle(ListNode*head){unordered_map<ListNode*,int>all;...
2020-03-15 17:58:44
71
原创 143. Reorder List
这个题有几种解法，一个是用vector 存储，O(n)空间复杂度，一个是直接在链表上操作，O(1)空间复杂度，但是操作复杂，涉及到链表中点查找，revserse 以及链表的merge，这样一个题就复习了三个解法。下面是O(1)的解法。classSolution{public:ListNode*reverseList(ListNode*head){...
2020-03-15 12:05:20
81
原创 86. 分隔链表
就是用两个head 一个是大，一个是小，然后分别制定，一定要将Big->next=NULL; 否则会形成循环列表，超出时间限制。classSolution{public:ListNode*partition(ListNode*head,intx){ListNode*DummySmall=newListNode(0);...
2020-03-14 22:37:31
68
原创 236. Lowest Common Ancestor of a Binary Tree
采用分治法来求解：如果找到任意一个node 则返回，这样就可以分为三种情况。两个node 在左右子树都找到，返回root.classSolution{public:TreeNode*lowestCommonAncestor(TreeNode*root,TreeNode*p,TreeNode*q){if(root==NULL...
2020-03-08 21:19:56
105
原创 450. 删除二叉搜索树中的节点
主要是分三种情况，叶子节点，有左子树，有右子树。当时有个bug就是在寻找mode的时候是root->left=deleteNode(root->left,key); 而不是deleteNode(root->left,key).classSolution{public:intprenodeSearch(TreeNode*root){...
2020-03-08 20:51:44
70
原创 124. 二叉树中的最大路径和
本质上是一个分治法。要记录每个节点的最大路径，同时记录maxPath. maxPath 可能包含左右路径。classSolution{private:intmaxPath=INT_MIN;public:intsinglePathMax(TreeNode*root){if(root==NULL)return0;...
2020-03-08 15:29:49
161
原创 148. 排序链表
nlog 的算法，是归并排序，同时是o1的空间复杂度，所以在merge的时候，直接在原链表上进行操作。在split的时候，由于包含head, 所以是走n-1步。classSolution{public:ListNode*merge(ListNode*l1,ListNode*l2){ListNodedummyhead(0);...
2020-02-27 00:24:26
68
原创 162. 寻找峰值
因为题目是log n的时间复杂度，所以很容易想到二分查找。主要是看区间选择的条件。注意left=mid+1 ； 不能是mid，否则死循环。classSolution{public:intfindPeakElement(vector<int>&nums){if(nums.size()==1)return0;...
2020-02-26 21:42:04
92
原创 56. 合并区间
这个主要是考察的排序，这里直接在原数组上操作，空间复杂度O1, 时间复杂度Onboolcmp(vector<int>&a,vector<int>&b){returna[0]<b[0];}classSolution{public:vector<vector<int>>m...
2020-02-16 22:57:47
107
原创 187. 重复的DNA序列
以10个字母的string作为一个查找的最小单位。要注意map[s.substr(i,10)]==2 是为了去重，同时以及边界条件。classSolution{public:vector<string>findRepeatedDnaSequences(strings){unordered_map<string,in...
2020-02-16 21:30:26
118
原创 179. 最大数
主要是注意cmp 需要定义在class外面，否则会出现非静态函数的问题。boolcmp(conststring&a,string&b){intmin_length=min(a.length(),b.length());for(inti=0;i<min_length;i++)...
2020-02-13 23:59:37
116
原创 200. 岛屿数量
参考标准解法，主要是用的DFS的解法。 这里有个坑就是在更新i,j的时候，要用tmpi。classSolution{private:vector<int>x{-1,1,0,0};vector<int>y{0,0,1,-1};public:intnumIslands(vector<vector<...
2020-02-09 21:45:16
83
原创 154. Find Minimum in Rotated Sorted Array II
和153的情况类似，主要是有相等重复的情况，需要将right-1classSolution{public:intfindMin(vector<int>&nums){if(nums.size()==0)return0;intleft(0),right(nums.size()-1),mid((ri...
2020-02-09 10:57:32
306
原创 173. 二叉搜索树迭代器
二叉搜索树迭代器 考了几个知识点：1.二叉搜索树迭代器 2. 迭代器。难点就是O1的时间复杂度以及Oh 的空间复杂度。/***Definitionforabinarytreenode.*structTreeNode{*intval;*TreeNode*left;*TreeNode*right;*...
2020-02-08 21:39:08
61
原创 1046. Last Stone Weight
这里就是用大顶堆。priority_queue堆的定义：https://blog.csdn.net/lym940928/article/details/89635690//构造一个空的优先队列,此优先队列是一个小顶堆 priority_queue<int,vector<int>,greater<int> > small_heap;时间复杂度时o(n...
2020-02-06 22:28:49
64
原创 199. 二叉树的右视图
这道题非常的好。可以用depth-first search以及breadth-first两种解法。参考了https://leetcode-cn.com/problems/binary-tree-right-side-view/solution/liang-chong-jie-ti-fang-fa-di-gui-ji-bai-100he-fei/并且depth-first search 不...
2020-02-03 16:06:54
88
原创 24. 两两交换链表中的节点
主要是记录中间状态， before以及after两个指针。另外注意终止条件：while(before->next!=NULL&&before->next->next!=NULL){ 避免报错。另外还有别人总结的递归的骚解法。// 我的解法classSolution{public:ListNode*swapPairs(List...
2020-01-05 19:06:50
45
原创 23. 合并K个排序链表
这个就是分治算法的一个实例。K个合并，先是两两合并，然后最后merge在一起。这里有两个trick,一个是用合并了的lsit替换合并的第一个.另外就是再size是奇数的处理，画一个实例图可解。c++ 遗忘知识点：除法默认是向下取整，3/2 =1 。分治算法: 分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原...
2020-01-05 17:56:13
66
原创 8. 四数之和
基本和3sum 差不多，都是双指针，只不过多了一层循环，所以算法时间复杂度是o(n3), 空间复杂度是O(1).vector<vector<int>>fourSum(vector<int>&nums,inttarget){if(nums.size()<4)return{};vector&...
2020-01-01 13:47:40
71
原创 16. 最接近的三数之和
这个题目的解法和15. 三数之和解法的基本框架是类似的。先sort ，再用双指针，复杂度是o(logn) + O(n2) = o(n2)。 主要区别是不需要判断重合，平且用一个int 来判断和target 的接近程度。classSolution{public:intthreeSumClosest(vector<int>&nums,inttarg...
2019-12-29 22:55:39
46
原创 42. 接雨水
用的是DP的解法，这道题是hard级别的，代码不多，难的应该是idea. 当前bin能接的水是和其当前的高度和min(左最大，右最大)左最大和右最大的解法明显就是一个DP问题。空间复杂度O(n), 时间复杂度O(3n)。classSolution{public:inttrap(vector<int>&height){if...
2019-12-22 21:03:43
72
原创 11. 盛最多水的容器
双指针，分别指向两端，每次移动的是比较短的那段，关于这个的说法，leetcode有人做了证明，我这里把这种算法理解为贪心法。每次都是做的看似最大的选择，只是猜测。intmaxArea(vector<int>&height){intstart(0),end(height.size()-1),max_a(0);intar...
2019-12-22 18:13:28
53
原创 5. 最长回文子串
主要的知识点就是DP问题。 有些基础知识点还顺便补了一下，二维数组的初始化。mark一下：intdp[s.size()][s.size()]; 这种方式需要自己初始化为0;vector<vector<int>>dp(s.size(),vector<int>(s.size())); 可以初始化为0; vector 的操作具体可见：https://blog...
2019-12-22 12:12:23
56
原创 3. 无重复字符的最长子串
主要的思路是双指针+ hash_map。classSolution{public:intlengthOfLongestSubstring(strings){if(s.size()<=1)returns.size();map<char,int>k;intmax_length...
2019-12-21 21:35:26
49
原创 108. 将有序数组转换为二叉搜索树
因为是有序数组，取中间位置的值为树根。将数组分成两半。 对左半递归构建左子树。对右半递归构建右子树。就是一个二分法。classSolution{public:TreeNode*sortedArrayToBST(vector<int>&nums){returnToBST(nums,0,nums.size()-1...
2019-12-09 17:33:31
83
原创 110. 平衡二叉树
就是深度优先收索。DFS 判断当前root左子树和右子数的高度，然后递归判断左边右边是否banlanced.classSolution{public:intheight(TreeNode*root){if(!root)return0;return(1+max(height(root->left),height(ro...
2019-11-28 20:21:13
45
原创 112. Path Sum
其实就是一个二叉树的递归过程。只需要判断一下减去的数值到最后叶子节点的时候是否是等于目标值。classSolution{public:boolhasPathSum(TreeNode*root,intsum){if(root==NULL)returnfalse;if(root->left==NULL&...
2019-11-24 22:05:20
52
原创 118. Pascal's Triangle
本质上是一个DP问题，主要是注意边界条件以及状态转移方程。另外要注意的是二维数组必须要进行初始化。k[i].resize(i+1,1); 否则会报错。时间太长，忘了。在下面的blog里面找到了答案。https://blog.csdn.net/m0_38088298/article/details/79249044classSolution{public:vector...
2019-11-24 20:23:12
68
原创 122. Best Time to Buy and Sell Stock II
典型的贪心问题。classSolution{public:intmaxProfit(vector<int>&prices){if(prices.size()<=1)return0;intmax=0;for(size_ti=0;i<=prices.siz...
2019-11-17 21:26:40
43
原创 121. Best Time to Buy and Sell Stock
典型的DP问题，第n个状态是max(第n-1个状态,第n个元素-min(n-1))。public:intmaxProfit(vector<int>&prices){if(prices.size()<=1)return0;intmin=prices[0],max=0,m=0;...
2019-11-17 20:40:53
62
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人