算法
2022-04-14 07:42:21 77 举报AI智能生成
登录查看完整内容
算法是一系列解决问题或执行任务的清晰指令。它以逻辑和数学规则为基础，用于处理数据、执行计算和自动化决策。算法可以应用于各种领域，如计算机科学、工程学、金融等。它们通常具有输入、输出和有限步骤的特点，能够提供准确且一致的结果。算法的效率和正确性对于解决复杂问题至关重要。通过优化算法，可以提高计算速度和准确性，从而节省时间和资源。算法的设计和分析是计算机科学的核心内容之一，也是现代科技发展的关键驱动力之一。
作者其他创作
大纲/内容
算法
动态规划
打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额
括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合
过滤条件：如果左括号数量不大于 n，我们可以放一个左括号。如果右括号数量小于左括号的数量，我们可以放一个右括号
每一个括号序列可以用 (a)b 来表示，递归调用 generate(i) 即可计算 a 的所有可能性；递归调用 generate(n - i - 1) 即可计算 b 的所有可能性
爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢
状态方程：f(x)=f(x−1)+f(x−2)
最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和
三角形最小路径和
给定一个三角形 triangle ，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1
最长公共子序列
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0
凑硬币
回溯
电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回
套用回溯模板
类型
组合
排列
子集
分割
棋盘问题
双指针法
三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组
排序+三指针，一个指针当做目标值，左指针和右指针向中心逼近
盛最多水的容器
利用双指针，分别从左边界和右边界向中心移动
移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序
利用双指针，右指针移动，遇到非0的数据，左右指针数据交换，左指针移动一步
移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度
跟移动零是一个逻辑
数据结构
数组
旋转数组
将数组中的后k位，移到数组的开头
利用首尾交换实现，先全部翻转，然后分别翻转0到k-1和k到数组末尾
二分查找
滑动窗口
长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0
链表
相交链表
编写一个程序，找到两个单链表相交的起始节点
利用双指针，当 pA 到达链表的尾部时，将它重定位到链表 B 的头结点 (你没看错，就是链表 B); 类似的，当 pB到达链表的尾部时，将它重定位到链表 A 的头结点
环形链表
给定一个链表，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况
利用hash表判重，还可以使用快慢指针
反转链表
首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null
两两交换链表中的节点
虚拟头节点
删除链表的倒数第N个节点
快慢指针+虚拟头节点
哈希表
有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词
排序、hash表
栈
有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效
利用栈
队列
二叉树
深度优先
前中后序遍历，基于栈实现迭代访问
广度优先
基于队列实现
对称二叉树
给定一个二叉树，检查它是否是镜像对称的
翻转二叉树
最大、最小树深度
定义
满二叉树
如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树
完全二叉树
在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置
平衡二叉树
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1
并查集
主要用于解决一些元素分组的问题。它管理一系列不相交的集合
合并（Union）：把两个不相交的集合合并为一个集合。
查询（Find）：查询两个元素是否在同一个集合中
trier树
贪心
跳跃游戏
给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标
确定最大覆盖范围
加油站
在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1
分发糖果
老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。你需要按照以下要求，帮助老师给这些孩子分发糖果：每个孩子至少分配到 1 个糖果。相邻的孩子中，评分高的孩子必须获得更多的糖果
一次是从左到右遍历，只比较右边孩子评分比左边大的情况。一次是从右到左遍历，只比较左边孩子评分比右边大的情况
多个维度时，可以先按一个维度贪心计算，再在前者基础上进行另一个维度的贪心计算
用最少数量的箭引爆气球
先按气球起始位置排序，如果气球重叠了，重叠气球中右边边界的最小值 之前的区间一定需要一个弓箭
抢红包
二倍均值法
剩余红包金额为M，剩余人数为N
每次抢到的金额 = 随机区间 （0， M / N X 2）
线段切割法
0 条评论
回复 删除
下一页
