了解贪心、分治、回溯算法和动态规划的算法思想

王铮老师《算法》系列文章之37-。

提纲：

贪心算法 greedy algorithm

• 贪心算法并不能总是给出最优解：有权图中找最短路径；
• 分糖果：
• 钱币找零
• 区间覆盖

Huffman Coding：

文本中不同字符个数 + 字符出现频率

编码方式：

字符看作结点并带有频率，所有节点在优先级队列中，每次选择最小的结点组成新的父结点，再放入队列中。

https://static001.geekbang.org/resource/image/7b/7a/7b6a08e7df45eac66820b959c64f877a.jpg

分治算法

divide and conquer：将原问题划分为n个小规模问题，且结构相似。可递归解决这些子问题，然后合并结果。

• 分治 思想

• 递归 编程

• 逆序度、有序度

在归并排序中，合并两个有序的数组过程中，就可以计算两个数组的逆序对个数。如图：

// 此处难以下笔，归并都忘得差不多了！
private int num = 0; //全局变量or成员变量

public int count(int[] a, int n){
    num = 0;
    mergeSortCounting(a, 0, n-1);
    return num;
}

private void mergeSortCounting(int[] a, int p, int r){
    
}

private void merge(int[] a, int p, int q, int r){ // low middle high
    
}

二维平面上有 n 个点，如何快速计算出两个距离最近的点对？

有两个 n*n 的矩阵 A，B，如何快速求解两个矩阵的乘积 C=A*B？

在海量数据处理中

扫描10GB的订单，划分金额区间，存储文件。单独加载小文件到内存中排序。最终合并即可。

MapReduce

MapReduce框架是一个任务调度器，本质为分治思想，底层使用GFS存储数据，使用Borg管理机器。

回溯算法

八皇后问题

package com.youdef.DataStructureAndAlgo;

/*
八皇后问题：
递归
 */

public class EightQueens {
    public static void main(String[] args){
        call8queens(0);
    }


    static int[] result = new int[8]; //全局变量or成员变量，这里下标表示行，值表示queen存储的列
    static int ccc = 1; //统计打印次数

    public static void call8queens(int row){
        if (row == 8){ //8行棋子都放好了，结束
            printQueens(result);
            return;
        }
        for (int column=0; column<8; ++column){ //每一行中有8个格子，依次检查放法
            if (isOk(row, column)){
                result[row] = column; //若放法满足要求， 第row行棋子放到column列
                call8queens(row+1); //考察下一行
            }
        }

    }

    public static boolean isOk(int row, int column){//判断row行column列 放置是否合适
        int leftup = column-1, rightup = column+1;  //这里是怎样安排的？？
        for (int i=row-1; i>=0; --i){ //逐行检查 每一行
            //第i行 第column列 是否有棋子
            if (result[i] == column) return false;
            //左上角对角线：第i行leftup列有棋子吗
            if (leftup >= 0){
                if (result[i] == leftup) return false;
            }
            //考察右上角对角线，第i行rightup列有棋子吗
            if (rightup < 8){
                if (result[i] == rightup) return false;
            }
            --leftup; ++rightup;
        }
        return true;
    }

    public static void printQueens(int[] result){ //打印二维矩阵
        System.out.println("第 "+ccc+" 种：");
        ccc++;

        for (int row=0; row<8; ++row){
            for (int column=0; column<8; ++column){
                if (result[row]== column) System.out.print("Q ");
                else System.out.print("* ");
            }
            System.out.println();
        }
        System.out.println();
    }
}

0-1背包问题

这里的背包问题中物体是不可分割的，要么装要么不装。这里使用回溯算法解决：

//见程序

正则表达式

动态规划