【C++刷题】校招笔试编程题第一辑

1. 组队竞赛

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() 
{
    int n;
    cin >> n;
    
    vector<int> v;
    v.resize(3*n);

    int i = 0;
    for(i = 0; i < v.size(); ++i)
    {
        cin >> v[i];
    }
    sort(v.begin(), v.end());
	
	/*
	* 例如排序后的 1 2 3 4 5 6 7 8 9
	* 每次取头 1 个数，和尾 2 个数
	* 1 8 9
	* 2 6 7
	* 3 4 5
	* 得到的 8 6 4 的第二水平值的和最大
	*/
    long long sum = 0;
    while(n--)
    {
        sum += v[i -= 2];
    }

    cout << sum;
    return 0;    
}

1. 删除公共字符

#include <iostream>
#include <string>
#include <cstring>
using namespace std;

int main() 
{
    string s1;
    getline(cin, s1);
    string s2;
    getline(cin, s2);

    int hashtable[256];
    memset(hashtable, 0, sizeof(hashtable));
    for(char c2 : s2)
    {
        hashtable[c2] = 1;
    }

    string ret;
    for(char c1 : s1)
    {
        if(hashtable[c1] == 0)
        {
            ret += c1;
        }
    }

    cout << ret;
    return 0;
}

1. 排序子序列

#include <iostream>
#include <vector>
using namespace std;

int trend(int a, int b)
{
    if (a < b)
        return 0;
    else
        return 1;
}

int main()
{
    int n;
    cin >> n;

    if (n < 3)
    {
        cout << 1;
        exit(0);
    }

    int a, b;
    cin >> a >> b;
    n -= 2;
    int flag = 0;
    
    int count = 0;
    while (1)
    {
        flag = trend(a, b); // 判断趋势

        a = b;
        if (n-- == 0)
            break;
        cin >> b;

        if ((flag == 0 && a > b) || (flag == 1 && a < b))
        {
            ++count;// 违背趋势就+1
            a = b;
            if (n-- == 0)
                break;
            cin >> b;
        }
    }

    cout << count + 1;
    return 0;
}

1. 字符串中找出连续最长的数字串

#include <iostream>
using namespace std;

int main() 
{
    string s;
    cin >> s;
    
    int tmpstart = 0;
    int tmpend = 0;
    int start = 0;
    int end = 0;
    int max = 0;
    for(size_t i = 0; i < s.size(); ++i)
    {
        if(s[i] >= '0' && s[i] <= '9')
        {
            tmpstart = i;
            tmpend = i;
            while(tmpend < s.size() && s[tmpend] >= '0' && s[tmpend] <= '9')
            {
                ++tmpend;
            }
            i = tmpend - 1; // ++i加了1
            if(tmpend - tmpstart > max)
            {
                max = tmpend - tmpstart;
                start = tmpstart;
                end = tmpend;
            }
        }
        else
        {
            ++i;
        }
    }
    for(size_t i = start; i < end; ++i)
    {
        cout << s[i];
    }
   return 0;
}

1. 计算糖果

#include <iostream>
using namespace std;

int main() 
{
    int num[4];
    for(int& n : num)
    {
        cin >> n;
    }

    /*
    * 0: A = B + n0
    * 1: B = C + n1
    * 2: A + B = 2*B + n0 = n2 -> B
    * 3: B + C = 2*C + n1 = n3 -> C
    */
    int B = (num[2] - num[0]) / 2;
    int C = (num[3] - num[1]) / 2;
    if(B == C + num[1])
    {
        cout << B + num[0] << " " << B << " " << C;
    }
    else
    {
        cout << "No";
    }
    return 0;
}

1. 进制转换

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() 
{
    int num, n;
    cin >> num >> n;
    if(num == 0)
    {
        cout << 0;
        exit(0);
    }
    string s, table = "0123456789ABCDEF";
    // 负数情况的判定
    int flag = false;
    if(num < 0)
    {
        flag = true;
        num = -num;
    }
    // 每次取余数进行+=
    while(num)
    {
        s += table[num % n];
        num /= n;
    }
    reverse(s.begin(), s.end());
    if(flag)
    {
        cout << "-";
    }
    for(char i : s)
    {
        cout << i;
    }
    return 0;
}

1. 连续最大和

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;

    int sum, max, num;
    cin >> sum;
    max = sum;
    for(size_t i = 1; i < n; ++i)
    {
        cin >> num;
        sum += num;
        if(sum < num)
        {
            sum = num;
        }

        if(sum > max)
        {
            max = sum;
        }
    }

    cout << max;
    return 0;
}

1. 不要二

