要怎么办呢牛 - 个人主页动态

2022-01-12 12:10

已编辑

本题的本质是树的dfs， 每次dfs可以确定以u为重心的最大连通块的节点数，并且更新一下ans。 也就是说，dfs并不直接返回答案，而是在每次更新中迭代一次答案。 树的dfs框架 //数组建立的邻接表 int h[N], e[N * 2], ne[N * 2], idx; void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; } //dfs框架 void dfs(int u) { st[u] = true; for(int i = h[u]; i != -1; i = ne[i]) ...

0 点赞评论收藏

2022-01-12 11:07

美团_核心本地商业_后端研发工程师(实习员工)

八数码

重点在于如何表示状态和如何进行状态转移 框架 void bfs() { q.push(起点); while(队列不空) { auto t = 队首元素; for(所有相邻节点) { 如果可以扩展，就扩展，入队; } } } #include<bits/stdc++.h> using namespace std; int bfs(string start) { string end = "12345678x"; queue<...

0 点赞评论收藏

2022-01-12 09:52

美团_核心本地商业_后端研发工程师(实习员工)

走迷宫

框架 void bfs() { q.push(起点); while(队列不空) { auto t = 队首元素; for(所有相邻节点) { 如果可以扩展，就扩展，入队; } } } 代码 #include<bits/stdc++.h> using namespace std; typedef pair<int,int> PII;//存储点对 const int N = 110; int n, m; int g[N][N]; int ...

0 点赞评论收藏

2022-01-12 09:19

美团_核心本地商业_后端研发工程师(实习员工)

n-皇后问题

