Java工程师丨面试真题（五）
【摘要】 一、雀魂启动描述小包最近迷上了一款叫做雀魂的麻将游戏，但是这个游戏规则太复杂，小包玩了几个月了还是输多赢少。于是生气的小包根据游戏简化了一下规则发明了一种新的麻将，只留下一种花色，并且去除了一些特殊和牌方式（例如七对子等），具体的规则如下：总共有36张牌，每张牌是1~9。每个数字4张牌。你手里有其中的14张牌，如果这14张牌满足如下条件，即算作和牌14张牌中有2张相同数字的牌，称为雀头。除...
一、雀魂启动
描述
小包最近迷上了一款叫做雀魂的麻将游戏，但是这个游戏规则太复杂，小包玩了几个月了还是输多赢少。
于是生气的小包根据游戏简化了一下规则发明了一种新的麻将，只留下一种花色，并且去除了一些特殊和牌方式（例如七对子等），具体的规则如下：
- 总共有36张牌，每张牌是1~9。每个数字4张牌。
- 你手里有其中的14张牌，如果这14张牌满足如下条件，即算作和牌
- 14张牌中有2张相同数字的牌，称为雀头。
- 除去上述2张牌，剩下12张牌可以组成4个顺子或刻子。顺子的意思是递增的连续3个数字牌（例如234,567等），刻子的意思是相同数字的3个数字牌（例如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 3 3 5 6 7 7 8 9 用1做雀头，组123,123,567,789的四个顺子，可以和牌
1 1 1 2 2 2 3 3 3 5 6 7 7 9 无论用1 2 3 7哪个做雀头，都无法组成和牌的条件。
现在，小包从36张牌中抽取了13张牌，他想知道在剩下的23张牌中，再取一张牌，取到哪几种数字牌可以和牌。
输入描述：
输入只有一行，包含13个数字，用空格分隔，每个数字在1~9之间，数据保证同种数字最多出现4次。
输出描述：
输出同样是一行，包含1个或以上的数字。代表他再取到哪些牌可以和牌。若满足条件的有多种牌，请按从小到大的顺序输出。若没有满足条件的牌，请输出一个数字0
示例1
输入：
1 1 1 2 2 2 5 5 5 6 6 6 9输出：
9说明：
可以组成1,2,6,7的4个刻子和9的雀头示例2
输入：
1 1 1 1 2 2 3 3 5 6 7 8 9输出：
4 7说明：
用1做雀头，组123,123,567或456,789的四个顺子示例3
输入：
1 1 1 2 2 2 3 3 3 5 7 7 9输出：
0说明：
来任何牌都无法和牌
题解：
import java.util.*;
public class Main {
static boolean flag;
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int[] nums = new int[10];
for (int i = 0; i < 13; i++) {
nums[cin.nextInt()]++;
}
for (int i = 1; i <= 9; i++) {
if (nums[i] <= 3) {
int[] card = Arrays.copyOf(nums, nums.length);
card[i]++;
flag = false;
if (isHu(card, 1, 14)) {
System.out.print(i + " ");
}
}
}
}
public static boolean isHu(int[] card, int start, int total) {
if (total == 0) {
flag = true;
return flag;
}
// 把该牌当作雀头
if (card[start] >= 2 && total % 3 != 0) {
card[start] -= 2;
if (card[start] == 0 && start + 1 <= 9) {
flag = isHu(card, start + 1, total - 2);
} else {
flag = isHu(card, start, total - 2);
}
// 回溯，去判断下一种情况
card[start] += 2;
}
// 把该牌当作顺子
if (card[start] >= 3) {
card[start] -= 3;
if (card[start] == 0 && start + 1 <= 9) {
flag = isHu(card, start + 1, total - 3);
} else {
flag = isHu(card, start, total - 3);
}
// 回溯，去判断下一种情况
card[start] += 3;
}
// 把该牌当作刻子
if (start + 2 <= 9 && card[start] > 0 && card[start + 1] > 0 && card[start + 2] > 0) {
card[start]--;
card[start + 1]--;
card[start + 2]--;
if (card[start] == 0) {
flag = isHu(card, start + 1, total - 3);
} else {
flag = isHu(card, start, total - 3);
}
// 回溯，去判断下一种情况
card[start]++;
card[start + 1]++;
card[start + 2]++;
}
// 这种牌没了，去判断下一种牌
if (card[start] == 0) {
flag = isHu(card, start + 1, total);
}
return flag;
}
}
二、特征提取
描述
小明是一名算法工程师，同时也是一名铲屎官。某天，他突发奇想，想从猫咪的视频里挖掘一些猫咪的运动信息。为了提取运动信息，他需要从视频的每一帧提取“猫咪特征”。一个猫咪特征是一个两维的vector<x, y>。如果x_1=x_2 and y_1=y_2，那么这俩是同一个特征。
因此，如果喵咪特征连续一致，可以认为喵咪在运动。也就是说，如果特征<a, b>在持续帧里出现，那么它将构成特征运动。比如，特征<a, b>在第2/3/4/7/8帧出现，那么该特征将形成两个特征运动2-3-4 和7-8。
现在，给定每一帧的特征，特征的数量可能不一样。小明期望能找到最长的特征运动。
输入描述：
第一行包含一个正整数N，代表测试用例的个数。
每个测试用例的第一行包含一个正整数M，代表视频的帧数。
接下来的M行，每行代表一帧。其中，第一个数字是该帧的特征个数，接下来的数字是在特征的取值；比如样例输入第三行里，2代表该帧有两个猫咪特征，<1，1>和<2，2>
所有用例的输入特征总数和<100000
N满足1≤N≤100000，M满足1≤M≤10000，一帧的特征个数满足 ≤ 10000。
特征取值均为非负整数。
输出描述：
对每一个测试用例，输出特征运动的长度作为一行
示例1
输入：
1 8 2 1 1 2 2 2 1 1 1 4 2 1 1 2 2 2 2 2 1 4 0 0 1 1 1 1 1 1输出：
3说明：
特征<1,1>在连续的帧中连续出现3次，相比其他特征连续出现的次数大，所以输出3
备注：
如没有长度大于2的特征运动，返回1
题解：
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int times = scanner.nextInt();
for(int i=0;i<times;i++){
//特征的行数
/*
循环输入，按List<List<Integer>>保存数据
*/
int n = scanner.nextInt();
List<List<Integer>> list = new ArrayList<>(n);
for(int j=0;j<n;j++){
int size = scanner.nextInt();
List<Integer> sp = new ArrayList<>();
for(int m = 0;m <size*2;m++){
sp.add(scanner.nextInt());
}
list.add(sp);
}
//将封装好List<List<Integer>>的数据进行处理
/*
数据输入的格式
1
8
2 1 1 2 2
2 1 1 1 4
数据封装在List<List<Integer>>的格式
1 1 2 2
1 1 1 4
*/
display(list);
}
}
public static void display(List<List<Integer>> list){
Map<String,Integer> map = new HashMap<>();
map.put("max",0);
//put 一个最大值
for(int i=0;i<list.size();i++){
//每一次遍历数组的2个值
for(int j=0;j<list.get(i).size();j+=2){
// 将key 以字符串的格式拼接
String str = list.get(i).get(j)+"and"+list.get(i).get(j+1);
int num = 0;
/*
所有用例的输入特征总数和<100000
-->map value 的最大值不超过100000
所以以 最后出现的特征的行数 * 100000 + 已经连续的次数进行保存
*/
if(map.get(str)!=null && map.get(str)/100000==i-1){//表示这个特征是连续的
// map.get(str)/100000==i-1 如果最后出现特征的行数是上一行 表示连续
num = map.get(str)%100000 + 1;
map.put(str,100000*i+num);
//将连续的次数加一 并换上新的行数
}else{
//这个特征不是连续的，则默认初始化为一
map.put(str,100000*i+1);
num =1;//不管连续还是不连续都要与max 比较大小
}
if(map.get("max") < num){
map.put("max",num);
}
}
}
System.out.println(map.get("max"));
}
}
三、毕业旅行问题
描述
小明目前在做一份毕业旅行的规划。打算从北京出发，分别去若干个城市，然后再回到北京，每个城市之间均乘坐高铁，且每个城市只去一次。由于经费有限，希望能够通过合理的路线安排尽可能的省一些路上的花销。给定一组城市和每对城市之间的火车票的价钱，找到每个城市只访问一次并返回起点的最小车费花销。
输入描述：
城市个数n（1<n≤20，包括北京）
城市间的车票价钱 n行n列的矩阵 m[n][n]
输出描述：
最小车费花销 s
示例1
输入：
4 0 2 6 5 2 0 4 4 6 4 0 2 5 4 2 0输出：
13说明：
共 4 个城市，城市 1 和城市 1 的车费为0，城市 1 和城市 2 之间的车费为 2，城市 1 和城市 3 之间的车费为 6，城市 1 和城市 4 之间的车费为 5，依次类推。假设任意两个城市之间均有单程票可购买，且票价在1000元以内，无需考虑极端情况。
题解：
【声明】本内容来自华为云开发者社区博主，不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息，否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
作者其他文章
评论（0）