建设银行 上海 招聘网站,深圳市建设工程造价管理站官网,河北省保定市唐县城乡建设网站,苏州网站制作电话647. 回文子串
力扣题目链接 如果s【i】和s【j】相同
dp【i1】【j-1】也是回文串的话 #xff08;等于true#xff09;
那么dp【i】【j】也是回文串 true
定义一个bool二维数组
遍历顺序是从下到上 从左到右
因为dp【i】【j】是通过dp【i1】【j-1】推出来的
i从最后一…647. 回文子串
力扣题目链接 如果s【i】和s【j】相同
dp【i1】【j-1】也是回文串的话 等于true
那么dp【i】【j】也是回文串 true
定义一个bool二维数组
遍历顺序是从下到上 从左到右
因为dp【i】【j】是通过dp【i1】【j-1】推出来的
i从最后一个开始 j从i开始 因为【ij】
j保持大于等于i
class Solution {
public:int countSubstrings(string s) {vectorvectorbool dp(s.size(), vectorbool(s.size(), false));int result 0;for (int i s.size() - 1; i 0; i--) { // 注意遍历顺序for (int j i; j s.size(); j) {if (s[i] s[j]) {if (j - i 1) { // 情况一 和 情况二result;dp[i][j] true;} else if (dp[i 1][j - 1]) { // 情况三result;dp[i][j] true;}}}}return result;}
}; 739. 每日温度
力扣题目链接 找到这个元素右边第一个比他大的元素
单调栈构造出一个单调底层栈
先把第一个元素的下标放进栈
然后for循环从第二个元素开始
如果这个数小于等于栈顶元素 就把这个数的下表放进栈
如果这个数大于栈顶元素
就说明这个元素是第一个比栈顶元素大的数
用result记录一下 把栈顶元素pop掉 while继续与下一个栈顶元素比较
最后把这个数放入栈
class Solution {
public:vectorint dailyTemperatures(vectorint T) {// 递增栈stackint st;vectorint result(T.size(), 0);st.push(0);for (int i 1; i T.size(); i) {if (T[i] T[st.top()]) { // 情况一st.push(i);} else if (T[i] T[st.top()]) { // 情况二st.push(i);} else {while (!st.empty() T[i] T[st.top()]) { // 情况三result[st.top()] i - st.top();st.pop();}st.push(i);}}return result;}
}; 精简版
class Solution {
public:vectorint dailyTemperatures(vectorint T) {stackint st; // 递增栈vectorint result(T.size(), 0);for (int i 0; i T.size(); i) {while (!st.empty() T[i] T[st.top()]) { // 注意栈不能为空result[st.top()] i - st.top();st.pop();}st.push(i);}return result;}
}; 42. 接雨水
力扣题目链接 单调栈
先把第一数的下标存进去
for循环从第二个数开始
如果小于栈顶元素 就push进栈
如果等于栈顶元素 把之前的数pop出去 新的数push进来
如果大于栈顶元素 说明找到凹槽了 可以接雨水了
while循环可能会形成并计算计算多个凹槽
首先记录一下槽的底部 也就是栈顶
然后把栈顶pop出去 新的栈顶就是槽的左边 现在的i是槽的右边
因为要接雨水 要在左边和右边选一个矮的高度再减去槽底的高度 就是雨水的高
槽的右边减去槽的左边再减1就是槽的宽度
宽乘高就是雨水的体积 再进行累加即可
class Solution {
public:int trap(vectorint height) {if (height.size() 2) return 0; // 可以不加stackint st; // 存着下标计算的时候用下标对应的柱子高度st.push(0);int sum 0;for (int i 1; i height.size(); i) {if (height[i] height[st.top()]) { // 情况一st.push(i);} if (height[i] height[st.top()]) { // 情况二st.pop(); // 其实这一句可以不加效果是一样的但处理相同的情况的思路却变了。st.push(i);} else { // 情况三while (!st.empty() height[i] height[st.top()]) { // 注意这里是whileint mid st.top();st.pop();if (!st.empty()) {int h min(height[st.top()], height[i]) - height[mid];int w i - st.top() - 1; // 注意减一只求中间宽度sum h * w;}}st.push(i);}}return sum;}
};
