TX-C++-算法题

目录

• 竖读
• • 题目
  • 思路
  • 代码
• 质数下标
• • 题目
  • 思路
  • 代码
• 攻与防
• • 题目
  • 思路
  • 代码

竖读 题目

输入n行字符串数字（1<=n<=9）,字符串数字的长度范围为1-10^5.
请将每一列的数读出来，并从小到大排序后，以空格间隔输出。
示例1：
输入：
3
0123
1234
2345
输出：
12 123 234 245

思路

这比较基础，使用一个string储存字符串数字，然后遍历每一列计算出每一列的结果存到vector容器中

代码

#include
#include
#include
#include

using namespace std;

bool cmp(int a, int b)
{//返回true不交换，false交换
    return a < b;
}
vector<int> solve(int n, string s[])
{
    vector<int> res;
    int length = s[0].size(); //字串长度

    for (int i = 0; i < length; i++)
    {
        int res_t = 0;
        for (int j = 0; j < n; j++)
        {
            res_t = 10 * res_t + (s[j][i] - '0');
        }
        res.push_back(res_t);
    }
    //排序
    //sort(res, res +length); // 从小到大
    //sort(res.begin(), res.begin() + length, greater()); //从大到小
    sort(res.begin(), res.begin() + length, cmp); //从小到大
    return res;
}

//竖读
int main()
{
    int n; //输入数据的行数，也即结果的最大长度
    cin >> n;
    string s[n]; //保存每一行的数据
    for (int i = 0; i < n; i++)
        cin >>s[i];

    vector<int> res = solve(n, s);
    for (auto a : res)
        cout << a << ' ';
}

质数下标 题目

有一个长度为n的数组a，数组下标从1~n。每一次会将a中所有下标为非质数的元素进行删除，即a且i不为质数。在删除完之后，将数组a重新按顺序拼接起来。不断循环这个过程，直至数组a的大小为1。求这个数组最后剩下的那个元素的值是多少。
示例：
输入：
[1, 2, 3, 4]
输出：
3
解释:
第一次变成[2,3]
第二次变成[3]

思路

主要是质数的判断，不是质数，则删除该下标的值

方案1：当数组长度大于1时，循环从数组后向前寻找需要删除的数（在这每次都需要调用质数的判断），最后更新数组长度，继续删除直到数组长度为1
方案2：使用vector来保存需要删除的非质数下标，后面只需判断此时的下标是否在vector中，在则删除
方案3：将vector换成unordered_map(基于哈希表，查找速度快)来保存非质数。
方案4：可以用map来存下标和删除标志位的键值对比如（1，true）表示1位置需要删除。
vector和map， map和unordered_map

代码

#include
#include
#include
#include
#include
#include

using namespace std;

class Solution
{
public:

    bool judge(int n)
    {//判断质数，是返回ture，否者返回false
        if (1 == n) return false;
        for (int i = 2; i * i <= n; i++)
        {
            if (n % i == 0) return false;
        }
        return true;
    }
    int getNumber ( vector<int> & a)
    {
        int length = a.size();
        while(length > 1)
        {
            for (int i = length; i >= 1; i--)
            {
                if (!judge(i)) //每次都要判断是否是质数，感觉比较耗时，改进1中先用vector保存小于数组长度非质数的数
                    a.erase(a.begin() + i - 1);
            }
            length = a.size();
        }
        return a[0];
    }

    int getNumber1( vector<int> & a)
    {//改进1
        //现根据a数组的大小，计算出一个不是质数的集合(用的vector（查找不效率不高）)，方便后面删除数据
        int length = a.size();
        if (length == 1) return a[0];
        if (length == 2) return a[1];
        vector<int> nozs = {1}; //1不是质数, 其实用unordered_map来存会好查找一点
        for(int i = 3; i <= length; i++)
        {
            if (!judge(i)) nozs.push_back(i);
        }
        while (length > 1)
        {
            for (int i = length; i >= 1; i--)
            {//从后往前找
                auto it = find(nozs.begin(), nozs.end(), i); //看i是否在不是质数的集合中
                if (it == nozs.end()) //没找到就继续
                    continue;
                else //找到了就删除
                    a.erase(a.begin() + i -  1);
            }
            length = a.size(); //更新数组长度
        }
        return a[0];
    }

    int getNumber2( vector<int> & a)
    {//改进2
        //用unordered_map来存非质数
        int length = a.size();
        if (length == 1) return a[0];
        if (length == 2) return a[1];
        unordered_map<int, int> nozs = {{1,1}}; //1不是质数, 其实用unordered_map来存会好查找一点
        for(int i = 3; i <= length; i++)
        {
            if (!judge(i)) nozs[i] = i;
        }
        /*
        for(auto iter = nozs.begin(); iter != nozs.end(); iter++)
            cout<first<<" "<second<
        while (length > 1)
        {
            for (int i = length; i >= 1; i--)
            {//从后往前找
                auto it = nozs.find(i); //看i是否在不是质数的集合中
                if (it == nozs.end()) //没找到就继续
                    continue;
                else //找到了就删除
                    a.erase(a.begin() + i -  1);
            }
            length = a.size(); //更新数组长度
        }
        return a[0];
    }
};

//质数下标
int main()
{
    int n; //输入数据的长度
    cin >> n;
   vector<int> nums(n);

    for (int i = 0; i < n; i++)
        cin >> nums[i];
    Solution s;
    int res = s.getNumber2(nums);
    cout << res << endl;
}

攻与防 题目

有n个战士，编号为1-n，战士的战斗力等于它的编号。寻找一个pos，将n个战士分成两个阵营，编号1-pos为第一个阵营，pos+1-n为第二个阵营，pos为0时，第一个阵营没战士，所有战士在第二阵营。假设第一个阵营为进攻方，第二个为防守方，进攻方能够进攻的总战斗力为w，防守方能够防守的总战斗力为v，我们希望w和v的差值最小，请找出pos。（相当于进攻方的防守战士不能提供攻击力，防守方的进攻战士不能提供攻击力）

输入：
第一行n，表示战士的数量。
第二行给出一个字符串s，由0和1组成，0表示这个战士只能进攻，1表示只会防守。
输出：
abs（w-v）的最小值

示例：
输入：
7
1000101
输出：
2
解释：
pos为第5个位置，进攻方w=2+3+4 = 9,防守方v=7.最后w-v = 2.

思路

先计算出pos为0时的w值和v值，然后移动pos位置，更新w和v，然后寻找一个最小的差值。

代码

#include
#include
#include
#include
#include
#include

using namespace std;

int solve(string s)
{
    int w = 0, v = 0; // 进攻和防守的战斗力总和
    int dif = INT_MAX;
    int length= s.size();
    //计算防守方的总和
    for (int i = 0; i < length; i++)
    {
        if ('1' == s[i]) v += i + 1;
    }
    dif= min(abs(v - w), dif); //防止全是0， 结果为0了
    for (int i = 1; i <= length; i++)
    {
        if ('0' == s[i - 1]) w += i; // 当前位置为0，进攻方加攻击力
        else if  ('1' == s[i - 1]) v -= i; //当前位置为1，防守方减攻击力

        if (abs(v - w) > dif) return dif; // 如果这次的防守方和攻击方的攻击力差值大于上次的最小值，则返回上次的最小值即可
        dif= min(abs(v - w), dif); //更新最小值
    }
    return dif; //防止全是1， 结果为0了
}

//攻与防
int main()
{
    int n; //输入数据的长度
    cin >> n;
    string s(n, '1');
    cout << s << endl;
    //cin >> s;
    int res = solve(s);
    cout << res << endl;
}