"笔试题代码整理"

  "笔试题"

Posted by Xu on July 17, 2018

笔试题整理

2018-07-15深信服笔试

1.给出一个数组,数组中有n个数,在这n个数中找到可以组合为100的任意组合

输入格式:

  • 第一行为数组个数:n
  • 后面n行为每个元素的值
5
20
10
30
50
5

输出格式:

  • 第一行为组合的元素个数m
  • 下面m行为组合的元素,且由大到小排列
3
20
30
50

思路:

  • 排列组合问题
  • 深度优先遍历尝试各种组合的可能,如果有满足和为100的组合即返回
bool dfs(vector<int>& v, int ix, int& rest, vector<int>& path)
{//深度优先遍历
    if (ix == v.size())//遍历到数组的最后一个元素
        return rest == 0;
    rest -= v[ix];
    if(rest<0)
        return false;
    path.push_back(ix + 1);
    if (dfs(v, ix + 1, rest, path)) return true;//取当前元素到组合中,遍历下一个元素
    rest += v[ix];
    path.pop_back();
    return dfs(v, ix + 1, rest, path);//不取当前元素到组合中,遍历下一个元素
}
int main()
{
    int n;
    cin >> n;
    vector<int> v(n, 0);
    for (int i = 0; i<n; ++i)
        cin >> v[i];
    int rest = 100;
    vector<int> path;
    dfs(v, 0, rest, path);//开始深度优先遍历
    cout << path.size() << endl;
    for (auto p : path)
        cout << p << endl;
}

2.重复子串

给出一个字符串,求该字符串中,出现连续重复(首尾相连)的字符串的最长长度是多少

"abcabcdl"
最长重复字符串为abcabc,长度为6

"abbbdebde"
最长重复字符串为bdebde,长度为6

思路:

  1. 使用后缀数组,将每个元素下标位置的后缀记录下来,下标位置也要记录
  2. 将这些后缀构成的数组进行排序
  3. 排序后,将相邻的相等的字符串进行比较,同时通过下标判断最长重复字符串
  4. 只要相邻字符串的公共长度超过两后缀字符串的下标之差,这两个后缀构成的最长重复子串为(abs(comlen/diff)+1)*abs(diff)
  5. 最后更新得到最长重复子串

例如

xcxcxcx

后缀xcxcx和xcxcxcx下标分别为2和0

下标之差为2,而公共部分长度为5

5>2所以肯定是以两个后缀之间的字符串为基础不断重复,重复的次数为5/2+1=3

所以得到其最长重复字符串长度为3*2 = 6
class Solution {
public:
    int getRepeatLen(string str) {
        int max = 0;
        int end = str.size();
        //vector<string> suffix;
        map<string, int> suffix_index;
        string tmp;
        for (int i = 0; i < end; i++) {
            tmp = str.substr(i,end);
            //suffix.push_back(tmp);
            suffix_index.insert(pair<string,int>(tmp,i));//插入到下标映射数组
        }

        auto iter_pre = suffix_index.begin();
        auto iter_back = suffix_index.begin();
        for (int i = 0; i < end-1; i++) {//比较相邻元素
            iter_back++;
            int comlen = getComLen(iter_pre,iter_back);
            int diff = (*iter_pre).second - (*iter_back).second;
            if (abs(comlen) >= abs(diff))
                max = max > (abs(comlen/diff)+1)*abs(diff) ? max : (abs(comlen / diff) + 1)*abs(diff);//这里尤其要注意,为什么是这样,只要公共子串的长度大于两后缀下标之差就要计算最长重复子串
            iter_pre++;
        }

        return max;
        
    }

    int getComLen(map<string, int>::iterator pre, map<string, int>::iterator back) {//获得公共子串长度
        string str1 = (*pre).first;
        string str2 = (*back).first;
        int sz = str1.size() > str2.size()? str2.size(): str1.size();
        int len = 0;
        for (int i = 0; i < sz; i++) {
            if (str1[i] == str2[i]) {
                len++;
            }
            else {
                break;
            }
        }
        return len;
    }
};

腾讯2018笔试题

1.小Q的歌单

链接:https://www.nowcoder.com/questionTerminal/f3ab6fe72af34b71a2fd1d83304cbbb3 来源:牛客网

小Q有X首长度为A的不同的歌和Y首长度为B的不同的歌,现在小Q想用这些歌组成一个总长度正好为K的歌单,每首歌最多只能在歌单中出现一次,在不考虑歌单内歌曲的先后顺序的情况下,请问有多少种组成歌单的方法。 输入描述: 每个输入包含一个测试用例。 每个测试用例的第一行包含一个整数,表示歌单的总长度K(1<=K<=1000)。 接下来的一行包含四个正整数,分别表示歌的第一种长度A(A<=10)和数量X(X<=100)以及歌的第二种长度B(B<=10)和数量Y(Y<=100)。保证A不等于B。

输出一个整数,表示组成歌单的方法取模。因为答案可能会很大,输出对1000000007取模的结果。

输入:
5
2 3 3 3

输出:
9

