推广网站报价,资阳优化团队信息,网络建设与管理专业,重庆网站建设制作参考练习习题总集 文章目录 10. 正则表达式匹配44. 通配符匹配45. 跳跃游戏53. 最大子数组和91. 解码方法97. 交错字符串115. 不同的子序列119. 杨辉三角IILCR 161. 连续天数的最高销售额 10. 正则表达式匹配
第一道题就是困难题让我很难蚌。真是磨人啊。
class Solution {
…参考练习习题总集 文章目录 10. 正则表达式匹配44. 通配符匹配45. 跳跃游戏53. 最大子数组和91. 解码方法97. 交错字符串115. 不同的子序列119. 杨辉三角IILCR 161. 连续天数的最高销售额 10. 正则表达式匹配
第一道题就是困难题让我很难蚌。真是磨人啊。
class Solution {
public:bool isMatch(string s, string p) {int * * matrixnew int * [p.size()1];for (int i0;ip.size()1;i){matrix[i]new int [s.size()1];for (int j0;js.size()1;j)matrix[i][j]0;}matrix[0][0]1;for (int i1;ip.size();i2){if (p[i]*) matrix[i1][0]1;else break;}for (int i1;ip.size()1;i)for (int j1;js.size()1;j)if (s[j-1]p[i-1] or p[i-1].){if (matrix[i-1][j-1]1){matrix[i][j]1;}}else if (p[i-1]*){if (matrix[i-2][j]1){matrix[i][j]1;continue;}if (matrix[i][j-1]1 and (s[j-1]p[i-2] or p[i-2].))matrix[i][j]1;}bool resultmatrix[p.size()][s.size()];for (int i0;ip.size()1;i)delete [] matrix[i];return result;}
};44. 通配符匹配
嗨嗨嗨思想差不多的又水一道困难题。
class Solution {
public:bool isMatch(string s, string p) {int len1s.size(),len2p.size();int * * matrixnew int * [len21];for (int i0;ilen21;i){matrix[i]new int [len11];for (int j0;jlen11;j)matrix[i][j]0;}matrix[0][0]1;for (int i0;ilen2;i)if (p[i]*) matrix[i1][0]1;else break;for (int i1;ilen21;i)for (int j1;jlen11;j){if (s[j-1]p[i-1] or p[i-1]?){if (matrix[i-1][j-1]1)matrix[i][j]1;}else if (p[i-1]*){if (matrix[i-1][j]1){matrix[i][j]1;continue;}if (matrix[i-1][j-1]1 or matrix[i][j-1]1)matrix[i][j]1;}}bool resultmatrix[len2][len1];for (int i0;ilen21;i)delete [] matrix[i];return result;}
};45. 跳跃游戏
记忆化搜索。这里的记忆化搜索本质就是线性DP。做这道题时真是气死我了一开始明明记着长度为0的时候需要特判但是后面做着做着就忘了加上去交了一次又发现if (temp[i]!0) return temp[i];没有加上去连着犯了两次低级错误。
class Solution {
public:vectorint lb;vectorint temp;int jump(vectorint nums) {if (nums.size()1) return 0;lbnums;temp.resize(nums.size(),0);return dfs(0);}int dfs(int i){if (temp[i]!0) return temp[i];if (ilb[i]lb.size()-1) return 1;int result1e4-1;for (int jlb[i];j1;j--){int result_tempdfs(ij)1;if (result_tempresult)resultresult_temp;}temp[i]result;return result;}
};53. 最大子数组和
前缀和。
class Solution {
public:int maxSubArray(vectorint nums) {int * lbnew int [nums.size()1];lb[0]0;for (int i1;inums.size()1;i)lb[i]lb[i-1]nums[i-1];int min_value0,resultINT_MIN;for (int i1;inums.size()1;i){int result_templb[i]-min_value;if (result_tempresult) resultresult_temp;if (lb[i]min_value) min_valuelb[i];}delete [] lb;return result;}
};线性DP。
class Solution {
public:int maxSubArray(vectorint nums) {for (int i1;inums.size();i)if (nums[i-1]0)nums[i]nums[i-1];int resultINT_MIN;for (int i0;inums.size();i)if (nums[i]result)resultnums[i];return result;}
};91. 解码方法
class Solution {
public:int numDecodings(string s) {if (s[0]0) return 0;int * lbnew int [s.size()1];lb[0]0;lb[1]1;for (int i2;is.size()1;i)if (s[i-1]0){if (s[i-2]1 or s[i-2]2)lb[i]max(lb[i-2],1);else return 0;}else{lb[i]lb[i-1];if (s[i-2]1 or (s[i-2]2 and s[i-1]6))lb[i]max(lb[i-2],1);}int resultlb[s.size()];delete [] lb;return result;}
};97. 交错字符串
记忆化搜索。
class Solution {
public:string string1,string2,string3;vectorvectorint temp;bool isInterleave(string s1, string s2, string s3) {if (s1.size()s2.size()!s3.size()) return false;string1s1;string2s2;string3s3;temp.resize(s1.size()1,vectorint (s2.size()1,0));return func(0,0);}bool func(int l1,int l2){if (l1string1.size() and l2string2.size()) return true;if (temp[l1][l2]!0) return temp[l1][l2]1;bool resultfalse;if (l1string1.size() and string1[l1]string3[l1l2])result|func(l11,l2);if (l2string2.size() and string2[l2]string3[l1l2])result|func(l1,l21);temp[l1][l2]result?1:-1;return result;}
};线性DP。
class Solution {
public:bool isInterleave(string s1, string s2, string s3) {if (s1.size()s2.size()!s3.size()) return false;int * * matrixnew int * [s1.size()1];for (int i0;is1.size()1;i){matrix[i]new int [s2.size()1];for (int j0;js2.size()1;j)matrix[i][j]0;}queuepairint,int dl;dl.push(make_pair(0,0));while (1){queuepairint,int temp;if (dl.front().first1s1.size())temp.push(make_pair(dl.front().first1,dl.front().second));while (!dl.empty()){int xdl.front().first,ydl.front().second;if (x0 and y0) matrix[x][y]1;else if (x0){if (matrix[x][y-1]1 and s2[y-1]s3[y-1])matrix[x][y]1;}else if (y0){if (matrix[x-1][y]1 and s1[x-1]s3[x-1])matrix[x][y]1;}else{if ((matrix[x][y-1]1 and s2[y-1]s3[xy-1]) or (matrix[x-1][y]1 and s1[x-1]s3[xy-1]))matrix[x][y]1;}if (dl.front().second1s2.size())temp.push(make_pair(dl.front().first,dl.front().second1));dl.pop();}if (temp.empty()) break;dltemp;}bool resultmatrix[s1.size()][s2.size()];for (int i0;is1.size()1;i)delete [] matrix[i];return result;}
};115. 不同的子序列
wtql感觉神功大成。
class Solution {
public:int numDistinct(string s, string t) {int mod1e97;int * * matrixnew int * [s.size()1];for (int i0;is.size()1;i){matrix[i]new int [t.size()1];for (int j0;jt.size()1;j)matrix[i][j]0;}for (int i1;is.size()1;i)for (int j1;jt.size()1;j)if (s[i-1]t[j-1]){matrix[i][j](matrix[i][j]matrix[i-1][j])%mod;matrix[i][j](matrix[i][j]matrix[i-1][j-1])%mod;if (j1) matrix[i][j]1;}else matrix[i][j]matrix[i-1][j];int resultmatrix[s.size()][t.size()];for (int i0;is.size()1;i)delete [] matrix[i];return result%mod;}
};119. 杨辉三角II
简单题
class Solution {
public:vectorint getRow(int rowIndex) {vectorvectorint lb{{1}};for (int i1;irowIndex;i){vectorint temp;temp.push_back(1);for (int j1;ji;j)temp.push_back(lb[i-1][j-1]lb[i-1][j]);temp.push_back(1);lb.push_back(temp);}return lb[rowIndex];}
};LCR 161. 连续天数的最高销售额
前缀和。
class Solution {
public:int maxSales(vectorint sales) {int * lbnew int [sales.size()1];lb[0]0;for (int i1;isales.size()1;i)lb[i]lb[i-1]sales[i-1];int min_value0,resultINT_MIN;for (int i1;isales.size()1;i){int result_templb[i]-min_value;if (result_tempresult) resultresult_temp;if (lb[i]min_value) min_valuelb[i];}delete [] lb;return result;}
};线性DP。 和53. 最大子数组和一样。 虽然做每道题的时间可能会有点久但是再也不像以前那样完全没有办法了那就这样吧。
