美团9.6笔试复盘

（有两道题没做出来，看了js8544老哥的题解，来记录一下，下次继续努力！

1. 题目

输入一个数组，数组中每个值表示该节点以下的所有节点数（包含该节点）。判断所有节点是否可以组成合法二叉树。
限制条件：二叉树子节点只能为空或者为2。

输入

     3
     1 1 3

输出

YES

错误总结

考试时候想的是单个节点必须满足2^-1，且相邻的节点数量满足二倍的关系，相邻节点的值满足
pre*2+1 = next。这个应该是完全二叉树的限制，题目中的二叉树不一定是完全二叉树。

思路

分析题目，应该可以得出所有节点的值必须为奇数才行。因为除了根，其他儿子都是0或者2。
通过递归的方法模拟建树。首先我们把结点的值和数目保存为哈希表，然后开始建树。

递归基，如果当前节点数目为空，返回true,否则总节点数目减一。
找到第一个小于该节点值的节点作为左儿子，如果没有，就返回false
计算出右儿子，如果没有，返回false;
最后dfs出来后，false当然是NO，true的话也要看是否还有多的节点，没有，就合法。

代码实现（手动测试ok）

#include<bits/stdc++.h>
#define MAXVAL 100005
using namespace std;

map<int, int, greater<int>> buffer;
int n, mm;
bool dfs(map<int,int>::iterator& root)
{

  if(root->second == 0)  return true;
  --buffer[root->first];
  n = n - 1;


  map<int,int>::iterator left, right;
  int rootKey = root->first;
  left = ++root;
  root = buffer.lower_bound(rootKey);

  for(; left != buffer.end() && left->first>=root->first; ++left)

  if(left == buffer.end()) return false;

  int rightKey = rootKey - left->first-1;
  right = buffer.lower_bound(rightKey);
  if(right == buffer.end()) return false;

  return dfs(left) && dfs(right);
}

int main(int argc, char const *argv[])
{
    int now;
    int flag = 0;
    string ans;
    while(1)
    {
      flag = 0;
      buffer.clear();
      ans = "YES";
      n = 0;

      cin>>n;
      for (int i = 0; i < n; ++i)
      {

          cin>>now;
          if(!(now&1))
          { 
            ans = "NO";
            flag = 1;
            break;
          }
          buffer[now]++;
      }


      if(!flag)
      {
         std::map<int,int>::iterator root;
         root = buffer.begin();
         auto e = buffer.end();
         --e;
         mm = e->first;
         if(dfs(root) && n == 0)
         {

           cout<<"YES"<<endl;
         }
         else
         {
           cout<<"NO"<<endl;
         }
      } 
    }

    return 0;
}

2 题目二

给定一个数组A，定义数组B为

$b_i = a_i \bigoplus \bigoplus_{j=1}^{n}(i mod j)$ ,
求

$\bigoplus_{j=1}^{n}b_i$

错误总结

这个题当时直接暴力法，按着题目意思去做，不出意外超时了~ 想起了以前读高中时候数学老师总说的一句话，要理解出题人的意思，哈哈，编程也是一样把，看了大佬题解才明白，这题是找规律的。剑指（s11）上面有有一道不用除法求数组中除了当前数字的和，和这个题目的思想类似。

解题思路

输入如果为[1，2，3，4]

学一下大佬画表观察，表中数据是求模数据，结果就是表中所有数字异或。由于求模运算的循环特性，
观察到列具有循环特性。每一列是0-(a-1),循环了(n/a)次，剩下(n%a),全部运算都是基于，0-n的异或操作，可以先计算出来。

b	a	2	3	4	5
b1	1	1	1	1	1
b2	2	0	2	2	2
b3	3	1	0	3	3
b4	4	0	1	0	4
b5	5	1	2	1	0

代码

这里

总结收获

做编程题目的时候，最重要的是思路，不要着急去写代码。对于一些过程类题目，其实，往往暴力法的思路是最清晰的，不妨模拟题意。另外，对于有关树的题目，递归的思想是很有用的。在笔试中，第一要义永远是先把题目做出来，然后去优化。对于找规律的题目，要多写几个例子，很多算法题目都用到了增量(Increment)的思想。