基础算法模板

1. 相向双指针

class Solution {  // 两数之和public int[] twoSum(int[] numbers, int target) {int left = 0; // 第一步初始化开头和结尾两个指针int right = numbers.length - 1;while (true) { // 之后一直while循环  int s = numbers[left] + numbers[right]; //计算左右两个指针对应的和 比较当前值和目标值的范围if (s == target) {return new int[]{left + 1, right + 1}; // 题目要求下标从 1 开始}if (s > target) { right--;} else {left++;}}}
}

前提:需要数组是有序

步骤:

  1. 第一步初始化左右两个节点
  2. 第二步while一直循环 while(true)
  3. while内计算左右两个值的和
  4. 三种情况 比较当前值 和 目标值的关系
// 三数之和
1、取出其中一个数值,然后取反,让另外两个数的和 和 这个数相加等于0 然后使用两数只和
2、题目的顺序没有关系 所以对于要确定一个顺序
盛水最多的容器:
同样是左边一个指针,右边一个指针,之后依次移动当前左右两边的最小值
结束条件: while(left > right)
接雨水
当前这个位置能接多少水,取决于当前这个位置左边的最大高度和右边的最大高度
所以从左往右计算当前这个位置的最大值,计算一个数组从右往左计算当前这个位置的最大值,计算一个数组依次计算当前这个位置能有多少水,分别是当前这个位置左边的最大值 - 右边的最大值 然后取绝对值

在这里插入图片描述

滑动窗口

class Solution {public int minSubArrayLen(int target, int[] nums) {int n = nums.length;int ans = n + 1;int sum = 0; // 子数组元素和int left = 0; // 子数组左端点for (int right = 0; right < n; right++) { // 枚举子数组右端点sum += nums[right];while (sum >= target) { // 满足要求ans = Math.min(ans, right - left + 1);sum -= nums[left++]; // 左端点右移}}return ans <= n ? ans : 0;}
}

步骤:

  1. 初始化一个左端点(从左边开始)
  2. 初始化当前所有结果的值
  3. 一个for循环 用户遍历右端点
  4. for循环内,首先将当前的值加上,判断现在是否符合条件,依次将左端点向右边延伸

总结:
右端点增加资源 左端点减少资源 左减右增
判断当前是否符合情况(都是用while 如果是大小关系,使用while进行判断是否大于小于
也可以用while判断是否存在)

##二分查找

    // 闭区间写法private int lowerBound(int[] nums, int target) {int left = 0, right = nums.length - 1; // 闭区间 [left, right]while (left <= right) { // 区间不为空// 循环不变量:// nums[left-1] < target// nums[right+1] >= targetint mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid + 1; // 范围缩小到 [mid+1, right]} else {right = mid - 1; // 范围缩小到 [left, mid-1]}}return left;}

步骤:

  1. 初始化左右两个端点,其中左端点指向0,右端点指向最后一个值
  2. 使用while(left <= right)判断是否循环结束
  3. 计算mid的位置,计算的时候使用left + (right - left)/ 2进行计算
  4. 判断nums[mid] 和 target的大小关系 (这里只需要两个判断就可以)
  5. 当while结束的时候返回left的位置 就是目标的位置

其他:
如果当前值有多个,可以首先计算比当前值小于1的位置,比如target是7,那么就计算目标值是6的位置,得出的位置 + 1就是目标位置

如果所有的值都 < target,那么left会一直向后面进行移动
同样,如果所有的值都 > target,right会一直向前面进行移动,最终left会等于right

反转链表


class Solution {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;}
}

步骤:

  1. pre = null cur = head
  2. 使用while(cur != null)
  3. 依次变换nxt cur.next pre cur
  4. return pre

内容:最后 pre当前的值,也可以说是最后的一个值 cur指向的是最后一个值的下一个值

快慢指针

class Solution {public ListNode middleNode(ListNode head) {ListNode slow = head, fast = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}return slow;}
}

步骤:

  1. 初始化slow和fast指针
  2. 使用while判断fast指针是否到达了null 具体是 fast != null && fast.next != null

计算二叉树的深度 最大深度或者最小深度

方法1:自顶向下
依次递归遍历当前是否到达叶子节点,如果没有的话,就 + 1,如果有的话 就更新答案
优化:如果查找到当前节点的深度已经是大于或者小于一个节点的值,那么就可以跳过之后的步骤了

方法2:自底向上
如果当前没有左子树,那么当前的深度为右子树 + 1
如果当前没有右子树,那么当前的深度为左子树 + 1
如果当前有左子树和右子树,那么当前的深度是 min(左子树,右子树)+ 1

判断是叶子节点使用: node.left == node.right

二叉树的前序遍历 中序遍历 后序遍历

前序遍历

class Solution {public boolean isValidBST(TreeNode root) {return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);}private boolean isValidBST(TreeNode node, long left, long right) {if (node == null) {return true;}long x = node.val;return left < x && x < right &&isValidBST(node.left, left, x) &&isValidBST(node.right, x, right);}
}

