左神算法

位运算技巧 组合起来n如果是负数就返回0，非负数就返回1 123456789101112// 请保证参数n，不是1就是8的情况下//1 ->@//0->1public static int flip(int n){ return n^1;}// n是非负数，返回1// n是负数，返回8public static int sign(int n){ return filp( (n>>31) & 1);} 例题题目1给定两个有符号int a b，返回其中 较大的，不要进行比较 解法1 配合上技巧1里面的判断符号位正反的代码 解法存在问题，a - b可能溢出，但是可以提醒 互斥条件的使用 可以模拟 ifelse 解法2 关键性代码解析，对于return A 等号右侧公式解读：ab的符号不同，并且a是正数的情况下 以及 ab符号相同并且ab差值大于零的情况下， 至于return B 则是反过来就可以了 题目2判断一个32位的正数是不是2的幂，4的幂 知识补充2的幂就代表在二进制数中只有一个位置上是1，其余 ...

大数据常见数据 2的32次方差不多是42亿 int类型的范围是 2的32次方 -1 技巧罗列 哈希函数分流思想是万能的 这类题严格意义上讲的内存限制题目，并且只有以上几种套路，是面试过程中最好准备的 例题问题132位无符号整数的范围是0~4,294,967.295，现在有一个正好包含40亿个无符号整数的文件，所以在整个范围中必然存在没出现过的数。可以使用最多1GB的内存，怎么找到所有未出现过的数?【进阶】内存限制为 10MB，但是只用找到一个没出现过的数即可 空间充足哈希表一个一个存储 空间紧凑利用int类型来作为byte数组，校验范围内每一个数是否出现，并且由于是索引判断，更新速度很快，最后只需要遍历一次byte数组即可 空间非常紧凑在给定的范围内求最大可以分成多长的int数组，得出的结果向下取一个最近的2的整数次幂，指数的大小就是数组的大小。然后用该数组对给定的数进行分割，可以使用 / 操作，获取对应的索引并将该位置上的值++，最后有不满足最大值的就是缺了，然后对于确定是缺少数组的范围再次进行上述操作，不同的是这次不在这个范围内的数不放进去，同时对这个范围的数 进 ...

并查集，KMP，Manacher——左神算法并查集代码实现并查集是把原有的链表结构重新优化，按照图的上一个node来进行保存 import java.util.HashMap; import java.util.List; import java.util.Stack; /** * @Author laimouren * @Date 2021/12/7 19:35 */ public class UnionFind { //样本进来会包一层，叫做元素 public static class Element<V>{ public V value; public Element(V value){ this.value = value; } } public static class UnionFindSet<V>{ ...

二叉树进阶树形dp的套路可能性罗列，左右树分别可能收集什么样的信息 过程总结 例题问题1规定 距离 是二叉树中任意连个node之前的node数量加上二者本身的数量和 求一棵二叉树中的最大距离 分析问题拆解，每一个子问题可以看做是1，不考虑根节点的距离，2，必须纳入根节点的距离 前者是根节点两棵子树的最大距离，后者是左右子树的高度和，由此对于树形dp套路中问左右字数要内容的结构就包含自己的最大值和高度。 代码 问题2一家公司人员结构可以看做一棵多叉树结构，每个人结构中包含一个int类型的欢乐值和下级，现在需要开一个排队，需要达到要求来人让欢乐值最大，但是员工的直接上下级不能同时出现。 分析还是从每一棵子树上进行分解，将这棵子树的欢乐值情况列举出来，首先是根节点来的情况，那么所有直接子节点就不来，然后是根节点不来的情况，最大欢乐值就变成了看每棵子树或者不来的最大值，因此可以由此确定返回值的结构，双int，分别代表根节点来或不来的最大欢乐值。 注意在遇见题目的时候不要跳过条件分解这一大前提，直接按照经验去构造解题过程必然会导致带着优化代码的目的去再次审题，容易陷入误区，建议还是跟着步骤 ...