返回信息流第1题：旋转字符串
2018年8月5日 拼多多笔试算法第1道
时间限制：C/C++ 1秒，其他语言2秒；
空间限制：C/C++ 32768K，其他语言65536K；
64bit IO Format:%IId
题目描述：
给定一个字符串，按顺时针顺序输出一个正方形，具体规则如下：
(1) 从上边开始，上边从左到右；
(2) 然后到右边，右边从上到下；
(3) 然后是下边，下边从右到左；
(4) 最后是左边，左边从下到上。
输入描述：
输入一行，包含4K(K为整数，1<=K<=10)个小写字母。
输出描述：
输出K+1行，按上面的规则输出正方形，正方形内部用空格填充。
示例：
输入：
abcdefghijklmnop
输出：
abcde
p f
o g
n h
mlkj i
Java代码：
/**
* the first problem
* 旋转的字符串
*/
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String str = scanner.nextLine();
char[] chars = str.toCharArray();
int K = chars.length/4;
char[] spaces = new char[K-1];
for(int i = 0;i<K-1;i++){
spaces[i] = ' ';
}
String spaceStr = new String(spaces);
for(int i = 0;i < K+1;i++){//控制行数：分成三种情况
if(i == 0){
System.out.println(str.substring(0,K+1));
}else if(i >0 && i < K){
System.out.println(chars[4*K-i]+spaceStr+chars[K+i]);
}else{
System.out.println(new StringBuilder(str.substring(2*K,3*K+1)).reverse().toString());
}
}
}
第2题：有趣的变换
2018年8月5日 拼多多笔试算法第2道
时间限制：C/C++ 1秒，其他语言2秒；
空间限制：C/C++ 32768K，其他语言65536K；
64bit IO Format:%IId
题目描述：
字符串形式的正整数(可能包含前缀0,1<=length<=10)，先将这个字符串拆分成两部分，接着可以在这两部分中分别加入一个小数点也可以不加入，分别形成一个整数或小数。找出所有经“拆分”和“变化”两次操作后所有可能组合的数目。
要求：
1). 对于新形成的整数和小数，不可包含多余的前缀0，比如010和010.1不合法；
2). 对于小数，不可包含多余的后缀0，比如0.10不合法；
3). .1和1.这样的小数不合法。
输入描述：
输入为一行，包含一个字符串形式的正整数。
输出描述：
输出为一行，找出经过“拆分”和“变化”后的所有组合的数目。
示例1：
输入： 123
输出： 4
说明：[[1,23],[12,3],[1.2,3],[1,2.3]]
示例2：
输入： 00011
输出： 2
可能的组合如下：
[[0.001,1],[0,0.011]]
Java代码
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String numStr = scanner.nextLine();
char[] nums = numStr.toCharArray();
int count = 0;
for(int i = 0;i < nums.length-1;i++){
int leftCount = halfCount(nums,0,i);
if(leftCount == 0) continue;//提高效率；左段不存在；右段就不用统计了
int rightCount = halfCount(nums,i + 1,nums.length-1);
count += leftCount*rightCount;
}
System.out.println(count);
}
public static int halfCount(char[] nums,int from ,int end){
if(from == end) return 1;//一位数肯定就一种
if(nums[from] == '0'&& nums[end] == '0') return 0;//前后都有0，肯定不合法
if(nums[from] == '0'|| nums[end] == '0') return 1;//以0开头只能为0.xxx;以0结尾只能为整数
return end-from+1;//如345,：345,3.45,34.5
}
第3题：多多社交推荐
2018年8月5日 拼多多笔试算法第3道
时间限制：C/C++ 1秒，其他语言2秒；
空间限制：C/C++ 32768K，其他语言65536K；
64bit IO Format:%IId
题目描述：
给定一个含有N个用户的朋友列表，对于一个指定用户，找出这个用户最可能认识的人。最可能认识的人的定义为这个人和当前用户不是朋友关系，但有最多的共同朋友。
朋友关系是相互的(如果A列出B为朋友，B也会列出A为朋友)，如果两个用户都有同样多的共同朋友，返回用户序号(从0开始)小的用户。如果用户和所有人都没有共同朋友，返回-1。
输入描述：
第一行两个数，第一个数表示用户数目N(N小于等于100)，第二个数为需要判断的用户序号。第2至N+1行表示序号为0到序号为N-1的每个用户的朋友序号列表，每个列表的长度小于100。
输出描述：
给定用户最可能认识的人的用户序号。
示例：
输入：
5 0
1 2 3
0 4
0 4
0 4
1 2 3
输出：
4
说明：用户0与用户1、2、3都相互认识，用户4与用户1、2、3都相互认识。
Java代码 待续......
第4题：升序降序取数游戏
2018年8月5日 拼多多笔试算法第4道
时间限制：C/C++ 1秒，其他语言2秒；
空间限制：C/C++ 32768K，其他语言65536K；
64bit IO Format:%IId
题目描述：
多多鸡正在玩一个取卡片的游戏，有n个标有正整数的卡片，从左到右一次排列，每轮取卡多多鸡必须满足升序规则和降序规则中的一种：
升序规则：取出的右边卡片数值大于左边卡片数值；
降序规则：取出的右边卡片数值小于左边卡片数值；
帮多多鸡算算最少需要多少轮游戏可以取完所有的卡片。
输入描述：
输入为两行，第一行为卡片个数n(1<= n<=50)，第二行为长度为n的正整数序列。
输出描述：
一个整数，代表最少的轮次。
示例1：
输入：
5
3 5 2 4 1
输出：
2
说明：
第一轮321，第二轮54
示例2：
输入：
6
1 2 4 3 3 3
输出：
3
说明：
第一轮13，第二轮23，第三轮43
Java代码 待续......
这是一条镜像帖。来源：北邮人论坛 / java / #59823同步于 2018/8/6
该镜像源已超过 30 天没有更新，可能在源站已被删除。
Java机器人发帖
2018年8月5日晚 【拼多多】算法题目第3、4题求助
zhaoxiyuan
2018/8/6镜像同步7 回复
订阅后，新回复会通过你的通知中心匿名送达。
7 条回复
第三题感觉可以直接暴力啊，N不超过100，并且每个人的朋友数也不超过100，建立一个res = [0]*N存储共同朋友数,拿测试样例来说，遍历0认识的所有人（1,2,3）`因为朋友数不超过100，所以循环次数不超过100`，遍历到1时，就把所有认识1的人res+1`这里也不超过100，所以总共不会超过10000`，最后排个序，然后排除自己本身，排除已经认识的人，取剩下最高的数的下标就Ok了吧（sort是稳定排序，所以此时最高就是下标最小）
暴力之前能不能先给我讲一讲第四题什么意思？
【 在 a2013211232 的大作中提到: 】
: 第四题感觉又可以用暴力啊，我的第一反应是进行若干次最长上升（下降）子序列的判断。。。毕竟数据长度不超过50，但感觉有点蠢
【 在 zhaoxiyuan 的大作中提到: 】
: 第1题：旋转字符串
: 2018年8月5日 拼多多笔试算法第1道
: 时间限制：C/C++ 1秒，其他语言2秒；
: ...................
第三题每个人建立一个朋友表hash，然后查询用户q和每个不是他朋友的共同好友的最大个数，直接暴力就好了；
第四题正序和逆序搜最长递增子序列，要注意的一点是相邻且相等值优先
但是代码是真恶心。
因为要找到具体的LIS，所以只能用O(n^2) DP。然后还要回头找LIS。然后再做好多轮。。=。=
【 在 a2013211232 的大作中提到: 】
: 第四题感觉又可以用暴力啊，我的第一反应是进行若干次最长上升（下降）子序列的判断。。。毕竟数据长度不超过50，但感觉有点蠢
多个LIS方案时咋办，如何保证正确性呢？
【 在 Wizmann 的大作中提到: 】
: 但是代码是真恶心。
: 因为要找到具体的LIS，所以只能用O(n^2) DP。然后还要回头找LIS。然后再做好多轮。。=。=
: