京东2018秋招技术类笔试题

1、求幂
东东对幂运算很感兴趣,在学习的过程中东东发现了一些有趣的性质: 9^3 = 27^2, 2^10 = 32^2 东东对这个性质充满了好奇,东东现在给出一个整数n,希望你能帮助他求出满足 a^b = c^d(1 ≤ a,b,c,d ≤ n)的式子有多少个。 例如当n = 2: 1^1=1^1 1^1=1^2 1^2=1^1 1^2=1^2 2^1=2^1 2^2=2^2 一共有6个满足要求的式子。

输入描述: 输入包括一个整数n(1 ≤ n ≤ 10^6)
输出描述: 输出一个整数,表示满足要求的式子个数。因为答案可能很大,输出对1000000007求模的结果
示例1： 输入 2
输出 6

题目分析：

两边底数相同时：（1）以1为底 ，则两边指数为任意值(1~n)，一共有n*n种 
               （2）除1以外的数为底，则两边指数相同(1~n之间取值），共有（n-1)*n种

两边底数不相同： 分析公式得出：(i^x)^c=(i^y)d,且x!=y;
求(x,y)的最大公约数：gcd(x,y) ; y/gcd(x,y)是约分后的分母，n/(y/gcd(x,y))表示n内有多少个最简分数的倍数，也就是有多少组c和d。等号左右交换位置也是成立的，所以一共有2*(n/(y/gcd(x,y)))种

c++实现：

#include<iostream>
using namespace std;
#include<set>

#define LL long long
const int mod = 1e9 + 7;

int gcd(int x, int y) // 求x，y的最大公约数
{
    return (x % y == 0) ? y : gcd(y, x % y);
}

int main()
{
    long long n; 
    cin >> n;

    // 左右两边底相同时，满足条件的等式个数
    long long count =  (n * n + n * (n - 1)) % mod;

    // 下面求两边底数不相同时，满足条件的个数
    set<int>s;
    for (int i = 2; i * i <= n; i++)
    {
        if (s.find(i) != s.end()) // 如果已经存在则跳过
            continue;
        long long temp = i;
        int cnt = 0;
        while (temp <= n)
        {
            s.insert(temp);
            temp = temp * i;
            cnt++;
        }

        for (int i = 1; i <= cnt; i++)
        {
            for (int j = i + 1; j <= cnt; j++)
            {
                count = (count + (n / j / gcd(i,j))*2) % mod;
            }
        }
    }

    cout << count << endl;
    return 0;
}

2、括号匹配方案
合法的括号匹配序列被定义为:

1. 空串""是合法的括号序列
2. 如果"X"和"Y"是合法的序列,那么"XY"也是一个合法的括号序列
3. 如果"X"是一个合法的序列,那么"(X)"也是一个合法的括号序列
4. 每个合法的括号序列都可以由上面的规则生成
   例如"", "()", "()()()", "(()())", "(((())))"都是合法的。
   东东现在有一个合法的括号序列s,一次移除操作分为两步:
   第一步： 移除序列s中第一个左括号
   第二步：移除序列s中任意一个右括号.保证操作之后s还是一个合法的括号序列
   东东现在想知道使用上述的移除操作有多少种方案可以把序列s变为空
   如果两个方案中有一次移除操作移除的是不同的右括号就认为是不同的方案。
   例如: s = "()()()()()",输出1, 因为每次都只能选择被移除的左括号所相邻的右括号.
   s = "(((())))",输出24, 第一次有4种情况, 第二次有3种情况, ... ,依次类推, 4 * 3 * 2 * 1 = 24
   输入描述: 输入包括一行,一个合法的括号序列s,序列长度length(2 ≤ length ≤ 20).
   输出描述: 输出一个整数,表示方案数
   题目分析：
   思路：遍历字符串，每次把左括号都压入栈，每次遇到右括号，先统计栈中有几个左括号，统计数与上次统计数相乘，接着弹出栈中的一个左括号，直到遍历结束，结果即为方案数

   #include<iostream>
   #include<string>
   #include<stack>
   using namespace std;
   int main()
   {
    string str;
    cin >> str;
    int res = 1; int top=0;
    for(int i = 0; i < str.size(); i++)
    {
        stack<char> s;
        if(str[i] == '(')
        {
            s.push(str[i]);
            top++;
        }
        else if(str[i] == ')')
        {
            res *= top;
            s.pop();
            top--;
        }
    }
    cout << res << endl;
    return 0;
   }

