开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【解题周报】week1 解题周报@笔试强训 -> 正文阅读

[数据结构与算法]【解题周报】week1 解题周报@笔试强训

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

Day01

1. 组队竞赛

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

重点在于如何分组。排序后，每次都从尾取两个数，这样能保证每次都取到次大的。它们的下标？见下图。

#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 sum = 0;
    for(size_t i = 1; i<= n; i++)
    {
        sum += a[a.size()-2*i];
    }
    cout << sum << endl;
    
    return 0;
}

注意的是sum类型要给long，否则有的测试用例数字非常大会溢出。

2. 删除公共字符

题目链接：删除公共字符_好未来笔试题_牛客网 (nowcoder.com)

可以暴力双循环遍历，erase删除，当然效率较低。同时注意erase涉及迭代器失效问题(vector的模拟实现)。

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

思路，一共分两类情况讨论 ——

<和>，一旦判断出大小关系，就进入对应循环；一旦跳出循环，就表示又检测到一个子序列
我们把=单拎出来，是因为不增不减可以属于任意子序列，不会影响count，i只管向后迭代++

本题还需要注意的是，在进入对应循环进行迭代时，需要限制i的迭代范围，否则遇到单增序列1234567，i便会如脱缰野马越界访问。

然而在这里，限制了i < n仍会发生越界访问(牛客并没有检查出来)，处理方式是resize多开一个空间，默认值是0（题目限制了数据范围刚好是正整数），一切都刚刚好。

#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 = s.begin();
    while(left != s.end())
    {
        string::iterator right = left;
        while(right != s.end() && *right != ' ')
        {
            right++;
        }
        reverse(left,right);
        
        if(right != s.end())
            left = right+1;
        else
            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;
}

2. 数组中出现次数超过一半的数字

题目链接：数组中出现次数超过一半的数字_牛客网 (nowcoder.com)

法一：直接映射，统计numbers中每个元素出现次数。但这其实浪费蛮多空间的我也知道

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)

排序，众数一定会出现在数组的中间位置
(本题目限制了题目有解，否则对于12345这样无解的数组) 需要再次遍历数组，计数确认

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;
    }
};

?? 法三：时间复杂度O(n)，空间复杂度O(1)

如果两个众数不相等，就消去这两个数。最坏情况下，每次删去一个众数&一个非众数
由于众数一定大于数组的长度的一半，那么最后留下来的数一定是众数

?? 那么如何消去呢？

我们用result表示目标数字，用times来记录当前数字出现次数，抵消就是通过改变times完成的。初始默认result是第一个元素，times相应为1。

若当前数字times不等于0，则与下一个数字比较。若不同，则抵消，times–；若相同，则++
若当前数字times等于0，说明此时前面的数字都被抵消了，那就把当前数字给result，接着检测下面的数字

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)

#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来拼接转换后的数字

#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;
}

注意M可能是负数，需要先转正，最后记得添加’-’.

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]本身更大。举例画图说明整个过程 ——

#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);
	vector<int> sumArr;
	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;
}

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

"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;
    }
};