专业网站开发哪里找,惠州市网站设计公司,网站开发的项目,网站空间的价格题目由入门往上递增
入门
斐波那契数列_牛客题霸_牛客网 (nowcoder.com)
动态规划甚至于算法的入门题目
方法一#xff1a;按照斐波那契的公式fnfn-1fn-2#xff0c;从1-n求出结果。
class Solution {
public:int Fibonacci(int n) {vectorintf{0,1,1};for(int …题目由入门往上递增
入门
斐波那契数列_牛客题霸_牛客网 (nowcoder.com)
动态规划甚至于算法的入门题目
方法一按照斐波那契的公式fnfn-1fn-2从1-n求出结果。
class Solution {
public:int Fibonacci(int n) {vectorintf{0,1,1};for(int i3;in;i)f.push_back(f[i-1]f[i-2]);return f[n];}
};
方法二按照公式倒推即用递归求出。
class Solution {
public:int Fibonacci(int n) {if(n1||n2) return 1;return Fibonacci(n-1)Fibonacci(n-2);}
};
简单
连续子数组的最大和_牛客题霸_牛客网 (nowcoder.com)
我们令dp[i]是以第i个数为结尾的子数组和的最大值。如果dp[i-1]为负则以i-1为结尾的子数组和都为负因此以dp[i]结果就是第i个数的值除此之外是dp[i-1]第i个数。
因此转移公式得出
验证假设以i为结尾的子数组和的最大值是r到l则以r-1为结尾的子数组和一定为负数和我们的推导符合。
class Solution {public:int FindGreatestSumOfSubArray(vectorint array) {int sum0;int maxxarray[0];sumarray[0];for(int i1;iarray.size();i){summax(sumarray[i],array[i]);maxxmax(sum,maxx);}return maxx;}
};
跳台阶_牛客题霸_牛客网 (nowcoder.com)
台阶n可以由n-1跳一步或n-2跳一步得到因此就是斐波那契数列。.
class Solution {
public:int jumpFloor(int number) {if(number1) return 1;if(number2) return 2;return jumpFloor(number-1)jumpFloor(number-2);}
};
跳台阶扩展问题_牛客题霸_牛客网 (nowcoder.com)
和上一题类似只不过通项公式变为了fnfn-1……f1求fn
因此这时候我们考虑高斯消元……
开个玩笑上述公式可以变化为fnfn-1*2
问题解决
class Solution {
public:int jumpFloorII(int number) {if (number1) {return 1;}return jumpFloorII(number-1)*2;}
};
买卖股票的最好时机(一)_牛客题霸_牛客网 (nowcoder.com)
因为只能买卖一次如果在第k天卖出就是要求第k天前最小值的买入
也可以dp太麻烦了没必要。
class Solution {
public:int maxProfit(vectorint prices) {int ans0;int minnprices[0];for(int i1;iprices.size();i){minnmin(minn,prices[i]);ansmax(prices[i]-minn,ans);}return ans;}
};
中等
连续子数组的最大和(二)_牛客题霸_牛客网 (nowcoder.com)
对于dp方面思路同上此时只是需要在sum小于0的时候更新l1在maxx更新的时候维护l和rl为l1r为i
class Solution {public:vectorint FindGreatestSumOfSubArray(vectorint array) {int sum 0;int maxx array[0];int l0,r0,l10;sum array[0];for (int i 1; i array.size(); i) {if(sum0){l1i;}sum max(sum array[i], array[i]);if(maxxsum){ll1;ri;}maxx max(sum, maxx);}vectorintans;for(int il;ir;i){ans.push_back(array[i]);}return ans;}
};
矩形覆盖_牛客题霸_牛客网 (nowcoder.com)
通过观察可以得出构成方式只有一竖和两横两种情况因此有n块肯定是n-1加上一块竖的或者n-2加上两条横的此时两条竖的已经被上一种情况包含了因此是斐波那契数列
class Solution {
public:int rectCover(int number) {if(number0) return 0;if(number1)return 1;if(number2) return 2;return rectCover(number-1)rectCover(number-2);}
};
礼物的最大价值_牛客题霸_牛客网 (nowcoder.com)
最后一格的最大值是它左边和上面的最大值的较大值加上自己因而只能往右和往下所以保证了每个格子只会被走一次无后效性。
此时注意最上面和最左边只有一种走法可以扩大一格dp数组或者预处理。
class Solution {
public:int maxValue(vectorvectorint grid) {int dp[202][202];dp[0][0]grid[0][0];for(int j1;jgrid[0].size();j){dp[0][j]grid[0][j]dp[0][j-1];}for(int j1;jgrid.size();j){dp[j][0]grid[j][0]dp[j-1][0];}for(int i1;igrid.size();i){for(int j1;jgrid[0].size();j){dp[i][j]max(dp[i-1][j],dp[i][j-1])grid[i][j];coutdp[i][j] ;}}return dp[grid.size()-1][grid[0].size()-1];}
};
最长不含重复字符的子字符串_牛客题霸_牛客网 (nowcoder.com)
设置滑动窗口记录窗口内的字符如果下一个进来会重复就将l往后移直到不重复。记录窗口最大值。
class Solution {
public:int lengthOfLongestSubstring(string s) {vectorint a(128,0);int l0,r0,lens.size();int ans0;while(rlen){int temps[r];while(a[temp]1){int xs[l];a[x]--;l;}a[temp];couttemp a[temp] r-l\n;ansmax(ans,r-l1);r;}return ans;}
};
把数字翻译成字符串_牛客题霸_牛客网 (nowcoder.com)
这题比较烦躁的是要判断一堆乱七八糟无解的情况反正特判一下。
存在多种编码的情况就是12、26这种既可以拆分也可以合并。因为字母编码最长为两位所以dpi的结果是dpi-1加一位或者dpi-2加两位此时要判断是否合法因此就是dpi-1dpi-2。
class Solution {
public:int solve(string nums) {if(nums0)return 0; vectorintans(100,0);ans[0]1;if((nums[0]1nums[1]!0)||(nums[0]2nums[1]6nums[1]0)) ans[1]2;else ans[1]1;for(int i 1; i nums.length(); i){ if(nums[i] 0)if(nums[i - 1] ! 1 nums[i - 1] ! 2)return 0;}for(int i2;inums.size();i){if((nums[i-1]1nums[i]!0)||(nums[i-1]2nums[i]6nums[i]0)){ans[i]ans[i-2]ans[i-1];}else ans[i]ans[i-1];}return ans[nums.size()-1];}
};
正则表达式匹配_牛客题霸_牛客网 (nowcoder.com)
又是蛇皮烦的一题……
首先还是设置dp数组dpij代表str第i位结尾、pattern第j位结尾的子字符串能否匹配。假设第i-1
位和第j-1位能成功匹配那么此时就是要对比第i位和第j位字符关系如果两个都是小写字母且相同那么dpij的结果就是dpi-1j-1的结果。如果不符合可以直接判断为false。
因此第j位如果是.代表着任意字符所以转移公式可以等同于上面的情况。
接下来就是考虑第j位为*的情况此时要把第j-1位一同考虑当作整体下面将j-1视作a。
第一种情况是假定*为0次此时dpij的结果就和dpij-2的结果相同。
第二种情况是假定*为1次因为如果前面*已经被当成a的话此时已经成功匹配了可以忽略了后面同理。假定为一次的话j-1就要等同于i*才能变成第i位进行匹配那么此时的转移公式就是dpijdpi-1j
第一种情况和第二种情况可以同时存在符合条件的时候取或就行。
#include vector
class Solution {bool match(string str, string pattern) {vectorvectorint dp;vectorint temp(30, 0);dp.resize(30, temp);dp[0][0] 1;for (int i 1; i pattern.size(); i) {if (pattern[i]*)dp[0][i1]dp[0][i-1];}for (int i 0; i str.size(); i) {for (int j 0; j pattern.size(); j) {if (str[i] pattern[j] || pattern[j] .) {dp[i 1][j 1] dp[i][j];} else {if (pattern[j] *) {dp[i1][j1]dp[i1][j-1];if(pattern[j-1].||pattern[j-1]str[i]){dp[i1][j1]dp[i][j1]||dp[i1][j1];}}}}}if (dp[str.size()][pattern.size()] 1)return true;else return false;}
};
