【算法】大疆8.14笔试题总结

码农智涵的程序人生 2022-08-15

511

15道单选 5道多选。啥都有，前端后端乱七八糟的一通乱答。全程60min。。

笔试第一题很简单，就是暴力写个双重循环就完事了。

第二题折腾够呛，只过了57% 结束后在力扣发现了类似的题目。

力扣1124题：

思路1：

哈希+前缀和

大于8的数可以换为1，否则换为-1，这样就转换为数组求最长区间、区间和为0的问题。
求最长的区间和，可以利用一个哈希表存储每个前缀和最早出现的位置。
遍历数组，对当前前缀和有两种情况：

（1）如果当前 s 大于0，说明此时满足要求，直接更新res

（2）如果当前 s 小于等于0，就去哈希表中找比它小1 出现的位置，并更新结果。

由于只有当前前缀和不大于0时才会在哈希表中进行查找，所以实际上只用记录前缀和不大于0的位置。

代码：

    public static int maxKPI(int[] hours){
        int res = 0;
        Map<Integer, Integer> map = new HashMap<>();
        int s = 0;
        for (int i = 0; i < hours.length; ++i) {
            s += hours[i] > 8 ? 1 : -1;
            if (s > 0) {
                res = i + 1;
            } else {
                int b = map.getOrDefault(s - 1, -1);
                if (b != -1) {
                    res = Math.max(res, i - b);
                }
                map.putIfAbsent(s, i);
            }
        }
        return res;
    }

时间复杂度：O(n)

空间复杂度：O(n)

map常用方法：

map.getOrDefault(k,v);
获取指定key对应的value，如果找不到key，就返回默认值。
map.putIfAbsent(k,v);
先判断指定的key是否存在，不存在就将这对键值插入到Map中。

思路2：

暴力法——通俗易懂

显然它是把原始数组进行了处理，把大于8的置换为1，小于等于8的置换为-1；
然后开始双重循环，i指针后面的元素符合要求就更新res，res就是 i --> j 之间的距离。
最后再来一个剪枝操作， n-i < res 的意思就是剩下的元素个数已经小于 res 结果了，就没有必要再向下遍历了，直接返回 res 即可。

代码：

        int n = hours.length;
        for(int i = 0; i < n; i++){
            hours[i] = hours[i] > 8 ? 1 : -1;
        }
        int res = 0;
        for(int i = 0; i < n; i++){
            int count = 0;
            for(int j = i; j < n; j++){
                count += hours[j];
                if(count > 0)
                    res = Math.max(res, j - i + 1);
            }
            if(n - i <= res)
                return res;
        }
        return res;

时间复杂度：双重循环 O(n2)

空间复杂度：原址操作，无其他容器开辟 O(1)

哈希表 hours

文章转载自码农智涵的程序人生，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

【算法】大疆8.14笔试题总结

评论