第一题
要求数总和为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, 实在不想做了就交了, 笔试结束分享个人代码。
头大了, 没有ide标红, 各种漏逗号, 漏括号, 真的顶不住呀。
秋招加油冲冲冲!!!
全部评论
(3) 回帖