一、快速排序算法（leetcode复盘： 8）

==主要思想==

  • 从序列中，任选一个记录k作为轴值pivot
  • 选择策略
    • 第一个元素
    • 最后一个元素
    • 中间元素
  • 将数组元素，分割成左子序列L和右子序列R
  • L 中所有元素都 < k， R 中所有元素都 > k
  • 对 L 和 R递归进行快排，直到子序列中有 0 个 或者 1 个元素，退出

通过画图理解算法

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
58
59
60
61
62
63
64
65
66
67
68
69
/**
 * @author hly
 * @Description: 分治思想：快速排序算法实现
 * @create 2021-05-31 11:13
 */
public class 快速排序 {

    public static void main(String[] args) {
        int[] n = {1,5,6,3,2,8,9};
        for (int i = 0; i < n.length; i++) {
            System.out.print(n[i] + " ");
        }
        System.out.println();
        quickSort(n,0,6);
        for (int i = 0; i < n.length; i++) {
            System.out.print(n[i] + " ");
        }
    }

    /**
     * 递归快排
     * @param n
     * @param left
     * @param right
     */
    public static void quickSort(int[] n,int left, int right) {
        int dp;
        if(left < right){
            dp = partition(n,left,right);
            quickSort(n,dp + 1,right);
            quickSort(n,left,dp - 1);
        }
    }

    /**
     * 分区函数
     * @param n
     * @param left
     * @param right
     * @return
     */
    public static int partition(int[] n, int left, int right){
        // pivot 存储基准值
        int pivot = n[left];
        while (left < right){
            while (left < right && n[right] >= pivot){
                right--;
            }
            if(left < right){
                n[left] = n[right];
                left++;
            }
            while (left < right && n[left] <= pivot){
                left++;
            }
            if(left < right){
                n[right] = n[left];
                right--;
            }
        }
        // 分区值
        n[left] = pivot;
        return left;
    }
}

结果：
    1 5 6 3 2 8 9 
	1 2 3 5 6 8 9

  • 时间复杂度：

    • 平均：O(Nlogn)

    • 最差：O(N^2^)

二、动态规划（leetcode 复盘： 9）

动态规划的解题核心主要分为两步：

  1. 第一步：状态的定义
  2. 第二步：状态转移方程的定义

在这里，我们为了避免混淆用“状态”这个词来替代“问题”这个词。“问题”表示的含义类似：题目、要求解的内容、题干中的疑问句这样的概念。状态表示我们在求解问题之中对问题的分析转化。

第一步：状态的定义

有的问题过于抽象，或者过于啰嗦干扰我们解题的思路，我们要做的就是将题干中的问题进行转化（换一种说法，含义不变）。转化成一系列同类问题的某个解的情况，比如说：

题目：求一个数列中最大连续子序列的和。

我们要将这个原问题转化为：

状态定义：Fk是第k项前的最大序列和，求F1～FN中最大值。

通过换一种表述方式，我们清晰的发现了解决问题的思路，如何求出F1～FN中的最大值是解决原问题的关键部分。上述将原问题转化成另一种表述方式的过程叫做：状态的定义。这样的状态定义给出了一种类似通解的思路，把一个原来毫无头绪的问题转换成了可以求解的问题。

第二步：状态转移方程的定义

在进行了状态的定义后，自然而然的想到去求解F1～FN中最大值。这也是状态定义的作用，让我们把一个总体的问题转化成一系列问题，而第二步：状态转移方程的定义则告诉我们如何去求解一个问题，对于上述已经转换成一系列问题我们要关注的点就在于：如何能够用前一项或者前几项的信息得到下一项，这种从最优子状态转换为下一个最优状态的思路就是动态规划的核心。
对于上面的例子题目来说，状态转移方程的定义应该是：

Fk=max{Fk-1+Ak,Ak}
Fk是前k项的和，Ak是第k项的值

仔细思考一番，我们能够得到这样的结论，对于前k个项的最大子序列和是前k-1项的最大子序列和Fk与第k项的和、或者第k项两者中较大的。如果大家还是不能理解这个原理建议用演算纸自己计算一番，这里就不过多赘述了。这种状态转移的思路就是DP的核心。

看过了如何去使用动态规划，那么随之而来的问题就在于：既然动态规划不是某个固定的算法，而是一种策略思路，那么什么时候应该去使用什么时候不能用呢？答案很简短：

对于一个可拆分问题中存在可以由前若干项计算当前项的问题可以由动态规划计算。

三、二叉树相关（leetcode 复盘：5、6、10）

前序遍历：

若二叉树为空，则退出，否则进行下面操作

  • 访问根节点
  • 先根遍历左子树
  • 先根遍历右子树
  • 退出
1
2
3
4
5
6
7
public void PreOrder(BinaryTreeNode node){
    if(node!=null){
        System.out.println(node.getData()); //先访问根节点
        PreOrder(node.getLeftChirld());  //先根遍历左子树
        PreOrder(node.getRightChirld());  //先根遍历右子树
    }
}

中序遍历：

若二叉树为空，则退出，否则进行下面操作

  • 中根遍历左子树
  • 访问根节点
  • 中根遍历右子树
  • 退出
1
2
3
4
5
6
7
public void InOrder(BinaryTreeNode node){
    if(node!=null){
        InOrder(node.getLeftChirld());  //中根遍历左子树
        System.out.println(node);    //访问根节点
        InOrder(node.getRightChirld());  //中根遍历右子树
    }
}

后序遍历：

若二叉树为空，则退出，否则进行下面操作

  • 后根遍历左子树
  • 后根遍历右子树
  • 访问根节点
  • 退出
1
2
3
4
5
6
7
8
    public void PostOrder(BinaryTreeNode node){
        if(node!=null){
            PostOrder(node.getLeftChirld());  //后根遍历左子树
            PostOrder(node.getRightChirld());  //后根遍历右子树
            System.out.println(node);   //访问根节点
        }
    }
}