#include <iostream>
#include <cstring>
using namespace std;

int main() 
{
    int H, W;
    cin >> H >> W;

    int arr[H][W];
    memset(arr, 1, sizeof(arr));

    int count = 0;
    for(int h = 0; h < H; ++h)
    {
        for(int w = 0; w < W; ++w)
        {
        	// arr[h][w]是1，可以放蛋糕
            if(arr[h][w])
            {
                ++count;
                // arr[h][w+2] 和 arr[h+2][w] 的位置都不能放蛋糕
                if (w + 2 < W)
                {
                    arr[h][w + 2] = 0;
                }
                if (h + 2 < H)
                {
                    arr[h + 2][w] = 0;
                }
            }
        }
    }

    cout << count;
    return 0;
}

1. 从根到叶的二进制数之和

class Solution {
public:
    void recursion(TreeNode* root, int num, int& sum)
    {
        if(root == nullptr)
        {
            return;
        }

        num = (num << 1) + root->val;

        if(root->left || root->right)
        {
            recursion(root->left, num, sum);
            recursion(root->right, num, sum);
        }
        else // 没有孩子，是叶节点
        {
            sum += num;
        }

    }
    int sumRootToLeaf(TreeNode* root)
    {
        int sum = 0;
        recursion(root, 0, sum);
        return sum;
    }
};

1. 二叉树的坡度

class Solution {
public:
    int getSum(TreeNode* root)
    {
    	// 计算子树和值
        if(root == nullptr)
        {
            return 0;
        }
        return root->val + getSum(root->left) + getSum(root->right);
    }
    int findTilt(TreeNode* root)
    {
        if(root == nullptr)
        {
            return 0;
        }
        // 左子树的坡度 + 右子树的坡度 + 根节点的坡度
        return findTilt(root->left) + findTilt(root->right) + abs(getSum(root->left) - getSum(root->right));
    }
};

1. 两种排序方法

void test()
{
    int n = 0;
    cin >> n;

    bool lexicographically = true;
    bool lengths = true;
    string s1;
    string s2;
    cin >> s1;
    for(int i = 1; i < n; ++i)
    {
        cin >> s2;
        if(s1 > s2)
        {
            lexicographically = false;
        }
        if(s1.size() > s2.size())
        {
            lengths = false;
        }
        s1 = s2;
    }
    if(lexicographically && lengths)
    {
        cout << "both";
        return;
    }
    if(lexicographically)
    {
        cout << "lexicographically";
        return;
    }
    if(lengths)
    {
        cout << "lengths";
        return;
    }
    cout << "none";
}

1. 走方格的方案数

int dp(int n, int m)
{
	// 第一种终止条件
    // if(n == 0 || m == 0)
    // {
    //     return 1;
    // }
	
	// 第二种终止条件
    if(n == 1 || m == 1)
    {
        return n + m;
    }
    
    // 走到当前格子位置的路径数量=走到左边格子的路径数量+走到上边格子的路径数量
    return dp(n -1, m) + dp(n, m - 1);
}

1. 另类加法

int addAB(int A, int B)
{
    while (A & B) // 判断有没有相交的1
    {
        int a = A ^ B; // 求和后当前位的1
        int b = (A & B) << 1; // 求和后进位的1
        A = a;
        B = b;
    }
    return A | B;
}

1. 查找组成一个偶数最接近的两个素数

bool isPrime(int num)
{
    for(int i = 2; i <= sqrt(num); ++i)
    {
        if(num % i == 0)
        {
            return false;
        }
    }
    return true;
}

int main()
{
    int n = 0;
    cin >> n;

    int half = n / 2;
    while(half)
    {
        if(isPrime(half) && isPrime(n-half))
        {
            cout << half << endl;
            cout << n-half << endl;
            break;
        }
        --half;
    }

    return 0;
}

1. 参数解析

int main()
{
    string str;
    getline(cin, str);
    bool flag = false; // 判断是否处于“”内部
    vector<string> v;
    string str2;
    for(size_t i = 0; i < str.size(); ++i)
    {
        if(str[i] == '"')
        {
            flag = !flag;
            continue;
        }

        if(str[i]!=' ')
        {
            str2 += str[i];
        }
        else if(flag == true)
        {
            str2 += " ";
        }
        else if(flag == false)
        {
            v.emplace_back(str2);
            str2.resize(0);
        }
    }
    v.emplace_back(str2); // 最后一个字符串不要忘掉

    cout << v.size() << endl;
    for(size_t i = 0; i < v.size(); ++i)
    {
        cout << v[i] << endl;
    }
    return 0;
}

1. 跳石板

