java编程题汇总（Java工程师）

java编程题汇总（Java工程师）

1.【爱奇艺】考虑定义在两正整数上的函数SSR(平方根之和的平方):SSR(A, B) = (sqrt(A)  sqrt(B))^2。牛牛对函数值为整数的情况很感兴趣。现在给定整数n和m,请帮助牛牛计算有序对(A, B)的数量, 满足1 ≤ A ≤ n, 1 ≤ B ≤ m而且SSR(A, B)是一个整数。

思路：

因为SSR(A, B) = (sqrt(A)  sqrt(B))^2 = A  B  2sqrt(AB)，所以只需要判断sqrt(AB)是否为整数即可。

可以发现，当 A = i ,B = i * j * j时，进行开方运算后结果一定为整数。

例如，从小的值开始遍历，当A = 1时， 可以取1*1*1, 1*2*2, 1**,…直到<= B值 
                                            当A = 2时， 可以取2*1*1, 2*2*2, 2** … 直到 <= B值 

解答：

public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int m = ();int n = ();int big = m > n ? m : n;int small = m < n ? m : n;int res = 0;for (int i = 1; i <= small; i) {int s = 1;for (int j = 2; j <= i / j; j) {if (i % (j * j) == 0) {s = j * j;}}int r = i / s;for (int j = 1; j * j * r <= big; j) {res;}}println(res);}
}

---

2.【爱奇艺】对于任意两个正整数x和k,我们定义repeat(x, k)为将x重复写k次形成的数,例如repeat(124, ) = 124124124,repeat(20,2) = 2020.牛牛现在给出4个整数x1, k1, x2, k2, 其中v1 = (x1, k1), v2 = (x2, k2),请你来比较v1和v2的大小。

例如：1010 1 10101010 2。

思路：

按照给定的值进行数据的拼接，判断两个数哪个的长度长，长度长的数据较大；若数据长度相同，则需要逐个字符进行比较。

解答：

import java.util.Scanner;public class aqy1 {public static void main(String args[]) {Scanner sc = new Scanner(System.in);int x1 = ();int k1 = ();int x2 = ();int k2 = ();compare(x1, k1, x2, k2);}public static void compare(int x1, int k1, int x2, int k2) {StringBuilder sb1 = new StringBuilder();StringBuilder sb2 = new StringBuilder();while (k1-- > 0) sb1.append(x1  );while (k2-- > 0) sb2.append(x2  );int l1 = sb1.length(), l2 = sb2.length();if (l1 > l2) {println(Greater);return;} else if (l1 < l2) {println(Less);return;}for (int i = 0; i < l1; i)if ((i) > (i)) {println(Greater);return;} else if ((i) < (i)) {println(Less);return;}println(Equal);}
}

---

.【爱奇艺】一个合法的括号匹配序列有以下定义:
1、空串是一个合法的括号匹配序列
2、如果X和Y都是合法的括号匹配序列,XY也是一个合法的括号匹配序列
、如果X是一个合法的括号匹配序列,那么(X)也是一个合法的括号匹配序列
4、每个合法的括号序列都可以由以上规则生成。
例如: ,(),()(),((()))都是合法的括号序列
对于一个合法的括号序列我们又有以下定义它的深度:
1、空串的深度是0
2、如果字符串X的深度是x,字符串Y的深度是y,那么字符串XY的深度为max(x,y) 、如果X的深度是x,那么字符串(X)的深度是x1
例如: ()()()的深度是1,((()))的深度是。牛牛现在给你一个合法的括号序列,需要你计算出其深度。

思路：

左右括号的题一般用栈都很好做，遇到左括号就放到栈里，遇到右括号就pop出一个左括号（因为肯定合法，不需要什么判断）。这道题其实就是问栈里边最多的时候有多少个左括号。由于没有别的要进行处理的，甚至可以用一个 int 来当做栈，记录栈里边有多少左括号。

解答：

import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String s = ();int cnt = 0, max = 0, i;for (i=0; i<s.length(); i) {if ((i) == 	(	)cnt;elsecnt--;max = (max, cnt);}println(max);}
}

---

4.【爱奇艺】【数字游戏】牛牛举办了一场数字游戏,有n个玩家参加这个游戏,游戏开始每个玩家选定一个数,然后将这个数写在纸上(十进制数,无前缀零),然后接下来对于每一个数字将其数位按照非递减顺序排列,得到新的数,新数的前缀零将被忽略。得到最大数字的玩家赢得这个游戏。例如:2 601 1940  输出结果为:106

思路：

首先要将输入的每个数字的数位按照非递减顺序排列，然后将所有的数字进行排序

解答：

// 我是写个方法用List做的反转，然后用StringBuffer直接在后面加，再返回为int的反转值【Integer.parseInt()会自动去掉前缀0】 
// 接着 主方法写个取最大的反转值就行import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int num = ();int max = 0;while (num-- > 0) {int cur = getReverse(());max = cur > max ? cur : max;}println(max);}static int getReverse(int x) {List<Integer> temp = new ArrayList<Integer>();while (x != 0) {temp.add(x%10);x /= 10;}Collecti.sort(temp);StringBuffer sb = new StringBuffer();for (int i = 0; i < temp.size(); i) {sb.append(temp.get(i));}return Integer.parseInt(());}
}

---