思路:如果当前节点是空节点,就返回true,说明是二叉搜索胡
接着就以根 左 右进行遍历
return的时候直接判断 当前节点 和 左节点 右节点之间的关系

中序遍历

class Solution {private long pre = Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {if (root == null) {return true;}if (!isValidBST(root.left) || root.val <= pre) {return false;}pre = root.val;return isValidBST(root.right);}
}

中序遍历需要知道的就是得到的是一个 递增序列
步骤:

  1. 初始化 pre节点,并且设置成为最大值
  2. 判断当前node是否是null,如果是的话 返回 true
  3. 判断左节点是否是二叉搜索树 并且判断当前节点的值是否发是 node.val <= pre (正常来说当前节点是需要大于pre节点的,这是因为得到的是一个递增的序列,如果当前的值暂时还没有原来的值大,说明现在并不是一个二叉搜索树)
  4. 更新pre的值为当前这个node的值
  5. 最后判断右子树是否是一个二叉搜索树

后序遍历

class Solution {public boolean isValidBST(TreeNode root) {return dfs(root)[1] != Long.MAX_VALUE;}private long[] dfs(TreeNode node) {if (node == null) {return new long[]{Long.MAX_VALUE, Long.MIN_VALUE};}long[] left = dfs(node.left);long[] right = dfs(node.right);long x = node.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)};}
}

思路:使用一个返回的数组进行判断,正常的形式是 {min,max}
步骤:

  1. 首先如果当前节点是null,返回 (max,min)
  2. 计算左右子树的数组,得到当前的值x
  3. 判断如果x <= left[1] (也就是左子树的最大值) 或者 x >= right[0] (也就是右子树的最小值),直接返回 一个类似于 false的结果
  4. 返回 当前值和 左子树最小值的最小值 右子树最大值和当前值的最大值

层序遍历

