记录一下自己的笔试的代码题

第一题

给定n段内存，起始地址加偏移地址，m个操作，操作a表示在a-2到a+2区间增加可用内存，-a表示在a-2到a+2区间减少可用内存。内存范围在0-4096之间。求操作后的可用内存地址有哪些。（需要合并重叠内存，并从低地址到高地址排序）

    //合并重叠内存
    vector<vector<int>> combineRAM(vector<vector<int>> &v){
        vector<vector<int>> ret;
        vector<int> tmp = v[0];
        for(int i = 1; i < v.size(); ++i){
            if(tmp[1] >= v[i][0] && tmp[1] <= v[i][1] ){ //重叠则合并
                tmp[1] = v[i][1];
            } else if(tmp[1] < v[i][0]){    //未重叠，则添加到返回数组里
                if(tmp[0] != tmp[1]) ret.emplace_back(tmp);
                tmp = v[i];
            } else if(tmp[1] > v[i][1]){
                continue;
            }
        }
        if(tmp[0] != tmp[1]) ret.emplace_back(tmp);
        return ret;
    }

    vector<vector<int>> ramManager(vector<vector<int>> input, vector<int> &options, int n, int m){
        vector<vector<int>> v(n, vector<int>(2));
        for(int i = 0; i < n; ++i){
            v[i][0] = input[i][0];
            v[i][1] = input[i][0] + input[i][1];
        }
        for(int i = 0; i < m; ++i){
            int t = options[i];     //取出当前操作
            if(t > 1 && t < 4095){
                vector<int> p = {t-2, t+2};
                v.emplace_back(p);
            } else if(t < 2 && t >= 0) {
                vector<int> p = {0, t + 2};
                v.emplace_back(p);
            } else if(t > 4094 && t <= 4096){
                vector<int> p = {t-2, 4096};
                v.emplace_back(p);
            } else {                //操作为负数，则是减少可用内存
                int l = abs(t) - 2;
                int r = abs(t) + 2;
                if(l < 0) l = 0;
                if(r > 4096) r = 4096;
                for(int j = 0; j < v.size(); ++j){
                    if(l <= v[j][0] && r > v[j][0]){
                        v[j][0] = r;
                        break;
                    } else if(l < v[j][1] && r > v[j][1]){
                        v[j][1] = l;
                        break;
                    } else if(l >= v[j][0] && r <= v[j][1]){
                        int tl = v[j][0], tr = v[j][1];
                        if(v[j][0] != l) v[j][1] = l;
                        if(v[j][1] != r){
                            vector<int> p = {r, tr};
                            v.emplace_back(p);
                        }
                        break;
                    }
                }
            }
        }
        sort(v.begin(), v.end());       //排序
        return combineRAM(v);           //返回合并后的内存
    }

首先转换为内存区间来表示。读取指令，当内存增加时，直接将新增内存块添加到列表里，而减少内存时，寻找当前空闲内存是否有和删除区间重叠的地方，如果没有则不删除，如果有，删除重叠部分，若增加了内存块数量，则修改原内存的区间，并在末尾添加新增的内存块。经过排序后，合并重叠内存部分，并返回。

第二题

给一张N*M的图，图里每个格子都有个高度，每次移动只能在高度差T内，问从0，0开始，有3次机会可以无视高度差移动，到最右下角最短需要多少步。


    vector<int> result;
    void backtracking(vector<vector<int>> &vec, vector<vector<bool>> path, int i, int j, int cnt, int bo, int &dif, int last_v){
        if( i  >= vec.size()  - 1 && j >= vec[0].size() - 1){
            result.push_back(cnt);
            return;
        }
        path[i][j] = true;
        if(abs(vec[i][j] - last_v) > dif) bo++;
        if(bo > 3) return;
        cnt++;
        if(i + 1 <= vec.size() - 1 && !path[i+1][j]) backtracking(vec, path, i+1, j, cnt, bo, dif, vec[i][j]);
        if(j + 1 <= vec[0].size() - 1 && !path[i][j+1]) backtracking(vec, path, i, j + 1, cnt, bo, dif, vec[i][j]);
        if(i - 1 >= 0 && !path[i-1][j]) backtracking(vec, path, i-1, j, cnt, bo, dif, vec[i][j]);
        if(j - 1 >= 0 && !path[i][j-1]) backtracking(vec, path, i, j-1, cnt, bo, dif, vec[i][j]);
    }

    int main(){
        int n, m, diff;
        cin >> n >> m >> diff;
        vector<vector<int>> vec(n, vector<int>(m, 0));
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                cin >> vec[i][j];
            }
        }
        vector<vector<bool>> path(n, vector<bool>(m, false));
        path[0][0] = true;
        int bo = 0;
        if(1 <= n - 1) backtracking(vec, path, 1, 0, 1, 0, diff, vec[0][0]);
        if(1 <= m - 1) backtracking(vec, path, 0, 1, 1, 0, diff, vec[0][0]);
        if(result.size() == 0){
            cout << -1;
            return 0;
        }
        sort(result.begin(), result.end());
        cout<<result[0];
        return 0;
    }

dfs寻找到满足条件的所有路径的步数，排序后取最小步数。（其实不用排序，直接循环一遍找最小值也可以）

第三题

有n号港口，每个港口有一个停靠花费和到下一个港口的距离。一艘船每次只能走N的距离，寻找花费最小的路径走到目的地，输出走过的路径，若花费相同，输出序列靠前的路径，目的地不在给出港口中。


    void dfs(vector<vector<int>> &paths, vector<int> &cost, vector<int> path, vector<int> &val, vector<int> &dist, int i, int c, int N){
        if(i < val.size()){
            path.emplace_back(i);
            c += val[i];
            int p = 0;
            for(int j = i; j < val.size(); ++j){
                p += dist[j];
                if(p <= N){
                    dfs(paths, cost, path, val, dist, j+1, c, N);
                } else return;
            }
        } else {
            paths.emplace_back(path);
            cost.emplace_back(c);
        }
    }

    vector<int> findPath(int n, vector<int> &val, vector<int> &dist, int N){
        vector<vector<int>> paths;
        vector<int> path;
        vector<int> cost;
        for(int i = 0; i < n ; ++i){
            if(dist[i] > N) return {-1};
        }
        dfs(paths, cost, path, val, dist, 0, 0, N);
        int minCost = INT32_MAX;
        for(int i = 0; i < cost.size(); ++i){
            minCost = min(minCost, cost[i]);
        }
        for(int i = 0; i < cost.size(); ++i){
            if(cost[i] == minCost){
                path = paths[i];
                break;
            }
        }
        return path;
    }

    int main(){
        int n;
        cin>>n;
        vector<int> val(n), dist(n);
        for(int i = 0; i < n; ++i){
            cin>>val[i];
        }
        for(int i = 0; i < n; ++i){
            cin>>dist[i];
        }
        int N;
        cin>>N;
        vector<int> path = findPath(n, val, dist, N);
        for(int i = 0; i < path.size(); ++i){
            cout<<path[i];
            if(i != path.size()-1) cout<<' ';
        }
        return 0;
    }

使用dfs搜索，找到满足条件的所有路径，取第一个消耗最小的路径。