高密建设局网站,网站开发如何设置视频教程,网站建设微金手指下拉12,网站开发公司哪家最专业参考练习习题总集 文章目录 前置知识练习习题87. 扰乱字符串97. 交错字符串375. 猜数字大小II403. 青蛙过河464. 我能赢吗494. 目标和552. 学生出勤记录II576. 出借的路径数 前置知识
没有什么特别知识#xff0c;只有一些做题经验。要做这类型的题目#xff0c;首先写出暴…参考练习习题总集 文章目录 前置知识练习习题87. 扰乱字符串97. 交错字符串375. 猜数字大小II403. 青蛙过河464. 我能赢吗494. 目标和552. 学生出勤记录II576. 出借的路径数 前置知识
没有什么特别知识只有一些做题经验。要做这类型的题目首先写出暴力搜索然后写出记忆搜索大概就是这个流程。感觉说了一些废话。
练习习题
87. 扰乱字符串
TLE(自己写的难蚌代码)
class Solution {
public:unordered_setstring jh;bool isScramble(string s1, string s2) {func(s1,0,s1.size()-1);return jh.find(s2)!jh.end();}void func(string s,int l,int r){if (lr) {jh.insert(s);return;}for (int il;ir;i){func(s,l,i);func(s,i1,r);string temps.substr(0,l)s.substr(i1,r-i)s.substr(l,i-l1)s.substr(r1,s.size()-1-r);func(temp,l,lr-i-1);func(temp,r-il,r);}}
};TLE(一个较合适的思路)
class Solution {
public:bool isScramble(string s1, string s2) {if (s1s2) return true;if (check(s1,s2)) return false;for (int i1;is1.size();i){string as1.substr(0,i),bs1.substr(i);string cs2.substr(0,i),ds2.substr(i);if (isScramble(a,c) and isScramble(b,d)) return true;string es2.substr(0,s1.size()-i),fs2.substr(s1.size()-i);if (isScramble(a,f) and isScramble(b,e)) return true;}return false;}bool check(const string s1,const string s2){int lb[26] {};for (int i0;is1.size();i)lb[s1[i]-a]1;for (int i0;is2.size();i)lb[s2[i]-a]-1;for (int i0;i26;i)if (lb[i]!0) return true;return false;}
};AC(刚上手就放弃的屑) temp[i][j][k]从s1[i]开始k个字符从s2[j]开始k个字符是否互为扰乱串呢。(包括下标本身字符)。if (temp[i][j][len]!0) return temp[i][j][len]1;是关键这句删除就是上面那种解法。
class Solution {
public:vectorvectorvectorint temp;string string1,string2;int n;bool isScramble(string s1,string s2) {if (s1.size()!s2.size()) return false;string1s1;string2s2;ns1.size();temp.resize(n,vectorvectorint (n,vectorint (n1,0)));return dfs(0,0,n);}bool dfs(int i,int j,int len){if (temp[i][j][len]!0) return temp[i][j][len]1;string astring1.substr(i,len),bstring2.substr(j,len);if (ab){temp[i][j][len]1;return true;}if (check(a,b)){temp[i][j][len]-1;return false;}for (int k1;klen;k) {if (dfs(i,j,k) and dfs(ik,jk,len-k)){temp[i][j][len]1;return true;}if (dfs(i,jlen-k,k) and dfs(ik,j,len-k)){temp[i][j][len]1;return true;}}temp[i][j][len]-1;return false;}bool check(const string s1,const string s2){int lb[26] {};for (int i0;is1.size();i)lb[s1[i]-a]1;for (int i0;is2.size();i)lb[s2[i]-a]-1;for (int i0;i26;i)if (lb[i]!0) return true;return false;}
};97. 交错字符串
MLE(第一反应还是暴搜)
class Solution {
public:string string1,string2;unordered_setstring jh;bool isInterleave(string s1, string s2, string s3) {if (s1.size()s2.size()!s3.size()) return false;string1s1;string2s2;string string3;func(0,0,string3);return jh.find(s3)!jh.end();}void func(int l1,int l2,string s){if (l1string1.size())func(l11,l2,sstring1[l1]);if (l2string2.size())func(l1,l21,sstring2[l2]);if (l1string1.size() and l2string2.size())jh.insert(s);}
};TLE(优化一下怎么还是没有过啊我要疯了)
class Solution {
public:string string1,string2,string3;unordered_setstring jh;bool isInterleave(string s1, string s2, string s3) {if (s1.size()s2.size()!s3.size()) return false;string1s1;string2s2;string3s3;string string4;func(0,0,string4);return jh.find(s3)!jh.end();}void func(int l1,int l2,string s){if (l1string1.size() and string1[l1]string3[s.size()])func(l11,l2,sstring1[l1]);if (l2string2.size() and string2[l2]string3[s.size()])func(l1,l21,sstring2[l2]);if (l1string1.size() and l2string2.size())jh.insert(s);}
};TLE(继续优化真是过不了一点啊最后一点真是可恶受不了了)
class Solution {
public:string string1,string2,string3;bool flagfalse;bool isInterleave(string s1, string s2, string s3) {if (s1.size()s2.size()!s3.size()) return false;string1s1;string2s2;string3s3;func(0,0);return flag;}void func(int l1,int l2){if (!flag){if (l1string1.size() and string1[l1]string3[l1l2])func(l11,l2);if (l2string2.size() and string2[l2]string3[l1l2])func(l1,l21);if (l1string1.size() and l2string2.size())flagtrue;}}
};AC(嗨嗨嗨导这么久了终于给我导出来了) temp[i][j]从s1[i]开始剩余字符从s2[j]开始剩余字符能否组成剩余部分。(包括下标本身字符)
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;}
};375. 猜数字大小II
AC(题都没有读懂的屑 temp[l][r]区间(l,r)的最小花费。
class Solution {
public:vectorvectorint temp;int getMoneyAmount(int n) {temp.resize(n5,vectorint (n5,0));return dfs(1,n);}int dfs(int l,int r){if (lr) return 0;if (temp[l][r]!0) return temp[l][r];int resultINT_MAX;for (int il;ir;i){int result_tempmax(dfs(l,i-1),dfs(i1,r))i;resultmin(result,result_temp);}temp[l][r]result;return result;}
};403. 青蛙过河
AC(不看题解也能做啦) cache[now][next]从第0个石头开始走now石头到next石头是否能够到达终点。
class Solution {
public:vectorint lb;vectorvectorint cache;bool canCross(vectorint stones) {if (stones[1]!1) return false;lbstones;cache.resize(stones.size(),vectorint (stones.size(),0));return dfs(0,1);}bool dfs(int now,int next){if (nextlb.size()-1) return true;if (cache[now][next]!0) return cache[now][next]1;vectorint temp;int stepslb[next]-lb[now];for (int inext1;ilb.size();i){if (lb[i]lb[next]steps-1) temp.push_back(i);if (lb[i]lb[next]steps) temp.push_back(i);if (lb[i]lb[next]steps1) temp.push_back(i);if (lb[i]lb[next]steps2) break;}for (int i0;itemp.size();i)if (dfs(next,temp[i])){cache[next][temp[i]]1;return true;}else cache[next][temp[i]]-1;return false;}
};464. 我能赢吗
超标超标还是超标。 这里共有三个关键 首先就是思路问题我有一个错的思路不论我去选择什么最终结果我都能赢。这种想法不正确的(例如输入样例4、6。只要先手去选择1后手无论怎么选择先手全部情况能赢。但是按照错误思路先手如果去选择4那么先手必然会输。)。也就是说选手只会选择成功最佳方案。 WA
class Solution {
public:int num1,num2;unordered_setint jh;bool canIWin(int maxChoosableInteger, int desiredTotal) {if ((1maxChoosableInteger)*maxChoosableInteger/2desiredTotal) return false;num1maxChoosableInteger;num2desiredTotal;for (int i1;imaxChoosableInteger;i) jh.insert(i);return dfs(0,0);}bool dfs(int times,int scores){int iter0,lengthjh.size();int * lbnew int [length];for (auto zzjh.begin();zz!jh.end();zz){lb[iter]*zz;iter1;}for (int i0;ilength;i){if (scoreslb[i]num2){if (times%20) continue;delete [] lb;return false;}jh.erase(lb[i]);if (!dfs(times1,scoreslb[i])) {delete [] lb;return false;}jh.insert(lb[i]);}delete [] lb;return true;}
};所以正确思路应是我的对手十分强大我选择数必须保证对手必须全部输掉否则那么不选这数继续进行下次循环循环结束如没找到那么我就不能够赢。 TLE
class Solution {
public:int num1,num2;unordered_setint jh;bool canIWin(int maxChoosableInteger, int desiredTotal) {if ((1maxChoosableInteger)*maxChoosableInteger/2desiredTotal) return false;num1maxChoosableInteger;num2desiredTotal;for (int i1;imaxChoosableInteger;i) jh.insert(i);return dfs(0,0);}bool dfs(int times,int scores){int iter0,lengthjh.size();int * lbnew int [length];for (auto zzjh.begin();zz!jh.end();zz){lb[iter]*zz;iter1;}for (int i0;ilength;i){jh.erase(lb[i]);if (scoreslb[i]num2) {jh.insert(lb[i]);delete [] lb;return true;}if (!dfs(times1,scoreslb[i])) {jh.insert(lb[i]);delete [] lb;return true;}jh.insert(lb[i]);}delete [] lb;return false;}
};暴力我们写出来了我们该写记忆搜索。但是我们发现由于使用集合并不好写所以第二关键就是必须换种存储方式。 TLE
class Solution {
public:int num1,num2,x1;bool canIWin(int maxChoosableInteger, int desiredTotal) {if ((1maxChoosableInteger)*maxChoosableInteger/2desiredTotal) return false;num1maxChoosableInteger;num2desiredTotal;x(xmaxChoosableInteger)-1;return dfs(0,0);}bool dfs(int times,int scores){for (int i1;inum1;i){if (((1(i-1))x)0) continue;x-(1(i-1));if (scoresinum2) {x(1(i-1));return true;}if (!dfs(times1,scoresi)) {x(1(i-1));return true;}x(1(i-1));}return false;}
};第三关键记忆搜索 AC
class Solution {
public:int num1,num2,x1;vectorint lb;bool canIWin(int maxChoosableInteger, int desiredTotal) {if ((1maxChoosableInteger)*maxChoosableInteger/2desiredTotal) return false;num1maxChoosableInteger;num2desiredTotal;x(xmaxChoosableInteger)-1;lb.resize(1maxChoosableInteger,0);return dfs(0,0);}bool dfs(int times,int scores){if (lb[x]!0) return lb[x]1;for (int i1;inum1;i){if (((1(i-1))x)0) continue;x-(1(i-1));if (scoresinum2) {x(1(i-1));lb[x]1;return true;}if (!dfs(times1,scoresi)) {x(1(i-1));lb[x]1;return true;}x(1(i-1));}lb[x]-1;return false;}
};494. 目标和
直接暴力 AC
class Solution {
public:int num,result0;vectorint lb;int findTargetSumWays(vectorint nums, int target) {numtarget;lbnums;dfs(0,0);return result;}void dfs(int begin,int count){if (beginlb.size()){if (countnum) result1;return;}dfs(begin1,countlb[begin]);dfs(begin1,count-lb[begin]);}
};552. 学生出勤记录II
首先暴力 TLE
class Solution {
public:int mod1e97;int checkRecord(int n) {return dfs(n,0,0)%mod;}int dfs(int n,int A,int P){if (n0) return 1;int count0;if (A0) count(countdfs(n-1,1,0))%mod;if (P1) count(countdfs(n-1,A,P1))%mod;count(countdfs(n-1,A,0))%mod;return count;}
};记忆搜索 AC
class Solution {
public:vectorvectorvectorint lb;int mod1e97;int checkRecord(int n) {lb.resize(n,vectorvectorint (2,vectorint (3,0)));return dfs(n,0,0)%mod;}int dfs(int n,int A,int P){if (n0) return 1;if (lb[n-1][A][P]!0) return lb[n-1][A][P];int count0;if (A0) count(countdfs(n-1,1,0))%mod;if (P1) count(countdfs(n-1,A,P1))%mod;count(countdfs(n-1,A,0))%mod;lb[n-1][A][P]count;return count;}
};576. 出借的路径数
首先暴力 TLE
class Solution {
public:int length,width,mod1e97;int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {lengthm,widthn;int count0;for (int i1;imaxMove;i)count(countdfs(i,startRow,startColumn))%mod;return count;}int dfs(int times,int x,int y){if (times0){if (x-1 or xlength or y-1 or ywidth) return 1;return 0;}if (x-1 or xlength or y-1 or ywidth) return 0;int count0;if (x0) count(countdfs(times-1,x-1,y))%mod;if (xlength) count(countdfs(times-1,x1,y))%mod;if (y0) count(countdfs(times-1,x,y-1))%mod;if (ywidth) count(countdfs(times-1,x,y1))%mod;return count;}
};记忆搜索 wc超时了怎么办怎么办哎呦你干嘛啊 TLE
class Solution {
public:int length,width;vectorvectorvectorint lb;int mod1e97;int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {lengthm,widthn;lb.resize(maxMove,vectorvectorint (m,vectorint (n,0)));int count0;for (int i1;imaxMove;i)count(countdfs(i,startRow,startColumn))%mod;return count;}int dfs(int times,int x,int y){if (times0){if (x-1 or xlength or y-1 or ywidth) return 1;return 0;}if (x-1 or xlength or y-1 or ywidth) return 0;if (lb[times-1][x][y]!0) return lb[times-1][x][y];int count0;if (x0) count(countdfs(times-1,x-1,y))%mod;if (xlength) count(countdfs(times-1,x1,y))%mod;if (y0) count(countdfs(times-1,x,y-1))%mod;if (ywidth) count(countdfs(times-1,x,y1))%mod;lb[times-1][x][y]count;return count;}
};我寻思这时间复杂度也不高也就 5 0 3 50^3 503。 破大防了C(传)T(统)M(美)D(德)。
