不经历怎么能成长

题解

/ 注册

全部文章 / 题解（共128篇）

题解 | #接雨水问题#（边界最低高度决定容器上限，由两边向中间查找）

/* 申明两个边界指针，容量由高度差决定，且边界的低高度决定容器大致容量，由两边向中间扫描，且低高度边界指针优先。边界指针肯定越高越好，内部高度越低越好。每次从左右边界最大值较小的一方开始向中间移动。左右指针只有按最小值移动，每次确定累加容量。拥有较小的边界最值指针移动，如果移动后的高度下于边...

2021-07-05

0 385

题解 | #设计getMin功能的栈#（一个额外栈保存每次添加数据是否影响最小值，判断最小值是否当前出栈元素）

一个栈存输入的数据。一个栈存每次输入后，该阶段的最小值。以空间换时间，每次添加新元素，保存此时最小值元素。 class Solution { public: stack<int> s,min_s; vector<int> getMinStack(vector&...

2021-06-16

0 471

题解 | #求平方根#（牛顿迭代法，泰勒公式推导）

牛顿迭代法：求f(x) = 0 中解 x 对f(x)泰勒展开，当x与接近时，可以用近似 x。当x与接近时,移项即对于任意, 令不断对迭代，会逐渐靠近x 即为解。求代入公式即 class Solution { public: int mysqrt(int x) { ...

2021-06-16

2 883

题解 | #在旋转过的有序数组中寻找目标值#（循环数组二分查找，分段）

与中间值比较，分前半段有序和后半段有序分别判断。比有序的二分查找多一些判定条件。1、要么前半段有序，要么后半段有序。2、当前半段有序时：即循环数组中间值比循环数组最左边值大则 nums[left] <= nums[mid] 当target 比中间值小，比最左值（前半段最小值）大时，...

2021-05-28

14 1146

题解 | #最长递增子序列#（一个数组记录查找最长上升子序列的过程，后面较小值可能覆盖结果，需要记录值并回溯）

转载大佬&自己增加解释 class Solution { public: vector<int> LIS(vector<int>& arr) { vector<int> res; // 贪心下，用res数组存储最长上...

2021-05-27

1 616

题解 | #螺旋矩阵#（设置四个方向的指针，每次向内循环，边界判断只有一行或一列的情况）

class Solution { public: vector<int> spiralOrder(vector<vector<int> > &matrix) { vector<int> ans; if(m...

2021-05-15

1 560

题解 | #在二叉树中找到两个节点的最近公共祖先#（递归左右子树，寻找并返回找到的节点）

应该说明查找的两个节点不能重复吧。很容易引起歧义。 class Solution { public: int lowestCommonAncestor(TreeNode* root, int o1, int o2) { return dfs(root, o1, o2)->...

2021-05-11

2 613

题解 | #二分查找-II#(查找第一个元素大于目标值的下标)

class Solution { public: int search(vector<int>& nums, int target) { int low = 0, high = nums.size(); while(low < hig...

2021-05-11

0 505

题解 | #最长公共子串#（记录一下最大长度时字符串的下标）

class Solution { public: /** dp[i][j]:下标i，j为结尾两字符串公共子串最大长度,且默认为0。更新dp值只能从dp[i-1][j-1]中得到。当str1[i] == str2[j] dp[i][j] = dp[i-1][j-1] + 1 dp初始化...

2021-04-24

2 542

题解 | #大数加法#（填0将字符串变换到同一长度）

class Solution { public: string solve(string s, string t) { int l = s.length(); int r = t.length(); if(!l) return t; ...

2021-04-24

0 495