虾皮提前批8.2后端笔试

第一题

要求数总和为n分k个数, 顺序不同算同一组,有多少种分法

回溯或者dp

class Solution {
public:
    int kk;
    int ans;
    int divide(int n, int k) {
        //回溯法
        //不考虑顺序不能相同。所以要求结果数组从小到大即可
        //数据量也不大，直接暴力回溯即可
        kk = k;
        ans = 0;
        vector<int> tmp;
        backtrace(tmp,n);
        return ans;
    }
    void backtrace(vector<int>& tmp, int n){
        int len = tmp.size();
        //退出条件
        if(len==kk && n==0){//刚好结束
            //退出条件
            ans++;
            return ;
        }
        if(len==kk || n<=0) return;

        //回溯选择
        if(len==0){//如果是第一个数字
            for(int i = 1 ; i <= n ; i++){
                tmp.push_back(i);
                backtrace(tmp,n-i);//tmp数组。剩余的总和
                tmp.pop_back();
            }
            return;//进了这里执行完就退出了
        }

        //如果不是第一个数字
        int last = tmp[len-1];//最后一个数字
        for(int i = last ; i <= n ; i++){
            //如果不是第一个数字。插入的数字必须比当前数字大了
            //此处可以优化一下 筛选一些明显不可能的结果
            tmp.push_back(i);
            backtrace(tmp,n-i);
            tmp.pop_back();
        }
    }
};

第二题

一个数组,找到一个数的下标,该数左边的所有数和与右边的所有数和相同。

class Solution {
public:
    int findBalancedIndex(vector<int>& inputArray) {
        // write code here
        //有可能存在2个平衡数吗。 感觉不太可能的样子。双指针
        long long leftsum = 0, rightsum = 0;
        int n = inputArray.size();
        int i = 0 , j = n-1;
        while(j!=i){//i/j 所在的数字是还没加的那个
            if(leftsum == rightsum){
                leftsum +=inputArray[i];
                i++;
            }
            else if(leftsum < rightsum){
                leftsum += inputArray[i];
                i++;
            }
            else if(leftsum > rightsum){
                rightsum += inputArray[j];
                j--;
            }
        }
        return i;
    }
};

第三题

XML解析。只能过60%。不知道哪里有问题,并不想再debug了。

三种情况。

* `<people><name>shopee</name></people>` 可以
* `<people><name>shopee</name><name2>qqqq</name2></people>` 可以
* `<people><name>shopee</name></people><people1><name>shopee</name></people2>`不支持

状态机+stack就能做。注意这题要include头文件。鬼知道为什么第一题vector就不用, 就是玩。

#include <string>
#include <map>
#include <stack>

using namespace std;
class Solution {
public:
    string GetXMLValue(string inxml, string path) {
        //先做解析。 然后存进map。然后直接取。
        //解析过程用状态机+stack来做。会比较方便
        int n = inxml.size();
        stack<string> stk;
        map<string,string> memo;
        string key = "" ;
        string value = "";
        int idx = 0;//这是还没解析到的
        char word;
        for( ; idx < n; ){
            word = inxml[idx];
            if(word== '<'){
                idx++;
                word = inxml[idx];
                if(word != '/'){
                    //执行插入stk
                    key = "";
                    while(idx<n && inxml[idx] != '>'){
                        key= key + inxml[idx]; //这里可能语法错。 或者append
                        idx++;
                    }
                    stk.push(key);//此时idx对应 >
                }
                else if(word == '/'){
                    //如果是/ 那就pop一个词
                    while(idx<n &&inxml[idx] != '>'){
                        idx++;
                    } //不需要关注这个单词
                    stk.pop();//此时idx也对应>
                }
                idx++;//此时idx对应下一个单词
            }
            else{
                //这里要解析单词了
                value = "";

                while(inxml[idx] != '<'){//一直是单词的部分
                    value = value + inxml[idx];
                    idx++;
                }
                memo[stk.top()] = value;
                //此时idx是‘<’ 不需要++
            }
        }
        //解析path
        n = path.size();
        idx = 0;
        while(path[idx] != '.'){
            idx++;
        }
        // idx现在是 .
        idx++;
        key = "";
        while(idx < n){
            key = key+path[idx];
            idx++;
        }
        return memo[key];
    }
};

--------------------------------

心态崩了, 借的同学电脑做的笔试。没有本地IDE。虾皮的平台把编译报错都给隐藏了, 语法错也不标红, 整场笔试都在与语法错斗智斗勇。改完语法错最后一题只过0.6, 实在不想做了就交了, 笔试结束分享个人代码。

虾皮提前批8.2后端笔试

全站热榜