3、牛牛的括号匹配
如果一个括号序列中的每个左括号都有一个右括号与之完成配对，这个序列就是一个合法的括号匹配序列。
例如"((())), ()()()“是合法的括号匹配序列, 而”(((()) ()((()"不是。
牛牛得到了一系列的括号序列, 牛牛要从这个序列中任意选取两个位置进行一次交换操作, 牛牛必须进行一次且仅一次操作。
牛牛想知道能否通过这次操作, 把这个序列变为合法的括号匹配序列。
例如序列 s = “())(”, 对第三个位置和第四个位置进行交换变为 s = “()()”, 这是一个合法的括号匹配序列。

输入描述:
输入的第一行包括测试样例数 t(1 <= t <= 1000),
接下来的 t 行, 每行一个括号序列 s(1 <= length(s) <= 100000),表示每个括号序列。
输出描述:
如果可以通过一次交换变为合法的括号匹配序列,则输出"Yes",否则输出"No"

输入示例：2
         ())(
         )))(((
输出：
        Yes
        No

题目分析：字符串长度必须是偶数；左括号和右括号个数相同；（）经过变换后为不合法序列；

#include<bits/stdc++.h>
using namespace std;
bool match(const string &str)
{
    if(str=='()')
        return false;
    if(str.size()%2!=0)
        return false;
    stack<char> s;
    int count=0;
    for(int i=0;i<str.size();i++)
    {
         if(str[i]=='(')
            s.push('(');
        else
        {
            if(s.empty())
            {
                ++count;
                if(count>2) 
                    return false;
            }
            else
                s.pop();
        }
    }
    if(count==s.size())
        return true;
    return false;
}

int main()
{
    int t=0;
    cin>>t;
    while(t--)
    {
        string str;
        cin>>str;
        if(match(str))
            cout<<Yes<<endl;
        else
            cout<<No<<endl;
    }
    return 0;
}

4、疯狂序列
东东从京京那里了解到有一个无限长的数字序列: 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, ...(数字k在该序列中正好出现k次)。东东想知道这个数字序列的第n项是多少,你能帮帮他么
输入描述:输入包括一个整数n(1 ≤ n ≤ 10^18)
输出描述:输出一个整数,即数字序列的第n项。
示例：输入 169 输出 18
题目解析：
相当于求：1+2+3+4+......+x>=n时x的最小值，即f(x)=(x+1)*x/2>=n,求解该二元一次方程，再向上取整得到x：x>=sqrt(2n+1/4)-1/2;

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    long long int n;
    cin>>n;
    long long num=0;
    long double x=sqrt(2*n+1/4)-1.0/2;
    num=x+1;
    cout<<num<<endl;
    return 0;
}

5、回文序列
回文是指从前往后读和从后往前读是一样的词语。京京准备给东东一个惊喜,先取定一个字符串s,然后在后面附上0个或者更多个字母形成回文,京京希望这个回文越短越好。请帮助京京计算他能够得到的最短的回文长度。
输入描述:输入包括一个字符串s,字符串s长度length(1 ≤ length ≤ 50)
输出描述:输出一个整数,表示牛牛能够得到的最短的回文长度。
输入：abab
输出：5
题目解析：利用排序算法reverse，将给定的字符串反转，并与原字符串比较，若相等，则为回文序列；不相等的话就在原字符串后面追加字符；

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
bool huiwen(string s) //判断字符串是否为回文序列
{
    string s2=s;
    reverse(s2.begin(),s2.end());
    if(s2==s)
        return true;
    else
        return false;
}
int main()
{
    string s;
    cin>>s;
    if(huiwen(s))
        cout<<s.size()<<endl;
    else
    {
        int(i=1;i<s.size();i++)
        string temp=s;
        string temp1=temp.substr(0,i);
        reverse(temp1.begin(),temp1.end());
        temp=temp+temp1;
        if(huiwen(temp))
        {
            cout<<temp.size()<<endl;
            break;
        }
    }
   return 0;
}