10月8号 虾皮、喜马拉雅秋招笔试记录
虾皮
有单选,多选,3道编程。只有最后一题编程偏难
相关知识点记录:
- cat grep chmod的区别
- 下列哪个属于对称加密:AES,DES,RSA,MD5
- 选择排序和堆排序是否是稳定的
- 分布式系统的CAP理论
第三题的编程题目:
给你一个整数数组nums,找出并返回所有该数组中不同的递增子序列个数,递增子序列中至少有两个元素
数组中可能含有重复元素,如出现两个整数相等,也可以视作递增序列的一种特殊情况。
例如,若数组为{4,6,7,7},则答案应为8
喜马拉雅
有单选,多选,2道编程。共一小时。
相关知识点记录:
- 广度优先除了队列还可以用什么数据结构
- 归并排序是否会退化,最坏情况是什么
- 迪杰斯特拉是深度优先吗
- 什么情况会发生page fault
- nginx支持反向代理 负载均衡 虚拟主机吗
- SSL协议握手的时候要交换哪些信息
编程
第一题90%通过 字符串s里面,找最多出现k种字母的子串,满足条件的最长子串有多长
public static int longestSubstring (String s, int k) { //贪心算法,随时记录start和end,用哈希表存每个字母上次出现的位置 if(k==0) return 0; Map<Character,Integer> map=new HashMap(); int ans=0; int len=s.length(); int start=0,count=0; int i=0; while(i<len){ char c=s.charAt(i); if(map.getOrDefault(c,-1)<start){ //说明前面没出现过 count++; if(count>k){ //说明这个地方不能留 ans=Math.max(ans,i-start); char first=s.charAt(start); start=map.get(first)+1;//找到这个字母最后出现的位置 if(start==len)break; count=1;i=start;c=s.charAt(i);map.clear(); } } map.put(c,i); i++; } //最后再判断一遍 if(count<=k&&count>0) ans=Math.max(ans,len-start); return ans; }
上述代码存在的问题:窗口每次收缩太多了
GPT提供的答案:
public static int longestSubstring2(String s, int k) { if (k == 0) return 0; Map<Character, Integer> map = new HashMap<>(); int ans = 0; int start = 0; for (int end = 0; end < s.length(); end++) { char endChar = s.charAt(end); map.put(endChar, map.getOrDefault(endChar, 0) + 1);//用map来计数 // 当窗口中的不同字符超过k时,通过while循环收缩窗口,步长为1 确保不会把start移到太后面 while (map.size() > k) { char startChar = s.charAt(start); map.put(startChar, map.get(startChar) - 1); if (map.get(startChar) == 0) { map.remove(startChar); } start++; } // 更新最大长度 ans = Math.max(ans, end - start + 1); } return ans; }
第二题AC 是找数组中单个出现的元素
public static int singleElement (ArrayList<Integer> v) { // write code here int ans=0; for(int i:v) ans=ans^i; return ans; }