阿里笔试4.1场(附代码 + 3月全5场代码链接)

隔几天做两道= =保持做题感觉
前5场代码链接:
——————————————————————————————————————
再更:第一题改成一种位运算的思路,因为题设里串长小于等于20,所以bfs复杂度应该是可以满足的(~1e6)
这种思路只要复杂度满足要求,一定是正确的。
之前的做法目前版本暂时没有证伪……如果有反例请留言,我有点没想出= =
/*
把一个串恢复全0的最小步数 = 从全0变为该串的最小步数
对于某一个串,计算其1步可达的串,等价于其与7(二进制111)及其左移N位作异或
(注意收尾位的处理,我是单独处理手尾位,用3和3的左移串长-2位作异或)
如果新增串之前没有记录过,就记录其到0的距离是当前串+1,并将其加入处理队列
队列空,则所有可达串访问完毕。
如果访问到目标串,返回其步长,否则返回No
*/

#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<math.h>

using namespace std;

int str2num(string s) {
    int res = s[0] - '0';
    int i;
    for(i = 1; i < s.length(); i++) {
        res = res*2 + s[i] - '0';
    }
    return res;
}

int fun(string s) {
    if(s.empty()) {
        return INT_MAX;
    }
    else if(s.length() == 1) {
        if(s[0] == '0') {
            return 0;
        }
        else {
            return INT_MAX;
        }
    }
    else if(s.length() == 2) {
        if(s[0] == s[1]) {
            return s[0] - '0';
        }
        else {
            return INT_MAX;
        }
    }
    
    int val = str2num(s);
    vector<int> mark;
    queue<int> pos;
    int i, tmp;
    for(i = 0; i < int(pow(2, s.length())); i++) {
        mark.push_back(INT_MAX);
    }
    mark[0] = 0;
    pos.push(0);
    
    int shiftv[s.length()];
    shiftv[0] = 3;
    for(i = 1; i < s.length()-1; i++) {
        shiftv[i] = 7<<(i-1);
    }
    shiftv[s.length()-1] = 3<<(s.length()-2);
    
    while(!pos.empty()) {
        for(i = 0; i < s.length(); i++) {
            tmp = pos.front()^shiftv[i];
            if(tmp == val) {
                return mark[pos.front()]+1;
            }
            else if(mark[tmp] == INT_MAX){
                mark[tmp] = mark[pos.front()]+1;
                pos.push(tmp);
            }
        }
        pos.pop();
    }
    return mark[val];
}

int main() {
    string s;
    cin>>s;
    int res = fun(s);
    if(res == INT_MAX) {
        cout<<"No"<<endl;
    }
    else {
        cout<<res<<endl;
    }
    return 0;
}
——————————————————————————————————————
注:以下都是根据讨论区实现的代码,数据输入格式、数据范围都不确定,所以只供思路探讨:
第1题:(简单更新了,想问问大家还有没有新的反例)
/*
 从左向右,如第i位碰到1时,反转第i,i+1,i+2位,直到完成完整串
 如果全部完成后,最后一位是1,表示不能翻转出全0;否则就返回翻转次数
 由于这种操作没有对同一位置的重复操作,一定是最少的
 时间复杂度O(n)
 */

/*
 补充:原代码没有考虑第一位需要翻转的情况,因此现在分别考虑第一位翻转和第一位不翻转两种情况,
 取两者中能够成功且次数小的一种。
*/

#include<iostream>
#include<string>
#include<math.h>

using namespace std;

int fun(string s) {
    if(s.empty()) {
        return 0;
    }
    
    int i;
    int count = 0;
    for(i = 0; i < s.length()-1; i++) {
        if(s[i] == '1') {
            s[i] = '0';
            s[i+1] = '0' + (1 - (s[i+1] - '0'));
            if(i < s.length() - 2) {
                s[i+2] = '0' + (1 - (s[i+2] - '0'));
            }
            count++;
        }
    }
    if(s[s.length()-1] == '1') {
        return INT_MAX;
    }
    else {
        return count;
    }
}

