lgyx2017校招笔试题

关键词：

前言

今天通知过了笔试，但总感觉有些笔试没来得及做的题不解决不舒服斯基。

题目

 大意就是，给你个形如a,b,c,ab,bb,cb,ac,bc,cc,aab,bab,cab,abb,bbb,cbb,acb,bcb,ccb......按某种规律排列的无限长的字符串数组，要求：

1）给定一个位置，输出对应的字符串。

2）给定一个字符串，找出它在这个数组里的位置。

思路

 仔细观察会发现其实就是用a,b,c在每一个字符串上不断循环头插得到新的字符串，比如a,b,c循环在b,c字符上头插得到,ab,bb,cb,ac,bc,cc，然后又在,ab,bb,cb,ac,bc,cc字符串的头部插入得到,aab,bab,cab,abb,bbb,cbb,acb,bcb,ccb......ccc。也就是说N位长度的一系列字符串是在N-1位长度的字符串上头插a,b,c得到的。那么可以用一个动态增长的数组来模拟这种情况，c++的vector是个不错的选择。

另外还要知道的是：N位长的字符串集合的最后一个字符串在该数组中的位置是3 ^ N，比如1位长的最后一个字符是“c”,位置在3^1 = 3。同理2位长度的最后一个字符串"cc"位置为9，同理"ccc"位置为27，以此类推。所以数组不管如何更新，它的长度一定是3^N，且N位长度的字符串的个数为2 * 3^(N - 2)。

那么对于 题目1) 求指定位置的字符串有如下代码：

#include<iostream>
#include<vector>
#include<math.h>
using namespace std;
const string base = "abc";
int main()
{
    int pos;
    vector<string> res = {"woshishabi","a","b","c"};  //动态增长的字符串数组，从1开始操作更方便
    while(cin >> pos)  //根据输入的位置来更新数组
    {
       int index = pos + 1; //加一，因为题目要求从0开始，但是从1开始便于操作。
       int len = res.size() - 1;
       if(index <= len)  //先判断指定位置的字符串所在的字符串集合是否已经在数组中了。
       {
           cout << res[index] << endl;
           continue;
       }
       //没有的话就把它所在的对应位数的所有字符串放入数组中
       int digit = 1;
       while(pow(3,digit) < index)
       {
           digit++; //循环结束得到需要更新的digit位长的字符串
       }
       int End = pow(3,digit - 1); //digit - 1位字符串的结束位置
       //int dis = num - len;
       int start = 1 + len - 2 * pow(3,res[len].size() - 1); //res中的最多位数的字符串集合的开始位置
       while(start != End) //开始更新字符串数组
       {
           for(int i = 0;i < base.size();i++)
           {
               string temp = res[start];
               temp.insert(0,1,base[i]);
               res.push_back(temp);
           }
           start++;
       }
       cout << res[index] << endl; //输出对应位置的字符串即可
    }
}

可以看到初始我是先把a,b,c放入数组中。然后基于输入的位置来确定需要更新到的最大位数。

对于题目2)求指定字符串的位置，

1.可以根据它的长度L确定它所在集合的最后一个字符串的位置lastpos = pow(3,L)。

2.求这个字符串集合的首位置startpos = lastpos - 2 * 3^(L- 2) + 1。

3.然后在[startpos,lastpos]区间找这个字符串就行，如果lastpos > res的长度，转4.

4.如果lastpos > res的长度就用题目1)的解决方法更新res的内容就行，然后再去查找。

微软2017校招笔试题3registrationday

题目It‘sHUniversity‘sRegistrationDayfornewstudents.ThereareMofficesinHUniversity,numberedfrom1toM.Studentsneedtovisitsomeoftheminacertainordertofinishtheirregistrationprocedures.Theofficesareindifferent 查看详情

小米2017校招笔试题

只过了20%...我日树的高度 时间限制：C/C++语言1000MS；其他语言3000MS 内存限制：C/C++语言65536KB；其他语言589824KB 题目描述： 现在有一棵合法的二叉树，树的节点都是用数字表示， 现在给定这棵树上所有的父子关系，求这棵树的高... 查看详情

网易2017年校招笔试题最大的奇约数

题目：定义函数f(x)为x的最大奇数约数，x为正整数，例如f(44)=11.现在给出一个N,需要求出f(1)+f(2)+f(3)+...+f(N)例如：N=7f(1)+f(2)+f(3)+f(4)+f(5)+f(6)+f(7)=1+1+3+1+5+7=21. 分析：奇数的最大约数是自身，偶数的最大约数是是除去所有偶因子之... 查看详情

奇虎3602017校招笔试题

最强大脑时间限制：C/C++语言1000MS；其他语言3000MS内存限制：C/C++语言65536KB；其他语言589824KB题目描述：小B乘火车和朋友们一起在N市到M市之间旅行。她在路途中时睡时醒。当她醒来观看窗外的风景时，注意到每个火车站都有一... 查看详情

