第一题
要求数总和为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) 回帖