哔哩哔哩：笔试题（20190910）

最小操作次数

典型的动态规划问题，相等则源字符串和目标字符串各往后移一个，不相等则要增加一次操作次数，此外就是三种情况的判别中的最小值。

def operator_count(source, target):
    if not source:
        return len(target)
    if not target:
        return len(source)

    su, tu = source[0], target[0]
    if su == tu:
        return operator_count(source[1:], target[1:])
    else:
        # print(source, target)
        return 1+min(operator_count(source[1:], target[1:]),    # replace
                    operator_count(source, target[1:]),        # insert
                    operator_count(source[1:], target))                    # delete


if __name__ == '__main__':
    s = list(input().strip().split()[0])
    t = list(input().strip().split()[0])
    res = operator_count(s, t)
    print(res)

连续整数求和

要使连续数组的和值等于目标，这里采用游标策略，不断地增加游标的宽度，来进行移动取值是否符合要求。优化上，游标上界为目标值的平方根，就是等差数列求和；其次游标的移动并没有切片增加求和，而是累加游标宽度就好了，当大于目标值则不需要继续了。题目有点奇怪，可能是边界值没考虑好。按理来说，除了超时，思路倒是没有问题。通过率为60%。

import math


def con_number_of_sum(n):
    upper = math.ceil(math.sqrt(n))
    res = 0
    for ui in range(1, upper+1):
        current = n // ui
        left = current - ui + 1
        if left < 1:
            left = 1
        start = sum(range(left, left+ui))
        while start <= n:
            # print(ui, start)
            if start == n:
                res += 1
            start += ui
    return res


if __name__ == '__main__':
    n = int(input().strip())
    res = con_number_of_sum(n)
    print(res)

字符串切分

不知道怎么了，突然就限制了语言。采用的方法是设置双标志位，来分别区别是否为起始的上界和是否为键和值的分界。但没考虑键值是否为多个字符，所以只通过了80%。

#include <iostream>
#include <map>
#include <vector>

using namespace std;

map<char, char> split_string(vector<char> values, char left, char right)
{
    map<char, char> res;
    bool lflag=true, rflag=false;
    char l='_', r='_';
    for(int vi=0; vi<int(values.size()); vi++)
    {
        char cur = values[vi];
        if(cur == left)
        {
            lflag = true;
            rflag = false;
            if(l!='_' && r!='_')
            {
                res.insert(pair<char, char>(l, r));
            }
            l = '_';
            r = '_';
        }
        else if(cur == right)
        {
            rflag = true;
        }
        else
        {
            if(lflag)
            {
                l = cur;
                lflag = false;
            }
            else
            {
                if(!rflag)
                    l = cur;
                else
                    r = cur;
            }
        }
    }
    //cout << rflag << " " << l << " " << r << endl;
    if((!lflag) && rflag && l!='_' && r!='_')
        res.insert(pair<char, char>(l, r));
    return res;
}


int main()
{
    char left, right;
    cin >> left >> right;

    vector<char> values;
    char tmp;
    while(cin >> tmp)
    {
        values.push_back(tmp);
    }

    map<char, char> res;
    res = split_string(values, left, right);
    cout << res.size() << endl;
    map<char, char>::iterator it;
    for(it=res.begin(); it!=res.end(); it++)
    {
        cout << it->first << " " << it->second << endl;
    }

    return 0;
}


/*
# : ##a:3#b:8#c:
*/

（最近更新：2019年09月11日）