算法知识
2024-01-07 21:24:34 0 举报数据结构、算法、算法思想、案例、leecode
作者其他创作
大纲/内容
基本数据结构
常用数据结构：数组（Array）、栈（Stack）、队列（Queue）、链表（Linked List）、树（Tree）、图（Graph）、堆（Heap）、散列表（Hash）等；
分类：
线性结构：数组（Array）、栈（Stack）、队列（Queue）、链表（Linked List）、散列表（Hash）
树形结构：树（Tree）、堆（Heap）
图形结构：图（Graph）
算法复杂度：
时间复杂度：O(1)、O(logn)、O(n)、O(n*logn)、O(n2)、O(n3)、O(2^n)、
空间复杂度
算法思想
分治算法
概念：将问题划分为更小的子问题并独立解决。
步骤：划分、解决、合并。
案例：归并排序、快速排序、二叉树的遍历。
相关思想：递归、记忆化搜索、动态规划。
贪心算法
概念：在每一步选择中都采取当前状态下最优的选择，从而希望最终达到全局最优解。
步骤：问题建模、选择策略、判断可行性、更新状态、终止条件。
案例：霍夫曼编码、最小生成树、活动选择、区间调度。
相关思想：动态规划、回溯。
动态规划算法
概念：将问题划分为重叠子问题，并使用记忆化搜索或自底向上的方法来求解。
步骤：定义问题状态、确定可行解的约束条件、确定状态的选择列表、定义状态转移函数、递归搜索、回溯、解决问题。
案例：最优子结构、重叠子问题、最长公共子序列、背包问题、最短路径。
相关思想：分治、贪心、回溯。
回溯算法
概念：通过尝试所有可能的选择来求解问题，适用于问题的解空间较小、约束条件较多、搜索路径有限的情况，通过尝试所有可能的选择并及时进行回溯。
步骤：定义状态、确定状态转移方程、初始化、递推计算、解决问题。
案例：子集问题、数独问题、数组总和、全排列问题、八皇后问题。
相关思想：剪枝、动态规划、贪心。
搜索算法
概念：在问题空间中寻找目标解。
步骤：。
案例：深度优先、广度优先、二分查找、回溯。
相关思想：二分查找、回溯。
二分法
概念：有序数组中查找目标元素。
步骤：确定搜索范围、计算中间位置、比较目标元素和中间元素。
案例：时间复杂度O(log n)、旋转有序数组的查找、查找第一个或最后一个满足某个条件的元素。
相关思想：分治。
算法问题
题目-leecode-70-爬楼梯
题目：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
思考1：1、总方法=走一步方法+走2两部方法，3、终止条件是什么
思考2：1、递归实现，时间复杂度 O(n^2)；2、引入HashMap解决重复计算；3、循环代替递归
算法思想：动态规划、递推、分治
同类案例：剑指offer-10
题目-leecode-1-两数之和
题目：给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
思考1：1、暴力求解，遍历两个元素的相加是否等于目标值，时间复杂度O(n^2)；2、记录元素位置，直接取
算法思想：哈希表、查找
同类案例：leecode-88-合并两个有序数组
题目-leecode-88-合并两个有序数组
题目：给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
思考1：1、将nums2加入到nums1，再排序，以快速排序为例，时间复杂度O(n*logn)；2、建临时数组从最小值开始存，时间复杂度O(n)；3、从大到小往nums1存
算法思想：双指针
同类案例：
题目-leecode-283-移动零
题目：给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
思考1：1、两个指针分别记录是否遍历完全部值和遍历完全部值时最后的非零元素的位置，时间复杂度O(n)；2、
算法思想：双指针
同类案例：
题目-leecode-？？？
0 条评论
下一页
