day38.动态规划+MySql数据库复习

844.比较含退格的字符串

给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。

注意：如果对空文本输入退格字符，文本继续为空

思路:定义两个栈，将字符加入栈中，遇到#就弹出栈最后比较栈中剩余元素是否相同

class Solution {//可以直接用栈来比较大小
public:bool backspaceCompare(string s, string t) {stack<char> st1;stack<char> st2;for(char c:s){if(c=='#'&&!st1.empty()){st1.pop();}else if(c!='#'){st1.push(c);}}for(char m:t){if(m=='#'&&!st2.empty()){st2.pop();}else if(m!='#'){st2.push(m);}}while (!st1.empty() &&!st2.empty()) {if (st1.top()!= st2.top()) {return false;}st1.pop();st2.pop();}return st1.empty()&&st2.empty();}
};

322.零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

思路:完全背包问题先遍历物品在遍历背包

class Solution {
public:int coinChange(vector<int>& coins, int amount) {vector<int> dp(amount+1,INT_MAX);int maxNum=INT_MAX;int res=0;dp[0]=0;for(int i=0;i<coins.size();i++){for(int j=coins[i];j<=amount;j++){if (dp[j - coins[i]] != INT_MAX) { // 如果dp[j - coins[i]]是初始值则跳过dp[j] = min(dp[j - coins[i]] + 1, dp[j]);}}}if (dp[amount] == INT_MAX) return -1;return dp[amount];}
};

279.完全平方数

给你一个整数 n ，返回和为 n 的完全平方数的最少数量。

完全平方数是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

思路:同样是完全背包问题由于是求完全平方所以第二个for循环要改成j*j的形式

class Solution {
public:int numSquares(int n) {//dp[j]代表完全平方数的最少数量vector<int> dp(n+1,INT_MAX);dp[0]=0;for(int i=0;i<=n;i++){//要凑的背包for(int j=1;j*j<=i;j++){//用来凑背包的物品dp[i]=min(dp[i-j*j]+1,dp[i]);}}return dp[n];}
};

139.单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

思路:

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> wordSet(wordDict.begin(), wordDict.end());vector<bool> dp(s.size() + 1, false);dp[0]=true;for(int i=1;i<=s.size();i++){//背包for(int j=0;j<i;j++){//物品string word=s.substr(j,i-j);if(wordSet.find(word)!=wordSet.end()&&dp[j]){dp[i]=true;}}}return dp[s.size()];}
};