int main() {
    string s;
    cin>>s;
    int res = fun(s), res2;
    string scp;
    scp = s;
    if(s.length() > 2) {
        scp[0] = '0';
        scp[1] = '0' + (1 - (s[1] - '0'));
    }
    res2 = fun(scp);
    if(res2 != INT_MAX) {
        res = min(res, res2 + 1);
    }
    
    if(res == INT_MAX) {
        cout<<"NO"<<endl;
    }
    else {
        cout<<res<<endl;
    }
    return 0;
}
一个只有01的串,每次可以同时翻转i-1,i,i+1位(左右端只翻转两位),求最小翻转次数(如无法反转,则输出”No")
这道题感觉思路不确定一定对,但没想到反例……希望讨论或者举点极端的例子= =

第2题:有N个怪兽,M个弓箭,每个怪兽有生命值,每个弓箭有杀伤力和价值,每个怪兽只能用一支弓箭攻击,弓箭杀伤>=怪兽生命时可消灭怪兽,求使用弓箭的最小价值。如无法消灭,返回-1。
/*
1. 对怪兽生命从大到小排序
2. 对弓箭按攻击力从大到小排序
3. 建立一个优先队列,按照价值从小到大
之后按照顺序对每个怪兽计算:
 1.找出所有攻击力大于等于其生命值的弓箭,将其加入优先队列
 2.若此时队列空,证明没有可以消灭该怪兽的弓箭了,返回-1
   否则将优先队列队头出队,记录其价值。
 返回总价值即可。
时间复杂度O(mlogm)
*/

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

struct prs {
    int cost;
    int att;
};

bool cmp1 (int a, int b) {
    return a > b;
}

bool cmp2(prs p1, prs p2) {
    return p1.att > p2.att;
}

int mincost(vector<int> &monst,vector<prs> &arrow) {
    if(monst.size() > arrow.size()) {
        return -1;
    }
    sort(monst.begin(), monst.end(), cmp1);
    sort(arrow.begin(), arrow.end(), cmp2);
    priority_queue<int, vector<int>, greater<int> > pq;
    
    int res = 0;
    int i, j = 0;
    
    for(i = 0; i < monst.size(); i++) {
        while(j < arrow.size() && arrow[j].att >= monst[i]) {
            pq.push(arrow[j].cost);
            j++;
        }
        if(pq.empty()) {
            return -1;
        }
        else {
            res = res + pq.top();
            pq.pop();
        }
    }
    return res;
}

int main() {
    int N, M;
    cin>>N>>M;
    
    vector<int> monst;
    vector<prs> arrow;
    prs ptmp;
    int tmp;
    int i;
    
    for(i = 0; i < N; i++) {
        cin>>tmp;
        monst.push_back(tmp);
    }
    for(i = 0; i < M; i++) {
        cin>>ptmp.cost;
        arrow.push_back(ptmp);
    }
    for(i = 0; i < M; i++) {
        cin>>arrow[i].att;
    }
    
    cout<<mincost(monst, arrow)<<endl;
    return 0;
}
#阿里笔试##阿里巴巴##笔试题目##实习##笔经#
全部评论
第一题这样做呢? https://www.nowcoder.com/discuss/397946
1 回复
分享
发布于 2020-04-01 23:07
更新了第一题的另一种解法,欢迎讨论
1 回复
分享
发布于 2020-04-02 15:30
百信银行
校招火热招聘中
官网直投
第一题感觉有点小问题,如果是11000这种,应该只要一次。应该对原数据分别从左往右,从右往左遍历一次,取较小值。
点赞 回复
分享
发布于 2020-04-01 22:23
第一题首先101这个例子都过不了吧,按照你的思路:101第一次翻转变成010,第二次变成001,输出“NO”。 实际上,101对左边两位翻转得011,对右边两位翻转得000.
点赞 回复
分享
发布于 2020-04-02 07:20
每一位是否翻转都由上一位是否翻转唯一决定了
点赞 回复
分享
发布于 2020-04-02 08:09

相关推荐

2 35 评论
分享
牛客网
牛客企业服务