这题不难，主要注意几个坑点： 用两个vector数组会内存不足 给的样例运算后超出了int的范围，需要用long ">using namespace std; //时间复杂度：O(N) //用vector老是内存超限，就用数组了 long num[100001]={0}; long sum[100001]={0};//sum[i]:第1个加到第i个的和 int main(){ int n,q; cin>>n>>q; for(int i=0;i<n;i++) cin>>num[i]; for(int i=1;i<=n;i++){ sum[i...

这是一道动态规划题目。将其分解为子问题，即分解成求解n个 以0到n-1下标的数为结尾的子序列的最大长度的问题。可以用一个dp数组保存每个数做结尾时对应的最大长度。假设一个以第i个元素arr[i]结尾的子序列Si，那么Si的长度是由i在Si中的前一个元素arr[j]决定的，Si的长度就等于Sj的长度加一。这前面一个数arr[j]必须要满足两个条件： arr[j]<arr[i],这样才能构成严格上升 dp[j]的值在i之前的所有dp中最大，这样我们求的才是最大长度。 "> using namespace std; int main(){ int n; cin>>n; vec...

"> using namespace std; int DP(vector<vector<int>> &mat,vector<vector<int>>& dp,int x,int y){ int n,m; n=mat.size();m=mat[0].size(); if(!x&&!y)//左上角 return dp[x][y]; if(!x)//第一行 return dp[x][y]+dp[x][y-1]; if(!y)//第一列 return dp[x][y]+dp[x-1][y]; return dp[x][y...

">using namespace std; int main(){ int n; cin>>n; vector<int> dp(n+1,0); vector<int> nums(n+1,0); for(int i=1;i<=n;i++) cin>>nums[i]; for(int i=1;i<=n;i++) dp[i]=nums[i]; int mx=-10000000; for(int i=1;i<=n;i++){ if(dp[i-1]>0) dp[i]+=dp[i-1]; mx=max(mx,dp[i]); } co...

">using namespace std; //dp void MinCost(vector<int>& cost,vector<int> &dp,int n){ dp[n]=min(dp[n-1]+cost[n-1],dp[n-2]+cost[n-2]); } int main(){ int n; cin>>n; vector<int> cost(n,0); vector<int> dp(n+1,0); for(int i=0;i<n;i++) cin>>cost[i]; for(int i=2;...

public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 递增路径的最大长度 * @param matrix int整型vector<vector<>> 描述矩阵的每个数 * @return int整型 */ //i为行,j为列，pre为上一个节点的值 int DFS(vector<vector<int>>& matrix,vector<vector<int>>& dp,int i,int j,int pre){ if(matrix[i][j]<=pre...

#include<bits/stdc++.h> using namespace std; int jump(int n){ if(n==1) return 1; if(n==2) return 2; else{ return jump(n-1)+jump(n-2); } } int main(){ int n; cin>>n; cout<<jump(n); return 0; }

这道题有一点点动态规划的感觉，不同的是后面的数的状态和前面的无关。我们只需要把被减数遍历一遍即可，每个被减数对应一个使其与之相减值最大的数,不断迭代求出最大的那个即可。 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param A int整型vector * @param n int整型 * @return int整型 */ int getDis(vector<int>& A, int n) { // write code here int min=A[0];//记录最小...

class Solution { public: int search(TreeNode* node){ if(!node) return NULL; int temp=1; if(!node->left&&!node->right){//叶子节点 return temp; } //特殊情况，即一边子树全空 if(!node->left) return search(node->right)+1; else if(!node->right) return search(node->left)+1; return min(temp+search...

class Solution { public: bool DFS(TreeNode* node,int sum,int res){ if(!node) return false; res+=node->val; if(!node->left&&!node->right){ if(res==sum)return true; else return false; } return DFS(node->left,sum,res)||DFS(node->right,sum,res); } bool hasPathSum(TreeNode* root, i...

class Solution { public: /** * * @param root TreeNode类 * @return int整型 */ int DFS(TreeNode* node){ if(node==NULL) return 0; int depth=1; int left=DFS(node->left); int right=DFS(node->right); return left>right?depth+left:depth+right; } int maxDepth(TreeNode* root) { // write code here int de...

基本思想：越大的数，应当排放在越前面。 当不满足该条件时，与本应放在该位的数值中的最后一个进行交换 public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param num string字符串 * @return string字符串 */ string maximumSwap(string num) { // write code here //贪心策略，大小排位越高，排到这个数的越前面 vector<int>a; for(auto c:num){ a.push_back(c-48); } int j=-1; sort(...

">using namespace std; int Reverse(int n){ int re=0; while(n!=0){ re*=10; re+=n%10; n=n/10; } return re; } bool IsSym(int n){ if(Reverse(n)==n) return true; else return false; } int main(){ for(int i=0;i<=256;i++){ if(IsSym(i*i)) cout<<i<<endl; } return 0; }