框架 void dfs(开始位置 u) { if(以后搜索完) { 输出结果; return; } //枚举在这个位置可能转移到的所有状态 for(所有可能转移到的状态) { 转移到新状态; dfs(新的开始位置); 恢复状态; } } 思路1 比较原始的方法，枚举每一个位置放不放皇后，时间复杂度为O(2n)O(2^n)O(2n) #include<iostream> using namespace std; const int N = 20...

0 点赞评论收藏

2022-01-12 08:22

美团_核心本地商业_后端研发工程师(实习员工)

排列数字[全排列]

把搜索的过程想象成一棵树，一共有n个位置需要填写，我们的顺序是从第一个位置开始向后填写，在过程中需要注意记录哪些数字还没有填写，还有，记得恢复状态 //枚举第u个位置 void dfs(int u) { if(已经遍历完) { 输出结果; return; } for() { 遍历每个可能转移到的状态; 做出改变； dfs(下一层); 恢复状态; } } //全排列问题 #include<iostream> using namespace std; co...

0 点赞评论收藏

2022-01-10 19:10

美团_核心本地商业_后端研发工程师(实习员工)

最长连续不重复子序列

题目描述 给定一个长度为 n 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。 输入格式 第一行包含整数 n。 第二行包含 n 个整数（均在 0∼105 范围内），表示整数序列。 输出格式 共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。 数据范围 1≤n≤105 样例 输入样例： 5 1 2 2 3 5 输出样例： 3 算法 双指针 O(n2)O(n^2)O(n2) 时间复杂度 O(n) C++ 代码 #include<iostream> using namespace std; const int N = 1e5 + 10; //q是原...

0 点赞评论收藏

2022-01-10 19:11

已编辑

美团_核心本地商业_后端研发工程师(实习员工)

中缀表达式求值

题目描述 给定一个表达式，其中运算符仅包含 +,-,*,/（加 减 乘 整除），可能包含括号，请你求出表达式的最终值。 注意： 数据保证给定的表达式合法。 题目保证符号 - 只作为减号出现，不会作为负号出现，例如，-1+2,(2+2)*(-(1+1)+2) 之类表达式均不会出现。 题目保证表达式中所有数字均为正整数。 题目保证表达式在中间计算过程以及结果中，均不超过 231−1231−1。 题目中的整除是指向 00 取整，也就是说对于大于 00 的结果向下取整，例如 5/3=15/3=1，对于小于 00 的结果向上取整，例如 5/(1−4)=−15/(1−4)=−1。 C++和Java中的整...

0 点赞评论收藏

2022-01-10 19:08

美团_核心本地商业_后端研发工程师(实习员工)

滑动窗口（单调队列）

单调队列的思考方式： 思考使用普通队列该怎么做？ 将队列中没有用的元素删除掉 --> 具有单调性 可以用O(1)的时间从队头或者队尾取出最值 单调队列的使用条件： 求窗口里面的最大值或者最小值，常规做法是遍历这个窗口O(k)，使用单调队列可以优化为O(1) 求离它最近的比它小（大）的数 本题（滑动窗口）的思考方式： 首先，我们使用队列来模拟这个滑动的窗口，因为队列的先入先出特性正好和滑动的窗口一致，然后就考虑如何去优化——**删除一些冗余（肯定不会被用到）**的元素，从而使得队头元素恰好是需要的元素。 这里有两个问题需要求解： 如何维护这个队列（使之与滑动的窗口对应）？ 如何删...

0 点赞评论收藏

2022-01-10 19:07

美团_核心本地商业_后端研发工程师(实习员工)

干草堆

考察差分数组 #include<iostream> #include<algorithm> using namespace std; const int N = 1e6 + 10; int b[N]; int n, k; void insert(int l, int r) { b[l]++, b[r + 1]--; } int main() { cin >> n >> k; while(k--) { int l, r; cin >> l >> r; ...

0 点赞评论收藏

2022-01-10 19:06

美团_核心本地商业_后端研发工程师(实习员工)

AcWing 2058. 笨拙的手指

思路 这道题目考察的是枚举+进制转换，属于基础题目，感觉重点可以学到枚举的一些技巧 //进制转换：其他进制转换为十进制 //s是带转换字符串，b是基数（base） int get(string s, int b) { int res = 0; for(auto c : s) res = res * 10 + c - '0'; return res; } 我们也可以使用C++库函数进行求解 //str是带转换字符串，b是基数，该函数转换结果是十进制 stoi(str, nullptr,b); //举例 int ans = stoi("1011", nul...

0 点赞评论收藏

2022-01-10 19:04

美团_核心本地商业_后端研发工程师(实习员工)

括号画家

题目描述 达达是一名漫画家，她有一个奇特的爱好，就是在纸上画括号。 这一天，刚刚起床的达达画了一排括号序列，其中包含小括号 ( )、中括号 [ ] 和大括号 { }，总长度为 NN。 这排随意绘制的括号序列显得杂乱无章，于是达达定义了什么样的括号序列是美观的： 空的括号序列是美观的； 若括号序列 AA 是美观的，则括号序列 (A)(A)、[A][A]、{A}{A} 也是美观的； 若括号序列 A、BA、B 都是美观的，则括号序列 ABAB 也是美观的。 例如 [(){}]() 是美观的括号序列，而)({)[}]( 则不是。 现在达达想在她绘制的括号序列中，找出其中连续的一段，满足这段子串是美...

0 点赞评论收藏

2022-01-10 19:04

已编辑

美团_核心本地商业_后端研发工程师(实习员工)

最长合法括号子序列

最长合法括号子序列 题目描述 一个合法的括号序列满足以下条件： 序列()被认为是合法的。 如果序列X与Y是合法的，则XY也被认为是合法的。 如果序列X是合法的，则(X)也是合法的。 例如，()，()()，(())这些都是合法的。 现在，给定一个由 ( 和 ) 组成的字符串。 请你求出其中的最长合法括号子序列的长度。 注意，子序列不一定连续。 输入格式 共一行，一个由 ( 和 ) 组成的字符串。 输出格式 一个整数，表示最长合法括号子序列的长度。 数据范围 前五个测试点满足， 1≤输入字符串的长度≤101≤输入字符串的长度≤10。 所有测试点满足，1≤输入字符串的长度≤1061≤输入字符串的...

0 点赞评论收藏

2022-01-10 19:02

已编辑

美团_核心本地商业_后端研发工程师(实习员工)

最长合法括号子串

题意 一个合法的括号字符串满足以下条件： 字符串“()”被认为是合法的。 如果字符串 “X” 与 “Y” 是合法的，则 “XY” 也被认为是合法的。 如果字符串 “X” 是合法的，则 “(X)” 也是合法的。 例如，“()”，“()()”，“(())” 这些都是合法的。 现在，给定一个由 ( 和 ) 组成的字符串 SS。 请你求出其中的最长合法括号子串的长度以及数量。 输入格式 共一行，一个由 ( 和 ) 组成的字符串。 输出格式 一行两个整数，表示最长合法括号子串的长度以及数量。 如果不存在合法括号子串，则输出 0 1。 数据范围 前六个测试点满足：1≤|S|≤1001≤|S|≤100。...

0 点赞评论收藏

2022-01-10 18:56

美团_核心本地商业_后端研发工程师(实习员工)

2134. 最少交换次数来组合所有的 1 II

题目描述 解题思路 设数组中1的数量为len，维护一个长度为len的滑动窗口，从左向右扫描一遍数组，对于每个窗口，需要交换的次数就是窗口中0的数量。 环形数组可以把数组想象成二倍的原数组，使用模运算加以简化，这样i和j就不需要特殊处理了！ 代码 class Solution { public: int minSwaps(vector<int>& nums) { int n = nums.size(); int len = 0;//1的数量 for(auto &x : nums) len += x; ...

0 点赞评论收藏

2022-01-10 18:51

美团_核心本地商业_后端研发工程师(实习员工)

LeetCode 2136. 全部开花的最早一天

题目描述 解题思路 代码 #include<bits/stdc++.h> using namespace std; typedef pair<int,int> PII; bool cmp(PII a, PII b) { //升序排序 return a.first > b.first; } class Solution { public: int earliestFullBloom(vector<int>& plantTime, vector<int>& growTime) { ...

0 点赞评论收藏

创作者周榜

关注他的用户也关注了：