class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param A string字符串 * @return int整型 */ int getLongestPalindrome(string A) { // write code here int n=A.size(); if(n==0) { return 0; } int maxlength=1; for(int i=0;i<2*n-1;i++) { int left=i/2; int right=left+i%2; while(left&g...

class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 最少货币数 * @param arr int整型vector the array * @param aim int整型 the target * @return int整型 */ //动态规划，主问题依赖于子问题，并且子问题的最优解是主问题的最优解 int minMoney(vector<int>& arr, int aim) { // write code here int n=arr.size(); if(n==0) { ret...

#include <cctype> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 解码 * @param nums string字符串 数字串 * @return int整型 */ //设dp表示前i个数字有多少种字符 //第i个字符，可以跟它前面的数字组成一个字符，这样dp[i]等于dp[i-2] //也可以是它自己组成一个字符，这样dp[i]等于dp[i-1] //综上，所以dp[i]根据是否能跟它前面的数字组成一个字符来决定它的值 //dp[i]依赖于前面的dp[i-1]和dp[...

#include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param matrix int整型vector<vector<>> the matrix * @return int整型 */ //典型的动态规划，最终结果依赖于它上一次的结果 int minPathSum(vector<vector<int> >& matrix) { // write code here if(matrix.size()=...

#include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param m int整型 * @param n int整型 * @return int整型 */ int uniquePaths(int m, int n) { // write code here vector<vector<int>> dp(m+1,vector<int>(n+1,0)); //起点等于1 dp[1][1]=1; //保证让起点等于1 dp[...

#include <cstddef> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param cost int整型vector * @return int整型 */ //cost数组的大小就是多少个台阶 //第i阶楼梯依赖于前面爬i-1阶台阶的最低花费 //可以转化为子问题，并且子问题会被多次计算 //典型的递归，并且可以通过自底向上来实现 int minCostClimbingStairs(vector<int>& cost) { // write cod...

class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param number int整型 * @return int整型 */ //第n阶楼梯有两种情况上来，第一种是从n-1爬1阶，第二种是从n-2爬2阶 //典型的主问题转换为子问题，主问题的解依赖于子问题，并且子问题被多次计算 //可以自底向上 int jumpFloor(int number) { // write code here if(number==1) { return 1; } if(number==2) { return 2; ...

#include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 递增路径的最大长度 * @param matrix int整型vector<vector<>> 描述矩阵的每个数 * @return int整型 */ //动态规划的通用5步 //①定义状态，明确dp[i]或dp[i][j]表示什么含义 //②写出状态转移方程 //③确定初始条件或者边界条件 //④确定遍历顺序 //⑤返回答案 //本题中，状态为矩阵的路径长度，也就是说dp[i][...

#include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param n int整型 * @return string字符串vector */ //总共n个左括号和右括号 //任意前缀中，要保证左括号数量大于等于右括号数量 void BackTrack(int n,string temp,int leftcount,int rightcount,vector<string>& res) { if(temp.size()==2*n) { ...

class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param n int整型 the n * @return int整型 */ void BackTrack(int n,int row,unordered_set<int>& cols,unordered_set<int>& diag1,unordered_set<int>& diag2,int& counter) { if(row==n)//每行放一个，所有行都放完了 { co...

class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param str string字符串 * @return string字符串vector */ //方法同数字全排列一样 void BackTrack(string str,string temp,vector<bool> used,vector<string>& res) { if(temp.size()==str.size()) { res.push_back(temp); return; } for(int...

class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 判断岛屿数量 * @param grid char字符型vector<vector<>> * @return int整型 */ //一个陆地四周全是海洋才算是岛屿，如果两个或多个陆地全都连在一起，也算是一个岛屿 //所以当找到一个1时，把它四周的所有1全都设为0，这是为了避免误将它周围的1也统计为岛屿 //通过DFS把它周围所有的1全都变为0,直到遇到0海洋时递归终止，此时陆地的周围全是海洋 void DFS(vector&lt...

class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param num int整型vector * @return int整型vector<vector<>> */ void backtrack(vector<int>& num,vector<int>& temp,vector<bool>& used,vector<vector<int>>& res) { if(temp.size(...

#include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param num int整型vector * @return int整型vector<vector<>> */ void backtrack(vector<int>& num,vector<int>& temp,vector<bool>& used,vector<vector<int>>&a...