解法一：暴力解法 根据题意，直接进行模拟，每次询问从 l 到 r 进行遍历求和。时间复杂度：O(n * q)，会超时解法二：前缀和两步走：第一步：预处理一个前缀和数组 用dp[i]表示从0位置到i位置的元素的和，则遍历数组一次，可以得到一个前缀和数组，前缀和数组中保存了dp[i]的每个数据。 在输入nums和预处理前缀和数组时，要注意边界情况，给nums和dp数组多开一个空间。第二步：使用前缀和数组 有了前缀和数组之后，就可以以O(1)时间拿到 l 到 r 的元素和：C++代码 #include <iostream> #include <vector&...

class Solution { public: int nextStep(int cur) { int res = 0; while(cur) { res += (cur % 10) * (cur % 10); cur /= 10; } return res; } //根据鸽巢原理，变换过程一定成环 //若为快乐数，环中数据全部为1 //否则不为快乐数 bool happynum(int n) { ...

#include <iostream> #include <string> #include <vector> #include <map> #include <utility> #include <algorithm> using namespace std; //自定义stable_sort()的仿函数，比较count struct Greater { bool operator()(const pair<string, int>& p1, const pair<string, in...

关键点1：二叉搜索树的中序遍历有序 关键点2：为了进行节点的链接，应引入前一个节点的引用 prev 在中序遍历的过程中对两两节点进行链接 class Solution { public: void InOrder(TreeNode* cur, TreeNode*& prev) { if(cur == nullptr) { return; } InOrder(cur->left, prev); //当前节点的前驱指针应指向前一个遍历的节点 cur-&...

using namespace std; class Date { friend istream& operator>>(istream& cin, Date& d); private: int _year; int _month; int _day; public: Date(int year = 1200, int month = 1, int day = 1) :_year(year), _month(month), _day(day) { } static int...

思路 本题与（DD3 地下迷宫）相似，在地下迷宫的基础上增加了体力值的限制。 当一个矩阵被确定时，青蛙移动的水平位移已经被确定为矩阵的长度，即青蛙水平移动消耗的体力已经被确定了。所以我们只需要考虑上下方向的移动：上下移动的位移越小，则消耗的体力值越少，所以青蛙的体力消耗主要取决于上下位移。同时上下位移越小，青蛙的移动路径越短，所以问题就转化成了：求青蛙离开的最短路径。 与DD3 地下迷宫不同的是，本题找到一条可行路径时不直接一路返回，而是回到关键位置继续搜索其他路径，所以这里的搜索函数不再设置返回值。需要注意的是，返回时要将路径中的位置重新置为 1，以便后...

#include <iostream> #include <stack> #include <vector> #include <utility> using namespace std; stack<pair<int, int>> path;//记录路径 void MazeInput(vector<vector<int>>& maze, int row, int col)//输入迷宫 { for(int i = 0; i < row; i++) { fo...