首页 > 社招, 之江实验室笔试
头像
星星上的louie
编辑于 2021-07-19 10:45
+ 关注

社招, 之江实验室笔试

新鲜的之江实验室社招笔试题目
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) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