naive的博客

题目一 洗衣机问题有n个打包机器从左到右一字排开，上方有一个 自动装置会抓取一批放物品到每个打包机上，放到每个机器上的这些物品数量有多有少，由于物品数量不相同，需要工人将每个机器上的物品进行移动从而到达物品数量相等才能打包。每个物品重量太大、每次只能搬一个物品进行移动，为了省力，只在相邻的机器上移动。请计算在搬动最小轮数的前提下，使每个机器上的物品数量相等。如果不能使每个机器上的物品相同,返回-1。例如[1, 0, 5]表示有3个机器，每个机器上分别有1、0、5个物品，经过这些轮后: 123第一轮:1 0 <- 5 => 1 1 4第二轮:1 <-1 <- 4 => 2 1 3第三轮:2 1 <- 3 => 2 2 2 移动了3轮，每个机器上的物品相等，所以返回3例如[2, 2, 3]表示有3个机器，每个机器上分别有2、2、3个物品，这些物品不管怎么移动，都不能使三个机器上物品数量相等，返回-1 leetcode517 超级洗衣机 贪心衣服和机器必须正好均分sum%n==0才能移动，将机器以机器i分开，为此时有以下几种情况： ...

题目一 差值为k的去重数字对给定一一个数组arr,，求差值为k的去重数字对。 给一个数组3,2,5,7,0,0 差值为2的有(0,2),(3,5),(5,7) (leetcode532 数组中的 k-diff 数对) 解 使用hash表将数据放入，遍历hash表，找到当前数+k的数是否存在 12345678910111213public List<List<Integer>> findPairs(int[] nums, int k) { HashSet<Integer> set = new HashSet<>(); for (int num: nums){ set.add(num); } List<List<Integer>> res = new ArrayList<>(); for (Integer num : set){ if (set.contains(num + k)){ ...

题目一 绳子覆盖最多点的数量给定一个有序数组arr,代表数轴上从左到右有n个点arr[0]、arr[1]... arr[n-1],给定一个正数T，代表一根长度为T的绳子，求绳子最多能覆盖其中的几个点。 解法一-二分查找以每个点开始，向左延伸T的长度，看有多个点被覆盖。时间复杂度：遍历一遍n,找点二分logn，O(nlogn)。 利用二分找小于等于arr[L]+k的最右侧的节点 123456789101112131415161718192021222324252627282930// 二分法public static int maxCoverPoint(int[] arr,int K){ if (arr == null || arr.length == 0 || K <= 0) { return 0; } int max=1; for(int L=0;L<arr.length;L++){ int R=binarySearch(arr,L,K); max=Math.max( ...

有序表是一种查找时间复杂度为O(logn)的算法，实现有序表的情况有红黑树、AVL树、SB树、跳表。 前3个都属于平衡搜索二叉树系列BST 如果我们有一个搜索二叉树，如何能让他的增删改查就尽量快一些。一般默认搜索二叉树没有重复节点，因为我们可以通过增数据项存重述节点的信息。就是一个节点的信息多一些，也不重要。在搜索二叉树中进行操作增删改查的操作，但是因为不平衡，所以我们是不能保证时间复杂度。一旦不平衡，我们的时间复杂度可能就是O(N)。所以我们要保证平衡性。 AVL树AVL树：是最最严格的平衡树，它每一个节点，左右子树高度差不超过一为了满足这个操作，需要引入两个操作：左旋+右旋。旋转表示的是头结点往哪边倒。 AVL树实现的是怎么用左旋和右旋的操作；红黑树也是实现左旋和右旋，并且有自己关于平衡的定义；SB树同样也有自己平衡的操作。 AVL树是怎么发现自己不平衡的？AVL数的增删改查与搜索二叉树相同，只是在增加节点后，会从当前增加的节点开始向上查找是否有平衡性；对于删除来说，是从替换节点（一个节点删除必然有节点替换这个节点）开始查找是否有平衡性。 对于插入节点1来说，就从插入节点1开始 ...

递归 -> 记忆化搜索 (dp)-> 严格表结构（dp） 某些问题上 记忆化搜索和严格表结构时间复杂度相同 机器人走路问题有N个格子，机器人初始在的位置S，目标位置是E，机器人可以向左或向右行走，每次走一步，可以走的步数为K步，问机器人有几种走法 暴力递归1234567891011121314151617181920212223242526272829303132// 暴力递归public int walkWays(int N, int E, int S, int K) { return f1(N, E, K, S);}/** * 递归方法 * * @param N 固定参数，一共有N个位置 * @param E 固定参数，目标位置E * @param rest 还剩下几步要走 * @param cur 当前所在位置 * @return 方法有多少种走法 */public int f1(int N, int E, int rest, int cur) { ...

比较两个数中较大的数12345678910111213141516171819202122232425262728293031323334353637383940414243public class GetMax { /* 保证参数n 不是n就是1 1->0 0->1 */ public int flip(int n) { return n ^ 1; } /* n是非负数返回1， n是负数返回0 */ public int sign(int n) { return flip((n >> 31) & 1); } // 不考虑溢出 public int getMax1(int a, int b){ int c = a - b; //可能会溢出 int scA = sign(c); // a-b为非负 scA为1，否则是0 int scB = sign(sc ...

资源限制类题目 哈希函数可以把数据按照种类均匀分流1一个大文件 无符号整数 (2^32^-1 就是 0- 42亿范围）有40亿个数，1g内存求出现次数最多的数是哪一个？ 如果使用hash表来做 key - value ,key是(4B),value是int(4B), 一个数就要8B，如果40亿个数都不一样，就需要 320亿B（32G）。 对数据a 先使用 hash函数得到数 b，然后 % 100得到 0-99范围的数，相同的数据进同一个文件，不同的数种类上进不同文件。对每一个小文件使用hash表，然后求出这100个数的最大值。不怕同一种数太多，怕不同种的数太多，内存不够。 布隆过滤器用于集合的建立与查询，并可以节省大量空间解决黑名单过滤、对100亿url(64Byte)进行黑名单过滤过滤，如果使用hashset,需要640G内存。 爬虫去重，多个线程爬url, 如果已经爬过，就不要再爬，爬虫之间不要爬同一个。 集合有添加、有查询，没有查询、极大程度减少内存使用，允许有一定程度失误率。如果一个数据不在布隆过滤器中，可能会误报，但一个数据在布隆过滤器中，一定不会误报。 一致性哈希解决数 ...

前提：如果题目求解目标是S规则，则求解流程可以定成以每一个节点为头节点的子树在S规则下的每一个答案，并且最终答案一定在其中。 二叉树节点间的最大距离问题从二叉树的节点a出发，可以向上或者向下走，但沿途的节点只能经过一次，到达节点b时路径上的节点个数叫作a到b的距离，那么二叉树任何两个节点之间都有距离，求整棵树上的最大距离。 分析： 当前节点X不参与的情况：当前最大距离可能来着左树的最大距离，右数的最大距离。 当前节点参与的情况下：左树最远节点，到右树最远节点。左树高 + 1（自己）+ 右树高。 三个值求最大值就为整棵树上的最大距离。对于每个节点需要2个信息：最大距离和树的高度。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859public class Morris { // 二叉树节点 public static class Node { public int valu ...

什么是事务事务：是数据库操作的最小单元，是作为单个逻辑工作单元执行的一系列操作；这些操作作为一个整体一起向系统提交，要么都执行，要么都不执行；事务是一组不可再分割的操作集合（工作逻辑单元）。 事务是四大特性 原子性（Atomicity）:事务中所有操作是不可再分割的原子单元。事务中所有操作要么全部执行成功，要么全部执行失败。 一致性（Consistency）:事务执行后，数据库状态与其他业务规则保持一致。如转账业务，无论事务执行成功与否，参与转账的连个账号余额之和应该是不变的。 隔离性（lsolation）:隔离性是指在并发操作中，不同事务之间应该隔离开来，使每个并发中的事务不会相互干扰。 持久性（Durability）:一旦事务提交成功，事务中所有的数据操作都必须被持久化到数据库中，即使提交事务后，数据库马上崩溃，在数据库重启时，也必须能保证通过某种机制恢复数据。 事务的隔离级别数据库事务的隔离级别有4种，由低到高分别为Read uncommitted 、Read committed 、Repeatable read 、Serializable。而且，在事务的并发操作中可能会出现脏 ...

AOP概述AOP为Aspect Oriented Programming的缩写，意为：面向切面编程，通过预编译方式和运行期间动态代理实现程序功能的统一维护的一种技术。 是一种新的模块化机制，用来描述分散在对象，类，或函数中的横切关注点，分离关注点使解决特定领域问题的代码从业务逻辑中独立出来，业务逻辑代码中不在含义针对特定领域的代码调用，业务逻辑同特定领域问题的关系通过切面封装，维护，这样原本分散在整个应用程序中的变动可以很好地管理起来。 用人话说就是，通过切面完成特定逻辑（事务，入参出参日志等） 可以和业务逻辑（CRUD）抽离开，便于维护 Advice 通知：定义在连接点做什么，为切面增强提供植入接口。描述Spring AOP围绕方法调而注入的切面行为 Pointcut切入点：切点决定Advice通知应该作用在哪个连接点，也就是通过Poincut来定义需要增强的方法集合，这些集合可以按照一定规则来完成，这种情况下，Pointcut意味着标识方法（比如事务切面定义了事务注解方法上生效）切入点是一些列织入逻辑代码的连接点集合 Advisor通知器：整合Advice 和 Pointcut， ...