5.【爱奇艺】【缺失的括号】一个完整的括号字符串定义规则如下:
1、空字符串是完整的。
2、如果s是完整的字符串，那么(s)也是完整的。
、如果s和t是完整的字符串，将它们连接起来形成的st也是完整的。
例如，(()()), 和(())()是完整的括号字符串，())(, ()( 和 )是不完整的括号字符串。
牛牛有一个括号字符串s,现在需要在其中任意位置尽量少地添加括号,将其转化为一个完整的括号字符串。请问牛牛至少需要添加多少个括号。

思路：

一个左括号需要对应一个右括号，需要注意的点是，字符串最开始如果有右括号的话，需要单独计数。

解答：

public static void main(String args[]){Scanner in = new Scanner(System.in);String str = ();//count计数多出来的(，n计数字符串最前面的)int count = 0, n=0;for(int i = 0; i < str.length(); i){if((i) == 	(	){count;}if((i) == 	)	) {if(count == 0){n;}else{count--;}}}println(countn);}
}

---

6.【vivo】小v所在的公司即将举行年会，年会方案设计过程中必不可少的一项就是抽奖活动。小v在本次活动中被委以重任，负责抽奖活动的策划；为了让中奖的礼物更加精美且富有神秘感，打算采用礼品盒来包装奖品，此时小v发挥了自己的创意想捉弄一下获奖的同事，便采取了多重包装来包装奖品。

现给出一个字符串，并假定用一对圆括号( )表示一个礼品盒，0表示奖品，你能据此帮获奖者算出最少要拆多少个礼品盒才能拿到奖品吗？

输入：(()(()((()(0))))) 输出：5

输入：(((0))) 输出：

实现思路：一对圆括号（）代表一个礼品盒，若左括号和右括号之间没有0则代表该礼品盒为空则不需要拆开

实现算法：

import java.io.*;public class Main {public static void main(String[] args) throws Exception {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String inputStr = br.readLine();int output = solution(inputStr );println(output);}private static int solution(String str) {// TODO Write your code herechar[] arr = ();int count = 0;for(int i = 0; i < arr.length; i){if(arr[i] == 	(	){count;}else if(arr[i] == 	)	){count--;}else if(arr[i] == 	0	){return count;}}return 0;}
}

---

7.【vivo】

小v在vivo手机的应用商店中下载了一款名为“一维消消乐”的游戏，介绍如下：

1、给出一些不同颜的豆子，豆子的颜用数字（0-9）表示，即不同的数字表示不同的颜；

2、通过不断地按行消除相同颜且连续的豆子来积分，直到所有的豆子都消掉为止；

、假如每一轮可以消除相同颜的连续 k 个豆子（k >= 1），这样一轮之后小v将得到 k*k 个积分；

4、由于仅可按行消除，不可跨行或按列消除，因此谓之“一维消消乐”。

请你帮助小v计算出最终能获得的最大积分。

示例： 输入：1 4 2 2 2 4 1 输出：21

示例说明： 第一轮消除，获得4分，序列变成1 4 2 2 2 4 1

                   第二轮消除2，获得9分，序列变成1 4 4 1

                   第三轮消除4，获得4分，序列变成1 1

                  第四轮消除1，获得4分，序列为空

                  总共得分21分

import java.io.*;public class Main {public static void main(String[] args) throws Exception {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String inputStr = br.readLine();int input[] = parseInts(inputStr.split( ));int output = solution(input);println(output);}private static int[] parseInts(String[] strArr) {if (strArr == null || strArr.length == 0) {return new int[0];}int[] intArr = new int[strArr.length];for (int i = 0; i < intArr.length; i) {intArr[i] = Integer.parseInt(strArr[i]);}return intArr;}private static int solution(int[] input) {// TODO Write your code hereif(input == null || input.length == 0){return 0;}int len = input.length;return DFS(input, len);}public static int DFS(int[] arr, int len){if(len == 1){return 1;}if(len == 2){if(arr[0] == arr[1]){return 4;}else{return 2;}}int max = 0;int L = 0;for(int i = 1; i < len; i){if(arr[i] != arr[L]){int[] copy = new int[len - (i - L)];int j = 0;for(; j < L; j){copy[j] = arr[j];}for(int r = i; r < len; r){copy[j] = arr[r];}max = (max, DFS(copy, copy.length)  (i - L)*(i - L));L = i;}}if(L == 0){return len * len;}int[] copy = new int[L];for(int j = 0; j < L; j){copy[j] = arr[j];}max = (max, DFS(copy, copy.length)  (len - L) * (len - L));return max;}
}

---

8.【vivo】小v是公司的运维工程师，现有一个有关应用程序部署的任务如下：

1、一台服务器的磁盘空间、内存是固定的，现在有个应用程序要部署；

2、每个应用程序所需要的磁盘、内存不同，每个应用程序允许访问的用户数也不同，且同一个应用程序不能在一台服务器上部署多个。

对于一台服务器而言，如何组合部署应用程序能够使得单台服务器允许访问的用户数最多？

输入描述:

输入包括三个参数，空格分隔，分别表示服务器的磁盘大小、内存大小，以及应用程序列表；
其中第三个参数即应用程序列表，表述方式为：多个应用程序信息之间用 	#	 分隔，每个应用程序的信息包括 	,	 分隔的部署所需磁盘空间、内存、允许访问的用户量三个数字；比如 50,20,2000 表示部署该应用程序需要50G磁盘空间，20G内存，允许访问的用户数是2000

输出描述:

单台服务器能承载的最大用户数

输入例子1:

15 10 5,1,1000#2,,000#5,2,15000#10,4,16000 =>磁盘大小15G,内存大小10G，应用程序列表(5,1,1000)、(2,,000)、(5,2,15000)、(10,4,16000)

输出例子1:

1000

例子说明1:

组合部署服务5,2,15000、10,4,16000  ，可以让单台服务器承载最大用户数1000

解题思路：该问题为背包问题

import java.io.*;
import java.util.*;public class Main {public static void main(String[] args) throws Exception {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String inputStr = br.readLine();String[] input = inputStr.split( );int totalDisk = Integer.parseInt(input[0]);int totalMemory = Integer.parseInt(input[1]);List<Service> services = parseServices(input[2].split(#));int output = solution(totalDisk, totalMemory, services);println(output);}private static int solution(int totalDisk, int totalMemory, List<Service> services) {// TODO Write your code hereint len = services.size();int[][][] dp = new int[len  1][totalDisk  1][totalMemory  1];for(int i = 1; i <= len; i)for(int j = totalDisk; j > 0; j--)for(int k = totalMemory; k > 0; k--){if(j >= services.get(i - 1).getDisk() && k >= services.get(i - 1).getMemory()){dp[i][j][k] = (dp[i - 1][j][k],dp[i - 1][j - services.get(i - 1).getDisk()][k - services.get(i - 1).getMemory()] services.get(i - 1).getusers());}else{dp[i][j][k] = dp[i - 1][j][k];}}return dp[len][totalDisk][totalMemory];}private static List<Service> parseServices(String[] strArr) {if (strArr == null || strArr.length == 0) {return new ArrayList<Service>(0);}List<Service> services = new ArrayList<>(strArr.length);for (int i = 0; i < strArr.length; i) {String[] serviceArr = strArr[i].split(,);int disk = Integer.parseInt(serviceArr[0]);int memory = Integer.parseInt(serviceArr[1]);int users = Integer.parseInt(serviceArr[2]);services.add(new Service(disk, memory, users));}return services;}static class Service {private int disk;private int memory;private int users;public Service(int disk, int memory, int users) {this.disk = disk; = memory;this.users = users;}public int getDisk() {return disk;}public void setDisk(int disk) {this.disk = disk;}public int getMemory() {return memory;}public void setMemory(int memory) { = memory;}public int getusers() {return users;}public void setusers(int users) {this.users = users;}}
}

---

9.【字节跳动】万万没想到之聪明的编辑

我叫王大锤，是一家出版社的编辑。我负责校对投稿来的英文稿件，这份工作非常烦人，因为每天都要去修正无数的拼写错误。但是，优秀的人总能在平凡的工作中发现真理。我发现一个发现拼写错误的捷径：

  1>三个同样的字母连在一起，一定是拼写错误，去掉一个的就好啦：比如 helllo -> hello

  2>两对一样的字母（AABB型）连在一起，一定是拼写错误，去掉第二对的一个字母就好啦：比如 helloo -> hello

  >上面的规则优先“从左到右”匹配，即如果是AABBCC，虽然AABB和BBCC都是错误拼写，应该优先考虑修复AABB，结果为AABCC

我特喵是个天才！我在蓝翔学过挖掘机和程序设计，按照这个原理写了一个自动校对器，工作效率从此起飞。用不了多久，我就会出任CEO，当上董事长，迎娶白富美，走上人生巅峰，想想都有点小激动呢！

……

万万没想到，我被开除了，临走时老板对我说： “做人做事要兢兢业业、勤勤恳恳、本本分分，人要是行，干一行行一行。一行行行行行；要是不行，干一行不行一行，一行不行行行不行。” 我现在整个人红红火火恍恍惚惚的……

请听题：请实现大锤的自动校对程序

输入描述:

第一行包括一个数字，表示本次用例包括多少个待校验的字符串。后面跟随行，每行为一个待校验的字符串。

输出描述:

行，每行包括一个被修复后的字符串。

输入例子1:

2
helloo
wooooooow

输出例子1:

hello
woow

解题思路：

利用正则表达式进行匹配

(.)\\1   =>  (.)代表任意字符 、\1代表匹配第一个括号、代表与第一个括号匹配的字符可以有多个，例如AAAA，没有的话只能匹配AA

(.)\\1(.)\\2  => (.)代表任意字符 、\1代表匹配第一个括号、\2代表匹配第二个括号

注意：类似于\d是数字，但是字符串中\是转义字符，所以表达\1或者\2要写作\\1和\\2,数字表示匹配第几个括号

//叠词 快快乐乐,高高兴兴
String regex = (.)\\1(.)\\2;                                                        
println(快快乐乐.matches(regex));//true
println(快乐乐乐.matches(regex));//false
println(高高兴兴.matches(regex));//true
println(死啦死啦.matches(regex));//false//叠词 死啦死啦,高兴高兴
String regex2 = (..)\\1;
println(死啦死啦.matches(regex2));//true
println(高兴高兴.matches(regex2));//true
println(快快乐乐.matches(regex2));//falseString regex = (.)(.)\\2\\1; 
println(死啦啦死.matches(regex));//true

Java源码实现：

public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int line = ();();for (int i = 0; i < line; i) {println(().replaceAll((.)\\1,$1$1).replaceAll((.)\\1(.)\\2,$1$1$2));}}
}

---

10.【字节跳动】万万没想到之抓捕孔连顺

我叫王大锤，是一名特工。我刚刚接到任务：在字节跳动大街进行埋伏，抓捕孔连顺。和我一起行动的还有另外两名特工，我提议

1>我们在字节跳动大街的个建筑中选定个埋伏地点。

2>为了相互照应，我们决定相距最远的两名特工间的距离不超过D。

我特喵是个天才! 经过精密的计算，我们从X种可行的埋伏方案中选择了一种。这个方案万无一失，颤抖吧，孔连顺！

……

万万没想到，计划还是失败了，孔连顺化妆成小龙女，混在cosplay的队伍中逃出了字节跳动大街。只怪他的伪装太成功了，就是杨过本人来了也发现不了的！

请听题：给定（可选作为埋伏点的建筑物数）、D（相距最远的两名特工间的距离的最大值）以及可选建筑的坐标，计算在这次行动中，大锤的小队有多少种埋伏选择。

注意：

1>两个特工不能埋伏在同一地点

2.>三个特工是等价的：即同样的位置组合(A, B, C) 只算一种埋伏方法，不能因“特工之间互换位置”而重复使用

输入描述:

第一行包含空格分隔的两个数字 和D(1 ≤  ≤ 1000000; 1 ≤ D ≤ 1000000)第二行包含个建筑物的的位置，每个位置用一个整数（取值区间为[0, 1000000]）表示，从小到大排列（将字节跳动大街看做一条数轴）

输出描述:

一个数字，表示不同埋伏方案的数量。结果可能溢出，请对 99997867 取模

输入例子1:

4 
1 2  4

输出例子1:

4

例子说明1:

可选方案 (1, 2, ), (1, 2, 4), (1, , 4), (2, , 4)

解题思路：

从题目要求来看，其实就是从个节点中选取三个，两两之间的差值不大于D

Java源码实现：

public class Test {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int  = (); // 建筑物个数int D = (); // 两人间最大的距离int[] builds = new int[];for (int i = 0; i < ; i) {builds[i] = ();}getAllWay(builds,D);}private static void getAllWay (int[] builds,int D) {int mod = 99997867;int count = 0;for (int i = 0; i < builds.length - 2; i) {for (int j = i  1; j < builds.length - 1;j) {if (builds[j] - builds[i] > D) {break;}for (int k = j  1; k < builds.length;k) {if (builds[k] - builds[j] > D) {break;}count;println(当前方案  builds[i]  ,  builds[j]  ,  builds[k]);}}}println(共有  (int) (count % mod)  种方案);}}

 

---

11.【字节跳动】雀魂启动

小包最近迷上了一款叫做雀魂的麻将游戏，但是这个游戏规则太复杂，小包玩了几个月了还是输多赢少。

于是生气的小包根据游戏简化了一下规则发明了一种新的麻将，只留下一种花，并且去除了一些特殊和牌方式（例如七对子等），具体的规则如下：

1. 总共有6张牌，每张牌是1~9。每个数字4张牌。
2. 你手里有其中的14张牌，如果这14张牌满足如下条件，即算作和牌

• 14张牌中有2张相同数字的牌，称为雀头。
• 除去上述2张牌，剩下12张牌可以组成4个顺子或刻子。顺子的意思是递增的连续个数字牌（例如24,567等），刻子的意思是相同数字的个数字牌（例如111,777）

例如：

1 1 1 2 2 2 6 6 6 7 7 7 9 9 可以组成1,2,6,7的4个刻子和9的雀头，可以和牌

1 1 1 1 2 2 5 6 7 7 8 9 用1做雀头，组12,12,567,789的四个顺子，可以和牌

1 1 1 2 2 2 5 6 7 7 9 无论用1 2 7哪个做雀头，都无法组成和牌的条件。

现在，小包从6张牌中抽取了1张牌，他想知道在剩下的2张牌中，再取一张牌，取到哪几种数字牌可以和牌。

输入描述:

输入只有一行，包含1个数字，用空格分隔，每个数字在1~9之间，数据保证同种数字最多出现4次。

输出描述:

输出同样是一行，包含1个或以上的数字。代表他再取到哪些牌可以和牌。若满足条件的有多种牌，请按从小到大的顺序输出。若没有满足条件的牌，请输出一个数字0

输入例子1:

1 1 1 2 2 2 5 5 5 6 6 6 9

输出例子1:

9

例子说明1:

可以组成1,2,6,7的4个刻子和9的雀头

Java源码实现（转载）：

public class Test {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int[] cards = new int[1];int[] state = new int[9]; // 牌的大小1-9，用于存储1-9的牌的个数int[] stateArr = new int[9];ArrayList<Integer> res = new ArrayList<>();for (int i = 0; i < 1; i) {int num = ();cards[i] = num;state[num - 1];}for (int i = 0; i < 9; i) { // 判断再加入哪张牌就可以和牌了if (state[i] < 4) {System.arraycopy(state,0,stateArr,0,9);stateArr[i];if(checkCanHu(stateArr,14,false)) res.add(i1);}}if (res.isEmpty()) println(0);else {StringBuffer sbf = new StringBuffer();sbf.append(res.get(0));for (int i = 1; i < res.size(); i) {sbf.append( );sbf.append(res.get(i));}println(());}}private static boolean checkCanHu(int[] arr,int total,boolean hasHead){if (total == 0) return true;if (!hasHead) {for (int i = 0; i < 9; i) {if (arr[i] >= 2) {arr[i] -= 2;if (checkCanHu(arr, total - 2, true)) return true;arr[i] = 2;}}return false;} else {for (int i = 0; i < 9; i) {if (arr[i] > 0) {if (arr[i] >= ) {arr[i] -= ;if (checkCanHu(arr, total - , true)) return true;arr[i] = ;}if (i  2 < 9 && arr[i  1] > 0 && arr[i  2] > 0) {arr[i]--;arr[i  1]--;arr[i  2]--;if (checkCanHu(arr, total - , true)) return true;arr[i];arr[i  1];arr[i  2];}}}}return false;}
}

---

12.【美团】给出两个字符串，分别是模式串P和目标串T，判断模式串和目标串是否匹配，匹配输出 1，不匹配输出 0。模式串中‘？’可以匹配目标串中的任何字符，模式串中的 ’*’可以匹配目标串中的任何长度的串，模式串的其它字符必须和目标串的字符匹配。例如P=a?b，T=acb，则P 和 T 匹配。

输入描述: 输入第一行包含一个字符串p， (1 ≤ |p| ≤ 20).

                输入第二行包含一个字符串t， (1 ≤ |t| ≤ 20).

输出描述: 输出仅包含0和1的整数，0表示p和t不匹配，1表示p和t匹配。

输入例子1:

a?b
ab

输出例子1:

0

输入例子2:

a*b
ab

输出例子2:

1

输入例子:

a*b
a(cb

输出例子:

1

解题思路：

模板字符串与目标字符串中的字符一一进行对比，

1>sourceChars[sourceStart] == targetChars[targetStart]，下标索引后移

   sourceChars[sourceStart] ！= targetChars[targetStart]，跳出循环，模板串与目标串不匹配

2>sourceChars[sourceStart] == ? ，下标索引后移

>sourceChars[sourceStart] == * ，

   若sourceChars.length - 1 == sourceStart，跳出循环，模板串与目标串匹配

   若sourceChars.length - 1 ！= sourceStart，则判断模板字符串后面一位是否仍然为 * ,如果仍为‘*’则模板字符串继续后移，直到第一个非 * 的字符，然后去目标字符串中查是否存在该字符，若存在则更新目标字符串当前指向的下标位置。

Java源码实现：

import java.util.Scanner;
public class Main{public static void main(String[] args) {Scanner scanner = new Scanner(System.in);String source = ();String target = ();if (source == null && target == null) {println(1);return;} else if ((source != null && target == null) || (source == null && target != null)) {println(0);return;} else {int sourceStart = 0;int targetStart = 0;char[] sourceChars = ();char[] targetChars = (); boolean flag = false;while(sourceStart < sourceChars.length && targetStart < targetChars.length) {if (sourceChars[sourceStart] == targetChars[targetStart]) {sourceStart;targetStart;} else if (sourceChars[sourceStart] == 	?	) {sourceStart;targetStart;} else if (sourceChars[sourceStart] == 	*	) {if (sourceChars.length - 1 == sourceStart) {flag = true; break;} else {if (sourceChars[sourceStart  1] == 	*	) {sourceStart;} else {int index = target.substring(targetStart).indexOf(sourceChars[sourceStart  1]);if (index != -1) {sourceStart;targetStart = index;} else {break;}}}} else {break;}}println((flag || (sourceChars.length == sourceStart && targetChars.length == targetStart)) ? 1 : 0);}}
}

---

1.【美团】给出一个布尔表达式的字符串，比如：true or false and false，表达式只包含true，false，and和or，现在要对这个表达式进行布尔求值，计算结果为真时输出true、为假时输出false，不合法的表达时输出error（比如：true true）。表达式求值是注意and 的优先级比 or 要高，比如：true or false and false，等价于 true or (false and false)，计算结果是 true。

输入描述:

输入第一行包含布尔表达式字符串s，s只包含true、false、and、or几个单词（不会出现其它的任何单词），且单词之间用空格分隔。 (1 ≤ |s| ≤ 10).

输出描述:

输出true、false或error，true表示布尔表达式计算为真，false表示布尔表达式计算为假，error表示一个不合法的表达式。

输入例子1:

and

输出例子1:

error

输入例子2:

true and false

输出例子2:

false

输入例子:

true or false and false

输出例子:

true

解题思路：

判断当前输入字符串是否符合要求，不符合要求则返回error；符合要求的情况下，首先进行and运算，将所有的and运算完成后再执行or操作

Java源码实现：

import java.util.Scanner;
import java.lang.*;
public class Main{public static void main(String[] args) {Scanner scanner = new Scanner(System.in);String str = ();if (str == null) return;else {String[] strs = str.split( );if ((strs.length == 1 && (strs[0].equals(and) || strs[0].equals(or))) || strs.length == 2) {println(error);return;} else if (strs.length == 1 && (strs[0].equals(true) || strs[0].equals(false))) {println(strs[0]);return;} else if (strs.length == ) {if (strs[1].equals(and)) {if (strs[0].equals(false) || strs[2].equals(false)) {println(false);} else {println(true);}return;} else {if (strs[0].equals(true) || strs[2].equals(true)) {println(true);return;}}} else {int num1 = 0;int num2 = 0;for (int i = 0; i < strs.length; i) {if (strs[i].equals(and) || strs[i].equals(or)) {num1;} else {num2;}}if (num1  1 != num2) {println(error);return;} else {int deleteum = 0;for (int i = 1; i < strs.length - 1; i) {if (strs[i].equals(and)) {String flagStr = false;if (strs[i - 1].equals(true) && strs[i  1].equals(true)) {flagStr = true;}strs[i - 1] = flagStr;for (int j = i  2; j < strs.length; j) {strs[j - 2] = strs[j];}deleteum = 2;}}boolean flag = false;for (int i = 0; i < strs.length - deleteum; i) {if (strs[i].equals(true)) {flag = true;break;}}println(flag ? true : false);}}}}
}

---

14.【美团】打车派单场景, 假定有个订单， 待分配给个司机。每个订单在匹配司机前，会对候选司机进行打分，打分的结果保存在*的矩阵A， 其中Aij 代表订单i司机j匹配的分值。

假定每个订单只能派给一位司机，司机只能分配到一个订单。求最终的派单结果，使得匹配的订单和司机的分值累加起来最大，并且所有订单得到分配。

输入描述:

第一行包含一个整数，2≤≤10。

第二行至第1行包含*的矩阵。

输出描述:

输出分值累加结果和匹配列表，结果四舍五入保留小数点后两位

（注意如果有多组派单方式得到的结果相同，则有限为编号小的司机分配编号小的订单，比如：司机1得到1号单，司机2得到2号单，就比司机1得到2号单，司机2得到1号单要好）

输入例子1:

1.08 1.25 1.5
1.5 1.5  1.75
1.22 1.48 2.5

输出例子1:

5.25
1 2
2 1
 

例子说明1:

第一行代表得到的最大分值累加结果5.25，四舍五入保留两位小数；

第二行至第四行代表匹配的结果[i j],其中i按行递增：

订单1被派给司机2，订单2被派给司机1，订单被派给司机。使得A12 A21 A= 1.25  1.5  2.5 = 5.25在所有的组合中最大。

Java源码实现（转载）：

import java.util.Scanner;public class Main {static double max = -Double.MAX_VALUE;static double[][] scores;static boolean[] isAssigned;static int[] res;public static void helper(int now, int[] cur, double sc) {if (now < cur.length) {for (int i = 0; i < cur.length; i = 1) {if (!isAssigned[i]) {cur[now] = i  1;isAssigned[i] = true;helper(now1, cur, sc  scores[now][i]);isAssigned[i] = false;}}} else {if (sc > max) {System.arraycopy(cur, 0, res, 0, res.length);max = sc;}}}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int size = ();double[][] score = new double[size][size];for (int i = 0; i < size; i = 1) {for (int j = 0; j < size; j = 1) {score[i][j] = ();}}res = new int[size];isAssigned = new boolean[size];scores = score;int[] cur = new int[score.length];helper(0, cur, 0);println(String.format(%.2f, max));for (int i = 0; i < size; i = 1) {println(String.format(%d %d, i1, res[i]));}}}

---

15.【美团】美团骑手包裹区间分组

2110年美团外卖火星第000号配送站点有26名骑手，分别以大写字母A-Z命名，因此可以称呼这些骑手为黄家骑士特工A，黄家骑士特工B…黄家骑士特工Z，某美团黑珍珠餐厅的外卖流水线上会顺序产出一组包裹，美团配送调度引擎已经将包裹分配到骑手，并在包裹上粘贴好骑手名称，如RETTEBTAE代表一组流水线包裹共9个，同时分配给了名字为A B E R T的5名骑手。请在不打乱流水线产出顺序的情况下，把这组包裹划分为尽可能多的片段，同一个骑手只会出现在其中的一个片段，返回一个表示每个包裹片段的长度的列表。

输入描述:

输入数据只有一行，为一个字符串(不包含引号)，长度不超过1000，只包含大写字母	A	到	Z	，字符之间无空格。

输出描述:

输出每个分割成片段的包裹组的长度，每个长度之间通过空格隔开

输入例子1:

MPMPCPMCMDEFEGDEHIHKLI

输出例子1:

9 7 8

解题思路：

美团配送调度引擎已经将包裹分配到骑手，并在包裹上粘贴好骑手名称，如RETTEBTAE代表一组流水线包裹共9个，同时分配给了名字为A B E R T的5名骑手。（所有的包裹中只包含了A B E R T五个骑手的包裹，那就可以理解为一个字母就代表一个骑手。）

同一个骑手只会出现在其中的一个片段  =》那就说明在分区间的时候同样的字母必须在一个区间内，我们在分区间的时候要得到每个字母第一次出现的位置和最后一次出现的位置，每个字母的区间间有交集的要进行合并成为一个区间。

1>判断所输入的字符串中有多少个不同的字母

2>得到每个字母在所输入字符串中第一次出现的位置和最后一次出现的位置

>每个字母的区间间的交集进行合并

Java源码实现：

import java.util.*;
import java.lang.*;
public class Main{public static void main(String[] args) {Scanner scanner = new Scanner(System.in);String str = ();if (str == null) return;List<String> list = new ArrayList<>();String temp = null;for(int i = 0; i < str.length(); i) {temp = str.substring(i,i  1);if(!(temp)) {list.add(temp);}}//创建一个二维数组int arra[n][2]，arra[i][0]表示第i1个字符第一次出现的位置，arra[i][1]表示最后一次出现的位置int n = list.size();int[][] arr = new int[n][2];for(int i = 0; i < n; i) {arr[i][0] = str.indexOf(list.get(i));arr[i][1] = str.lastIndexOf(list.get(i));}	//遍历二维数组，有相同区间就合并int last = -1;//上一个输出的数int big = arr[0][1];//当前循环区间的最大值for(int i = 1; i < n; i) {if (big < arr[i][0]) {print((big - last)  );last = big;big = arr[i][1];} else if (big < arr[i][1]) {big = arr[i][1]; }}println(big - last);}
}

---

16.【美团】火星文字典

已知一种新的火星文的单词由英文字母（仅小写字母）组成，但是此火星文中的字母先后顺序未知。给出一组非空的火星文单词，且此组单词已经按火星文字典序进行好了排序（从小到大），请推断出此火星文中的字母先后顺序。

输入描述:

一行文本，为一组按火星文字典序排序好的单词(单词两端无引号)，单词之间通过空格隔开

输出描述:

按火星文字母顺序输出出现过的字母，字母之间无其他字符，如果无法确定顺序或者无合理的字母排序可能，请输出invalid(无需引号)

输入例子1:

z x

输出例子1:

zx

输入例子2:

wrt wrf er ett rftt

输出例子2:

wertf

输入例子:

z x z

输出例子:

invalid

解题思路：

拓扑排序

Java源码实现（有问题，需调试，AC:10%）：

import java.util.*;
import java.lang.*;
public class Main {private static ArrayList<String> list;private static int[][] edges;private static int size;private static boolean[] vertexStatus;public static void main(String[] args) {Scanner scanner = new Scanner(System.in);String str = ();if (str == null) return;String[] strs = str.split( );list = new ArrayList<>();for (int i = 0; i < strs.length; i) {char[] chars = strs[i].toCharArray();for (int j = 0; j < chars.length; j) {if (!(String.valueOf(chars[j]))) {list.add(String.valueOf(chars[j]));}}}size = list.size();edges = new int[size][size];vertexStatus = new boolean[size];for (int i = 0; i < strs.length; i) {char[] chars = strs[i].toCharArray();for (int j = 0; j < chars.length - 1; j) {int row = list.indexOf(String.valueOf(chars[j]));int col = list.indexOf(String.valueOf(chars[j1]));if (row != col) {edges[row][col] = 1;}}}sort();}/** 拓扑排序 */private static void sort() {int index = getInDegreeIndex();if (index != -1) {Stack stack = new Stack();stack.push(index);while(!stack.isEmpty()) {int stackIndex = Integer.parseInt(String.valueOf(stack.peek()));updateInDegree(stackIndex);vertexStatus[stackIndex] = true;print(list.get(stackIndex));stack.pop();index = getInDegreeIndex();if (index != -1) {stack.push(index);}}} else {println(该图存在环，不能进行拓扑排序！);}}/** 入度减1操作*/private static void updateInDegree (int index) {int col = edges.length;for (int i = 0; i < col;i) {if (edges[index][i] != 0) {edges[index][i]--;}}}/** 获取入度为0的结点下标索引*/private static int getInDegreeIndex () {int index = -1;int row = edges.length;int col = edges[0].length;for (int i = 0; i < col;i) {if (!vertexStatus[i]) {for (int j = 0; j < row; j) {index = i;if (edges[j][i] != 0) {index = -1;break;}}if (index != -1) {return index;}}}return index;}
}

---

17.【美团】统计输入字符串大小写字母，数字，空格，其他字符的个数

package semantic.similarity;import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);String str = ();int letterum = 0; // 字母的数量int figureum = 0; // 数字的数量int blankSpaceum = 0;// 空格的数量int otherum = 0; // 其它字符的数量if (str != null) {char[] chars = ();for (int i = 0; i < chars.length;i) {if ((chars[i] >= 	a	 && chars[i] <= 	z	) || chars[i] >= 	A	 && chars[i] <= 	Z	) {letterum;} else if (chars[i] >= 	0	 && chars[i] <= 	9	) {figureum;} else if (chars[i] == 	 	) {blankSpaceum;} else {otherum;}}}println(字母的数量:  letterum);println(数字的数量:  figureum);println(空格的数量:  blankSpaceum);println(其它字符的数量:  otherum);}
}

---

18.【美团】一个数组先降序后升序，出给定值在数组中的索引

package semantic.similarity;import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int size = ();int[] nums = new int[size];for (int i = 0; i < nums.length;i) {nums[i] = ();}int num = ();int midIndex = -1;int midValue = -1;for (int i = 0; i < nums.length - 1;i) {if (nums[i] > nums[i1]) {midValue = nums[i];midIndex = i;break;}}if (midValue == -1) {println(search(nums,0,nums.length - 1,num));} else {if (num != midValue) {int index = search(nums,0,midIndex  1,num);if (index == -1) {index = searchReverse(nums,midIndex,nums.length - 1,num);}println(index);} else {println(midIndex);}}}// 正向折半查（非递减排序）public static int search(int[] R,int low,int high,int k){int mid;while(low<=high){mid = (lowhigh)/2;if(R[mid]==k){return mid;}else if(R[mid]>k){high=mid-1;}else{low=mid1;}}return -1;}// 反向折半查（非递增排序）public static int searchReverse(int[] R,int low,int high,int k){int mid;while(low<=high){mid = (lowhigh)/2;if(R[mid]==k){return mid;}else if(R[mid]>k){low=mid1;}else{high=mid-1;}}return -1;}}

---

19.【】方块消除游戏

题目描述：如下图，有10*10个不同颜的方块，每个方块可能是红、绿、蓝、黄、紫5种颜之一。当点击其中某一个方块时，如果它有相邻的同颜方块，则将所有与此方块连续同颜相邻的方块消除；剩下的方块中，如果下方有空位则向下移动，如果左侧整列都为空位则向左移动。

输入：

输入数据有多组，每组占一行，包括一个或多个正整数，取值范围为1~100。每个数代表一次点击，数值为点击的方块编号。

上图中的方块初始值定义已为你写好，可以直接粘贴使用：

ct int RED = 0, GREE = 1, BLUE = 2, YELLOW = , PURPLE = 4;

int p[10][10] = {

{RED,RED,BLUE,BLUE,GREE,YELLOW,BLUE,YELLOW,RED,PURPLE},

{GREE,GREE,GREE,BLUE,RED,PURPLE,RED,YELLOW,YELLOW,BLUE},

{BLUE,RED,RED,YELLOW,YELLOW,PURPLE,BLUE,GREE,GREE,BLUE},

{YELLOW,RED,BLUE,YELLOW,BLUE,RED,PURPLE,GREE,GREE,RED},

{YELLOW,RED,BLUE,BLUE,PURPLE,GREE,PURPLE,RED,YELLOW,BLUE},

{PURPLE,YELLOW,RED,RED,YELLOW,RED,PURPLE,YELLOW,RED,RED},

{YELLOW,YELLOW,GREE,PURPLE,GREE,RED,BLUE,YELLOW,BLUE,GREE},

{RED,YELLOW,BLUE,BLUE,YELLOW,GREE,PURPLE,RED,BLUE,GREE},

{GREE,GREE,YELLOW,YELLOW,RED,RED,PURPLE,BLUE,BLUE,GREE},

{PURPLE,BLUE,RED,RED,PURPLE,YELLOW,BLUE,RED,RED,GREE}};

输出：

对于每个测试实例，要求输出连续各次点击全部完成之后，红、绿、蓝、黄、紫方块的数量;每个测试实例的输出占一行。

样例输入：

6

6 1

样例输出：

26 18 22 21 1

24 18 22 21 1

解题思路：

1>统计当前二维数组中红、绿、蓝、黄、紫方块的数量；

2>根据所输入的方块序号，得到其在二维数组中的位置；

>根据得到的位置信息，判断其上下左右方块的颜是否与该方块的颜一致，统计颜一致的方块数量；

4>根据第一步得到的各颜方块数量，减去第三步得到的方块数量，更新各方块的数量。

Java源码实现：

public static void main(String[] args) {int RED = 0, GREE = 1, BLUE = 2, YELLOW = , PURPLE = 4;int[][] p = new int[][]{{RED,RED,BLUE,BLUE,GREE,YELLOW,BLUE,YELLOW,RED,PURPLE},{GREE,GREE,GREE,BLUE,RED,PURPLE,RED,YELLOW,YELLOW,BLUE},{BLUE,RED,RED,YELLOW,YELLOW,PURPLE,BLUE,GREE,GREE,BLUE},{YELLOW,RED,BLUE,YELLOW,BLUE,RED,PURPLE,GREE,GREE,RED},{YELLOW,RED,BLUE,BLUE,PURPLE,GREE,PURPLE,RED,YELLOW,BLUE},{PURPLE,YELLOW,RED,RED,YELLOW,RED,PURPLE,YELLOW,RED,RED},{YELLOW,YELLOW,GREE,PURPLE,GREE,RED,BLUE,YELLOW,BLUE,GREE},{RED,YELLOW,BLUE,BLUE,YELLOW,GREE,PURPLE,RED,BLUE,GREE},{GREE,GREE,YELLOW,YELLOW,RED,RED,PURPLE,BLUE,BLUE,GREE},{PURPLE,BLUE,RED,RED,PURPLE,YELLOW,BLUE,RED,RED,GREE}};operate(p, 6);operate(p, 1);}public static void operate(int p[][], int position) {int[] count = new int[5]; //count[0]代表红方块的数量.....count[4]代表紫方块的数量for(int i=0; i<p.length; i) {for(int j=0;j<p[i].length;j) {if(p[i][j] == 0) { // 红方块count[0];}else if (p[i][j] == 1) { // 绿方块count[1];}else if (p[i][j] == 2) { // 蓝方块count[2];}else if (p[i][j] == ) { // 黄方块count[];}else if (p[i][j] == 4) { // 紫方块count[4];}}}//本次点击的方块在二维数组中的位置(i,j)int i = (position-1)/10;int j = (position-1)%10;// 比较(i,j)位置的上下左右方块的颜是否与点击的方块颜一致int count_de_num = 1; // 默认为1，指的是本次点击的方块if(i!= 0) { // 第一行没有上方的方块if(p[i-1][j] == p[i][j]) { // 颜一致count_de_num;}}if(i!= 9) { // 最后一行没有下方的方块if(p[i1][j] == p[i][j]) {count_de_num;}}if(j!= 0) { // 第一列没有左侧的方块if(p[i][j-1] == p[i][j]) {count_de_num;}}if(j!= 9) {// 最后一列没有右侧的方块if(p[i][j1] == p[i][j]) {count_de_num;}}if(count_de_num != 1) { // 说明存在与当前方块颜一致的其它方块if(p[i][j] == 0) {count[0] = count[0] - count_de_num; // count[0]红方块的总数量 - 当前方块以及周边同方块的数量}else if (p[i][j] == 1) {count[1] = count[1] - count_de_num;}else if (p[i][j] == 2) {count[2] = count[2] - count_de_num;}else if (p[i][j] == ) {count[] = count[] - count_de_num;}else if (p[i][j] == 4) {count[4] = count[4] - count_de_num;}}println((count));}

 

---

20.