虾皮

有单选，多选，3道编程。只有最后一题编程偏难

相关知识点记录：

1. cat grep chmod的区别
2. 下列哪个属于对称加密：AES,DES,RSA,MD5
3. 选择排序和堆排序是否是稳定的
4. 分布式系统的CAP理论

第三题的编程题目：

给你一个整数数组nums,找出并返回所有该数组中不同的递增子序列个数，递增子序列中至少有两个元素

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

例如，若数组为{4,6,7,7}，则答案应为8

喜马拉雅

有单选，多选，2道编程。共一小时。

相关知识点记录：

1. 广度优先除了队列还可以用什么数据结构
2. 归并排序是否会退化，最坏情况是什么
3. 迪杰斯特拉是深度优先吗
4. 什么情况会发生page fault
5. nginx支持反向代理 负载均衡 虚拟主机吗
6. 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;
    }