Lucky Le の Blog

15. 三数之和 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。 注意：答案中不可以包含重复的三元组。 示例 1： 输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 思路比较简单：双指针，从两边开始，和两数之和类似，主要记录一下实现的一些细节。 123456789101112131415161718192021222324252627282930313233343536373839404142class Solution { public List<List<Integer>> threeSum(int[] nums) { int len = nums.length; List<List<Integer>> ans = new ArrayList<>(); if (len < 3) ...

一、基础秒杀项目概述 1. 项目架构 接入层模型（View Object）：与前端页面对接的模型，用于前端页面的展示，是一个聚合模型。 业务层（Domain Object）：领域模型，是业务的核心模型，拥有完整的生命周期，是贫血模型。和业务相关，因此是最先设计的。 数据层（Data Object）：数据模型，同数据库映射，用以ORM方式操作数据库的模型。 贫血模型：对应的Domain Model只包含基础的属性、get、set方法，不包含具体的业务逻辑。而业务逻辑则放在调用贫血模型的service中。 这种设计模式其实是和面向对象的思想背道而驰的，它是一种面向过程的思想。它破坏的面向对象的封装性。面向对象主张将数据和行为绑定在一起，对外提供接口。 这里项目中采用贫血模型可能因为只有秒杀业务逻辑，相对简单，开发迅速。对于复杂的业务逻辑，则需要更完善的设计，并采用充血模型。 2. 对象、模型关系 图中的三层对应了上述的三种模型。并且可以看到模型间进行了各种组合/聚合。 (1) 商品模型ItemModel组合了数据库中的商品数据表ItemDO和库存数据表ItemStockDO，并且如 ...

5. 最长回文子串 给你一个字符串 s，找到 s 中最长的回文子串。 1. 动态规划解 定义状态：dp[i][j]表示子串s[i...j]是否为回文子串 状态转移方程：dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1] 两个指针i和j分别 代表区间的两端，当两端相等时，s[i...j]是否为回文子串 就取决于s[i+1...j-1] 理清楚上面的转移方程代码思路就比较清晰了。 时空复杂度都为O(N2)O(N^2)O(N2) 1234567891011121314151617181920212223242526272829303132333435class Solution { public String longestPalindrome(String s) { int len = s.length(); if (len < 2) { return s; } int maxLen = 1; int b ...

4. 寻找两个正序数组的中位数 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。 算法的时间复杂度应该为 O(log (m+n)) 。 一、归并算法 合并两个有序数组，再根据长度直接得到中位数。时间复杂度不符合要求。 其实可以不用全部合并完，合并到中位数的位置即可。 1234567891011121314151617181920class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int len1 = nums1.length; int len2 = nums2.length; int i = 0; int j = 0; int k = 0; int[] tmp = new int[len1 + len2]; while (i < len1 && j &l ...

Spring随笔 视频是黑马的SSM教程，传送门，记录些知识点，主要是概念及使用，本篇不涉及源码相关。 1. Spring核心概念 Spring核心概念这部分内容中主要包含IOC/DI、IOC容器和Bean。 1.1 提出概念前，项目中的问题？ (1)业务层需要调用数据层的方法，就需要在业务层new数据层的对象 (2)如果数据层的实现类发生变化，那么业务层的代码也需要跟着改变，发生变更后，都需要进行编译打包和重部署 (3)所以，现在代码在编写的过程中存在的问题是：耦合度偏高 针对这个问题，该如何解决呢? 我们就想，如果能把框中的内容给去掉，不就可以降低依赖了么，但是又会引入新的问题，去掉以后程序能运行么? 答案肯定是不行，因为bookDao没有赋值为Null，强行运行就会出空指针异常。 所以现在的问题就是，业务层不想new对象，运行的时候又需要这个对象，该咋办呢? 针对这个问题，Spring就提出了一个解决方案: 使用对象时，在程序中不要主动使用new产生对象，转换为由外部提供对象 这种实现思就是Spring的一个核心概念 1.2 IOC、IOC容器、Bean、DI概念 1 ...

剑指 Offer 49. 丑数 264. 丑数 II 我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。 示例: 输入: n = 10 输出: 12 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。 参考题解 丑数递推性质：丑数=某较小丑数×某因子丑数 = 某较小丑数 \times 某因子丑数=某较小丑数×某因子 为了不遗漏，我们用三个游标a、b、c分别标记哪些数乘了2、乘了3和乘了5。如a则表示a前面的a-1个数都乘过2了，下一个应该乘2的数应该是a。 那么新的丑数应该是a * 2、b * 3、c * 5中最小的那个数 丑数递推公式：xn+1=min(xa×2,xb×3,xc×5)x_{n+1}=min(x_a×2,x_b×3,x_c×5)xn+1​=min(xa​×2,xb​×3,xc​×5) 12345678910111213141516171819class Solution { public int nthUglyNumber(int n)  ...

剑指 Offer 37. 序列化二叉树 请实现两个函数，分别用来序列化和反序列化二叉树。 你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。 提示：输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。 思路：采用dfs遍历、使用StringBuilder存储，每个节点使用,分隔，遇到null节点使用#标识。注意反序列化时，左右节点的顺序要与序列化dfs时一致 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162/** * Definition for a binary tree node. * public class TreeNode { * int ...

参考黑马的redis入门到实战视频，记录一些知识点 视频在b站 -> 传送门 一、基础 1. redis特征 键值(key-value)型，value支持多种不同数据类型，功能丰富 单线程，每个命令具备原子性 低延迟，速度快（基于内存、IO多路复用、良好的编码） 支持数据持久化 支持主从集群、分片集群 2. redis的常用指令 2.1 通用指令 KEYS：查看符合模板的所有key DEL：删除一个指定的key EXISTS：判断key是否存在 EXPIRE：给一个key设置有效期，有效期到期时该key会被自动删除 TTL：查看一个KEY的剩余有效期 通过help [command] 可以查看一个命令的具体用法： 2.2 String相关指令 SET：添加或者修改已经存在的一个String类型的键值对 GET：根据key获取String类型的value MSET：批量添加多个String类型的键值对 MGET：根据多个key获取多个String类型的value INCR：让一个整型的key自增1 INCRBY:让一个整型的key自增并指定步长 ...

剑指 Offer 39. 数组中出现次数超过一半的数字 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2 思路：采用摩尔投票法。思想为票数正负抵消。时间复杂度为O(n)，空间为O(1)。 简单理解：最坏情况拿众数和其他数一换一，最终剩下的肯定是众数。 具体的证明可以看参考题解。 实现：遍历时，两个数不同则票数-1，两个数相同则票数+1，票数为0时，则更新统计的数字(votes) 12345678910111213141516171819class Solution { public int majorityElement(int[] nums) { int len = nums.length; int votes = 0; int res = 0; for (int num : nums) { if (votes ...

剑指 Offer 56 - I. 数组中数字出现的次数 一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。 示例 1： 输入：nums = [4,1,4,6] 输出：[1,6] 或 [6,1] 思路：直接参考题解 假设只出现一次的两个数分别为x和y 首先将数组中所有数进行异或，因为两个相同的数异或后为0，因此最终的结果就是x和y的异或值 我们找到第一步结果中二进制的一个1位，该位的值为1，说明x和y在该位的值不同 我们循环数组，将数组进行分组，将x和y分在不同组。分组的标准就是第二步中的那一位1。将组内的数进行异或，因为只有x和y出现一次，因此两组异或的结果分别就是所求的x和y。 12345678910111213141516171819202122232425class Solution { public int[] singleNumbers(int[] nums) { int x = 0; int y = 0; ...