思路分析:

  1. 回溯法,同样是排列组合的问题,利用深度优先遍历,碰到每一个元素后选择拿或者不拿的问题。
  2. 动态规划:
    • 横坐标代表歌曲总长度
    • 纵坐标代表长度为A的歌曲编号及长度为B的歌曲编号
    • 二维数组中的元素代表,在当前编号前的所有歌曲中取长度为x共有多少种方案。
    • 状态转移方程:
      • 若当前元素还在长度为A的歌单范围中,则F[x][y] = F[x-A][y-1]+F[x][y-1];//前面一个式子代表取当前元素,后面式子代表不取当前元素
      • 否则F[x][y] = F[x-B][y-1]+F[x][y-1];
    • 如此直到最后一个元素F[K][X+Y]即为所有可能的组合总数

代码实现:只实现回溯法的,因为思路简单,利于笔试

class Solution {
public:
    int getSongComponents(int a, int x, int b, int y, int k) {//参数分别为,歌曲长度a,及数量x,歌曲长度b及其数量y,及要取的歌曲总长度
        long nums = dfs(a,x,b,y,k,0,0);
        return nums%1000000007;
        
    }

    //如果题目要求输出所有可能的分类方法,这里需要传入一个参数path来记录路径,当res==k时,将path输出即可
    long dfs(int a, int x, int b, int y, int k, int i, int res) {
        if (res > k)//当前元素组合已经超过限制时,直接返回当前方案失败
            return -1;
        if (res == k)//正好组合成功时,则直接返回组合成功
            return 1;
        long num1,num2;
        if (i < x) {//还在歌曲长度为a的歌单范围内时
            num1 = dfs(a, x, b, y, k, i + 1, res + a);//取当前a元素
            num2 = dfs(a, x, b, y, k, i + 1, res);
            //返回有多少种成功的方法
            if (num1 != -1 && num2 != -1) {
                return num1 + num2;
            }
            else if (num1 == -1 && num2 != -1)
                return num2;
            else if (num2 == -1 && num1 != -1)
                return num1;
            else
                return -1;//组合失败
        }
        else if (i >= x && i<x+y) {
            num1 = dfs(a, x, b, y, k, i + 1, res + b);//取当前b元素
            num2 = dfs(a, x, b, y, k, i + 1, res);//不取当前元素

            //返回有多少种可以成功的方法
            if (num1 != -1 && num2 != -1) {
                return num1 + num2;
            }
            else if (num1 == -1 && num2 != -1)
                return num2;
            else if (num2 == -1 && num1 != -1)
                return num1;
            else
                return -1;
        }
        else {
            return -1;//所有元素都作出选择后还是没有达到指定长度k
        }
            
    }
};

京东2018笔试

神奇数

神奇数:将一个数的数字分为两组,使得这两组的和相等,这样的数就叫做神神奇数,如242,可以分为{2,2}和{4}。所以242为神奇数,给出一个范围(l,r),且l>=1,r<=10^9,0<=r-l<=10^6。问该范围内有多少个神奇数。

简单一点说:给定一个数组,是否可以将该数组分为两个和相等的子数组。且数组中的每个元素都有一定的范围。

输入示例:
1,50

输出示例:
4

思路:

  1. 若一个数的数字可以平分成两组那么他所有数字之和一定是个偶数
  2. 平分后为所有数字之和的一半
  3. 所以我们需要求出所有可能的数字组成的和的情况。
  4. 如果这个和没有范围的话,那么这题不好处理,但这一题的数字之和是有范围的,因为r最多为9位数,每一位都为9的话,最多的和也只是81
  5. 所有我们只需要找到是否存在组合的和为总和sum的一半即可,而sum<=81,一半的范围只在41以内。
  6. 所以我们用一个有42的元素的bool数组s,来记录是否有组合可以达到0-42的任意一个数。最后判断s[sum/2]是否为真即可。

代码实现:

class Solution {
public:
    int getNum(int l, int r) {
        int res = 0;
        for (int i = l; i <= r; i++) {
            if (check(i))
                res++;
        }
        return res;
    }

    bool check(int num) {
        
        int s[9] = {0};
        int cur = 0, sum = 0;
        while (num>0) {
            s[cur] = num % 10;
            sum += s[cur++];
            num /= 10;
        }

        if (sum % 2) return false;//奇数不可能分为两组和相等的数组

        sum /= 2;

        bool a[42] = { 0 };
        a[0] = true;
        for (int i = 0; i < cur; i++) {//遍历所有数字
            int k = s[i];
            for (int j = 41; j >= 0; j--) {
                if (a[j] && k + j <= 41)//a记录所有可能的和的情况
                    a[k + j] = true;
            }
            if (a[sum]) {
                return true;
            }
                
        }
        return false;
    }
};

2.整除

给出一个数n,求能被1~n整除的最小的数。

输入: 3

输出: 6

思路:遍历1~n循环求最小公倍数

最小公倍数 = a*b/gcd(a,b);//乘积除以最大公约数

代码实现:

class Solution
{
public:
    int getNum(int n) {
        long cur = 1;
        for (int i = 2; i <= n; i++) {
            cur = cur*i/gcd(cur,i);
        }
        return cur % 987654321;
    }

    long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a%b);
    }
};