int step(int n, int m)
{
    // 开辟m+1大小的数组
    int* p = new int[m + 1];
    for (int i = 1; i <= m; ++i)
    {
        p[i] = -1;
    }

    p[n] = 0; // 当前石板步数设为0
    while (n < m)
    {
        // 寻找因数
        for (int i = 2; i <= sqrt(n); ++i)
        {
            if (n % i == 0)
            {
                //石板的步数为-1
                if (n + i <= m && p[n + i] == -1)
                {
                    p[n + i] = p[n] + 1;
                }
                else if (n + i <= m) // 石板的步数不为-1
                {
                    if (p[n] + 1 < p[n + i])
                        p[n + i] = p[n] + 1;
                }

                if (n + n / i <= m && p[n + n / i] == -1)
                {
                    p[n + n / i] = p[n] + 1;
                }
                else if (n + n / i <= m)
                {
                    if (p[n] + 1 < p[n + n / i])
                        p[n + n / i] = p[n] + 1;
                }
            }
        }

        while (++n < m && p[n] == -1); // 寻找当前对应步数不为-1的石板
    }
    return p[m] == -1 ? -1 : p[m];
}

1. 幸运的袋子

int getLuckyBag(vector<int>& v, int size, int pos, int sum, int product)
{
    int count = 0;
    for(int i = pos; i < size; ++i)
    {
        sum += v[i];
        product *= v[i];

        if(sum > product)
            count += 1 + getLuckyBag(v, size, i + 1, sum, product);
        else if(v[i] == 1)
            count += getLuckyBag(v, size, i + 1, sum, product);
        else
            break;

        // 回溯
        sum -= v[i];
        product /= v[i];

        // 去重
        while(i < size - 1 && v[i] == v[i + 1])
            ++i;
    }

    return count;
}

int main()
{
    int n;
    while(cin >> n)
    {
        vector<int> v(n);
        for(int i = 0; i < n; ++i)
            cin >> v[i];
        sort(v.begin(), v.end());

        cout << getLuckyBag(v, v.size(), 0, 0, 1) << endl;
    }

    return 0;
}

1. 手套

int findMinimum(int n, vector<int> left, vector<int> right)
{
    int left_sum = 0, left_min = 26;
    int right_sum = 0, right_min = 26;

    int sum = 0;
    for(int i = 0; i < n; ++i)
    {
        if(left[i] * right[i] == 0)
        {
            sum += (left[i] + right[i]);
        }
        else
        {
            left_sum += left[i];
            if(left[i] < left_min)
            {
                left_min = left[i];
            }

            right_sum += right[i];
            if(right[i] < right_min)
            {
                right_min = right[i];
            }
        }
    }

    return sum + min(left_sum - left_min + 1, right_sum - right_min + 1) + 1;
}

1. 扑克牌大小

#include <iostream>
#include <vector>
#include <string>
using namespace std;

#define gezi_space 0
#define duizi_sapce 1
#define sange_sapce 2
#define zhadan_sapce 3
#define shunzi_sapce 4

const vector<string> poker = {"3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K", "A", "2", "joker", "JOKER"};

int get_space_count(const string& str)
{
    int space_count = 0;
    for(char c : str)
    {
        if(c == ' ')
        {
            ++space_count;
        }
    }
    return space_count;
}

string poker_judge(const string& left, const string& right)
{
    if(left == "joker JOKER" || right == "joker JOKER")
    {
        return "joker JOKER";
    }

    int left_space_count = get_space_count(left);
    int right_space_count = get_space_count(right);
	
	// 类型相同
    if(left_space_count == right_space_count)
    {
    	// 获取第一张牌
		string left_0 = left.substr(0, left.find(' '));
        string right_0 = right.substr(0, right.find(' '));

        int left_index = 0;
        int right_index = 0;
        for(int i = 0; i < poker.size(); ++i)
        {
            if(left_0 == poker[i])
            {
                left_index = i;
            }
            if(right_0 == poker[i])
            {
                right_index = i;
            }
        }
		
		// 第一张牌比大小
        if(left_index > right_index)
        {
            return left;
        }
        else
        {
            return right;
        }
    }
    else if(left_space_count == zhadan_sapce)
    {
        return left;
    }
    else if(right_space_count == zhadan_sapce)
    {
        return right;
    }
    else
    {
        return "ERROR";
    }
}
int main()
{
    string str;
    while(getline(cin, str))
    {
        size_t pos = str.find('-');
        string left(str.begin(), str.begin() + pos);
        string right(str.begin() + pos + 1, str.end());

        cout << poker_judge(left, right) << endl;
    }

    return 0;
}