大厂算法面试通关_day01

第一题

给定长度L,求出数组中小于等于长度L区间内最多覆盖几个点(包括两端)

• 贪心
• 窗口

第二题

给定一个目录,求解目录下多少个文件,文件夹不算

第三题

给定一个非负整数num,如何不用循环语句返回 >= num并且离num最近的2的幂次方

• 使用二进制的特性求解
• 无符号右移>>>和有符号右移>>
  • >>>不管是正数还是负数,都是使用数字0来补位
  • >> 当数字为正数时使用0来补位,如果是负数使用1来部位

第四题

一个数组中只有两种字符G和B字符,[BBGGBGBBBGGBB],如何让所有字符G在左边而B字符全部放在右边或者所有字符B在左边而所有G字符在右边,但只能在相邻字符之间交换,请问至少需要交换多少次

• 贪心
• 暴力破解 + 贪心 ？
• 盲点

# 字符串转换成数组
String s;
char[] str = s.toCharArray(); //兼容各种编程语言,java 可直接使用 s.charAt(i);

第五题- ==Leetcode 329. Longest Increase Path In Matrix==

给定一个二维数组Matrix，你可以从任何位置出发,可以走上下左右四个方向,返回能走出来的最长的递增量长度

• 计划搜索(自顶向下的动态规划)

第六题- ==Hard==

给定两个非负数组x和hp，长度都是N,在给定一个正数rangx有序x[i]表示 i 号怪兽在 x轴上的位置;

hp[i] 表示 i 号怪兽的血量, range表示法师如果站在 x位置,用AOE技能打到的范围是: [x - range, x + range],被打到的每只怪兽损失一点血量

返回要把所有怪兽血量清空,至少需要释放多少次AOE技能？

• 线段树

第七题-==LeetCode 494. TargetSum==

给定一个数组arr,你可以决定在每一个数字前面 + 或者 - ,但是所有数字必须参与

再给定一个数字target,请问最后所有数字运算结果为target的组合数是多少？

• 暴力破解
• 使用缓存命中将可变参数放入缓存
  • 构建缓存 HashMap<Integer,HashMap<Integer,Integer>>
• 动态规划
  • 优化方案
    • 将数组所有元素都当作是正数
    • 如果所有正数元素之和为Sum，如果target > sum 此时无解
    • target 和 Sum的奇偶性是不会变的 即 ((target & 1) ^ (sum & 1) == 0)
    • 假定有集合 $P = [1,3,5], Q = [2,4]$ 存在多少种组合使得 $P = \frac{target + (P + Q)}{2} = \frac{target + sum}{2}$
    • 空间压缩