一开始理所当然地用模拟的方法做，但是怎么都是时间超时，才仔细考虑了一下应该用动态规划定义为第一次到达第号房间所用的步数由题意知，若要到达第号房间，则必须到达第号至少两次：第一次到达号时，再走步则跳回到前面的某个房间，记为，此时必须重新返回第号房间，那么所花费的步数即为：，即综上，，最后的是第二次到达号房时再走一步才到也可以合并同类项：由于题目提示了要取余1000000007，因此需要特殊处理 #include <iostream> #include <vector> #define MOD 1000000007 using namespace std; int main...

定义表示走到i行j列时能获得的最高奖金，由于只能向右走或者向下走，要求最高奖金，那么可得转移方程：即当前能获得的最大奖金为 左边和上边一格中的较大值+当前格子的值 #include <vector> class Bonus { public: int getMost(vector<vector<int> > board) { vector<vector<int>> dp(6, vector<int>(6, 0)); dp[0][0] = board[0][0]; // 注意第一列、第一行只能选择直直走 for (int i...

首先理解题意：如字符串aabbcde中，一共有abcde五种字母，而5是斐波那契数，因此这个子串可以被输出；如字符串aabbcdef中，一共有abcdef六种字母，而6不是斐波那契数，因此这个子串不能被输出那么接下来处理好逻辑就行了：先生成给定字符串的所有子串，再分别对每一个子串统计其字母种类数，再判断是不是斐波那契数即可注意unordered_set无序，而set自带排序，因此无需再排 #include <iostream> #include <set> #include <string> #include <unordered_set> us...

参考文章：https://blog.csdn.net/melonyzzZ/article/details/128599307经典的左闭右闭二分查找，即查找的范围是 [l,r] class BinarySearch { public: int getPos(vector<int> A, int n, int val) { int l = 0, r = n - 1; while (l <= r) { int mid = (l + r) / 2; if (val > A[mid]) { l = mid + 1; } else { r = mid - 1; } } return...

使用双指针从两端遍历数组，根据遍历的情况决定往左边加数还是往右边加数，遍历完的条件是两个指针相遇，至于中间分一组这个要求，可以直接不做处理 #include <algorithm> #include <iostream> #include <vector> using namespace std; int main() { int n; while (cin >> n) { vector<int> d; long long money; for (int i = 0; i < n; i++) { cin >> mon...

题目的题意有点难以理解，参考了讨论区大佬的解读： 1.如果两人体重不一样，则上面的身高要小于等于下面的身高 2.如果两人体重一样，那么他们的身高也必须一样先按照体重降序排列，再对得到的序列按照身高求最长递减子序列 #include <algorithm> #include <iostream> #include <vector> using namespace std; int main() { int N; while (cin >> N) { vector<pair<int, int>> data; int id, w...

参考大佬的java做法，由题意知，每递归一层，整体vector长度乘以2倍，由于相邻的编码只能有一个数不同，因此需要事先计算出添加1的位置 #include <vector> class GrayCode { public: vector<string> getGray(int n) { if (n == 1) { return {"0", "1"}; } vector<string> prefix = getGray(n - 1); int size = prefix.size(); vector<string...

这题的输入输出、测试用例都挺恶心的，每个题竟然可以自问自答，也可以重复由同一个人回答，因此用集合方便去重思路大体不难，但细思还挺绕，需要熟悉哈希表中嵌套集合的遍历语法 #include <iostream> #include <set> #include <unordered_map> #include <unordered_set> using namespace std; int main() { int N; while (cin >> N) { unordered_map<int, unordered_set<in...

不用排序，直接拿每个圆全部判断一次，找到就跳出即可。判断圆是否相交，其实不用想的太复杂，只需要两个圆的坐标两两对比即可：用pair数对的first和second分别表示圆的左右端点，那么用甲圆的first、second分别与乙圆的first、second交叉对比，就有三个条件联立判断：甲的first与乙的first、甲的first与乙的second、甲的second与乙的second，但需注意由于并未对圆进行排序，因此无法界定甲圆和乙圆谁在数轴上更靠后，因此需分别讨论，最后取“或” #include <any> #include <iostream> #include ...

这题其实跟********121.买卖股票的最佳时机是一个题每遍历一个数，保存遍历到的最小值，更新最大差值即可 #include <algorithm> #include <climits> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param A int整型vector * @param n int整型 * @return int整型 */ int getDis(vector<int>& A, int n) { // write code h...

既然题目分别要求了O(n)和O(1)的时空复杂度，那么就简单扫一遍数组就好。根据提议，要找到最大乘积，要么是三个最大的正数相乘，要么是两个最小的负数及一个最大的正数相乘。遍历数组，及时更新几个变量即可，注意不能用int，会溢出。 #include <iostream> #include <vector> using namespace std; int main() { int n; while (cin >> n) { int num; vector<int> nums; for (int i = 0; i < n; i++) { cin...

简单画个草稿图可知，直接连接要移动到的圆心和原来的圆心线段，那么最快的方法即为每次绕着这条线段与圆桌的交点旋转180°，那么每次圆心可移动直径的距离，最终答案即为线段长度除以直径 #include <iostream> #include <cmath> using namespace std; int main() { long r, x, y, x1, y1; while (cin >> r >> x >> y >> x1 >> y1) { long dis = sqrt((x1 - x) * (x1 - x...

经典动态规划定义dp[i]为遍历到第i位时的连续最大和前缀和<0时，说明前面的负数太多了，使当前的总和小于0，应当抛弃掉前面的数，直接从当前遍历到的数“另起炉灶”详细版：for (int i = 1; i < N; i++) { if(dp[i-1]<0){ dp[i]=nums[i]; }else{ dp[i]=dp[i-1]+nums[i]; } }合并起来就是： dp[i] = max(nums[i], dp[i - 1] + nums[i]); #include <iostream> #include <vector> #include &lt...

1、使用BFS构建树2、使用DFS搜索树并得到两个节点各自的路径3、对比路径找到最后一个公共祖先 #include <queue> #include <unordered_map> #include <unordered_set> #include <vector> class Solution { private: // 使用BFS构建树 unordered_map<int, vector<int>> BFS(vector<string>& matrix) { unordered_map<int...