您现在的位置是:首页 >技术教程 >常见基础算法网站首页技术教程
常见基础算法
简介常见基础算法
一、排序 & 查找算法
1.1 冒泡排序
-
相邻的数据进行比较。每次遍历找到一个最大值。
-
public void sort(int[] nums) { if (nums == null) { return; } for (int i = 0; i < nums.length; i++) { for (int j = 0; j < nums.length - 1 - i; j++) { if (nums[j] > nums[j + 1]) { int temp = nums[j]; nums[j] = nums[j + 1]; nums[j + 1] = temp; } } } }
1.2 二分查找
- 要求数据有序,或者至少部分有序。
int mid = left + (right - left) / 2;
直接使用(left + right) /2 时,left + right 可能出现整型溢出- 704 二分查找
- #33 搜索旋转排序数组
1.3 快速排序
- 快速排序有几种写法,左右双边指针交换法、单边指针交换法
1.3.1 左右双边指针交换法
- 创建左右两个指针。记录左指针数值为分界值,假设为key。
- 首先右指针从右向左找出比key小的数据坐标,同时保证左指针小于右指针。
- 然后左指针从左向右找出比key大的数据坐标,同时保证左指针小于右指针。
- 左右指针交换,进入下一次循环。
- 结束一次循环的条件,必然是左右指针相等。并且结束时指针指向的数值小于等于key。
- 结束一次循环后,将当前指针的数据与分界值互换。
- 然后把分界处左右两边的数据分别快速排序。(递归)
1.3.2 leetcode
1.4 桶排序
小结
二、双指针
-
双指针就是通过移动指针来满足某些条件,计算出最优结果。
-
双指针的题型是不固定的,题型多变,需要灵活的运用。
-
#剑指 Offer 22 链表中倒数第k个节点 双指针记录距离。
-
11. 盛最多水的容器 双指针求最大值,始终按照固定的规则来选择移动其中一个指针。
三、单调栈
- 将数字一次入栈,同时要求栈中的元素单调递增(也可递减),如果新入栈的数字 N 小于栈顶的数字,那么就依次出栈,直到数字N大于栈顶的元素。
- 利用单调性质作为临界点,解决问题。
- 503. 下一个更大元素 II
- 739. 每日温度
四、滑动窗口
-
用于求解满足特定条件的连续子数组问题
-
滑动窗口无法解决存在负值的问题,存在负值的问题,可以考虑使用前缀和方法进行求解。
-
1208. 尽可能使字符串相等 这个题目中,最长子串就是要满足的条件,同时也满足连续子数组的要求。
五、前缀和
- 用于求解满足特定条件的连续子数组问题。
- 可以求解数据中存在负值的问题。
- 前缀和利用的性质:
Sum(i...n) = Sum(n) - Sum(i)
。即 从i到n的连续子数组的和 等于 Sum(n) - Sum(i)。 - #560 和为 K 的子数组
- #1124 表现良好的最长时间段
六、DFS & BFS
- 深度遍历适合存在性问题,广度遍历适合寻找最短路径问题。
- 深度遍历有两种实现方式:递归 和 栈。广度遍历只能用队列进行实现。
- 在进行遍历时,必须要记录已经访问过的节点,避免造成循环。
- 在迷宫、网格、岛屿类问题遍历时,要考虑上下左右四个方向进行遍历。可以如下定义方向数组遍历四个方向:
private static final int[][] steps = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
for (int[] step : steps) {
Point next = new Point(point.x + step[0], point.y + step[1]);
//省略...
}
6.1 深度遍历
6.2 广度遍历
- #1293 网格中的最短路径 已经访问过的节点使用三维数据进行表示。
七、回溯算法
- 回溯算法是深度优先的一种衍生算法,是一种遍历算法。
- 回溯算法可以用来求解排列问题
- 46. 全排列 经典问题,数字全排列。
- #17 电话号码的字母组合
- 78. 子集
八、动态规划
- 关键是寻找:状态转移方程 和 边界条件,然后使用递归。
- 因为递归可能会出现重复求解的情况,所以应该记录已经求解的问题,避免重复运算。
- 空间优化。因为在计算F(n)的时候,往往只需要F(n - 1) 和 F(n - 2)的值,所以在计算时可以只保留这两个数值,优化空间复杂度。
8.1 leetcode
-
53. 最大子数组和 面试常见动态规划问题
九、贪心算法
十、回文子串(马拉车算法)
十一、 位运算
- 136. 只出现一次的数字 利用异或的性质去重
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。