@toc

:green_heart: 认真付出，是对自己的祝福，温暖守护美好生活之路，进步与你同步，每一天全情投入，累积一些小幸福，就这样稳稳地一步一步~
正文开始@一个人的乐队

Day01

1. 组队竞赛

题目链接：组队竞赛__牛客网 (nowcoder.com)

题目字儿挺多，总结成一句话就是“使中位数之和最大”。

首先排序，这是个人都知道；既然不管多少组，每组都是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. 排序子序列

题目链接：排序子序列_牛客网 (nowcoder.com)

列举一些情况 ——

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. 计算糖果

题目链接：计算糖果__牛客网 (nowcoder.com)

经观察发现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. 统计回文

题目链接：统计回文__牛客网 (nowcoder.com)

• 遍历插入
• 判断是否是回文串儿 - 逆置，进行字符串比较

为了不破坏原串儿，要都拷贝构造一份。

#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 -9

Day06

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咱还得练，还有比较巧的想法，比如，出现超过一半儿的数字这种最优的方法咱还得多开阔眼界。总之，刷题还是比较好玩的，每当我觉得好难的时候，我就想想颜神，然后说，我一定行耶~