LeetCode常用算法的总结_leetcode算法总结

---

前言

大家好，我是独沽一味的猪。对于LeetCode刷题，相信大家并不陌生，然而很多人在付出了大量的时间和精力之后，往往收效甚微。基于此种现象，我希望能将LeetCode中经典的算法加以总结，方便大家对很多常见的算法有一个清晰的认识，更是对自己刷题的心得做出一些总结。

---

一、排序算法

常见的排序算法有：

• 冒泡排序
• 插入排序

1.冒泡排序

public class Test {
	public static void main(String[] args) {
		int[] arr = {6,4,3,9,2};
		bubbleSort(arr);
	}
    
	public static void bubbleSort(int[] arr) {
		
		for(int i = 0;i<arr.length-1;i++) {
			for(int j = 0;j<arr.length-1-i;j++) {
				
				if(arr[j]>arr[j+1]) {
					
					int temp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = temp;
				}
			}
		}
		
		for(int i = 0; i<arr.length;i++) {
			System.out.print(arr[i]);   //2,3,4,6,9
		}
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

题目分析：

2.插入排序（参考：https://blog.csdn.net/qq_45407302/article/details/116778798）

import java.util.Arrays;
public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {5,8,6,3,9,2,1,7};
        for (int i = 1; i < arr.length; i++) {
            //arr[i] 当前元素  arr[i-1] 他前面的一个元素
            //如果当前元素小于我前一个元素，那就交换位置
            for (int j = i; j > 0; j--) {
                if (arr[j] < arr[j - 1]) {
                    int t = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = t;
                }
            }
        }

        System.out.println(Arrays.toString(arr));
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

题目分析：

3.堆排序(参考：https://blog.csdn.net/cativen/article/details/124810686)

package com.qf.sort;

import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) {
        int[] arr={4,6,8,5,9};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void heapSort(int[] arr){
        //给你一个数组 {4,6,8,5,9} , 要求使用堆排序法，将数组升序排序
        /*
         将待排序序列构造成一个大顶堆
        此时，整个序列的最大值就是堆顶的根节点。*/
        /*adjustHeap( arr,1,arr.length);
        adjustHeap( arr,0,arr.length);*/
        for (int i = arr.length/2-1; i >=0; i--) {
            adjustHeap( arr,i,arr.length);
        }
        int temp=0;
        /*
         将其与末尾元素进行交换，此时末尾就为最大值。
         然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。*/
        for (int j=arr.length-1;j>0;j--){
            temp=arr[j];
            arr[j]=arr[0];
            arr[0]=temp;
            adjustHeap(arr,0,j);
        }

    }

    public static void adjustHeap(int[] arr,int i,int length){
        //第一步把数组 {4,6,8,5,9}调整排序为{4,9,8,5,6}
        //k=i*2+1 是循环对应的左子树元素
        //记录当前要调整的元素
        int temp=arr[i];
        for (int k=i*2+1;k<length;k=k*2+1){
            //把当前左子树和右子树的数据作比较，更换较大的数据
            if (k+1<length&&arr[k]<arr[k+1]){
                k++;
            }
            if (arr[k]>temp){
                //交换位置
                arr[i]=arr[k];
                i=k;
            }else{
                break;
            }
        }
        arr[i]=temp;
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

题目分析：

二、查找算法

常见的查找算法有：

• 二分查找
• 滑动窗口

1.二分查找

2.滑动窗口

题目描述：给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

题目解析：
01.当src(i - 1)到src(i + 1)的值为10到25之间，那么f(i)可以包括f(i - 2)种可能，集合为：
f(i - 2)、src(i - 1)、src(i)；以及包括f(i - 1)种可能，集合为：f(i - 1)、src(i)。举个例子就是122可以看作1的所有可能集合 + 12的所有可能集合，所以122的所有可能集合是3
注意：f(i - 2)、src(i - 1)、src(i)和f(i - 1)、src(i)是完全不同的，一个最后两个数字是src(i - 1)、src(i)，一个最后一个数字是src(i)
02.当src(i - 1)到src(i + 1)的值不在10到25之间，那么src(i)是没有贡献的，所以f(i) = f(i - 1)。举个例子就是128的28是没有贡献的，所以128和12的可能集合是一样的，最后的结果都是2

class Solution {
public:
    int translateNum(int num) {
        string src = to_string(num);
        int p = 0, q = 0, r = 1;
        for (int i = 0; i < src.size(); ++i) {
            p = q; 
            q = r; 
            r = 0;
            r += q;
            if (i == 0) {
                continue;
            }
            //src.substr(i - 1, 2)表示src(i - 1)到src(i + 1)，注意i + 1不包括
            auto pre = src.substr(i - 1, 2);
            if (pre <= "25" && pre >= "10") {
                r += p;
            }
        }
        return r;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

题目分析：使用滑动窗口的思想，创建一个0、0、1的窗口进行滑动，核心思想是窗口元素之间的1关系

3.动态规划：

题目描述：假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

/**
 * 设置初始值：maxprofit 为 0，minprice 是无穷大
 * 遍历规则：
 *    1.获取最小的股票价格：数组中的某个值
 *    2.获取处于最小的股票价格时，所获取的 maxprofit （比较当前的 maxprofit 和之前的 maxprofit ）
 *    3.返回 maxprofit 
 */
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int inf = 1e9;     //1e9 = 1 * 10^9 = 1000000000
        int minprice = inf, maxprofit = 0;
        /**
         * 目标数组：7 、1 、5 、3 、6 、4
         * 初始值：maxprofit = 1e9 、minprice = 0
         * 第一次遍历：maxprofit  = 7 、minprice = 7 - 1e9
         * 第二次遍历：maxprofit = 1 、minprice = 1
         * 第三次遍历：maxprofit = 4 、minprice = 1
         * 第四次遍历：maxprofit = 1e9 、minprice = 0
         * 第五次遍历：maxprofit = 1e9 、minprice = 0
         * 第六次遍历：maxprofit = 1e9 、minprice = 0
         */
        for (int price: prices) {
            //获取历史最低价格minprice，比较第i天卖出股票的利润，获取最大利润price[i] - minprice
            maxprofit = max(maxprofit, price - minprice);
            minprice = min(price, minprice);
        }
        return maxprofit;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

题目分析：只能买卖一次，就是数组中最大的值和最小的值之间的差值，且较小的值得在较大的值前面。采用动态规划的思路：01.定义数组；02.找出数组元素之间的关系式；03.找出初始条件

三、遍历算法

常见的遍历算法有：

1.递归算法

题目描述：输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

/**
 * 递归解决问题
 * 节点A和节点B比较，节点A的左节点和B比较，节点A的右节点和B比较
 */
 public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A == null || B == null) return false;
        return dfs(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }
    /**
     * 节点A的值和节点B的值相等
     *  节点A的左节点和节点B的左节点相等
     *  节点A的右节点和节点B的右节点相等
     */
    public boolean dfs(TreeNode A, TreeNode B){
        if(B == null) return true;
        if(A == null) return false;
        //节点值相等、左子树 = 左子树、右子树 = 右子树
        return A.val == B.val && dfs(A.left, B.left) && dfs(A.right, B.right);
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

题目分析：本题的核心在于巧妙地使用了递归算法对两个TreeNode进行了遍历，总结一下递归算法的使用条件：

• 一个问题可以拆分为重复的小问题
• 拆分后，原问题和子问题的求解思路相同
• 递归存在明确的终止条件

2.迭代算法

题目描述：给你一棵二叉树的根节点 root ，返回其节点值的后序遍历
后序遍历：按照访问左子树—右子树—根节点的方式遍历这棵树，而在访问左子树或者右子树的时候，我们按照同样的方式遍历，直到遍历完整棵树。 

/**
 * 利用栈后进先出的特点来存储树的节点
 *  找到根节点的左子树，存储左子树
 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }

        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode prev = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;      //找到根节点的左子树
            }
            root = stack.pop();
            if (root.right == null || root.right == prev) {       //右子树不存在，或者左子树就是右子树
                res.add(root.val);   
                prev = root;
                root = null;
            } else {
                stack.push(root);      //根节点出栈
                root = root.right;      //根节点向下遍历
            }
        }
        return res;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

题目解析：本题利用迭代的思想，逐层迭代来获取树的后序遍历节点。总结一下迭代算法的使用条件：

• 迭代是重复反馈过程的活动，其目的通常是为了逼近所需目标或结果
• 每一次对过程的重复称作一次迭代，而每一次迭代得到的结果会作为下一次迭代的初始值

---

总结

优秀的算法需要深入的理解和充分的运用，希望大家在以后编程的过程中，充分吸收这些算法的设计思想，代码越来越优雅，越来越严谨。