一、思路 利用哈希表优化O(n)复杂度的查找,这是工作中常见优化点。 二、问题 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 的那 两个 整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。 你可以按任意顺序返回答案。 示例 1: 输入:nums =…
一、思路 与前两道打家取舍相比,结合了二叉树。 选择变成了,偷当前节点,下一步就去偷孙子节点。不偷当前节点,就去偷儿子节点。两个选择一计算,看哪个状态更优。 这儿还得注意动态规划常见的重叠子问题,用哈希表来优化。 二、问题 在上次打劫完一条街道之后和一圈房屋后,小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为“根&rd…
一、思路 相比打家取舍一,不能同时偷第一家和最后家。就是多了个选择,要不偷第一家,要不偷最后家。 动态规划问题就是要在题目中找出选择,得出状态。 二、问题 你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相…
一、思路 这是典型的动态规划问题。要想得到最优策略,就得在每个选择时刻最出最优决策。选择产生状态,合并状态得到结果。 开始认为,求最优选择时,只计算某一个选择。导致不知道怎么得出某一个。后来发现,应该把所有选择都计算,得到多个状态,取最优的状态。 二、问题 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就…
GC 一、定义 1. 什么是垃圾 没有引用的对象(注意Java引用分为强软弱虚) 2. 怎么找到垃圾 引用计数法(Reference Counting): 虽然循环引用的问题可通过 Recycler 算法解决,但是在多线程环境下,引用计数变更也要进行昂贵的同步操作,性能较低,早期的编程语言会采用此算法。 可达性分析,又称引用链法(Tracing G…
一、线程 1. 线程方法 new T1().run() 调用run方法,同步的 Thread.yield() 让一下CPU,线程进入等待队列,从RUNNING变为RUNABLE状态 t.join() 等待t线程运行结束再运行 2. 线程状态 注意:Wating的原因 二、关键字 1. volatile 保证线程可见性 MESI 缓存一致性协议 禁止…
一、思路 这题也是滑动窗口类型,判断窗口内是否有重复值时,我使用的是集合+队列。集合判断是否重复,队列记录窗口位置。解题后看了下题解,才发现滑动窗口类型确实做少了,这题明明可以用通用解法:下标+map,下标记录窗口位置,map判断是否重复(泛型为<字符,出现的次数>)。 用集合+队列还有个坑:当窗口从未缩小时,是没有触发计算length,需要…
一、思路 这题虽然也是滑动窗口,但是是属于比较“死板”的滑动窗口,因为它的窗口是固定的,所以有相对简单的解法。我将两种解法都写出来了(简单解法和滑动窗口一般解法)。 二、题目 给定一个字符串 s 和一个非空字符串 p,找到 s 中所有是 p 的字母异位词的子串,返回这些子串的起始索引。 字符串只包含小写英文字母,并且字符串 s 和 p 的长度都不超…
一、思路 熟悉下滑动窗口算法,虽然能理解,但细节问题还是遇到很多。调试了很多遍才通过。 最后个用例过不了,用例长度特别大,当时只想到是不是Integer溢出,但是又没报错。那个用例大得都复制不了,无赖只能看题解。 原来是Integer比较时用了==,前面的用例为啥通过了?因为Integer缓存[-128-127]。 二、题目 给你一个字符串 s 、…
一、定义注解 @Retention(RetentionPolicy.RUNTIME) @Target(ElementType.METHOD) public @interface NoNeedLogin { } 二、定义拦截器 @Component public class AuthenticationInterceptor extends Hand…