给你一个由小写英文字母和 .
组成的字符串 SS 。请找出从 SS 中删除所有 .
后得到的字符串。
创建一个字符串来存储输入信息,在再创建一个字符串来存储除字符.
外的所有字符。
#include <iostream>
#include <string>
using namespace std;
int main()
{
string s;
cin >> s;
string ans;
for (int i = 0; i < s.size(); ++i) {
if (s[i] != '.') {
ans += s[i];
}
}
cout << ans;
return 0;
}
给你一个正整数
。求满足以下所有条件的正整数
和非负整数序列
:
可以证明,在约束条件下,总是存在至少一对满足条件的
和
。
因为M一定是由许多不同的3的幂得到的,也就说明了M一定是3的倍数,然后我们又可以知道,3的1次方会等于,3个3的0次方,以此往后类推,我们就可以得到,3的n次方会等于3个3的n-1次方。这就告诉了我们应该尽量去求3的高次幂,也就是贪心,我们从3的高次幂来往前推。 如果M可以由这个3的幂组成,就把该幂次存入数组。反之就降低幂次。
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int m;
int main()
{
cin >> m;
//N [1,20];
//a [0,10]
//逆向思维
int num = m;
int ans_n = 0;
vector<int> ans_v;
int x = 10;
while (num > 0) {
int tmp = num - pow(3, x);
if (tmp >= 0){
ans_n += 1;
ans_v.push_back(x);
num = tmp;
}
else {
if(x!=0)
x -= 1;
}
}
//因为我们是从后往前求,所以需要逆置一下
reverse(ans_v.begin(), ans_v.end());
cout << ans_n << endl;
for (int i = 0; i < ans_v.size(); ++i) {
cout << ans_v[i] << ' ';
}
return 0;
}
给你一个长度为
的字符串
。同时还给了你
个查询,你应该按顺序处理这些查询。
-th 查询如下:
和一个字符
,用
替换
中的
-th 字符。然后,打印字符串 ABC
作为子串出现在
中的次数。
这里,
的子串是指从
的开头删除零个或多个字符,从结尾删除零个或多个字符后得到的字符串。
例如,ab
是abc
的子串,但ac
不是abc
的子串。
因为要求的是字串而且还固定了,那么求子串的操作就很简单了。直接遍历字符串,每次往取3个字符进行比较就可以了,这样的话,我们就求出了最初版本的字串数量num
了。
不过这题的重点肯定不是求字串。因为字符串每次都会变一个字符,每次都重新求的话,程序会超时的。为了防止超时,肯定要做一些策略。
可以知道的是,每一次都只会改变一个,那么这个字符影响的范围就固定了,取极限情况,该字符会影响的范围,只要它的前两个字符和后两个字符。也就是说,加上自己该字符会影响5个字符的范围,为此我们每次只需要检查这5个字符。如果改变字符导致目标子串出现j就让num+1
,反之num-1
,就考虑到越界情况,加个判断就可以了。
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int n, t;
int func(string& s, const string& tmp) {
int ans = 0;
for (int i = 0; i < n; ++i) {
if (s.substr(i, 3) == tmp) {
ans += 1;
}
}
return ans;
}
int main()
{
cin >> n >> t;
string s;
cin >> s;
int num = func(s, "ABC");
while (t--) {
int x;
char c;
string tmp = s;
cin >> x;
x -= 1;
cin >> c;
s[x] = c;
for (int i = 0; i <= 2 && x - i >= 0; ++i) {
if (s.substr(x - i, 3) == "ABC" && tmp.substr(x - i, 3) != "ABC") {
num += 1;
}
else if (s.substr(x - i, 3) != "ABC" && tmp.substr(x - i, 3) == "ABC") {
num -= 1;
}
}
for (int i = 1; i <= 2 && x + i < n; ++i) {
if (s.substr(x + i, 3) == "ABC" && tmp.substr(x + i, 3) != "ABC") {
num += 1;
}
else if (s.substr(x + i, 3) != "ABC" && tmp.substr(x + i, 3) == "ABC") {
num -= 1;
}
}
cout << num << endl;
}
return 0;
}
有
幢楼房,依次为
幢、
幢、
幢、
幢。
号楼的高度为
。
的高度为
.。
求每个
的整数
的个数。
满足下列条件:
和
之间没有比建筑物
高的建筑物。
要求为建筑物i和j间没有比建筑物j高的建筑物数量(不包括i),为此我们可以用单调栈来解决问题。创建一个栈,从后往前遍历数组,不过是从倒数第2个元素开始,因为最后一个元素对应的值一定是0。但是我们比较时要让i+1
。
这样的话,算法的逻辑就出来了,当栈不为空时,就循环比较,如果栈顶元素小于v[i+1]
就出栈。如此一来就可以保证i到j内的数没有比v[j]大的元素
。循环结束后要让v[i+1]
入栈,因为出了最后一个元素,其他的每个元素保底都有一个相邻的元素满足条件。最后每个v[i]
对应的答案就是当前栈中元素的个数。
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> v(n+1);
for (int i = 1; i <= n; ++i) {
cin >> v[i];
}
//要求为建筑物i和j间没有比建筑物j高的建筑物数量
//单调栈?
stack<int> st;
vector<int> ans(n + 1);
for (int i = n - 1; i >= 1; --i) {
while (!st.empty() && v[st.top()] < v[i + 1]) {
st.pop();
}
st.push(i + 1);
ans[i] = st.size();
}
for (int i = 1; i <= n; ++i) {
cout << ans[i]<<' ';
}
return 0;
}