@toc
:green_heart: 认真付出，是对自己的祝福，温暖守护美好生活之路，进步与你同步，每一天全情投入，累积一些小幸福，就这样稳稳地一步一步~
正文开始@一个人的乐队
Day01
1. 组队竞赛
题目字儿挺多，总结成一句话就是“使中位数之和最大”。
首先排序，这是个人都知道；既然不管多少组，每组都是3个人，那么这个中位数的位置是很固定的，那如何保证每次都取到次大的呢？那就是尽量往后取。
它们的下标？画画图，取n组。
" title="">
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
int n = 0;
cin >> n;
vector<int> a;
a.resize(3*n);
for(size_t i = 0;i < n*3; i++)
{
cin>>a[i];
}
sort(a.begin(),a.end());
long long sum = 0;
for(size_t i = 1; i<= n; i++)
{
sum += a[a.size()-2*i];
}
cout << sum << endl;
return 0;
}注意的是sum类型要给long long，否则有的测试用例数字非常大会溢出，这个要有经验，我在颜神博客里看到了哈哈。。
2. 删除公共字符
题目链接：删除公共字符_好未来笔试题_牛客网 (nowcoder.com)
首先想到的暴力双循环遍历，erase删除，效率较低不说，它还涉及迭代器失效问题(vector的模拟实现有仔细说过)。
我们固然可以根据底层逻辑，修改下标，以应对连续有“待删除字符”这样的状况，比如 ——
Theey are students. //结巴时候的我(但你不应该这样做，事实上，在Java中这边用迭代器遍历边erase的行为会直接抛异常。
你这样勉强做出来的破想法，面试时候可就寄了。。。但我就是拿它过的(
#include<string>
#include<iostream>
using namespace std;
int main()
{
string s1;
string s2;
getline(cin, s1);
getline(cin, s2);
size_t i = 0;
for( i= 0;i< s1.size();i++)
{
for(auto e: s2)
{
if(s1[i] == e)
{
s1.erase(i,1);
i--;
break;
}
}
}
cout << s1;
return 0;
}
所以采取哈希映射(256个字符，直接映射) 来改进 ——
- 标记待删除的字符：先遍历s2字符串，若出现则在hash中进行记录(++)
- 拼接想要的字符：遍历s1，找到当中是0(s2中不存在的)的字符，就是我们想要的，拼接。
#include<iostream>
#include<string>
using namespace std;
int main()
{
string s1;
string s2;
string s;
getline(cin, s1);
getline(cin, s2);
int hash[256] = {0};
// 1.遍历str2，记录相应字符
for(auto e : s2)
{
hash[e]++;
}
// 2.拼接想要的字符
for(auto e : s1)
{
if(hash[e] == 0)
s += e;
}
cout << s << endl;
return 0;
}Day02
1. 排序子序列
列举一些情况 ——
1 2 3 3 4 5 8 8 非递减排列
9 8 7 7 6 5 5 2 1 非递增序列思路，一共分两类情况讨论 ——
<和>：判断a[i]和a[i+1]大小关系，以判断即将进入非递减/非递增序列；一旦跳出循环，就表示又检测到一个子序列，还需要i++，再检测下一个序列- 我们把
=单拎出来，是因为不增不减可以属于任意子序列，不会影响count，i只管向后迭代++
这种循环套循环时，常常要注意内层仍需要限制迭代范围，比如对于否则遇到单增序列1234567，i便会如脱缰野马越界访问。
然而内层限制了i < n仍会发生越界访问(牛客并没有检查出来，但处理起来是真的头疼 。处理方式是resize多开一个空间，默认值是0（题目限制了数据范围刚好是正整数），就，没影响，这nm谁能想到啊(
#include<iostream>
#include<vector>
using namespace std;
int main()
{
int n = 0;
cin >> n;
vector<int> v;
v.resize(n+1);
for(size_t i = 0; i < n; i++)
{
cin >> v[i];
}
int i = 0;
int count = 0;
while(i < n)
{
if(v[i]<v[i+1])
{
while(i < n && v[i]<=v[i+1])
{
i++;
}
i++;
count++;
}
else if(v[i]==v[i+1])
{
i++;
}
else
{
while(i < n && v[i]>=v[i+1])
{
i++;
}
i++;
count++;
}
}
cout << count << endl;
return 0;
}2. 倒置字符串 单词不倒
题目链接：倒置字符串__牛客网 (nowcoder.com)
思路
- 先逆置整个字符串（调用算法库中的reverse，迭代器区间，左闭右开）
- 再逆置字符串中的单词
这题要思考的就是边界了，是很经典的题目。
"I like beijing."
—————— 逆置 ———————
".gnijieb ekil I"
—— 逆置其中的单词 ——
"beijing. like I"题解 ——
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
string s;
getline(cin,s);
// 1.逆置整个字符串
reverse(s.begin(),s.end());
// 2.逆置字符串中的单词
string::iterator left, right;
left = right = s.begin();
while(left != s.end())
{
while(right != s.end() && *right != ' ')
{
right++;
}
reverse(left,right);
if(right != s.end())
{
right++;
left = right;
}
}
cout << s << endl;
return 0;
}注意限制迭代范围时，<并不符合一般迭代器的含义，虽然这儿用没问题，但最好用!=。
Day03
1. 输出字符串中连续最长数字串
题目链接：字符串中找出连续最长的数字串_牛客网 (nowcoder.com)
我们通过打擂台的方式寻找最长数字串儿，设置两个字符串cur&res ——
cur用来记录数字串- 当遇到字母时，说明这个数字串儿结束。若
cur串儿比res串儿长，则替换它。
#include<iostream>
#include<string>
using namespace std;
int main()
{
string s;
cin >> s;
string cur;
string res;
for(auto e: s)
{
if(e>= '0' && e<='9')
{
cur += e;
}
else
{
if(cur.size() > res.size())
res = cur;
cur.clear();
}
}
if(cur.size() > res.size())
res = cur;
cout << res << endl;
return 0;
}当str字符串不以字母结尾时，是没刷cur串儿中的内容到res的，所以在外面还要再刷一下。
2. 数组中出现次数超过一半的数字
题目链接：数组中出现次数超过一半的数字_牛客网 (nowcoder.com)
法一：直接映射，统计numbers中每个元素出现次数。但这其实浪费蛮多空间的，而且开数组空间时候，取大小也算投机取巧了...
时间复杂度：O(N)，空间复杂度：O(N)
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
vector<int> v(10001);//统计数字出现次数
for(auto e: numbers)
{
v[e]++;
}
int i = 0;
for(i = 0; i <= 10000; i++ )
{
if(v[i] > numbers.size()/2)
break;
}
return i;
}
};法二：时间复杂度O(nlogn)，空间复杂度O(1)
- 排序后，众数一定会出现在数组的中间位置
本题目限制了题目有解，否则对于[1, 2, 3, 4, 5]这样无解的数组，需要再次遍历数组，计数确认
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
if(numbers.empty())
return 0;
sort(numbers.begin(), numbers.end());
int result = numbers[numbers.size()/2];
//计数确认
int count = 0;
for(auto e:numbers)
{
if(result == e)
count++;
}
if(count > numbers.size()/2)
return result;
else
return 0;
}
};:heart: 法三：时间复杂度O(n)，空间复杂度O(1)，效率最好，所以你最好，哦不能你应该写出来这个。。
- 如果两个众数不相等，就消去这两个数。最坏情况下，每次删去一个众数&一个非众数
- 由于众数一定大于数组的长度的一半，那么最后留下来的数一定是众数
:star: 这思路也不难，难点在于如何消去...
我们用result表示目标数字，用times来记录当前数字出现次数，抵消就是通过改变times完成的。初始默认result是第一个元素，times相应为1。
- 若当前数字
times不等于0，则与下一个数字比较。若不同，则抵消，times--；若相同，则++ - 若当前数字
times等于0，说明此时前面的数字都被抵消了，那就把当前数字给result，接着检测下面的数字
这nm谁能想到啊( 慢慢积累吧~ 两个月我又忘了。。我现在又想起来了。建议走读代码。
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
if(numbers.empty())
return 0;
int result = numbers[0];
int times = 1;
for(size_t i = 1; i < numbers.size(); i++)
{
if(times != 0)
{
if(result != numbers[i])
{
// 消去
times--;
}
else
{
times++;
}
}
else
{
result = numbers[i];
times = 1;
}
}
return result;
}
};Day04
1. 计算糖果
经观察发现B可由两种方式解出，这就是“是否有解”的突破口。
#include<iostream>
using namespace std;
int main()
{
int m,n,p,q;
cin >> m >> n >> p >> q;
int A,B1,B2,C;
A = (m+p)/2;
B1 = (p-m)/2;
B2 = (n+q)/2;
C = (q-n)/2;
if(B1 == B2)
cout << A << " " << B1 << " " << C << endl;
else
cout << "No" << endl;
return 0;
}
2. 进制转换
题目链接：进制转换_滴滴笔试题_牛客网 (nowcoder.com)
- 涉及在十六进制时，用A表示10等等。我们用一个字符串来存放[ 0123456789ABCDEF ] (谁也不要像我一样傻了吧唧的还去计算10和字符'A'的关系 /秃头
- 由于有字母，用字符串儿
s来拼接转换后的数字
是的，这样的话思路一点都不难，毕竟这题在C语言那儿都练烂了。。糟糕的是你笔试的时候对于M == 0或者M < 0这样的情况能不能考虑到，不能AC还一头雾水，首先怀疑自己的主体逻辑，这就不好了。。
- 如果是负数，先转成正数处理。
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
string s;
string table = "0123456789ABCDEF";
int M,N;
cin >> M >> N;
if(M ==0)
cout << 0 <<endl;
// 处理负数
bool flag = false;
if(M < 0)
{
M = -M;
flag = true;
}
while(M)
{
s += table[M%N];
M /= N;
}
if(flag)
{
s += '-';
}
reverse(s.begin(),s.end());
cout << s << endl;;
return 0;
}Day05
1. 统计回文
- 遍历插入
- 判断是否是回文串儿 - 逆置，进行字符串比较
为了不破坏原串儿，要都拷贝构造一份。
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
//判断是否是回文串
bool isReverse(string& s)
{
string rev(s);
reverse(rev.begin(), rev.end());
return rev == s;
}
int main()
{
string A;
string B;
getline(cin, A);
getline(cin, B);
int count = 0;
for (size_t i = 0; i <= A.size(); i++)
{
string s(A);
s.insert(i, B);
//cout << s << endl;
if (isReverse(s))
count++;
}
cout << count << endl;
return 0;
}2. 连续子数组最大和
题目链接：连续最大和_牛客题霸_牛客网 (nowcoder.com)
最简单的动规。时间复杂度O(N)
状态方程式: max(dp[i]) = getMax(max(dp[i-1])+arr[i], arr[i])状态：其中dp[i]表示以i结尾的子数组.
每次加入一个数字有两种情况：原最大子数组和 + a[i]更大 或 a[i] 本身更大。
举例画图说明整个过程 ——
" title="">
#include<iostream>
#include<vector>
using namespace std;
int getMax(int a,int b)
{
return a>b?a:b;
}
int main()
{
int n = 0;
cin >> n;
vector<int> a;
a.resize(n);
for (size_t i = 0; i<n; i++)
{
cin >> a[i];
}
int sum = a[0];
int max = a[0];
for (size_t i = 0; i < n; i++)
{
sum = getMax(sum+a[i], a[i]);
if(sum > max)
max = sum;
}
cout << max << endl;
return 0;
}
咱就是说我连最简单的动规都把握不住。。还得多积累啊！
注意初始状态要给v[0]，我开始是没大注意，姑且认为我还没抓到DP的精髓吧。。
-1 -2 -3 -4 -5 -6 -7 -8 -9Day06
1. 欧几里得摆蛋糕
题目链接：不要二_牛客题霸_牛客网 (nowcoder.com)
所谓的欧几里得距离(欧氏距离)，即两点间的实际距离。
$$ (x1-x2)^2 + (y1-y2)^2 = 2 $$
两蛋糕的欧氏距离不能为2，如果从左上角开始遍历，即下2和右2处不能摆蛋糕。
我们先把二维数组初始化为1，遍历数组，不能摆蛋糕的地方则标记为0.
#include<iostream>
#include<vector>
using namespace std;
int main()
{
int W,H;
cin >> W >> H;
vector<vector<int>> a(W);
for(size_t i = 0;i < W; i++)
{
a[i].resize(H,1);
}
int count = 0;
for(size_t i = 0; i < W;i++)
{
for(size_t j = 0;j < H;j++)
{
if(a[i][j] == 1)
{
count++;
// 标记不能摆蛋糕
if(i+2 < W)
a[i+2][j] = 0;
if(j+2 < H)
a[i][j+2] = 0;
}
}
}
cout << count << endl;
return 0;
}- 怎么初始化二维数组你得会。。
- 比起往上放蛋糕，这样“往下拿”更容易实现；边往下拿，边统计摆了多少个也挺巧。。
2. 字符串转整数
题目链接：把字符串转换成整数_牛客题霸_牛客网 (nowcoder.com)
相当于模拟实现 stoi，显然从str高位开始累加更简单：
"123" -> 123
1
1*10 + 2 = 12
12*10 + 3 = 123 题解 ——
class Solution {
public:
int StrToInt(string str) {
if(str.empty())
return 0;
// 处理最高位是符号位的情况
int i = 0;
if(str[0] == '+' || str[0] == '-')
{
i++;
}
int ret = 0;
for( ;i < str.size();i++)
{
if(str[i]>= '0' && str[i]<= '9')
ret = ret*10 + str[i]-'0';
else
return 0;
}
if(str[0] == '-')
ret = -ret;
return ret;
}
};解题周报持续更新中~
:purple_heart: 风尘仆仆我会化作天边的晚霞~
总结：DP咱还得练，还有比较巧的想法，比如，出现超过一半儿的数字这种最优的方法咱还得多开阔眼界。总之，刷题还是比较好玩的，每当我觉得好难的时候，我就想想颜神，然后说，我一定行耶~
