记录菜鸡的快手笔试，刚看到有人说会因为复杂度过高进不去面试，有大佬回答下吗

• 许愿一面

1.三种括号的个数

思路：
遍历就完了

#include <iostream>
using namespace std;
int main() {
    string str;
    cin >> str;
    int left=0, right=0, nums=0;
    for( int i=0; i<str.size(); ++i )
    {
        if( str[i]=='(' )
        {
            ++left;
        }
        else if( str[i]==')' )
        {
            if( left )
            {
                --left;
                ++nums;
            }
            else
                ++right;
        }
    }
    cout<<nums<<" "<<left<<" "<<right<<endl;
    return 0;
}

2.无重复幂因子的N进制完美数之和

思路：
1.遍历，先找到比R大的最小的N进制完美数的位置index；
2.从index开始，从右往左移动，每遇到比R小的值时，将index放入res保存，并且更新减小后的R值；
3.最后R＝０时，成功，对res排序，返回res；否则返回空。

• 
• 
• 

  class Solution {
  public:
    /**
     * 返回无重复幂因子的 N进制完美数之和的所有幂因子
     * @param R int整型 
     * @param N int整型 N进制
     * @return int整型vector
     */
    vector<int> GetPowerFactor(int R, int N) {
        vector<int> res, vec;
        int i=0;
        while(1)
        {
            if( pow(N,i) <= R )
                vec.push_back( pow(N,i) );
            else
                break;
            ++i;
        }
        for( --i; i>=0; --i )
        {
            if( R>=vec[i] )
            {
                res.push_back( i );
                R -= vec[i];
            }
            if( R==0 )
            {
                sort( res.begin(), res.end() );
                return res;
            }
        }
        return {};
    }
  };

3.

思路：
0.对于index=i，j,当ai+bj>aj+bi时，i在前，j在后；

1. 时间复杂度O（n^2），遍历就完了。复杂度好像有点高，没想到什么好办法，欢迎大神指点

• 

  class Solution {
  public:
    /**
     * 根据顾客属性计算出顾客排队顺序
     * @param a int整型vector 顾客a属性
     * @param b int整型vector 顾客b属性
     * @return int整型vector
     */
    vector<int> WaitInLine(vector<int>& a, vector<int>& b) {
        int n=a.size();
        vector<int> orders(1,0);
        for( int i=1; i<n; ++i )
        {
            bool flag=0;
            for( auto jbegin=orders.begin(), jend=orders.end(); jbegin!=jend; ++jbegin )
            {
                //排在前面
                if( a[i]+b[*jbegin] > a[*jbegin]+b[i] )
                {
                    orders.insert( jbegin,i );
                    flag=1;
                    break;
                }
            }
            if( !flag )
                orders.push_back(i);
        }
        for( int i=0; i<n; ++i )
            orders[i]++;
        return orders;
    }
  };

4.

遍历。O(n^2)

• 
• 

  class Solution {
  public:
    /**
     * 获取最大可同事办公员工数
     * @param pos char字符型vector<vector<>> 工位分布
     * @return int整型
     */
    int GetMaxStaffs(vector<vector<char> >& pos) {
        int count=0;
        for( int i=0; i<pos.size(); ++i )
        {
            for( int j=0; j<pos[i].size(); ++j )
            {
                if( pos[i][j]=='.' )
                {
                    if( i<pos.size()-1 )
                        pos[i+1][j]='*';
                    if( j<pos[i].size()-1 )
                        pos[i][j+1]='*';
                    ++count;
                }
            }
        }
        return count;
    }
  };