leetcode题经
重在将自己解题的思路发上来，当然有时候是最快的解法加上一些我对它的想法，希望大家都能有所收获。若题目有更好的解法，欢迎一起交流。具体github项目专门放了我对算法的看法，leetcode结题，还有源码分析等等，持续更新中。
/**
* 注意HashMap的put(Key,Value)是可以替换旧值的，所以当我们遇到测试数据中包含重复数值时可以无视它。
* 所以其实判断条件里面的map.get(supplement)!=i其实也是可以无视的，因为我们的value已经更新为后面的值了
* @param nums
* @param target
* @return
*/
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<>(16);
for (int i = 0; i < nums.length; i++) {
int supplement = target - nums[i];
if (map.containsKey(supplement) && map.get(supplement) != i) {
return new int[]{i, map.get(supplement)};
}
map.put(nums[i], i);
}
return null;
}
算法题知识点总结
以下内容合并自 kgNotes/notes/算法题知识点总结.md。原 Obsidian 图片附件未在知识库中找到，已保留为“图示”文件名提示。
数组类
两数之和
图示：算法题知识点总结-两数之和.png
- 由于数组有序
- 设置快慢指针，通过比较大小，来驱动指针向中间游动
public int[] twoSum(int[] numbers, int target) {
int left =0;
int right=numbers.length - 1;
while(left<right){
int sum=numbers[left]+numbers[right];
if(sum==target){
break;
}
if(sum>target){
right--;
}else{
left++;
}
}
return new int[]{left+1, right+1};
}
三数之和
图示：算法题知识点总结-三数之和.png
- 设置三个指针，而内部的两个指针其实就是双数之和
- 优化点
- 如果数字相同，则指针向前移动
- 如果三个最小数和已经大于0，则没必要继续处理了
- 如果两个最大值+当前的左指针小于0了，则左指针向前
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> resultList=new ArrayList<>();
int length=nums.length;
for(int i=0;i<length-2;i++){
int x=nums[i];
if(i>0 && x==nums[i-1]){
// 重复数字跳过
continue;
}
// 最小的三个数已经大于0了
if(x+nums[i+1]+nums[i+2]>0){
break;
}
// 最小的+两个最大值如果小于0，则左指针继续往下
if(x+nums[length-2]+nums[length-1]<0){
continue;
}
int j=i+1, k=length-1;
while(j<k){
int sum=x+nums[j]+nums[k];
if(sum>0){
k--;
}else if(sum<0){
j++;
}else{
resultList.add(List.of(x,nums[j],nums[k]));
for(j++;j<k && nums[j]==nums[j-1];++j);
for(k--;j<k && nums[k]==nums[k+1];k--);
}
}
}
return resultList;
}
盛水最多的容器
图示：算法题知识点总结-盛水最多的容器.png
- right 左移使右侧变蓝 (判断条件为 true )
- left 右移使左侧变红 (判断条件为 false )
- 故确定二分处 ( mid ) 的染色条件是关键
- 关键的面积计算公式是
- 宽度 * 两根线的minHeight
- 基于这条公式
- 我们先算出来左右两个指针的面积
- 如果说要比我们最开始最大宽度的面积要大，那么高度一定要上升
- 要么右边的高度比左边的高了，我们左边指针右移试试
- 要么左边的高度比右边的高了，我们右边指针左移试试看
public int maxArea(int[] height) {
int result=0;
int left=0;
int right=height.length-1;
while(left<right){
int area=(right-left)*Math.min(height[left],height[right]);
result=Math.max(result,area);
if(height[left]<height[right]){
left++;
}else{
right--;
}
}
return result;
}
接雨水
图示：算法题知识点总结-接雨水.png
- 核心的关键抽象怎么计算出水单位
- 我们可以发现水的单位是由前面的墙高度和后面墙的高度，取两者的最小值
- 这里我们就会发现这里就是一堆的盛水最多容器的变种题目
- 那么我们做两个遍历
- 第一遍我们去计算所有节点的前面墙高度是多少
- 第二遍我们去计算所有节点的后面墙高度是多少
- 最后我们遍历整个数组
- 首先取墙的最低高度，因为这个决定了水到底能装多少，因为超过这个的会漏出去
- 然后用墙的最低高度-当前的数组高度= 实际水单位
public int trap(int[] height) {
// 时间复杂度On
// 空间复杂度On
int l=height.length;
int[] preMax=new int[l];
preMax[0]=height[0];
for(int i=1;i<l;i++){
preMax[i]=Math.max(preMax[i-1],height[i]);
}
int[] sufMax=new int[l];
sufMax[l-1]=height[l-1];
for(int j=l-2;j>=0;j--){
sufMax[j]=Math.max(sufMax[j+1],height[j]);
}
int result=0;
for(int n=0;n<l;n++){
result+=Math.min(preMax[n],sufMax[n]) -height[n];
}
return result;
}
- 如果不使用空间存储呢，我们优化两个指针，表示前序最高的高度以及后序的最高高度
- 如果前序的小，那么此时能装水的高度就为前序
- 我们就直接拿前序减去此时的高度即可
public int trap(int[] height) {
int l=height.length;
int result=0;
int left=0;
int right=l-1;
int preMax=0;
int sufMax=0;
// 如果相等，也要计算水
while(left<=right){
preMax=Math.max(preMax,height[left]);
sufMax=Math.max(sufMax,height[right]);
if(preMax<sufMax){
result+=preMax-height[left++];
}else{
result+=sufMax-height[right--];
}
}
return result;
}
长度最小的子数组
图示：算法题知识点总结-长度最小子数组.png
- 核心可以转为，维护一个最左节点
- 我们从0开始迭代数组
- 如果发现迭代和减掉最左节点值，依然大于target【即满足题意要求的话】，那左节点持续右移
- 直到不满足且当前和大于target时，我们存储结果值【当然要判断此时是不是最优解】
public int minSubArrayLen(int target, int[] nums) {
int l=nums.length;
int result=l+1;
int sum=0;
int left=0;
for(int right=0;right<l;right++){
sum+=nums[right];
while(sum-nums[left]>=target){
sum-=nums[left++];
// 左端点右移
}
if(sum>=target){
result=Math.min(result,right-left+1);
}
}
return result<=l?result:0;
}
乘积小于k的子数组
图示：算法题知识点总结-乘积小于k的子数组.png
- 只要最长的子数组满足了
- 那么我们就可以得到right-left+1的节点就肯定是结果数组个数一部分，再然后我们就继续右移right节点即可
public int numSubarrayProductLessThanK(int[] nums, int k) {
if(k<=1){
return 0;
}
int result=0;
int prod=1;
int left=0;
for(int right=0;right<nums.length;right++){
prod *= nums[right];
while(prod>=k){
prod/=nums[left];
left+=1;
}
// 只要满足了，那么结果就为l到r之间的每一个和，因为他们都是小于target的
// 所以直接right-left，再把位点+1加上即可
result+=right-left+1;
}
return result;
}
无重复字符的最长字串
图示：算法题知识点总结-无重复字符的最长子串.png
- 由于题干说了是数字、字符，那么就是ASCII码，128的数组即可秒
- 由于是判断是否重复，我们可以初始化boolean的128位数组
- 首先定义一个left节点，作为滑动窗口起始
- 开始遍历数组
- 当发现有重复字符的时候
- 将滑动窗口的左节点持续向右移，直到不重复为止
- 记录最大的子串长度结果
public int lengthOfLongestSubstring(String s) {
int result=0;
int left=0;
boolean[] has=new boolean[128];
for(int right=0;right<s.length();right++){
char c=s.charAt(right);
while(has[c]){
has[s.charAt(left++)]=false; //左移窗口，并且置为false
}
has[c]=true;
result=Math.max(result,right-left+1);
}
return result;
}
获取单值网络中最小操作数
2033. 获取单值网格的最小操作数 - 力扣（LeetCode）
class Solution:
def minOperations(self, grid: List[List[int]], x: int) -> int:
flat = []
first = grid[0][0]
for row in grid:
for num in row:
if (num-first) % x != 0:
return -1
flat.append(num)
flat.sort()
medium = flat[len(flat)//2]
res=0
for num in flat:
res += abs(num-medium)//x
return res
class Solution {
public int minOperations(int[][] grid, int x) {
int totalEle=grid.length * grid[0].length;
int[] temp=new int[totalEle];
int num=0;
for(int row=0;row<grid.length;row++){
for(int i=0;i<grid[row].length;i++){
int j=grid[row][i];
// m每个元素都必须是x的倍数，不然不可能达标
if((j-grid[0][0])%x!=0){
return -1;
}
// 转为一维数组，其实也可以不转，变成动态下标也能直接玩
temp[num++] = grid[row][i];
}
}
// 需要排序 或者 搞成第k大算法来找中位数
Arrays.sort(temp);
int result=0;
for(int ele=0;ele<temp.length;ele++){
// 通过每个元素和中位数进行比较，除以x，就代表每个元素到达中位数需要的次数
// 全部加起来就是结果了
result += Math.abs(temp[ele] - temp[totalEle/2])/ x;
}
return result;
}
}
查找
排序数组查找第一个和最后一个
图示：算法题知识点总结-查找元素第一个和最后一个.png
- 观察题干需要什么数字
- 第一个等于target的数字
- 转化为>=target的区间
- 最后一个等于target的数字
- 转换为> = target+1的
- 第一个等于target的数字
- 使用LowerBound实现
- 定义一个闭区间为【L，R】即【0，nums.length-1】
- 每一次取中间值mid= L+（R-L）/2
- 除以2直接向下取整，对于偶数场景那就是左边的数字
- 判断中间值与target的关系
- 假如说中间值< target
- 那么中间值以及左边的数据都是小于target的
- 即我们的区间可以缩小到【mid+1，right】
- 如果说中间值>=target
- 那么中间值以及右边的数据都是大于等于target的
- 即我们的区间可以缩小到【left，mid-1
- 假如说中间值< target
- 当我们判断完上面的值，得到最后的【left，right】区间时
- 我们的left一定是>=target的，因为最后一步操作里面left=mid+1的
- 通过这样子的方法，我们可以找到第一个大于等于target的数字
- 那么怎么找到最后一个等于target的数字呢？
=target+1
- 则得到数字-1
public int[] searchRange(int[] nums, int target) {
int start=lowerBound(nums,target);
if(start==nums.length|| nums[start] != target){
return new int[]{-1,-1};
}
int end=lowerBound(nums,target+1)-1;
return new int[]{start,end};
}
// 闭区间
public int lowerBound(int[] nums, int target){
int left=0,right=nums.length-1;
while(left<=right){
int mid=left+(right-left)/2;
if(nums[mid]<target){
left=mid+1; // [mid+1,right]
}else{
right=mid-1; // [left,mid-1]
}
}
return left;
}
二分查找数据
图示：算法题知识点总结-二分查找数据.png
- 都是把问题转换为>=target，然后找下标的过程
- 注意，如果遍历完找不到数据，那么此时返回的下标一定是数组长度的，即越界了
public int search(int[] nums, int target) {
// 转换题目 找到>=target的值并返回下标
int left = 0, right=nums.length-1;
while(left<=right){
int mid=left+(right-left)/2;
if(nums[mid]<target){
left=mid+1;
}else{
right=mid-1;
}
}
if(left == nums.length || nums[left] != target){
return -1;
}
return left;
}
找封顶值
图示：算法题知识点总结-找封顶值.png
- 封顶即一定是大于左右两边的值
- 那么我们可以抽象为nums【top】>= nums【top+1】
public int findPeakElement(int[] nums) {
int left=0,right=nums.length-2;
while(left<=right){
int mid=left+(right-left)/2;
// 重点在于爬坡的过程，封顶那么左边的值一定是小于封顶的
// 即mid<mid+1
// 由于找任意，所以我们随便找个地方开始计算即可
if(nums[mid]<nums[mid+1]){
left=mid+1;
}else{
right=mid-1;
}
}
return left;
}
寻找旋转排序数组的最小值
图示：算法题知识点总结-旋转数组找最小.png
- 核心在于，由于它有可能是两段有序的，所以我们用lowerBound实现时，并不能很好地找到边界
- 但我们可以做个判断
- 首先如果起始位置的值比结束位点的小，那么就证明没有旋转，那么结果就是0下标的值
- 假如有旋转过
- 我们可以每次染色比较时和第0位元素进行比较
- 假设mid的值比第0位要小，那就说明mid到right的数字都是比最小值要大的，因为递增的原因
- 所以我们可以把right=mid-1
- 假如比第0位大于or 等于，那就说明left到mid之间的数字肯定是比最小值要大的，同样是因为递增的原因
- 所以我们可以把left=mid+1
- 假设mid的值比第0位要小，那就说明mid到right的数字都是比最小值要大的，因为递增的原因
public int findMin(int[] nums) {
// 首先是抽象题目
// 要找到最小的值，由于这个是相对有序的
// 那么也就是说 >= 最小的值
// 假设最后一个数字是最小的
if(nums[0]<=nums[nums.length-1]){
return nums[0];
}
int left=0, right=nums.length-1;
while(left<=right){
int mid=left+(right-left)/2;
if(nums[mid]<nums[0]){
right=mid-1;
}else{
left=mid+1;
}
}
return nums[left];
}
求平方数
AA
public boolean isPerfectSquare(int num) {
int left = 0, right=num;
while(left<=right){
int mid=left+(right-left)/2;
long square = (long) mid * mid;
if (square < num) {
left = mid + 1;
} else if (square > num) {
right = mid - 1;
} else {
return true;
}
}
return false;
}
寻找旋转数组里面相等的值
图示：算法题知识点总结-旋转数组里找数字.png
- 先说两次二分查找
- 先找到最小值，这块就用和尾节点、or 开始节点查询即可
- 然后接lowerBound可破
- 紧接着是判断target和尾节点的关系
- 如果target>尾节点，那么一定在起始节点到minINdex间，要么就不存在
- 反之，一定在minINdex到结尾节点上
- 这里就是接lowerBound，把上面的区间范围传入即可
- 再说只用一次查找的写法
- 核心在于isBlue的判断
- 如果是翻转数组
- 如果target>尾节点 且 当前指针比target>=的话，那么右边就是蓝色，right可以右移到mid-1
- 如果是正向数组
- 如果target>尾节点
- 那么一定都是蓝色的，右移
- 如果当前指针比target大于等于的话，右边也是蓝色
- 如果target>尾节点
- 如果是翻转数组
- 核心在于isBlue的判断
public int search(int[] nums, int target) {
int minIndex=findMin(nums);
int left=0,right=nums.length-1;
// 如果target比起始位置小，那么一定是在minIndex的左边
// 如果相反的话，则不能确认了，因为翻转的原因，一定在起始位置右边，而且由于翻转无法排除，所以right不能优化
// 如果是跟结尾节点比呢？
// 如果比结尾节点大，那么一定是在起始位置到最小值的节点，因为这里才有可能找到比结尾节点还大的值【考虑翻转】
// 如果是比结尾节点<=，那么就是在尾节点的左边，且在minIndex间
if(target>nums[nums.length-1]){
// 如果比起始位置大，那么数字一定是从0开始往右边递增的数字里面
// 哪怕最小值就是0，那也是0和minIndex间
left=0;
right=minIndex;
}else{
// 如果比起始位置要小，那就证明这个值一定是在最小值的位置~结尾的地方
left=minIndex;
right=nums.length-1;
}
return lowerBound(nums, left, right, target);
}
public int lowerBound(int[] nums,int left, int right, int target){
int tempL=left;
int tempR=right;
while(left<=right){
int mid=left+(right-left)/2;
if(nums[mid]<target){
left=mid+1;
}else{
right=mid-1;
}
}
if(left<=tempR && nums[left]==target){
return left;
}
return -1;
}
public int findMin(int[] nums){
if(nums[0]<=nums[nums.length-1]){
return 0;
}
int left=0, right=nums.length-2;
while(left<=right){
int mid=left+(right-left)/2;
if(nums[mid]<nums[0]){
right=mid-1;
}else{
left=mid+1;
}
}
return left;
}
public int search(int[] nums, int target) {
int left=0;
int right=nums.length-1;
while(left<=right){
int mid=left+(right-left)/2;
if(isBlue(nums,target,mid)){
right=mid-1;
}else{
left=mid+1;
}
}
if(left<nums.length && nums[left]==target){
return left;
}
return -1;
}
public boolean isBlue(int[] nums, int target, int index){
int end=nums[nums.length-1];
if(nums[index]>end){
return target>end && nums[index]>=target;
}
return target >end || nums[index]>=target;
}
递归
二叉树最大深度实现方式
AA
对于这类题目 . - 力扣（LeetCode） 二叉树的最大深度
图示：算法题知识点总结-二叉树最大深度题图.png
- 我们不需要上来考虑树的结构或者纠结于题目，要学会抽象
- 比如这道题目可以转为这样子的思考
图示：算法题知识点总结-二叉树最大深度子问题.png
- 再往下“递“的过程中，总会有尽头，我们要做的就是边界值的定义
- 以及在遇到尽头后，怎么把值返回回去，而这就是“归”的过程
public int maxDepth(TreeNode root) {
// 定义退出边界值
if(root==null){
return 0;
}
// 求出左边的和 + 右边的和 = 最后输出结果
int maxLeftDepth=maxDepth(root.left);
int maxRightDepth=maxDepth(root.right);
return Math.max(maxLeftDepth, maxRightDepth) +1;
}
当然也要另外一种思路，就是我们维护一个全局变量，在递归的时候，就把值传下去，每一次递的过程，就对全局变量进行操作维护。
相同的树
图示：算法题知识点总结-相同的树题图.png
首先依然是对题目的抽象
- 可以抽象为每个节点的左子树是否相同
- 以及每个的右子树是否相同
- 接下来就是找到尽头，边界值问题
- 尽头就是两个子树都走到了相同的节点，我们判断两者的值是否相等
图示：算法题知识点总结-相同的树实现.png
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p==null || q==null){
return p==q;
}
return p.val==q.val && isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}
轴对称树
图示：算法题知识点总结-轴对称树题图.png
- 首先依然是抽象问题，轴对称
- 根节点肯定满足可跳过
- 每一次判断时就是节点的左子树是否与节点的右子树相等
- 注意：这里一定是传入两个轴对称的树根节点进来判断的
public boolean isSame(TreeNode left, TreeNode right){
if(left == null || right==null){
return left == right;
}
return left.val==right.val && isSame(left.left, right.right) && isSame(left.right, right.left);
}
public boolean isSymmetric(TreeNode root) {
return isSame(root.left, root.right);
}
是否平衡二叉树
图示：算法题知识点总结-平衡二叉树图解.png
- 首先是对问题的抽象
- 计算左子树的最大深度 以及 右子树的最大深度的绝对差值是否大于1
- 如果大于1，我们就返回-1，视为树是不平衡的
- 计算树的高度
- 计算子树的深度
- 边界值为null时，代表走到尽头，往回return 1
- 在归的过程也就是+1，表示深度+1
- 同时我们需要判断每次计算节点的时候，是否遇到了已经不平衡的情况
- 如果已经不平衡了，返回-1
public boolean isBalanced(TreeNode root) {
return getHeight(root) != -1;
}
public int getHeight(TreeNode root){
if(root==null){
return 1;
}
int leftHeight=getHeight(root.left);
if(leftHeight==-1){
return -1;
}
int rightHeight=getHeight(root.right);
if(rightHeight==-1){
return -1;
}
if(Math.abs(leftHeight-rightHeight)>1){
return -1;
}
return Math.max(leftHeight, rightHeight) +1;
}
前序遍历二叉树
前序遍历实现
AA
- 外围节点即左子树优先
- 执行顺序上是
- 先处理自己
- 再处理左子树
- 再处理右子树
. - 力扣（LeetCode）图示：算法题知识点总结-前序遍历二叉树.png
- 抽象题目开始
- 每一个节点都应该在一个范围区间，比如往1节点遍历时，则一定在MIN_VALUE到2之间；而3一定在2到MAX_VALUE之间
- 而每次归的过程，我们可以把范围给代入进行设置，比如1，2；2，3的范围
- 退出条件为
- 遍历到null时，返回true
- 而当位枝节点时，就可以判断值是否在范围内
public boolean isValidBST(TreeNode root) {
return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
public boolean isValidBST(TreeNode root, long left, long right){
if(root==null){
return true;
}
long x=root.val;
return left < x && x <right && isValidBST(root.left, left, x) && isValidBST(root.right, x, right);
}
中序遍历
AA
- 先左子树
- 再根节点
- 最后右子树
- 代码的话，就是先递归左子树，处理自己，递归右子树
. - 力扣（LeetCode）图示：算法题知识点总结-前序遍历二叉树.png
- 对于中序遍历，即顺序为左节点、根节点、右节点
- 对于这道题而言
- 左节点<根节点<右节点； 即每一个节点是大于上一个节点的值
- 那么退出条件是什么
- 当节点为空
- 返回true，因为没有值
- 当节点的值如果比上一个节点pre的值要大
- 返回false，说明不满足
- 当节点为空
- 递归的动作是
- 先递归左树
- 设置值
- 递归右树
- 这样子我们的的顺序就永远是
- 优先最左节点
- 最左节点的上个节点
- 上个节点的右节点
- 右节点又开始了左节点的递归顺序
long preVal=Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
if(root==null){
return true;
}
if(!isValidBST(root.left)){
return false;
}
if(root.val<=preVal){
return false;
}
preVal=root.val;
return isValidBST(root.right);
// return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
后序遍历
- 后序的话，就是先递归左右子树
- 再处理节点的值
图示：算法题知识点总结-前序遍历二叉树.png
- 抽象问题
- 后序遍历与前序遍历差别在哪呢？
- 前序遍历是每次都会先进行判断
- 在判断的时候，会把判断值的范围往下传
- 相当于是每次先判断，再递归；【理解为for就好】
- 而后序遍历是先进行递归
- 先走到根节点，再把判断值的范围往归的地方传
- 在收到归传回来的范围后，再进行判断
- 前序遍历是每次都会先进行判断
- 对于这道题而言
- 每一个节点都应该大于左子树的最大值以及右子树的最小值
- 所以每次我们需要返回最大值以及最小值的范围
public boolean isValidBST(TreeNode root) {
return dfs(root)[1]!=Long.MAX_VALUE;
}
public long[] dfs(TreeNode root){
if(root==null){
return new long[]{Long.MAX_VALUE, Long.MIN_VALUE};
}
long[] left=dfs(root.left);
long[] right=dfs(root.right);
int x=root.val;
if(x<= left[1] || x>=right[0]){
return new long[]{Long.MIN_VALUE,Long.MAX_VALUE};
}
return new long[]{Math.min(left[0],x), Math.max(right[1],x)};
}
二叉树层序遍历
图示：算法题知识点总结-二叉树层序遍历.png
- 维护一个队列，先把当层节点加入
- 只要队列不为空，就将每一层的左右节点依次压入队列
- 然后再进行pop
public List<List<Integer>> levelOrder(TreeNode root) {
if(root==null)return List.of();
List<List<Integer>> ans=new ArrayList();
Queue<TreeNode> q=new ArrayDeque<>();
q.add(root);
while(!q.isEmpty()){
List<Integer> vals=new ArrayList();
int n=q.size();
while(n-->0){
TreeNode node=q.poll();
vals.add(node.val);
if(node.left!=null)q.add(node.left);
if(node.right!=null)q.add(node.right);
}
ans.add(vals);
}
return ans;
}
计算最小深度
AA
深度优先法
. - 力扣（LeetCode）
图示：算法题知识点总结-dfs计算最小深度.png
private int result=Integer.MAX_VALUE;
public int minDepth(TreeNode root) {
dfs(root,0);
return root!=null?result:0;
}
public void dfs(TreeNode root, int cnt){
if(root==null){
return;
}
cnt++;
if(root.left==root.right){
result=Math.min(result,cnt);
return;
}
dfs(root.left,cnt);
dfs(root.right,cnt);
}
二叉树最近公共祖先
图示：算法题知识点总结-二叉树公共节点.png
- 考虑退出条件
- null 退出
- p退出
- q退出
- 先找左，再找右
- 接着输出结果
- 如果两边都找到了，则当前节点为祖先，return
- 如果只在一边有，则返回一边
链表
翻转链表
图示：算法题知识点总结-翻转链表.png
- 要翻转，先考虑最简单的
- 首先要记录已经翻转的，记为pre，最开始的节点是null
- 然后是需要迭代，cur=head
- 还需要一个节点记录next，记为nxt=cur.next
- 接下来就是交换的操作，我们在cur上直接翻转，由于记录了next，所以原地翻转
- nxt=cur.next
- cur.next=pre
- pre=cur;
- cur=nxt;
public ListNode reverseList(ListNode head) {
ListNode cur=head, pre=null;
while(cur!=null){
ListNode nxt=cur.next;
cur.next=pre;
pre=cur;
cur=nxt;
}
return pre;
}
翻转链表Ⅱ
图示：算法题知识点总结-翻转链表2.png
- 先暂存一下head节点，初始化dummy=new ListNode(0,head);
- 首先要找到头节点left的位置，并记录
- 比如left=2，相当于从哨兵节点开始遍历left-1次的next
- 然后我们要翻转2~4之间的节点，还是和之前的步骤一样
- 初始化pre=null
- next=cur.next
- cur.next=pre
- pre=cur
- cur=next
- 这一段翻转完后，此时pre是指向4的，cur是指向5的
- 最开始哨兵节点dummy以及p0我们是没有动过的
- p0.next.next 翻转后的节点要指向最新的
- p0.next 要指向翻转的节点pre
- return dummy.next
public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode dummy=new ListNode(0,head), p0=dummy;
for(int i=0;i<left-1;i++){
p0=p0.next;
}
//reverse
ListNode pre=null, cur=p0.next;
for(int i=0;i<right-left+1;i++){
ListNode nxt=cur.next;
cur.next=pre;
pre=cur;
cur=nxt;
}
// 链接节点
p0.next.next=cur;
p0.next=pre;
return dummy.next;
}
k个一组翻转链表
图示：算法题知识点总结-k个翻转链表.png
- 翻转的写法和之前的一样，关键在于每一次要把p0推进到下一组
图示：算法题知识点总结-翻转链表的debug图.png
- 输出结果
public ListNode reverseKGroup(ListNode head, int k) {
int n=0;
// 先记录总长度
for(ListNode cur=head;cur!=null;cur=cur.next){
n++;
}
ListNode dummy=new ListNode(0,head),p0=dummy;
ListNode pre=null, cur=head;
for(;n>=k;n-=k){
for(int i=0;i<k;i++){
ListNode nxt=cur.next;
cur.next=pre;
pre=cur;
cur=nxt;
}
// 在这一步交换节点
ListNode nxt=p0.next;
p0.next.next=cur;
p0.next=pre;
p0=nxt;
}
return dummy.next;
}
两数相加【迭代版本】
图示：算法题知识点总结-两数相加.png
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode r1=reverseList(l1);
ListNode r2=reverseList(l2);
ListNode rr=addTwo(r1,r2);
return reverseList(rr);
}
public ListNode addTwo(ListNode l1, ListNode l2){
ListNode dummy=new ListNode();
ListNode cur=dummy;
int carry=0;
while(l1!=null || l2!= null || carry!=0){
if(l1!=null){
carry+=l1.val;
}
if(l2!=null){
carry+=l2.val;
}
cur.next=new ListNode(carry%10);
carry/=10;
cur=cur.next;
if(l1!=null){
l1=l1.next;
}
if(l2!=null){
l2=l2.next;
}
}
return dummy.next;
}
public ListNode reverseList(ListNode head){
ListNode pre=null, cur=head;
while(cur!=null){
ListNode nxt=cur.next;
cur.next=pre;
pre=cur;
cur=nxt;
}
return pre;
}
链表
删除倒数N个节点
图示：算法题知识点总结-删除倒数第n个节点.png
- 倒数第n个节点，我们可以优化成，先让一个节点right走n步
- 然后再让一个节点left从起点陪同一起出发
- 当尾节点到最后一个节点时，left就是倒数第n个节点
- 因为他们之间的n距离就是步长，而步长就是倒数第n个节点
public ListNode deleteDuplicates(ListNode head) {
if(head==null){
return head;
}
ListNode cur=head;
while(cur.next!=null){
if(cur.next.val==cur.val){
cur.next=cur.next.next;
}else{
cur=cur.next;
}
}
return head;
}
删除出现过重复的链表
图示：算法题知识点总结-删除重复元素.png
- 由于要删掉出现过重复的，即头节点可能被删
- 被删就要考虑dummy的节点
- 通过cur指针，判断next和next.next是否一致，如果一致删除，并继续
- 如果不相等了，则跳过
public ListNode deleteDuplicates(ListNode head) {
ListNode dummy=new ListNode(0,head),cur=dummy;
while(cur.next != null && cur.next.next != null){
int val=cur.next.val;
if(val==cur.next.next.val){
while(cur.next!=null && val==cur.next.val ){
cur.next=cur.next.next;
}
}else{
cur=cur.next;
}
}
return dummy.next;
}
回溯
电话号码的字母组合
图示：算法题知识点总结-回溯电话号码.png
- 回溯是一种增量构造答案的过程，往往我们会用递归来实现
- 递归我们只需要关注边界条件和非边界条件，然后相信数学归纳即可
- 回溯三问
- 当前操作？
- 子问题？
- 下一个子问题？
- dfs（i）+dfs（i+1）
private static final String[] MAPPING = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
private List<String> ans=new ArrayList();
private char[]digits,path;
public List<String> letterCombinations(String digits) {
int n=digits.length();
if(n==0)return List.of();
this.digits=digits.toCharArray();
path=new char[n];
dfs(0);
return ans;
}
public void dfs(int i){
// exit
// if dfs to end
if(i==digits.length){
ans.add(new String(path));
return;
}
// iterate all digits then dfs next
for(char c:MAPPING[digits[i]-'0'].toCharArray() ){
path[i]=c;
dfs(i+1);
}
}
子集型回溯
图示：算法题知识点总结-子集型回溯问题.png
- 回溯三问
- 当前操作？
- 枚举第i个节点选、不选？
- 子问题？
- 从下标>=i的数字构造子集
- 下一个子问题？
- 从下表>=i+1的数字构造子集
- 当前操作？
- dfs(i) + dfs(i+1)
- 从选or不选考虑
- 如果不选，则当前数字跳过
- 如果选，则当前数字要加到路径中，再跳过当前数字
private final List<List<Integer>> ans = new ArrayList<>();
private int[] nums;
public List<List<Integer>> subsets(int[] nums) {
this.nums=nums;
dfs(0,new ArrayList());
return ans;
}
public void dfs(int i , List<Integer> path){
List<Integer> temp=new ArrayList(path);
if(i==nums.length){
ans.add(new ArrayList<>(temp));
return;
}
// mock no need
dfs(i+1,temp);
// mock need
temp.add(nums[i]);
dfs(i+1,temp);
}
public void dfs(int i ){
// add every result to ans
ans.add(new ArrayList(path));
if(i==nums.length)return;
// must choose every number
// then use j>=i
// add nums[j]
// next sub question will be j+1
for(int j=i;j<nums.length;++j){
path.add(nums[j]);
dfs[j+1];
path.remove(path.size()-1);
}
}
组合问题
图示：算法题知识点总结-组合类问题图.png
List<List<Integer>> ans=new ArrayList();
List<Integer> path=new ArrayList();
private int k;
public List<List<Integer>> combine(int n, int k) {
this.k=k;
dfs(n);
return ans;
}
public void dfs(int i){
// 剪枝，比如一共需要2个数字k，那么就是用需要数字-当前路径=还需要选的数字
// 如果当前要选择的数字i<要选的数字，那就不需要再选了
int d=k-path.size();
// if(i<d){
// return;
// }
// exit 条件，没有要选的，则退出
if(d==0){
ans.add(new ArrayList(path));
return;
}
// 上面的语句也可以拆到下面来
for(int j=i;j>=d;j--){
path.add(j);
dfs(j-1);
path.remove(path.size()-1);
}
}
// 选不选的思路
public void dfs(int i){
int d=k-path.size();
// 剪枝
if(i<d){
return ;
}
// exit
if(d==0){
ans.add(new ArrayList(path));
return;
}
// 先写主体，使用选or不选
dfs(i-1);
// 选
path.add(i);
dfs(i-1);
path.remove(path.size()-1);
}
组合Ⅱ问题
图示：算法题知识点总结-组合问题.png
List<List<Integer>> ans=new ArrayList();
List<Integer> path=new ArrayList();
int k,n;
public List<List<Integer>> combinationSum3(int k, int n) {
this.k=k;
this.n=n;
dfs(9, n);
return ans;
}
public void dfs(int i, int temp){
int d=k-path.size();
// 剪枝
if(i<d){
return;
}
// exit
if(d==0){
if(temp==0){
ans.add(new ArrayList(path));
}
return;
}
// 主体
// 枚举要选的数字
for(int j=i;j>=0;j--){
path.add(j);
dfs(j-1,temp-j);
path.remove(path.size()-1);
}
}
生成括号组合
图示：算法题知识点总结-括号生产.png
class Solution {
List<String> ans=new ArrayList();
char[] path;
int n;
public List<String> generateParenthesis(int n) {
this.n=n;
this.path=new char[n*2];
dfs(0,0);
return ans;
}
public void dfs(int i, int open){
if(i==n*2){
ans.add(new String(path));
return;
}
// 主体
// 选左还是选右
// 同时要记录左括号的字符个数n
// 右括号的个数就为i-n
if(open<n){
path[i]='(';
dfs(i+1,n+1);
}
if(i-open<open){
path[i]=')';
dfs(i+1,open);
}
}
}
组合总和
图示：算法题知识点总结-组合总和问题.png
class Solution {
List<List<Integer>> ans=new ArrayList();
List<Integer> path=new ArrayList();
int [] candidates;
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
this.candidates=candidates;
dfs(0, target);
return ans;
}
public void dfs(int i, int target){
//exit
if(target==0){
ans.add(new ArrayList(path));
return;
}
// cutoff
if(i>=candidates.length|| candidates[i]>target){
return;
}
// for
for(int j=i;j<candidates.length;j++){
path.add(candidates[j]);
// 不需要推进下一个问题，只需要在当前数字，如果处理完了，则回退，通过迭代推进
dfs(j, target-candidates[j]);
path.remove(path.size()-1);
}
}
}
全排列
图示：算法题知识点总结-全排列.png
class Solution {
List<List<Integer>> ans=new ArrayList();
List<Integer> path;
boolean[] onPath;
int[] nums;
public List<List<Integer>> permute(int[] nums) {
this.nums=nums;
path= new ArrayList();
onPath=new boolean[nums.length];
dfs(0);
return ans;
}
private void dfs(int i){
// exit;
if(i==nums.length){
ans.add(new ArrayList(path));
return;
}
// 挑选数字
for(int j=0;j<nums.length;j++){
if(!onPath[j]){
path.add(nums[j]);
onPath[j]=true;
dfs(i+1);
path.remove(path.size()-1);
onPath[j]=false;
}
}
}
}
n皇后问题
图示：算法题知识点总结-N皇后问题.png
class Solution {
private int n;
private int[] col;
private boolean[] onPath, diag1, dig2;
private List<List<String>> ans = new ArrayList();
public List<List<String>> solveNQueens(int n) {
this.n=n;
col=new int[n];
onPath=new boolean[n];
diag1=new boolean[n*2-1];
dig2=new boolean[n*2-1];
dfs(0);
return ans;
}
private void dfs(int r){
if(r==n){
List<String> board=new ArrayList(n);
for(int c: col){
char[] row=new char[n];
Arrays.fill(row,'.');
row[c]='Q';
board.add(new String(row));
}
ans.add(board);
return;
}
for(int c=0;c<n;c++){
// r -c 代表是行下标与列下标的差值，由于n皇后一定是斜线的，所以rc值一定相等
// 加上n-1的原因是因为，如果放在右上角位置，此时的值就为n-1，我们给它加回来，就不是负数了
int rc= r - c + n - 1;
// 维护几个数组
// 当前列是否设置过
// diag1 表示r+c的值
// dig2 表示r-c的值
// 只要都没设置过，则我们给它放进去
if(!onPath[c] && !diag1[r+c] && !dig2[rc]){
col[r]=c;
onPath[c] = diag1[r+c]=dig2[rc]=true;
dfs(r+1);
onPath[c] = diag1[r+c] = dig2[rc] =false;
}
}
}
}
动态规划
打家劫舍
图示：算法题知识点总结-打家劫舍.png
class Solution {
private int[] nums, memo;
public int rob(int[] nums) {
this.nums=nums;
int n=nums.length;
memo=new int[n];
Arrays.fill(memo,-1);
return dfs(n-1);
}
private int dfs(int i){
if(i<0){
return 0;
}
if(memo[i]!=-1){
return memo[i];
}
// DP
// 1. 回溯要怎么写
// 1.1 入参和返回值
// 1.2 递归到哪里
// 1.3 递归边界和入口
// 2. 记忆化搜索
// 3. 1：1翻译成递推
// main opeartion‘
// 回溯三问
// 1. 当前i的房子选不选
// 2. 子问题==》从前i个房子里面得到的最大金额
// 3. 下一个子问题==》从前i-1个得到的值 or 从前i-2个得到的值
// 因为不允许相邻，所以dfs(i-2)时是加上当前的nums[i]
int res=Math.max(dfs(i-1), dfs(i-2) + nums[i]);
memo[i]=res;
return res;
}
}
// 1：1递推
class Solution {
public int rob(int[] nums) {
int n=nums.length;
// int[] f=new int[n+2];
// for(int i=0;i<n;i++){
// f[i+2]=Math.max(f[i+1], f[i]+nums[i]);
// }
// return f[n+1];
// 如何把数组优化掉
int f0 =0, f1 = 0;
int result=0;
for(int i=0;i<n;i++){
result=Math.max(f1, f0+nums[i]);
f0=f1;
f1=result;
}
return result;
}
}
爬楼梯
AA
class Solution {
int n;
int[] memo;
public int climbStairs(int n) {
this.n = n;
memo = new int[n + 1];
Arrays.fill(memo, -1);
return dfs(n);
}
public int dfs(int i) {
if (i <= 1) {
return 1;
}
if (memo[i] != -1) {
return memo[i];
}
// 从0爬到i
// dfs(i) 代表从0到i有多少种方法
// 如果最后一步爬了1个台阶，要先爬到i-1，则问题变成从0爬到i-1有多少种
// 如果最后一步爬了2个台阶，要先爬到i-2，则问题变成从0爬到i-2有多少种
// 由于两个子问题互相独立，我们可以根据加法原理算到一起
int result = dfs(i - 1) + dfs(i - 2);
memo[i] = result;
return result;
}
}
class Solution {
public int climbStairs(int n) {
int[] f=new int[n+2];
f[0]=f[1]=1;
// 因为f0 f1 也是我们的答案，所以这里是要算进去的
for(int i=2;i<=n;i++){
f[i]=f[i-1]+f[i-2];
}
return f[n];
}
public int climbStairs(int n) {
int[] f=new int[n+2];
f[0]=f[1]=1;
// 因为f0 f1 也是我们的答案，所以这里是要算进去的
int f0= 1, f1=1;
for(int i=2;i<=n;i++){
int temp=f0+f1;
f0=f1;
f1=temp;
}
return f1;
}
}
0-1背包
AA
. - 力扣（LeetCode）
有n个物品，第i个物品体积为w[i], 价值为v[i]，每个物品至多选一个，求体积和不超过capacity的最大价值和
- 回溯三问
- 当前操作：枚举第i个物品选还是不选
- 选了，则capacity-w[i]
- 不选，没变化
- 子问题
- 在剩余容量为c时，从前i个物品得到的最大价值和
- 下一个子问题：
- 不选：
- 在生剩余容量为c时，从前i-1个得到的最大价值和选
- 选
- 在剩余c-w【i】，从前i-1 个物品得到最大价值和
- 不选：
- 当前操作：枚举第i个物品选还是不选
class Solution {
private int[] nums;
private int[][] cache;
public int findTargetSumWays(int[] nums, int target) {
// 假设正数的和为p
// 那么负数的和为 所有元素的数和s - p
// 我们希望正数的和-负数的绝对值和 p - (s-p) = target
// 2p - s = target
// p = (s+target)/2;
// 这样子我们就变成从nums的数组中，我们要挑选p个正数出来
for(int x:nums) target+=x;
// 如果数组为负数，且最后是奇数，那么一定不会有结果
if(target<0 || target%2==1)return 0;
target/=2;
this.nums=nums;
int n=nums.length;
// 我们要挑选p个正数，让它等于target
// n-1，是为了要获取数组里面的值
return dfs(n-1, target);
}
private int dfs(int i, int target){
// 如果遍历完了，且target刚好等于0，那么就是正数，不然就不选
if(i<0) return target==0?1:0;
// 如果当前元素大于target，跳过不选
if(target<nums[i])return dfs(i-1, target);
// 从0到i，就代表了有多少种方法可以恰好等于target
// 子问题思考
// 如果最后一步我们选得是正数，则target-=i
// 如果是负数，不处理
// 由于这两个方案是独立的，我们可以按加法原理相加
return dfs(i-1, target)+ dfs(i-1, target-nums[i]);
}
}
class Solution {
public int findTargetSumWays(int[] nums, int target) {
// p
// s-p
// p - (s-p) =t
// p=(t+s)/2
// 要选n个p数字处理
for(int x:nums){
target+=x;
}
if(target<0 || target%2==1)return 0;
target/=2;
int n=nums.length;
int[][] f= new int[n+1][target+1];
// 当i=0时，且target=0了，那么就是要选正数
f[0][0] = 1;
for(int i=0;i<n;i++){
for(int c=0;c<=target;c++){
// 如果当前数字比target小，跳过不选
if(c<nums[i]) f[i+1][c]=f[i][c];
else f[i+1][c] = f[i][c] + f[i][c-nums[i]];
}
}
return f[n][target];
}
}
单词划分
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> wordDictSet=new HashSet(wordDict);
boolean[] dp=new boolean[s.length()+1];
dp[0]=true;
// 动归思想，把所有的标题都试一遍
// 每次都测试i，j间的字符串是否满足
// dp数组表示的是切分开来的每一个小数组
// 对于dp0 来说，就代表0，1字符是否在dict中
// 比如leetcode的词组
// 当i=3，j=0的时候，匹配上了，dp[i]=true，那么接下来只要看dp[i+1]开始的小数组能不能满足
// 当j=3, i=7的时候，匹配上了，dp[j]之前就是true的，继续设置dp[i]=true，那么此时dp[结尾数组]已经满足了
for(int i=1;i<=s.length();i++){
for(int j=0;j<i;j++){
if(dp[j] && wordDictSet.contains(s.substring(j,i))){
dp[i]=true;
break;
}
}
}
return dp[s.length()];
}
}
零钱兑换
class Solution {
int[] coins;
int[][]memo;
public int coinChange(int[] coins, int amount) {
int n=coins.length;
this.coins=coins;
memo=new int[n][amount+1];
for(int[] row:memo){
Arrays.fill(row,-1);
}
int ans=dfs(n-1,amount);
return ans<Integer.MAX_VALUE/2?ans:-1;
}
public int dfs(int i,int c){
// 作为一个剪枝内容进行透出
if(i<0){
return c==0?0:Integer.MAX_VALUE/2;
}
// 记忆数组
if(memo[i][c]!=-1)return memo[i][c];
// 剪枝
if(c< coins[i])return memo[i][c]=dfs(i-1,c);
// 第i个硬币选还是不选
// 子问题是 选or不选最小组合是什么
// 如果不选，那就跳到下一个硬币进行组合
// 如果选，那么就将target减去硬币组合，并且组合数+1
// 初始化memo数组，二元是为了作为完全背包的完全记忆模式，比如选了XX硬币时，当前target的组合是多少
int result= Math.min(dfs(i-1,c),dfs(i,c-coins[i])+1);
memo[i][c]=result;
return result;
}
}
字符串类
两个超大的小数的相加
public static String sumTwoLongNumber(String num1, String num2) {
int len1 = num1.length() - 1;
int len2 = num2.length() - 1;
int add = 0;
StringBuilder ans = new StringBuilder();
while (len1 >= 0 || len2 >= 0 || add != 0) {
int i = len1 >= 0 ? num1.charAt(len1) - '0' : 0;
int j = len2 >= 0 ? num2.charAt(len2) - '0' : 0;
int sum = i + j + add;
ans.append(sum % 10);
add = sum / 10;
len1--;
len2--;
}
return ans.reverse().toString();
}
public static void main(String[] args) {
String a = "1233.512142";
String b = "123.124124124";
String mainSum = sumTwoLongNumber(a.split("\\.")[0], b.split("\\.")[0]);
String subString1 = a.split("\\.")[1];
String subString2 = b.split("\\.")[1];
int maxLen = Math.max(subString1.length(), subString2.length());
subString1 = padRightZeros(subString1,maxLen);
subString2 = padRightZeros(subString2,maxLen);
String subSum = sumTwoLongNumber(subString1, subString2);
if (subSum.length() > a.length() && subSum.length() > b.length()) {
mainSum = sumTwoLongNumber(mainSum, "1");
subSum = subSum.substring(1);
}
System.out.println(mainSum + "." + subSum);
}
public static String padRightZeros(String str, int length) {
if (str.length() >= length) {
return str;
}
return str + "0".repeat(length - str.length());
}
判断字符串有没有重复的字母
面试题 01.01. 判定字符是否唯一 - 力扣（LeetCode）
class Solution {
public boolean isUnique(String astr) {
if(astr==null || astr.equals("")){
return true;
}
for(int i=0;i<astr.length()-1;i++){
for(int j=i+1;j<astr.length();j++){
if((astr.charAt(i)) != (astr.charAt(j))){
continue;
}else{
return false;
}
}
}
return true;
}
}
正确写法
class Solution {
public boolean isUnique(String astr) {
if(astr==null || astr.equals("")){
return true;
}
int result=0;
for(int i=0;i<astr.length();i++){
int move=astr.charAt(i)-'a';
int temp=1<<move;
if((result & temp)!=0){
return false;
}else{
result = result | (1<<move);
}
}
return true;
}
}
找字符串里面最大嵌套的括号深度
1614. 括号的最大嵌套深度 - 力扣（LeetCode）
class Solution:
def maxDepth(self, s: str) -> int:
ans, size=0,0
for ch in s:
if ch =='(':
size=size+1
ans=max(size,ans)
if ch ==')':
size=size-1
return ans
class Solution {
public int maxDepth(String s) {
int result=0;
int countLeft=0;
for(int i=0; i<s.length();i++){
char c=s.charAt(i);
if(c=='('){
countLeft++;
result = Math.max(result, countLeft);
}
if(c==')'){
countLeft--;
}
continue;
}
return result;
}
}
贪心
跳跃算法
class Solution {
public int jump(int[] nums) {
// i 需要几次
int jumps=0, curEnd=0, farthest=0;
// 最后一位不需要处理，肯定在前面就能跳到位置了
for(int i=0;i<nums.length-1;i++){
farthest=Math.max(farthest, i+nums[i]);
if(i==curEnd){
// 必须跳
jumps+=1;
curEnd = farthest;
}
}
return jumps;
}
}
排序
计数排序
class Solution {
public int hIndex(int[] citations) {
int n = citations.length;
int[] counter = new int[n+1];
for(int c: citations){
if(c>=n){
counter[n]++;
}else{
counter[c]++;
}
}
int total=0;
// 核心原理是，我先统计引用次数分别有多少个，其中大于数组n的都记为n
for(int i=n;i>=0;i--){
total += counter[i];
// 然后倒过来统计，比如都大于等于n，就相当于五篇论文都被统计了5次以上，则为5
// 假如不满足，则再往下看4有多少个，加上刚刚5的够不够现在的合计四篇
if(total>=i){
return i;
}
}
return 0;
}
}
算法题常用工具类和方法
AA
- Queue
- ArrayDeque
- Collections.reverse
- Integer.MAX_VALUE
相关文档和插件
- 代码可视化：Online Java Compiler, Visual Debugger, and AI Tutor - Learn Java programming by visualizing code
- b站算法up主：看到递归就晕？带你理解递归的本质！_哔哩哔哩_bilibili
- 二叉树遍历：http://www.hangdaowangluo.com/archives/2979
- 算法题目单：leetcode.cn/circle/discuss/SqopEo/
