今日头条客户端工程师实习生笔试题-2017年

1、现在有一个字符串，你要对这个字符串进行 n 次操作，每次操作给出两个数字：(p, l) 表示当前字符串中从下标为 p 的字符开始的长度为 l 的一个子串。你要将这个子串左右翻转后插在这个子串原来位置的正后方，求最后得到的字符串是什么。字符串的下标是从 0 开始的，你可以从样例中得到更多信息。

2、你作为一名出道的歌手终于要出自己的第一份专辑了，你计划收录 n 首歌而且每首歌的长度都是 s 秒，每首歌必须完整地收录于一张 CD 当中。每张 CD 的容量长度都是 L 秒，而且你至少得保证同一张 CD 内相邻两首歌中间至少要隔 1 秒。为了辟邪，你决定任意一张 CD 内的歌数不能被 13 这个数字整除，那么请问你出这张专辑至少需要多少张 CD ？

3、给出 n 个字符串，对于每个 n 个排列 p，按排列给出的顺序(p[0] , p[1] … p[n-1])依次连接这 n 个字符串都能得到一个长度为这些字符串长度之和的字符串。所以按照这个方法一共可以生成 n! 个字符串。

一个字符串的权值等于把这个字符串循环左移 i 次后得到的字符串仍和原字符串全等的数量，i 的取值为 [1 , 字符串长度]。求这些字符串最后生成的 n! 个字符串中权值为 K 的有多少个。

注：定义把一个串循环左移 1 次等价于把这个串的第一个字符移动到最后一个字符的后面。

4、给定 x, k ，求满足 x + y = x | y 的第 k 小的正整数 y 。 | 是二进制的或(or)运算，例如 3 | 5 = 7。

比如当 x=5，k=1时返回 2，因为5+1=6 不等于 5|1=5，而 5+2=7 等于 5 | 2 = 7。

参考答案

1、参考代码：

importjava.util.Scanner;
 
public class Main{ 
 
    public static void main(String[]args){
 
        Scanner a = new Scanner(System.in);
 
        StringBuffer bf = new StringBuffer(a.next());
 
        int n = a.nextInt();
 
        a.nextLine();
 
        for(int i=0; i<n; i++){
 
            String[] aa = a.nextLine().split(" ");
 
            int p = Integer.parseInt(aa[0]);
 
            int l = Integer.parseInt(aa[1]);
 
            StringBuffer sb= newStringBuffer(bf.substring(p,p+l));
 
            sb.reverse();
 
            bf.insert(p+l,sb);
 
        }
 
        System.out.println(bf.toString());
 
    }
 
}

2、参考代码：

import java.util.*;
 
public class Main{
     
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int n = in.nextInt();
            int s = in.nextInt();
            int l = in.nextInt();
            int count = (l+1)/(s+1);
            count = Math.min(n, count);
            if(count%13==0){
                count--;
            }
            int sum = n/count;
            int yu = n%count;
            if(yu!=0){
                sum++;
                if(yu%13==0&&(count-yu)==1){//查看最后最后一张专辑的情况
                    sum++;
                }
            }
            System.out.println(sum);
        }
    }
}

3、参考代码：

import java.util.*;
public class Main{
    static ArrayList<String> res;
    public static int next(String arr){
        int[] next=new int[arr.length()+1];
        int res=1;
        next[0]=next[1]=0;
        int j=0;
        for(int i=1;i<arr.length();i++){
            while(j>0&&arr.charAt(i)!=arr.charAt(j)) j=next[j];
            if(arr.charAt(i)==arr.charAt(j)) {
                j++;
            }
            next[i+1]=j;
        }
        if(arr.length()%(arr.length()-next[arr.length()])==0)
            res=arr.length()/(arr.length()-next[arr.length()]);
        return res;
    }
    public static void allString(String[] strr,int s,int n){
        String tmp;
        if(s==(n-1)){
            tmp="";
            for(int i=0;i<n;i++){
                tmp+=strr[i];
            }
            res.add(tmp);
        }  
        for(int i=s;i<n;i++){
            tmp=strr[s];
            strr[s]=strr[i];
            strr[i]=tmp;
            allString(strr,s+1,n);
            tmp=strr[s];
            strr[s]=strr[i];
            strr[i]=tmp;
        }
    }
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n,k,count;
        String[] strr;
        while(sc.hasNext()){
            res=new ArrayList<String>();
            count=0;
            n=sc.nextInt();
            k=sc.nextInt();
            strr=new String[n];
            for(int i=0;i<n;i++){
                strr[i]=sc.next();
            }
            allString(strr,0,n);
            for(int i=0;i<res.size();i++){
                if(next(res.get(i))==k)
                    count++;
            }
            System.out.println(count);
        }
        sc.close();
    }
}

4、参考代码：

#include <iostream>
using namespace std;
int main()
{
    long long x, k;
    cin >> x >> k;
    long long bitNum = 1;
    long long ans = 0;
    //目标是把k的各位依次填在x中是0的位上
    //bitNum用来移动到x中零的位置，然后把k的最低位放在x的零位上, k左移，将下一位变成最低位,bitNum一直左移，知道x中的下一个为0的位上。
    while (k)
    {
        if ((x & bitNum) == 0) //x中当前bitNUM为0的话,把k的最低位放在这儿
        {
            ans += (bitNum*(k & 1)); //k&1是将k的最低位取出来, bitNum*(k&1)的结果就是得到bitNum位和当前k的最低位一样的一个数,而其它位都是0
            //而ans原来的bitNum为肯定为0，ans+(bitNum*(k&1)) 就将k的最低位放在x的这个零上了。
            k >>= 1;
        }
 
        bitNum <<= 1; //bitNum的1一直左移到x中第k个零的位置
    }
    cout << ans << endl;
    return 0;
}