小米嵌入式软件实习笔试编程题

《嵌入式软件开发笔试与面试手册》：https://blog.nowcoder.net/zhuanlan/jvN8gj

《软件开发笔试汇总》：https://blog.nowcoder.net/zhuanlan/0oDWVm

偏爱的字符

题目描述：

小李天生偏爱一些字符，对于一个字符串，他总是想把字符串中的字符变成他偏爱的那些字符。如果字符串中某个字符不是他所偏爱的字符，称为非偏爱字符，那么他会将该非偏爱字符替换为字符串中距离该字符最近的一个偏爱的字符。这里的距离定义即为字符在字符串中的对应下标之差的绝对值。如果有不止一个偏爱的字符距离非偏爱字符最近，那么小李会选择最左边的那个偏爱字符来替换该非偏爱字符，这样就保证了替换后的字符串是唯一的。小李的所有替换操作是同时进行的。

假定小李有m个偏爱的字符，依次为c1,c2...cm，当小李看到一个长度为n的字符串s时，请你输出小李在进行全部替换操作后形成的字符串。

输入描述

第一行输入两个正整数n，m。

接下来一行输入m个字符c1,c2...cm，每两个字符之间用空格隔开，表示小李偏爱的字符。

接下来一行输入一个字符串s。

1≤n≤100000，1≤m≤26，保证题目中所有的字符均为大写字符，小李偏爱的字符互不相同，且偏爱字符至少出现一次。

输出描述

输出一行字符串，表示小李将给定的字符串s替换后形成的字符串。

样例输入

12 4

Z G B A

ZQWEGRTBYAAI

样例输出

ZZZGGGBBBAAA

提示

字符Q为非偏爱字符，且偏爱字符Z距离它最近，所以替换成Z；同理E距离G最近，替换成G；

对于字符W，偏爱字符Z和G与其距离相同，所以替换为左边的Z；

.......

对于字符 I ，右边没有偏爱字符，左边第一个偏爱字符是A，所以替换成字符A。

同一个偏爱字符可能会在字符串中出现多次。

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
#include <limits>
#include <string>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    
    string loves;
    cin.ignore();
    getline(cin, loves);
    unordered_set<char> loves_set(loves.begin(), loves.end());
    
    string inputs;
    getline(cin, inputs);
    
    vector<int> loves_indexes;
    for (int i = 0; i < inputs.length(); ++i) {
        if (loves_set.find(inputs[i]) != loves_set.end()) {
            loves_indexes.push_back(i);
        }
    }
    
    for (int i = 0; i < inputs.length(); ++i) {
        if (loves_set.find(inputs[i]) == loves_set.end()) {
            auto lower = lower_bound(loves_indexes.begin(), loves_indexes.end(), i);
            int l_index = (lower != loves_indexes.begin()) ? *(--lower) : numeric_limits<int>::min();
            auto upper = upper_bound(loves_indexes.begin(), loves_indexes.end(), i);
            int r_index = (upper != loves_indexes.end()) ? *upper : numeric_limits<int>::max();
            
            if (i - l_index <= r_index - i) {
                inputs[i] = inputs[l_index];
            } else {
                inputs[i] = inputs[r_index];
            }
        }
    }
    
    cout << inputs << endl;
    
    return 0;
}

小明打砖块

题目描述：

小明在玩一个消除游戏。这个消除游戏有点特别。游戏中，你会得到n个一维排列的有各自颜色的砖块。

消除的时候，你有三种消除方案。你可以单消一个砖块，这样你可以得到a的得分；如果两个颜色一样的砖块在一起，你可以将这两个砖块一起消除获得b的得分；如果三个颜色一样的砖块在一期，你可以将这三个砖块一起消除获得c的得分。

消除后，被消除的砖块自动消失，被消除砖块的左右两端的砖块将在消除之后挨在一起。

小明想知道在最优策略下他能得到多少得分。

输入描述

第一行4个整数n，a，b，c，表示砖块数量，和一消/二消/三消的得分。

接下来一行n个整数，第i个整数si表示第i个砖块的颜色。

输出描述

输出最高得分

样例输入

8 1 3 7

3 1 3 1 3 2 2 3

样例输出

14

提示

1≤si≤n≤300，0≤a,b,c≤10000

#include <iostream>
#include <vector>
#include <map>
#include <tuple>
#include <algorithm>

using namespace std;

int a, b, c;
vector<int> blocks;
map<pair<int, int>, int> memo;

int dfs(int i, int j) {
    if (i >= j)
        return i > j ? 0 : a;

    auto key = make_pair(i, j);
    if (memo.find(key) != memo.end())
        return memo[key];

    int ans = max(dfs(i+1, j), dfs(i, j-1)) + a;
    if (blocks[i] == blocks[j])
        ans = max(ans, b + dfs(i+1, j-1));

    for (int k = i+1; k < j; ++k) {
        if (blocks[i] == blocks[k] && blocks[k] == blocks[j])
            ans = max(ans, dfs(i+1, k-1) + dfs(k+1, j-1) + c);
    }

    memo[key] = ans;
    return ans;
}

int main() {
    int n;
    cin >> n >> a >> b >> c;
    blocks.resize(n);
    for (int i = 0; i < n; ++i)
        cin >> blocks[i];

    cout << dfs(0, n-1) << endl;
    return 0;
}