fancycarp
fancycarp
全部文章
分类
题解(44)
归档
标签
去牛客网
登录
/
注册
fancycarp的博客
全部文章
(共44篇)
NC92 #最长公共子序列#
第一步,通过动态规划找到最长公共子序列长度,并构建dp数组:dp[i][j]:s1[i]和s2[j]为止的最长公共子序列的长度。dp[0][0] = s1[0] == s2[0]dp[i][0] = s1[i] == s2[0] ? 1 : dp[i - 1][0]dp[0][i] = s1[0] ...
动态规划
2021-05-11
0
490
题解 | #二分查找-I#
三种查找: 普通的二分class Solution { public: int binary_search(vector<int>& nums, int target) { int len = nums.size(); int left = 0, rig...
二分
2021-05-10
0
453
NC105 #二分查找-II#
二分搜索模板,然后下标前移。注意:写成left + (right - left) / 2而不是(left + right) / 2可以避免溢出。 class Solution { public: int binary_search(vector<int>& nums, i...
二分
2021-05-10
0
323
NC32 #求平方根#
二分查找。注意点: right直接设置为x/2因为当x>4时log2(x)<x/2。 注意int溢出!判断middle与x/middle的关系,而不是middle*middle与x的关系。class Solution { public: int sqrt(int x) { ...
二分
2021-05-10
0
383
NC12 #重建二叉树#
递归。注意下标!先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素。先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素。 class S...
递归
2021-05-09
0
342
NC54 #数组中相加和为0的三元组#
双指针。先排序,然后固定一个数,用双指针从两端遍历得到其他两个数。注意去重复。 class Solution { public: vector<vector<int> > threeSum(vector<int> &num) { v...
双指针
2021-05-09
0
397
NC17 #最长回文子串#
经典的动态规划。dp[i][j]代表着从i开始到j为止的子串是不是回文串, l代表回文串长度。状态转移方程:dp[i][j] = 1, l == 1dp[i][j] = A[i] == A[j], l == 2 or l == 3dp[i][j] = dp[i + 1][j - 1] &&a...
动态规划
2021-05-09
0
614
NC65 #斐波那契数列#
最简单的动态规划了 class Solution { public: int Fibonacci(int n) { if(n == 0 || n == 1) return n; int a = 0, b = 1, c; for(int i = ...
动态规划
2021-05-09
0
329
NC38 #螺旋矩阵#
leetcode上能过,但是在这里就过不了,不知道为啥段错误:您的程序发生段错误,可能是数组越界,堆栈溢出(比如,递归调用层数太多)等情况引起 class Solution { public: vector<int> spiralOrder(vector<vector<...
2021-05-09
0
386
NC103 #反转字符串#
直接反转就行。 class Solution { public: /** * 反转字符串 * @param str string字符串 * @return string字符串 */ string solve(string str) { ...
2021-05-09
0
272
首页
上一页
1
2
3
4
5
下一页
末页