JD机试代码_京东神奇树和疯狂数列

/*京东神奇树
思路：
来一个数，先把他数位拆分放到vector
再判断vector能不能分为两部分，和相等
转换为求是否存在vector的子集，满足子集中的数之和等于vector中所有数的和的一半*/

#include<iostream>
#include<vector>
using namespace std;
vector<int> vec;
void putDigitIntoVec(int num, vector<int> &v)
{
    while(num != 0)
    {
        int n = num % 10;
        v.push_back(n);
        num = num / 10;
    }
}

bool isSumEqual(vector<int> v, int target)
{
    vector<int> tmp;
    int length = v.size();
    int num = (1 << length) - 1;
    for(int i = 1; i <= num; ++i)
    {
        int idx = 0;
        int j = i;
        while(j > 0)
        {
            if(j & 1)
            	tmp.push_back(v[idx]);
            idx++;
        	j = j >> 1;
        }
        int sumsum = 0;
        for(int ii = 0; ii < tmp.size(); ii++)
        {
            sumsum = sumsum + tmp[ii];
        }
        if(sumsum == target)
            return true;
        tmp.clear();
    }
    return false;
}

bool isTwoSumEqual(vector<int> v)
{
    int sum = 0;
    for(int i = 0; i < v.size(); ++i)
        sum = sum + v[i];
    if(sum % 2 == 1)
        return false;
    sum = sum / 2;
    if(isSumEqual(v,sum))
        return true;
    else
        return false;
}

int f(int l, int r)
{
    int ret = 0;
    for(int i = l; i <= r; ++i)
    {
        putDigitIntoVec(i, vec);
        if(isTwoSumEqual(vec))
        {
            ret++;
        }
        vec.clear();
    }
    return ret;
}

int main()
{
    int left, right;
    while(cin >> left >> right)//注意while处理多个case
    {
        if(left > right)
            return 0;
        else
            cout << f(left, right) << endl;
    }
}

==========================================================================================================================
/*京东疯狂数列
思路：
等差数列求和
*/
#include<iostream>
#include<math.h>
using namespace std;

long long f(long long n)
{
    long long a = 1 + 4 * 2 * n;
    double d = sqrt(a) - 1;
    double dd = d / 2;
    long long root = (long long)dd;
    if(root * (root + 1) < 2 * n)
        return root + 1;
    if(root * (root + 1) == 2 * n)
        return root;
    return 0;
}

int main()
{
    long long n;
    while(cin >> n)//注意while处理多个case
    {
        if(n < 1)
            return 0;
        else
            cout << f(n) << endl;
    }
    return 0;
}