您现在的位置是:首页 >技术教程 >常见基础算法网站首页技术教程

常见基础算法

followYouself 2024-06-17 10:22:31
简介常见基础算法

一、排序 & 查找算法

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 二分查找

1.3 快速排序

  • 快速排序有几种写法,左右双边指针交换法、单边指针交换法

1.3.1 左右双边指针交换法

  1. 创建左右两个指针。记录左指针数值为分界值,假设为key。
  2. 首先右指针从右向左找出比key小的数据坐标,同时保证左指针小于右指针。
  3. 然后左指针从左向右找出比key大的数据坐标,同时保证左指针小于右指针。
  4. 左右指针交换,进入下一次循环。
  5. 结束一次循环的条件,必然是左右指针相等。并且结束时指针指向的数值小于等于key。
  6. 结束一次循环后,将当前指针的数据与分界值互换。
  7. 然后把分界处左右两边的数据分别快速排序。(递归)

1.3.2 leetcode

1.4 桶排序

小结

在这里插入图片描述

二、双指针

三、单调栈

  • 将数字一次入栈,同时要求栈中的元素单调递增(也可递减),如果新入栈的数字 N 小于栈顶的数字,那么就依次出栈,直到数字N大于栈顶的元素。
  • 利用单调性质作为临界点,解决问题。
  • 503. 下一个更大元素 II
  • 739. 每日温度

四、滑动窗口

  • 用于求解满足特定条件的连续子数组问题

  • 滑动窗口无法解决存在负值的问题,存在负值的问题,可以考虑使用前缀和方法进行求解。

  • 1208. 尽可能使字符串相等 这个题目中,最长子串就是要满足的条件,同时也满足连续子数组的要求。

五、前缀和

六、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 广度遍历

七、回溯算法

八、动态规划

  • 关键是寻找:状态转移方程 和 边界条件,然后使用递归。
  • 因为递归可能会出现重复求解的情况,所以应该记录已经求解的问题,避免重复运算。
  • 空间优化。因为在计算F(n)的时候,往往只需要F(n - 1) 和 F(n - 2)的值,所以在计算时可以只保留这两个数值,优化空间复杂度。

8.1 leetcode

九、贪心算法

十、回文子串(马拉车算法)

十一、 位运算

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。