校招笔试题大杂烩

1、某表达式的前缀形式为"+-*^ABCD/E/F+GH",运算符优先级为^>*/>-+,它的中缀形式为(C)A  A^B*C-D+E/F/G+H  B A^B*(C-D)+(E/F)/G+H  C  A^B*C-D+E/(F/(G+H))  D A^B*(C-D)+ 查看详情

快手2019校招笔试题(代码片段)

目的：分别从前面和后面开始找划分点，使得前面的数字之和=后面的数字之和目标表述：sum(前面m个数)=sum(后面n个数）s.t.m+n<=N（总个数）变形：sum[i]表示前i个数之和，sum2[i]表示后i... 查看详情

1~n的全排列--阅文集团2018校招笔试题

题目大意：给定整数n，求出1~n的全排列示例输入：n=3输出：[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]1importjava.util.Scanner;2importjava.util.ArrayList;34publicclassMain{5privatevoidfunc(ArrayList<Integer>nArray,Arra 查看详情

兆易创新9月校招笔试题_ic设计/验证

       还有器件岗位的笔试题：1、CMOS中哪些制造步骤中用到了离子注入，需要注意哪些？2、有哪些薄膜制备方法？各有什么优缺点？3、COMS的制作步骤，简要叙述。4、载流子的输运方式有哪些，简要叙... 查看详情

天上掉馅饼--移动研究院2018校招笔试题

题目：天上掉馅饼时间限制：C/C++语言1000MS；其他语言3000MS内存限制：C/C++语言131072KB；其他语言655360KB题目描述：大家都知道“天上不会掉馅饼”这句话，但是有一天，小明在回学校的路上，天上还真掉起了馅饼。小明的人品实... 查看详情

网易2019校招笔试题-瞌睡(代码片段)

分析：由于小易清醒的时间是连续的，所以整个搜索空间为O(n)，根本不需要贪心或者动态规划就能搞定。小易这堂课获得的兴趣值分为两部分：本来就清醒时获得的兴趣值，被叫醒的k分钟获得的兴趣值。因为... 查看详情

阿里巴巴2016校招笔试题（含答案解析）(代码片段)

3、将1,2,3,……,99,100任意排列成一个圈，相邻两数的差的绝对值求和最多为（）A：100B：198C：200D：500E：2500F：5000答案：F4、如果下列的公式成立：84*148=B6A8。则采用的是（&# 查看详情

快手2019校招笔试题(代码片段)

目的：分别从前面和后面开始找划分点，使得前面的数字之和=后面的数字之和目标表述：sum(前面m个数)=sum(后面n个数）s.t.m+n<=N（总个数）变形：sum[i]表示前i个数之和，sum2[i]表示后i... 查看详情

网易2017秋招笔试题3：最长公共子括号序列长度

【问题来源】网传的2017网易秋招笔试题【问题描述】 【算法思路】 下面的解题思路摘自 http://www.cnblogs.com/Atanisi/p/7500186.html刚看到题我就想到暴力解，深搜出所有合法的括号序列，再依次比较公共子序列的长度，返... 查看详情

tx2017秋招笔试题之素数对

问题描述：给定一个正整数，编写程序计算有多少对质数的和等于输入的这个正整数，并输出结果。输入值小于1000。如，输入为10,程序应该输出结果为2。（共有两对质数的和为10,分别为(5,5),(3,7)）输入描述:输入包括一个整数n,(3... 查看详情

2017华为优招笔试题

 哎，没有接到笔试通知，不知道为啥就错过了。之后见到题目，前两道编程题。其实都见过类似的题目，有点思路，但是直接快速完整实现出来，水平还是达不到。这样的题目，也不算难，三道编程题至少AC两道才算可以。... 查看详情

校招笔试题

题目描述：给出m个字符串S1，S2，...，Sm和一个单独的字符串T。请在T中选出尽可能多的子串同时满足：1）这些子串在T中互不相交。2）这些子串都是S1，S2，...，Sm中的某个串。问最多能选出多少个子串。输入第一行一个数m（1≤... 查看详情

美团2017秋招笔试题拼凑钱币

给你六种面额1、5、10、20、50、100元的纸币，假设每种币值的数量都足够多，编写程序求组成N元（N为0~10000的非负整数）的不同组合的个数。 输入描述:输入包括一个整数n(1≤n≤10000)输出描述:输出一个整数,表示不同的组合方... 查看详情

2017腾讯秋招笔试题之编码

Description：  假定一种编码的编码范围是a~y的25个字母，从1位到4位的编码，如果我们把该编码按字典序排序，形成一个数组如下：a,aa,aaa,aaaa,aaab,aaac,……,b,ba,baa,baaa,baab,baac……,yyyw,yyyx,yyyy其中a的Index为0，aa的Index为1，aaa的... 查看详情