关于LeetCode刷题及题目列表归纳
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了关于LeetCode刷题及题目列表归纳，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含19338字，纯文字阅读大概需要28分钟。
内容图文
leetcode题目简评
言简意赅，持续更新，利于速览复习。有导航、有代码、有细节、有引申。
已记录题目编号：1, 3, 5, 10, 15, 20, 21, 26, 53, 54, 56, 65, 72, 79, 84, 88, 101, 102, 103, 104, 105, 121, 122, 123, 125, 136, 137, 138, 145, 146, 153, 154, 155, 161, 167, 169, 170, 172, 190, 191, 198, 203, 206, 215, 217, 219, 220, 226, 229, 240, 295, 297, 343,426, 653, 946, 974, 1209
0000.资料
0001.two-sum 两数之和
- one-pass hash table
0003.longest-substring-without-repeating-characters 无重复字符的最长子串
- 滑窗：O(n)复杂度，可以用字典储存i跳转的位置，把计算量从2n降到n，类似KMP的思想。
0005.longest-palindromic-substring 最长回文子串
- 法1:中心扩散
- 法2:动态规划
- 法3:Manacher算法
0010.regular-expression-matching 正则表达式匹配
- 《剑指offer》第19题
- 和0072.Edit-Space类似
0015.3sum 三数之和
- 方法一：先排序，在排序的基础上，虽然也是O(n^2)复杂度，但可以利用双指针尽量提高效率
- 方法二：hash，先预处理排序，并把重复元素合并
0020.valid-parentheses 有效的括号
- 栈的使用；利用map定义括号和反括号的映射关系
0021.merge-two-sorted-lists 合并两个有序链表
- 《剑指offer》第25题，经典题，引入一个头节点
- 代码模版：
ListNode*head=new ListNode(0);
ListNode*p=head;
...
return head->next;
0026.remove-duplicates-from-sorted-array 删除排序数组中的重复项
- O(n)的解法，注意原地操作
0053.maximum-sum-subarray 最大子序和
- less is more，O(n)的简洁解法，也可用分治
int maxSubArray(vector<int>& nums) {
if(nums.size()==0)return 0;
int i=1;
int maxsum=nums[0];
int sum=maxsum;
while(i<=nums.size()-1){
if(sum<0){
sum=nums[i];
}
else
sum+=nums[i];
if(sum>=maxsum)
{
maxsum=sum;
}
i++;
}
return maxsum;
}
0054.spiral-matrix 螺旋矩阵
- 《剑指offer》第29题
- 最简洁的写法
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int>ret;
int m=matrix.size();
if(!m)return ret;
int n=matrix[0].size();
int b=0,t=m-1,l=0,r=n-1;
while(1){
for(int j=l;j<=r;j++)ret.push_back(matrix[b][j]);
if(++b>t)break;
for(int i=b;i<=t;i++)ret.push_back(matrix[i][r]);
if(--r<l)break;
for(int j=r;j>=l;j--)ret.push_back(matrix[t][j]);
if(--t<b)break;
for(int i=t;i>=b;i--)ret.push_back(matrix[i][l]);
if(++l>r)break;
}
return ret;
}
0056.merge-intervals 合并区间
- 先sort再遍历
- 复习sort的cmp函数定义（这题不需要cmp函数）
static bool cmp1(vector<int> &a, vector<int> &b){
return a[0] < b[0] || (a[0] == b[0] && a[1] < b[1]);
}
0065.valid-number 有效数字
- 《剑指offer》第20题，书上的代码结构很简洁，值得学习
int pointer;
bool isNumber(string s) {
if(s=="")return -1;
scanSpace(s);
bool numeric=scanInteger(s);
if(s[pointer]=='.'){
++pointer;
numeric=scanUnsignedInteger(s)||numeric;
//用||因为整数、小数部分有一即可
}
if(s[pointer]=='e'||s[pointer]=='E'){
++pointer;
numeric=numeric&&scanInteger(s);
}
scanSpace(s);
return numeric&&s[pointer]=='\0';
}
- 也可以用有限状态机来做
0072.edit-distance 编辑距离
- 很漂亮的动态规划
KaTeX parse error: Undefined control sequence: \notag at position 108: …i]\\\end{cases}\?n?o?t?a?g? ?
0079.word-search 单词搜索
- 经典回溯法
0084.largest-rectangle-in-histogram 柱状图中最大的矩形
- 单调栈，很好的文章，但有小错，纠正代码如下：
int largestRectangleArea(vector<int> &heights)
{
stack<int> st;
int top = 0;
int maxarea = 0;
heights.insert(heights.begin(), 0);
heights.push_back(0); //左右插0，利于边界条件
for (int i = 0; i < heights.size(); i++)
{
top = i;
while (!st.empty() && heights[i] < heights[st.top()])
{
top = st.top();
st.pop();
maxarea = max(maxarea, heights[top] * (i-1 - st.top()));
}//求出栈处往左右延伸的最大矩形面积
st.push(i);
}
return maxarea;
}
- 单调栈模版
stack<int> st;
//此处一般需要给数组最后添加结束标志符
for (遍历这个数组)
{
while (栈不为空 && 栈顶元素小于当前元素)
{
栈顶元素出栈;
更新结果;
}
当前数据入栈;
}
0088.merge-sorted-array 合并两个有序数组
- 注意原地操作
0101.symmetric-tree 对称二叉树
bool isSymmetric(TreeNode* root) {
if(!root)return 1;
else return isSymmetric1(root->left,root->right);
}
bool isSymmetric1(TreeNode* a,TreeNode* b) {
if(!(a||b))return 1;
else if(!(a&&b))return 0;
else return a->val==b->val&&isSymmetric1(a->left,b->right)&&isSymmetric1(a->right,b->left);
}
0102.binary-tree-level-order-traversal 二叉树的层序遍历 (medium)
- 《剑指offer》第32-II题
- 队列，设变量curNum和nextNum分别保存本层和下层的数的个数
- 引申：关于vector的内存释放问题
-
方法一：clear
-
方法二：
vector<int>().swap(nums); -
方法三：利用代码块和临时变量
{ vector<int> tmp = curLevel; curLevel.swap(tmp); } -
clear虽然不会deallocate释放空间，但是会destroy执行析构函数，所以可以用同一个空间构造节点，如果swap了就要重新分配空间再构造节点。由于本题是对同一个vector的重复利用，可以直接用clear();，空间复杂度是单层最大节点数。
-
如果要每次都释放空间，也可以用
res.emplace_back(std::move(curLevel))，涉及emplace_back, std::move, 左值、右值引用, 这是一篇有关类定义的总结
-
0103.binary-tree-zigzag-level-order-traversal 二叉树的锯齿形层次遍历
- 《剑指offer》第32-III题
- 在0102的基础上保存层数的奇偶性
0104.maximum-depth-of-binary-tree 二叉树的最大深度
- 方法一：递归
- 方法二：BFS，queue
- 方法三：DFS，stack，利用c++的pair，或者python的tuple
0105. construct-binary-tree-from-preorder-and-inorder-traversal 从前序与中序遍历序列构造二叉树
- 《剑指offer》第7题
- 找到中间节点，递归
0121. best-time-to-buy-and-sell-stock 买卖股票的最佳时机
- O(n)遍历，记录之前的数组最小值
0122. best-time-to-buy-and-sell-stock-ii 买卖股票的最佳时机 II
0123. best-time-to-buy-and-sell-stock-iii 买卖股票的最佳时机 III
- 超巧妙的方法，本质上是贪心的思想，先记录maxp的位置，一定会取到股票的最大最小值high、low处，再做处理
class Solution:
def maxProfit(self, prices: List[int]) -> int:
def max_p(ps):
if not ps or len(ps) == 1:
return 0, 0, 0
very_low = 0
low = 0
high = 0
profit = 0
for i, p in enumerate(ps):
if p < ps[low]:
low = i
elif p - ps[low] > profit:
high = i
very_low = low
profit = p - ps[low]
return very_low, high, profit
low, high, profit = max_p(prices)
_, _, profit_right = max_p(prices[0:low])
_, _, profit_left = max_p(prices[high+1:])
_, _, profit_middle = max_p(prices[low:high+1][::-1])
return profit + max(profit_left, profit_middle, profit_right)
0125.valid-palindrome 验证回文串
def isPalindrome(self, s: str) -> bool:
s = ''.join(i for i in s if i.isalnum()).lower()
return s == s[::-1]
0136.single-number 只出现一次的数字
- 位运算，xor性质
0137.single-number-II 只出现一次的数字 II
- 非常巧妙的方法，多设一个数记录状态，位运算与有限状态机的结合，本质上，位运算的意义在于将n位信息转化为O(1)
def singleNumber(self, nums: List[int]) -> int:
seen_once = seen_twice = 0
for num in nums:
# first appearance:
# add num to seen_once, don't add to seen_twice because of presence in seen_once
# second appearance:
# remove num from seen_once, add num to seen_twice
# third appearance:
# don't add to seen_once because of presence in seen_twice, remove num from seen_twice
seen_once = ~seen_twice & (seen_once ^ num)
seen_twice = ~seen_once & (seen_twice ^ num)
return seen_once
0138.copy-list-with-random-pointer 复制带随机指针的链表
- 《剑指offer》第35题
- 思路值得学习，在原链表的主线上复制节点，进行删改操作。
0145.binary-tree-postorder-traversal 二叉树的后序遍历
- 方法一：教科书，先一路向左，用tag记录节点的右子树是否遍历
struct WTreeNode{TreeNode* TNode;bool tag;};
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ret;
stack<WTreeNode*>s;
TreeNode* p=root;
if(root==NULL) return ret;
WTreeNode* l;
while(!s.empty()||p){
if (p!=NULL){ //左子树不断入栈
l=new WTreeNode;
l->TNode=p;l->tag=0;
s.push(l);
p=p->left;
}
else{
l=s.top();
s.pop();
if(l->tag==1){
ret.push_back(l->TNode->val);
}
else{ //右子树没输出
l->tag=1;
s.push(l);
p=l->TNode->right;
}
}
}
return ret;
}
- 引申：二叉树非递归遍历的模版
while(!s.empty()||p){
if (p!=NULL){
}
else{
}
}
- 方法二：后序遍历是左右根，倒过来是根右左，相当于左右遍历顺序相反的DFS，用栈即可，得到结果再reverse
vector<int> postorderTraversal1(TreeNode* root) {
vector<int> ret;
stack<TreeNode*>s;
vector<int>invert;
s.push(root);
while(!s.empty()){
TreeNode *p=s.top();s.pop();
if(p!=NULL){
invert.push_back(p->val);
s.push(p->left);
s.push(p->right);
}
}
reverse(invert.begin(),invert.end());
return invert;
}
0146.lru-cache LRU缓存机制
- 双向链表+Map，自己实现双向链表可以高效实现move to head操作，也可以用STL的list
0153.find-minimum-in-rotated-sorted-array 寻找旋转排序数组中的最小值
- 二分法，注意相等的情况
0154.find-minimum-in-rotated-sorted-array-ii 寻找旋转排序数组中的最小值 II
- 《剑指offer》第11题
- 如果有重复数字，则难以判断mid是在左边还是右边，r-=1是解决这一问题的关键代码
int findMin(vector<int>& numbers) {
//if(numbers.size()==0)return -1;
int l=0,r=numbers.size()-1;
int mid;
while(l<r){
if(r-l==1)
return (numbers[l]<=numbers[r])?numbers[l]:numbers[r];
mid=(l+r)/2;
if(numbers[mid]>numbers[r]) l=mid;
else if(numbers[mid]<numbers[l])r=mid;
else
r-=1;
//return minArraySeq(numbers,l,r);
}
return 1;
}
0155.min-stack 最小栈
- 《剑指offer》第30题
- 用另一个栈记录min的变化值
0161.one-edit-distance 相隔为 1 的编辑距离
- 遍历较短的数字，直到遇到第一个和长数组对应位置不等的元素，再做判断处理
0167.two-sum-ii-input-array-is-sorted 两数之和 II - 输入有序数组
- 先二分查找到中间，再往两边扩散，这样当N很大时时间复杂度近似 O ( l o g 2 N ) O(log_{2}N) O(log2?N)
0169. majority-element 多数元素
-
方法一：hashmap
-
方法二：随机算法，先取再验证
-
方法三：Boyer-Moore Voting Algorithm：核心是利用这个数据的前缀特性，用军队打仗理解；每个非众数都会和一个数配对
int majorityElement(vector<int> nums) {
int solider = nums[0];
int count=0;
for(int i=0;i<nums.length();i++){
if(nums[i]==solider){ //队伍增加了同胞
count++;
}
else{ //没人去抵抗了
if(count==0){
solider=nums[i];
count++;
}else {
count--; //抓住一个人
}
}
}
return solider;
}
0170.two-sum-iii-data-structure-design 两数之和 III - 数据结构设计
与两数之和联系的数据结构
- 有序数组：因此可以用sort排序，或者用multiset维持数据结构的有序性
- Hash表
0172.factorial-trailing-zeroes 阶乘后的零
- n / 5 + n / 5 2 + n / 5 3 + … n/5+n/5^2+n/5^3+… n/5+n/52+n/53+… 递归即可
0190.reverse-bits 颠倒二进制位
- 法一：位运算
uint32_t reverseBits(uint32_t n) { //注意定义uint32_t，如果是int要小心算术移位
unsigned int t = 0;
int i = 0;
while (n >= 1)
{
t = (t << 1) | (n & 1);
i++;
n = n >> 1;
}
if (i == 0) //细节：左移不要越界
return t;
return t << (32 - i);
}
- 法二：按字节操作
def reverseByte(byte):
return (byte * 0x0202020202 & 0x010884422010) % 1023
0191.number-of-1-bits 位1的个数
- 《剑指offer》第15题
- n=n&(n-1);
- 易错点：
return n&1+hammingWeight(n>>=1);- 位运算优先级很低，n&1应该打括号
- 复习运算符优先级
- 基本的优先级需要记住：
- 指针最优，单目运算优于双目运算，如正负号。
- 先算术运算，后移位运算，最后位运算。1 << 3 + 2 & 7等价于 (1 << (3 + 2))&7，逻辑运算最后结合。
0198.house-robber 打家劫舍
- 简单DP
0203.remove-linked-list-elements 移除链表元素
- 《剑指offer》第18题
- 直接遍历，也可以用sentinel node简化操作（在LRU cache也有应用）
class Solution {
public:
ListNode* deleteNode(ListNode* head, int val) {
if(head==NULL)return NULL;
if(head->val==val)return head->next;
ListNode *p=head;
while(p->next){
if(p->next->val==val){
p->next=p->next->next;
break;
}
p=p->next;
}
return head;
}
};
0206.reverse-linked-list 反转链表
ListNode* reverseList(ListNode* head) {
if(!head||!head->next) return head;
ListNode *p=head,*q=head->next;
p->next=NULL;
ListNode* temp;
while(q!=NULL){
temp=q->next;
q->next=p;
p=q;
q=temp;
}
return p;
}
0215.kth-largest-element-in-an-array 数组中的第K个最大元素
-
方法1: 快排
-
方法2: 利用小顶堆，保证size不大于k; C++中用priority_queue, 配合unordered_map
-
方法3: 快排变体，quick select
-
引申：堆的实现
#define ElemType pair<int,int>
class CMaxHeap { //小顶堆
private:
ElemType *heap;
int heapSize, MaxHeapSize;
public:
CMaxHeap(int size) {
heapSize = 0;
MaxHeapSize = size;
heap = new ElemType[size + 1];
}
~CMaxHeap() { delete[] heap; }
void ClearHeap() { heapSize = 0; }
bool IsEmpty() { return heapSize == 0; }
bool IsFull() { return heapSize == MaxHeapSize; }
int getLength() { return heapSize; }
ElemType top() { return heap[0]; }
void push(ElemType e);
ElemType pop(); //去堆顶元素
void FixUp(int k);
void FixDown(int k);
};
void CMaxHeap::FixDown(int k) {
int i;
i = 2 * k + 1;
while (i < heapSize) {
if (i < heapSize - 1 && heap[i] > heap[i + 1])
i++; //取孩子结点中较小者
if (heap[k] < heap[i])
break;
swap(heap[k], heap[i]);
k = i;
i = 2 * k + 1;
}
}
void CMaxHeap::FixUp(int k) {
int i;
i = (k - 1) / 2;
while (k > 0 && heap[i] > heap[k]) {
swap(heap[k], heap[i]);
k = i;
i = (k - 1) / 2;
}
}
void CMaxHeap::push(ElemType e) {
heap[heapSize] = e;
heapSize++;
FixUp(heapSize - 1);
}
ElemType CMaxHeap::pop() { //去掉堆顶
swap(heap[0], heap[heapSize - 1]);
heapSize--;
FixDown(0);
return heap[heapSize];
}
void heap_sort(ElemType *a, int l, int r) {//
int N = r - l;
ElemType *p = a + l;
for (int k = (N - 1) / 2; k >= 0; k--)
FixDown(p, k, N);
while (N > 0) {
exch(p, p + N);
N--;
FixDown(p, 0, N);
}
}
- 引申：快排代码
template<class T>
void quick_sort(T*a, int l, int r) {//递归实现
if (r <= l)return;
int i = partition(a, l, r);//划分操作
quick_sort(a, l, i - 1);
quick_sort(a, i + 1, r);
}
template<class T>
int partition(T*a, int l, int r) {//思想，从两边向中间扫描
int i = l - 1,j = r;
T e = a[r];//最右端元素为划分元素
while (1) {
while (a[++i] < e);
while (e < a[--j])if (j == left)break;
if (i >= j)break;
exch(a + i, a + j);
}
exch(a + i, a + right);
return i;
}
//改进：中间元素法和小序列处理
template<class T>
void quick_sort(T*a, int l, int r) {//递归实现
if (r-l< 5)return;
exch(a[(l + r) / 2], a[r - 1]);
compExch(a[l], a[r - 1]);//取三个值的中间值
compExch(a[l], a[r]);
compExch(a[r], a[r - 1]);
int i = partition(a, l, r);//划分操作
quick_sort(a, l, i - 1);
quick_sort(a, i + 1, r);
}
0217.contains-duplicate 存在重复元素
- 排序或者hash
0219.contains-duplicate-ii 存在重复元素 II
- 本题关注点在于是否有邻近的重复，因此除了用hash，可以尝试利用数据的邻近特性，例如JAVA的treeset：self-balancing Binary Search Tree (BST)，C++的multiset
0220.contains-duplicate-iii 存在重复元素 III
- 方法一：multiset+滑窗法，利用lower_bound
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
int size = nums.size(); if(size <= 1) return false;
if(k==0) return t==0;
multiset<long long> window;
//construct the first window
for(int i=0; i<min(size, k+1); i++) {
bool tmp = updateWindow(window, nums[i], t); if(tmp) return true;
window.insert(nums[i]);
}
//slide the wondow
for(int i=1; i+k<size; i++) {
auto itPrev = window.find(nums[i-1]); window.erase(itPrev);
bool tmp = updateWindow(window, nums[i+k], t); if(tmp) return true;
window.insert(nums[i+k]);
}
return false;
}
private:
bool updateWindow(multiset<long long>& window, int val, int t) {
auto itlower = window.lower_bound(val);
if(itlower != window.end() && (*itlower)-val <= t) return true;
if(itlower != window.begin()) {
--itlower;
if(val - (*itlower) <= t) return true;
}
return false;
}
- 方法二：巧妙的方法，注意到数据结构特点，要求没有邻近数，因此可以用bucket数据结构
- 引申：桶排序 =>基数排序
public class Solution {
// Get the ID of the bucket from element value x and bucket width w
// In Java, `-3 / 5 = 0` and but we need `-3 / 5 = -1`.
private long getID(long x, long w) {
return x < 0 ? (x + 1) / w - 1 : x / w;
}
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if (t < 0) return false;
Map<Long, Long> d = new HashMap<>();
long w = (long)t + 1;
for (int i = 0; i < nums.length; ++i) {
long m = getID(nums[i], w);
// check if bucket m is empty, each bucket may contain at most one element
if (d.containsKey(m))
return true;
// check the neighbor buckets for almost duplicate
if (d.containsKey(m - 1) && Math.abs(nums[i] - d.get(m - 1)) < w)
return true;
if (d.containsKey(m + 1) && Math.abs(nums[i] - d.get(m + 1)) < w)
return true;
// now bucket m is empty and no almost duplicate in neighbor buckets
d.put(m, (long)nums[i]);
if (i >= k) d.remove(getID(nums[i - k], w));
}
return false;
}
}
0226.invert-binary-tree 翻转二叉树
0229.majority-element-ii 求众数 II
- Boyer-Moore，代码
0240.search-a-2d-matrix-ii 搜索二维矩阵 II
- 《剑指offer》第4题
- 关键在于起点的选取，从左下角或者右上角开始
0295.find-median-from-data-stream 数据流的中位数
- 《剑指offer》第41题
- 思路1: AVL树的平衡因子改为左、右子树节点数目之差
- 思路2: 左边最大堆，右边最小堆
- 书上代码：push_heap和pop_heap
- 也可直接用priority_queue，注意小顶堆的定义：
priority_queue<int, vector<int>, greater<int>> hi;
min.push_back(num);
push_heap(min.begin(),min.end(),greater<int>());
- 字节后端面试：变式题，在本题基础上增加erase功能，需要把堆改成BST（即set），保证删除性能
0297.serialize-and-deserialize-binary-tree 二叉树的序列化与反序列化
- 《剑指offer》第37题
- 思路上可以使用DFS或者BFS
- C++具体实现，利用stringstream
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
if(root==NULL)return "";
ostringstream ostr;
queue<TreeNode*>q;
TreeNode*temp;
q.push(root);
int curNum=1;
while(!q.empty()){
temp=q.front();
q.pop();
if(!temp){
if(curNum) ostr<<"null,";
}
else {
ostr<<temp->val<<",";
curNum--;
q.push(temp->left);
if(temp->left)curNum++;
q.push(temp->right);
if(temp->right)curNum++;
}
}
return ostr.str();
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
if(data=="")return NULL;
istringstream istr(data);
queue<TreeNode*>q;
TreeNode* root=new TreeNode;
TreeNode **number=new TreeNode*;
if(ReadStream (istr,number)){
root=number[0];
if(!root)return NULL;
q.push(root);
}
else return NULL;
TreeNode *temp;
while(!q.empty()){
temp=q.front();
q.pop();
if(!temp)continue;
if(ReadStream(istr,number)){
temp->left=number[0];
q.push(temp->left);
}
else break;
if(ReadStream(istr,number)){
temp->right=number[0];
q.push(temp->right);
}
else break;
}
return root;
}
bool ReadStream(istringstream &istr,TreeNode **number){
string s;
if(getline(istr,s,',')){
if(s=="null")number[0]=NULL;
else number[0]=new TreeNode(stoi(s));
return 1;
}
return 0;
}
};
0343.integer-break 整数拆分
- 简单DP
0426.convert-binary-search-tree-to-sorted-doubly-linked-list将二叉搜索树转化为排序的双向链表
- 《剑指offer》第36题
- 方法一：二叉搜索树特性，中序遍历的递归/非递归实现，用nonlocal last记录上一次遍历的末尾节点
- 方法二：用flag指示返回最左/最右节点，递归后序遍历操作
Node *treeToDoublyList(Node *root)
{
root = treeToDoublyList(root, 0);
if (root == NULL)
return NULL;
Node *p = root;
while (p->right) p = p->right;
p->right = root;
root->left = p;
return root;
}
Node *treeToDoublyList(Node *root, int flag)
{ //flag=0:left, flag=1:right
if (root == NULL)
return NULL;
Node *l = treeToDoublyList(root->left, 1);
Node *r = treeToDoublyList(root->right, 0);
root->left = l;
root->right = r;
if (l)
l->right = root;
if (r)
r->left = root;
Node *p = root;
if (!flag) while (p->left) p = p->left;
else while (p->right) p = p->right;
return p;
}
0653.two-sum-iv-input-is-a-bst 两数之和 IV - 输入 BST
- 我用的方法比较奇怪：分治的思想，利用BST特性减少运算量，直接递归即可通过。
- 其它的常见方法：
- 方法一：使用HashSet
- 方法二：中序遍历BST树，转化为排序数组的两数之和问题
class Solution {
public:
typedef TreeNode* Link;
bool searchR(Link p,int x){ //判断子树内是否存在x
if(p==NULL)return 0;
int key=p->val;
if(x==key)return 1;
if(x<key)return searchR(p->left,x);
else return searchR(p->right,x);
}
bool findTarget(TreeNode* root, int k) {
int result=0;
if(root==NULL)return 0;
if(k>2*root->val){ //利用BST特性减少运算量
if(findTarget(root->right,k))return 1;
}
else if(k<2*root->val){
if(findTarget(root->left,k))return 1;
}
if(searchR(root->left,k-root->val))return 1;
if(searchR(root->right,k-root->val))return 1;
if(findinAB(root->left,root->right,k))
return 1;
return 0;
}
bool findinAB(TreeNode* A,TreeNode* B,int k){ //在A、B中各取一个节点
int result=0;
if(A==NULL||B==NULL)
return 0;
if(searchR(B,k-A->val))return 1;
if(findinAB(A->left,B,k))return 1;
if(findinAB(A->right,B,k))return 1;
return 0;
}
};
0946.validate-stack-sequences 验证栈序列
- 建一个辅助栈模拟这一过程
0974.subarray-sums-divisible-by-k 和可被 K 整除的子数组
- 记录前缀和数组v[i]，
1209.remove-all-adjacent-duplicates-in-string-ii 删除字符串中的所有相邻重复项 II
- 利用pair存储当前连续字符数，建立栈模拟操作，符合条件则出栈
内容总结
以上是互联网集市为您收集整理的关于LeetCode刷题及题目列表归纳全部内容，希望文章能够帮你解决关于LeetCode刷题及题目列表归纳所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】