class Solution {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()) {int n = q.size();List<Integer> vals = new ArrayList<>(n); // 预分配空间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;}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/365785.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Flutter循序渐进==>数据结构(列表、映射和集合)和错误处理

导言 填鸭似的教育确实不行&#xff0c;我高中时学过集合&#xff0c;不知道有什么用&#xff0c;毫无兴趣&#xff0c;等到我学了一门编程语言后&#xff0c;才发现集合真的很有用&#xff1b;可以去重&#xff0c;可以看你有我没有的&#xff0c;可以看我有你没有的&#xf…

mybatis实现多表查询

mybatis高级查询【掌握】 1、准备工作 【1】包结构 创建java项目&#xff0c;导入jar包和log4j日志配置文件以及连接数据库的配置文件&#xff1b; 【2】导入SQL脚本 运行资料中的sql脚本&#xff1a;mybatis.sql 【3】创建实体来包&#xff0c;导入资料中的pojo 【4】User…

Swift宏的实现

上篇介绍了Swift宏的定义与生声明&#xff0c;本篇主要看看是Swift宏的具体实现。结合Swift中Codable协议&#xff0c;封装一个工具让类或者结构体自动实现Codable协议&#xff0c;并且添加一些协议中没有的功能。 关于Codable协议 Codable很好&#xff0c;但是有一些缺陷&…

141个图表,完美展示数据分类别关系!

本文介绍使用Python工具seaborn详细实现分类关系图表&#xff0c;包含8类图141个代码模版。 分类关系图表用于展示数字变量和一个或多个分类变量之间的关系&#xff0c;可以进一步分为&#xff1a;箱形图&#xff08;box plot&#xff09;、增强箱形图&#xff08;enhanced bo…

DP:子数组问题

文章目录 引言子数组问题介绍动态规划的基本概念具体问题的解决方法动态规划解法&#xff1a;关于子数组问题的几个题1.最大子数组和2.环形子数组的最大和3.乘积最大子数组4.乘积为正数的最长子数组长度5.等差数列划分 总结 引言 介绍动态规划&#xff08;DP&#xff09;在解决…

Deep-LIBRA:一种用于可靠量化乳腺密度的人工智能方法,并在乳腺癌风险评估中进行了独立验证| 文献速递-深度学习自动化疾病检查

Title 题目 Deep-LIBRA: An artificial-intelligence method for robust quantification of breast density with independent validation in breast cancer risk assessment Deep-LIBRA&#xff1a;一种用于可靠量化乳腺密度的人工智能方法&#xff0c;并在乳腺癌风险评估中…

【内网渗透】从0到1的内网渗透基础概念笔记

目录 域 域的介绍 单域 父域和子域 域树 域森林 域名服务器 活动目录 活动目录介绍 域内权限 组 域本地组 全局组 通用组 总结 示例 A-G-DL-P策略 重要的域本地组 重要的全局组、通用组 安全域划分 域 域的介绍 Windows域是计算机网络的一种形式&#xf…

【机器学习】FFmpeg+Whisper:二阶段法视频理解(video-to-text)大模型实战

目录 一、引言 二、FFmpeg工具介绍 2.1 什么是FFmpeg 2.2 FFmpeg核心原理 2.3 FFmpeg使用示例 三、FFmpegWhisper二阶段法视频理解实战 3.1 FFmpeg安装 3.2 Whisper模型下载 3.3 FFmpeg抽取视频的音频 3.3.1 方案一&#xff1a;命令行方式使用ffmpeg 3.3.2 方案二&a…

[论文精读]Variational Graph Auto-Encoders

论文网址&#xff1a;[1611.07308] Variational Graph Auto-Encoders (arxiv.org) 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎…

Android 界面库 (二) 之 Data binding 详细介绍

1. 简介 回顾我们在前面文章《Android 界面库 (一) 之 View binding 简单使用》中学习的 View Binding&#xff0c;它旨在简化 View 与代码之间的绑定过程。它会在编译时期为每个 XML 布局文件生成相应的绑定类(Binding class)&#xff0c;该类里包含了布局文件每个有 ID 的 Vi…

基于SpringBoot扶农助农政策管理系统设计和实现(源码+LW+调试文档+讲解等)

&#x1f497;博主介绍&#xff1a;✌全网粉丝10W,CSDN作者、博客专家、全栈领域优质创作者&#xff0c;博客之星、平台优质作者、专注于Java、小程序技术领域和毕业项目实战✌&#x1f497; &#x1f31f;文末获取源码数据库&#x1f31f; 感兴趣的可以先收藏起来&#xff0c;…

利用 Docker 简化 Nacos 部署:快速搭建 Nacos 服务

利用 Docker 简化 Nacos 部署&#xff1a;快速搭建 Nacos 服务 引言 在微服务架构中&#xff0c;服务注册与发现是确保服务间通信顺畅的关键组件。Nacos&#xff08;Dynamic Naming and Configuration Service&#xff09;作为阿里巴巴开源的一个服务发现和配置管理平台&…

【单片机毕业设计选题24039】-基于单片机的太阳能储能智能恒温外卖柜设计

系统功能: 以单片机为控制核心&#xff0c;综合运用传感器、物联网、太阳能等技术&#xff0c;设计一种基于单片机为控制核心的智能恒温外卖柜。它由恒温系统、无线模块、智能提醒系统、供电系统等组成&#xff0c;通过太阳能电池板独立供电&#xff0c;利用太阳能储能元件驱动…

Linux网络编程:套接字编程

1.Socket套接字编程 1.1.什么是socket套接字编程 Socket套接字编程 是一种基于网络层和传输层网络通信方式&#xff0c;它允许不同主机上的应用程序之间进行双向的数据通信。Socket是网络通信的基本构件&#xff0c;它提供了不同主机间的进程间通信端点的抽象。一个Socket就是…

免费开源的后端API服务-supabase安装和使用-简直是前端学习者福音

文章目录 它是什么安装和部署关于安装关于部署1、注册用户2、创建组织3、创建项目 创建数据库表&#xff08;填充内容&#xff09;填充数据库表 使用postman联调API 它是什么 一个开源免费的后端框架&#xff0c;firebase的替代品。可以简单理解类似于headless cms&#xff0c…

浅谈定时器之泊松随机定时器

浅谈定时器之泊松随机定时器 “泊松随机定时器”(Poisson Random Timer)&#xff0c;它允许你基于泊松分布来随机化请求之间的延迟时间&#xff0c;这对于模拟具有随机到达率的事件特别有用&#xff0c;如用户访问网站或服务的请求。 泊松分布简介 泊松分布是一种统计与概率…

HarmonyOS开发探索:父子组件手势绑定问题处理

场景一&#xff1a;父子组件同时绑定手势的冲突处理 效果图 方案 在默认情况下&#xff0c;手势事件为非冒泡事件&#xff0c;当父子组件绑定相同的手势时&#xff0c;父子组件绑定的手势事件会发生竞争&#xff0c;最多只有一个组件的手势事件能够获得响应&#xff0c;默认子…

有哪些方法可以恢复ios15不小心删除的照片?

ios15怎么恢复删除的照片&#xff1f;在手机相册里意外删除了重要的照片&#xff1f;别担心&#xff01;本文将为你介绍如何在iOS 15系统中恢复已删除的照片。无需专业知识&#xff0c;只需要按照以下步骤操作&#xff0c;你就能轻松找回宝贵的回忆。 一、从iCloud云端恢复删除…

Transformer动画讲解 - 工作原理

Transformer模型在多模态数据处理中扮演着重要角色,其能够高效、准确地处理包含不同类型(如图像、文本、音频、视频等)的多模态数据。 Transformer工作原理四部曲:Embedding(向量化)、Attention(注意力机制)、MLPs(多层感知机)和Unembedding(模型输出)。 阶段一:…

网上下载的PDF文件为何不能复制文字?该怎么办呢?

不知道大家有没有到过这种情况&#xff1f;在网上下载的PDF文件打开之后&#xff0c;发现选中文字之后无法复制。甚至其他功能也都无法使用&#xff0c;这是怎么回事&#xff1f;该怎么办&#xff1f; 首先&#xff0c;有可能PDF文件是扫描文件&#xff0c;是扫描文件的话&…