新鲜的之江实验室社招笔试题目
1年经验投的之江实验室, 题目不难，但是用的是赛码网的编译器, 很难用, 输入格式也不对, 也没给输出, 好多API啥的也忘了, 所以没有跑起来
中间还有点公司的事情去处理, 回来时候已经只剩30分钟了, 后面思考了一下给了个Java版本的解法, 让大家看看行不行的通.
1. 给定一个序列S, 需要找一个尽可能长的子串, 使得子串的最大最小值不超过m, 输出子串的长度
input: [10,1,3,5,9] m = 4
output: 3
思路是: 滑动窗口+ TreeMap, 给一个Java的解法,
public int findSubSequence(int m, int[] input){
if(input == null || input.length == 0 ) return 0;
int j = 0;
//右指针
int len = 1;
//最大长度值初始化
TreeMap<Integer, List<Integer>> maxMinMap = new TreeMap<>();
//记录最大最小值, <key = 值, val = index列表>
HashMap<Integer, Integer> indexMap = new HashMap<>();
//记录index, value 关系 <key = index, val = 值>
for(int i=0; i< input.length; i++){
while(j < input.length){
maxMinMap.putIfAbsent(input[j], new ArrayList<>());
maxMinMap.get(input[j]).add(j);
//index放入值对应的列表
indexMap.put(j, input[j]);
if(!maxMinMap.isEmpty() && maxMinMap.lastKey() - maxMinMap.firstKey() > m ) {
//最大最小值超过m, 移动左指针
break;
}
len = Math.max(len, j-i+1);
//计算最大值
j++;
}
if(!maxMinMap.isEmpty()){
//获得当前左指针index对应的值
int val = indexMap.get(i);
List<Integer> resultList = maxMinMap.getOrDefault(val, new ArrayList<>());
//拿到值对应的列表
if(!resultList.isEmpty()) {
resultList.remove(Integer.valueOf(i));
//去掉在列表中的当前值
if(resultList.isEmpty()) {
//如果空列表, 移除列表
maxMinMap.remove(val);
}
}
}
}
return len;
}
2. 一个游戏的副本, 有一排需要打败的怪物, 初始状态下, 每个怪物1点血, 希望从左到右击杀这些怪物, 怪物分为0型和1型, 0型怪物1血, 1型怪物击杀后会给后面的0型怪物+1血
你每次挥刀扣怪物1血, 问你打完这些怪物需要挥刀多少次
input = [0,1,0,1]
output = 5
思路: 一开始觉得是dp, 后面发现应该就计数几次就可以解决了
public int fightBoss(int[] input){
int sum = input.length;
//0, 1怪物血量基数=1
int[] sumArray = new int[input.length];
//建一个统计数组
int countOne = 0;
for(int i=0; i<input.length; i++){
if(input[i] == 1) {
countOne++;
}
}
//扫描1的个数
for(int i=input.length-1; i >=0 ; i--) {
//从右往左扫
if(input[i] == 0) {
sumArray[i] = countOne;
//遇到0加当前的1个数
}
if(input[i] == 1) {
countOne--;
//遇到1当前1个数-1
}
}
for(int i=0; i<input.length; i++) {
sum+=sumArray[i];
}
//累加结果
return sum;
}
全部评论
(7) 回帖