数据结构与算法

参考文档
《算法图解》
《计算机算法设计与分析》

简单查找

1. 时间复杂度

1. 空间复杂度
2. java Demo

public class HelloWorld {

    public static void main(String[] args) {
        List<Integer> arr = Lists.newArrayList(7, 9, 2, 5, 1);
        Integer index = simpleSearch(9, Lists.newArrayList(arr));
        System.out.print("index = " + index);
    }

    public static Integer simpleSearch(Integer target, List<Integer> arr) {
        for (int i = 0; i < arr.size(); i++) {
            if (target.equals(arr.get(i))) {
                return i;
            }
        }
        return null;
    }
}

二分查找

1. 时间复杂度
   

2. 空间复杂度

3. Java Demo

public class MyClass {
  
    public static void main(String args[]) {
        Integer[] array = new Integer[]{1,7,9,14,26,87,100};
        Integer index = binarySearch(10, array, 0, array.length);
        System.out.println("index = " + index);
    }
    
    public static Integer binarySearch(Integer target, Integer[] array, Integer startIndex, Integer endIndex){
        if(startIndex > endIndex){
            return null;
        } else if(startIndex < endIndex){
            Integer mid = ( startIndex + endIndex ) / 2;
            Integer midValue = array[mid];
            if(midValue == target){
                return mid;
            } else if(midValue > target){
                return sort(target, array, startIndex, mid - 1);
            } else {
                return sort(target, array, mid + 1, endIndex);
            }
        } else {
            if(array[startIndex] == target){
                return startIndex;
            } else {
                return null;
            }
        }
    }
}

选择排序

1. 时间复杂度

2. 空间复杂度
3. Java Demo

public class HelloWorld {
    public static void main(String[] args) {
        Integer[] arr = new Integer[]{7, 9, 2, 5, 1};
        arr = selectionSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }


    public static Integer findSmallest(Integer[] arr, int startIndex) {
        int smallest = arr[startIndex];
        int smallestIndex = startIndex;
        for (int i = startIndex; i < arr.length; i++) {
            if (arr[i] < smallest) {
                smallest = arr[i];
                smallestIndex = i;
            }
        }
        return smallestIndex;
    }


    public static Integer[] selectionSort(Integer[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int smallestIndex = findSmallest(arr, i);
            if (smallestIndex != i) {
                arr[i] = arr[i] ^ arr[smallestIndex];
                arr[smallestIndex] = arr[smallestIndex] ^ arr[i];
                arr[i] = arr[i] ^ arr[smallestIndex];
            }
        }
        return arr;
    }
}

快速排序

1. 平均时间复杂度

2. 最糟糕的时间复杂度
   

3. Java Demo

public class HelloWorld {

    public static void main(String[] args) {
        List<Integer> arr = Lists.newArrayList(7, 9, 2, 5, 1);
        arr = quicksort(Lists.newArrayList(arr));
        System.out.print("arr = " + arr);
    }

    public static List<Integer> quicksort(List<Integer> arr) {
        if (arr.size() < 2) {
            return arr;
        } else {
            Integer pivot = arr.get(0);
            List<Integer> less = new ArrayList<>(arr.size() - 1);
            List<Integer> greater = new ArrayList<>(arr.size() - 1);
            for (int i = 1; i < arr.size(); i++) {
                if (arr.get(i) > pivot) {
                    greater.add(arr.get(i));
                } else {
                    less.add(arr.get(i));
                }
            }
            List<Integer> sortedLess = quicksort(less);
            List<Integer> sortedGreater = quicksort(greater);
            List<Integer> result = new ArrayList<>(arr.size());
            result.addAll(sortedLess);
            result.add(pivot);
            result.addAll(sortedGreater);
            return result;
        }
    }
}

散列表

基础知识

散列表适合用于：模拟映射关系；防止重复；缓存/记住数据，以免服务器在通过处理来生成它们；

散列冲突：散列函数很重要，最理想的情况是，散列函数将键均匀地映射到散列表的不同位置。如果散列表存储的链表很长，散列表的速度将急剧下降；

填装因子与散列表长度：一旦填装因子超过0.7，就该调整散列表的长度；

性能

image-20200520094840682.png

广度优先搜索

图

图是什么？

图用于模拟一组连接。图由节点和边组成。一个节点可能与众多节点直接相连，这些节点被称为邻居。

image-20200520132224217.png

有向图：两个节点的关系是有箭头的

无向图：没有箭头，直接相连的节点互为邻居。

下面的两个图是等价的。

image-20200520133820786.png

广度优先搜索

广度优先搜索是一种用于图的查找算法，可帮助回答两类问题。

1. 第一类问题：从节点A出发，有前往节点B的路径吗？
2. 第二类问题：从节点A出发，前往节点B的哪条路径最短？

实现图

散列表让你能够将键映射到值。在这里，你要将节点映射到其所有的邻居。

队列可以控制进栈出栈的顺序。

假设这个一个人际关系图，其中 peggy 是销售员，其他人都不是，利用广度优先算法查看某人的朋友圈是否存在销售员？

image-20200521104942452.png

public class HelloWorld {


    public static void main(String[] args) {
        // 初始化人物 假设 peggy 是销售员
        Person anuj = new Person("anuj", false);
        Person bob = new Person("bob", false);
        Person peggy = new Person("peggy", true);
        Person alice = new Person("alice", false);
        Person jonny = new Person("jonny", false);
        Person claire = new Person("claire", false);
        Person thom = new Person("thom", false);
        Person you = new Person("you", false);
        // 构建图
        Map<Person, List<Person>> map = new HashMap<>();
        map.put(anuj, Arrays.asList());
        map.put(bob, Arrays.asList(peggy, anuj));
        map.put(peggy, Arrays.asList());
        map.put(alice, Arrays.asList(peggy));
        map.put(you, Arrays.asList(bob, alice, claire));
        map.put(claire, Arrays.asList(thom, jonny));
        map.put(thom, Arrays.asList());
        map.put(jonny, Arrays.asList());
        // 广度优先搜索, 查看 you的朋友圈有没有售货员
        Person seller = search(you, map);
        System.out.printf("you's seller = " + seller);
    }

    public static Person search(Person person, Map<Person, List<Person>> map) {
        Stack<Person> stack = new Stack<>();
        List<Person> personFriends = map.get(person);
        List<Person> searchedList = new ArrayList<>();
        stack.addAll(personFriends);
        while (!stack.empty()) {
            Person item = stack.pop();
            if (!searchedList.contains(item)) {
                if (item.isSeller()) {
                    return item;
                } else {
                    searchedList.add(item);
                    List<Person> itemFriends = map.get(item);
                    for (Person itemFriend : itemFriends) {
                        if(!searchedList.contains(itemFriend)){
                            stack.push(itemFriend);
                        }
                    }
                }
            }
        }
        return null;
    }
}

class Person {
    // 名字
    private String name;
    // 是否为售货员
    private boolean seller;

    public Person(String name, boolean seller) {
        this.name = name;
        this.seller = seller;
    }

    public String getName() {
        return this.name;
    }

    public boolean isSeller() {
        return this.seller;
    }

    @Override
    public String toString() {
        return "Person{" +
                "name='" + name + '\'' +
                ", seller=" + seller +
                '}';
    }
}

运行时间

广度优先搜索的运行时间为O(人数+边数)，这通常写作O(V+E)，其中V为顶点(vertice)数，E为边数。

树

拓扑排序

image-20200521111540814.png

从某种程度上说，这种列表是有序的。如果任务A依赖于任务B，在列表中任务A就必须在任务B后面。这被称为拓扑排序，使用它可根据图创建一个有序列表。假设你正在规划一场婚礼，并有一个很大的图，其中充斥着需要做的事情，但却不知道要从哪里开始。这时就可使用拓扑排序来创建一个有序的任务列表。

树的定义

数是一种特别的图，其中没有往后指的边。

狄克斯特拉算法

术语

狄克斯特拉算法用于每条边都有关联数字的图，这些数字称为权重。

image-20200522202339242.png

带权重的图叫加权图，不带权重的图为非加权图；

要计算非加权图的最短路径，可使用广度优先搜索。要计算加权图中的最短路径，可使用狄克斯特拉算法。不能将狄克斯特拉算法用于计算包含负权边的图，在包含负权边的图中，要找出最短路径，可使用另一种算法——贝尔曼-福德算法。

TODO 贝尔曼-福德算法

实现

算出从起点到终点最"便宜"的路径

image-20200522203102358.png

public class HelloWorld {

    private static final String START_NODE_NAME = "start";

    private static final String END_NODE_NAME = "end";


    /**
     * 记录从起点到某个点的最短消耗
     */
    private static Map<String, Integer> costs = new HashMap<>();

    /**
     * 记录已经处理过的节点
     */
    private static List<String> processed = new ArrayList<>();

    /**
     * 图：记录各个节点的关系以及关系的权值  其实是一个二维数组
     */
    private static Map<String, Map<String, Integer>> GRAPH = new HashMap<>();


    static {
        // 初始化图
        Map<String, Integer> startMap = new HashMap<>();
        startMap.put("A", 6);
        startMap.put("B", 2);
        GRAPH.put(START_NODE_NAME, startMap);
        Map<String, Integer> aMap = new HashMap<>();
        aMap.put(END_NODE_NAME, 1);
        GRAPH.put("A", aMap);
        Map<String, Integer> bMap = new HashMap<>();
        bMap.put(END_NODE_NAME, 5);
        bMap.put("A", 3);
        GRAPH.put("B", bMap);
        Map<String, Integer> endMap = new HashMap<>();
        GRAPH.put(END_NODE_NAME, endMap);
        // costs
        costs.put("A", 6);
        costs.put("B", 2);
        costs.put(END_NODE_NAME, Integer.MAX_VALUE);
    }


    public static void main(String[] args) {
        Integer lowestCost = search();
        System.out.println("start -> end , lowestCost = " + lowestCost);
    }


    private static Integer search() {
        for (String lowestCostNode = findLowestCostNode(); lowestCostNode != null; lowestCostNode = findLowestCostNode()) {
            if (!processed.contains(lowestCostNode)) {
                Integer lowestCost = costs.get(lowestCostNode);
                Map<String, Integer> neighbors = GRAPH.get(lowestCostNode);
                for (Map.Entry<String, Integer> entry : neighbors.entrySet()) {
                    String neighborNodeName = entry.getKey();
                    Integer costItem = entry.getValue();
                    Integer newCost = lowestCost + costItem;
                    if (newCost < costs.get(neighborNodeName)) {
                        costs.put(neighborNodeName, newCost);
                    }
                }
                processed.add(lowestCostNode);
            }
        }
        return costs.get(END_NODE_NAME);
    }


    private static String findLowestCostNode() {
        Integer lowestCost = Integer.MAX_VALUE;
        String lowestCostNode = null;
        for (Map.Entry<String, Integer> entry : costs.entrySet()) {
            Integer costItem = entry.getValue();
            String nodeNameItem = entry.getKey();
            if (costItem < lowestCost && !processed.contains(nodeNameItem)) {
                lowestCost = costItem;
                lowestCostNode = nodeNameItem;
            }
        }
        return lowestCostNode;
    }
}

NP完全问题

NP完全问题(NP-C问题)，是世界七大数学难题之一。 NP的英文全称是Non-deterministic Polynomial Complete的问题，即多项式复杂程度的非确定性问题。简单的写法是 NP=P？，问题就在这个问号上，到底是NP等于P，还是NP不等于P。

生成问题的一个解通常比验证一个给定的解时间花费要多得多。这是这种一般现象的一个例子。与此类似的是，如果某人告诉你，数13,717,421可以写成两个较小的数的乘积，你可能不知道是否应该相信他，但是如果他告诉你他可以因式分解为3607乘上3803，那么你就可以用一个袖珍计算器容易验证这是对的。人们发现，所有的完全多项式非确定性问题，都可以转换为一类叫做满足性问题的逻辑运算问题。既然这类问题的所有可能答案，都可以在多项式时间内计算，人们于是就猜想，是否这类问题，存在一个确定性算法，可以在多项式时间内，直接算出或是搜寻出正确的答案呢？这就是著名的NP=P？的猜想。 不管我们编写程序是否灵巧，判定一个答案是可以很快利用内部知识来验证，还是没有这样的提示而需要花费大量时间来求解，被看作逻辑和计算机科学中最突出的问题之一。它是斯蒂文·考克于1971年陈述的。

没有办法判断问题是不是NP完全问题，但还是有些蛛丝马迹可循。

1. 元素较少时算法的运行速度非常快，但随着元素的增加，速度会变得非常慢。

2. 涉及"所有组合"的问题通常是NP完全问题。

3. 不能将问题分成小问题，必须考虑各种可能的情况。这可能是NP完全问题。

4. 如果问题设计序列且难以解决，他可能就是NP完全问题。

5. 如果问题设计集合且难以解决，他可能就是NP完全问题。

回溯法

回溯法有"通用的解题法"之称。用它可以系统地搜索一个问题的所有解或任一解。回溯法是一个既带有系统性有带有跳跃性地搜索算法。它在问题的解空间树中，按深度优先包含问题的解。如果肯定不包含，则跳过对以该节点为根的子树的搜索，逐层向其祖先节点回溯。否则，进入该子树，继续按深度优先策略搜索。回溯法求问题的所有解时，要回溯到根，且根节点的所有子树都已被搜索遍才结束。回溯法求问题的一个解时，只要搜索到问题的一个解就可结束。这种以深度优先方式系统搜索问题解的算法称为回溯法，它适用于解组合数较大的问题。

01背包问题 - 回溯背包

解题思路：利用深度优先搜索，得到所有的装包方式，挑选最大价值的方式进行装包；在获取所有装包方式时，如果能判断某些方式价值不够，就忽略该方式（剪枝）。

image.png

public class Hello {
​
 /**
 * 物品数量
 */
 private static int n = 5;
 /**
 * 背包的容量
 */
 private static int capacity = 10;
 /**
 * 物品的重量
 */
 private static int[] weight = {2, 6, 4, 1, 5};
 /**
 * 物品的价值
 */
 private static int[] value = {6, 9, 6, 1, 4};
 /**
 * 最大的价值
 */
 private static int maxValue = 0;
 /**
 * 当前的价值
 */
 private static int tempValue = 0;
 /**
 * 当前的重量
 */
 private static int tempWeight = 0;
 /**
 * 当前装包的物品(0:未装入;1:已装入)
 */
 private static int[] way = new int[n];
 /**
 * 最大价值的装包的物品(0:未装入;1:已装入)
 */
 private static int[] bestWay = new int[n];
​
​
 public static void backtrack(int t) {
 if (t > n - 1) {
 if (tempValue > maxValue) {
 maxValue = tempValue;
 for (int i = 0; i < n; i++) {
 bestWay[i] = way[i];
 }
 }
 return;
 }
 // 走左分支
 if (tempWeight + weight[t] <= capacity) {
 tempWeight += weight[t];
 tempValue += value[t];
 way[t] = 1;
 // 放入该物品, 然后处理下一个物品, 计算完如果得到当前最优解会保存到 bestWay maxValue
 backtrack(t + 1);
 // 取出该物品
 tempWeight -= weight[t];
 tempValue -= value[t];
 way[t] = 0;
 }
 // 走右分支
 if (bound(t + 1) >= maxValue) {
 // 剪枝, 如果剩余物品的最高价值都没有当前的最高价值高,那就不用走右分支了
 backtrack(t + 1);
 }
 }
​
 /**
 * 计算剩余物品的最高价值上界
 */
 public static double bound(int k) {
 // 计算剩余物品的单位重量价值
 double[] maxUnitValues = new double[n];
 for (int i = k; i < n; i++) {
 maxUnitValues[i] = value[i] / weight[i];
 }
 // 根据单位重量价值计算背包剩余的最大价值
 int surplusCapacity = capacity - tempWeight;
 double surplusValue = 0;
 for (int j = k; j < n; j++) {
 int maxUnitValueIndex = 0;
 double maxUnitValue = 0;
 for (int i = k; i < maxUnitValues.length; i++) {
 if (maxUnitValue < maxUnitValues[i]) {
 maxUnitValue = maxUnitValues[i];
 maxUnitValueIndex = i;
 }
 }
 if (surplusCapacity > weight[maxUnitValueIndex]) {
 surplusCapacity -= weight[maxUnitValueIndex];
 surplusValue += value[maxUnitValueIndex];
 } else {
 // 对于不能完全装入的物品，用该物品的单位重量价值折算到剩余空间
 surplusValue += maxUnitValues[maxUnitValueIndex] * surplusCapacity;
 surplusCapacity = 0;
 }
 maxUnitValues[maxUnitValueIndex] = 0;
 }
 return tempValue + surplusValue;
 }
​
 public static void main(String[] args) {
 backtrack(0);
 System.out.println("该背包能够装载的最大价值为 : " + maxValue);
 System.out.print("装包的方式 : ");
 for (int i = 0; i < bestWay.length; i++) {
 String s = "no";
 if(1 == bestWay[i]){
 s = "yes";
 }
 System.out.print("商品" + i + "(" + s + ") ; ");
 }
 }
}

n后问题

n后问题

public class Hello {
​
​
 private static final int SIZE = 9;
​
 private static List<List<Location>> wags = new ArrayList<>();
​
 static class Location {
 /**
 * 横坐标(对应棋盘的行)
 */
 private int x;
 /**
 * 纵坐标(对应棋盘的列)
 */
 private int y;
​
 Location(int x, int y) {
 this.x = x;
 this.y = y;
 }
​
 @Override
 public String toString() {
 return "Location{" +
 "x=" + x +
 ", y=" + y +
 '}';
 }
​
 public int getX() {
 return x;
 }
​
 public int getY() {
 return y;
 }
 }
​
 /**
 * 判断位置为loc的皇后是否合法
 */
 private static boolean isLegalLoc(List<Location> placedLocations, Location current) {
 for (Location item : placedLocations) {
 if (current.getX() == item.getX() || current.getY() == item.getY()) {
 // 判断是否在同一行或同一列
 return false;
 } else if (Math.abs(current.getX() - item.getX()) == Math.abs(current.getY() - item.getY())) {
 // 判断是否在同斜线上
 return false;
 }
 }
 return true;
 }
​
 private static void NQueen(List<Location> placedLocations, int x, int y) {
 // 当list元素个数为SIZE时，表示SIZE个皇后都摆放完毕
 if (placedLocations.size() == SIZE) {
 wags.add(new ArrayList<>(placedLocations));
 return;
 }
​
 for (int i = x; i < SIZE; i++) {
 Location loc = new Location(i, y);
 if (isLegalLoc(placedLocations, loc)) {
 //将第y行的皇后摆放好
 placedLocations.add(loc);
 //开始摆放y+1行的皇后，同样从第0列开始摆放
 NQueen(placedLocations, 0, y + 1);
 //每次摆放完一个皇后后，都要将其撤回，再试探其它的摆法。
 placedLocations.remove(loc);
 }
 }
 }
​
 public static void main(String[] args) {
 List<Location> placedLocations = new ArrayList<Location>();
 //从棋盘的第0行第0列开始
 NQueen(placedLocations, 0, 0);
 System.out.println(SIZE + "皇后共有 " + wags.size() + "种摆放方式");
 }
}

贪婪算法

01背包问题 - 贪心背包

假设你是个贪婪的小偷，背着可装35磅重东西的背包，在商场伺机盗窃各种可装入背包的商品。你力图往背包装入价值最高的商品，你会使用哪种算法？

如果采用『贪婪策略』，问题就非常简单了。

1. 盗窃可装入背包的最贵的商品
2. 再盗窃还可以装入背包的最贵的商品，以此类推。

在这里，贪婪策略并不能保证最优解。在有些情况下，完美是优秀的敌人。有时候，你只需要找到一个能够大致解决问题的算法，此时贪婪算法正好派上用场，因为实现起来很容易，得到的结果又与正确值相当接近。

集体覆盖问题

image.png

假设你办了一个广播节目，要让全美50个州的听众都得听得到。为此，你需要决定在哪些广播台播出。在每个广播台播出都需要支付费用，因此你力图在尽可能少的广播台播出。现有广播台名单如下。每个广播台都覆盖特定的区域，不同广播台的覆盖区域可能重叠。

image.png

由于各个广播台的组合方式有 2^n 中可能，如果使用枚举法，运行时间为O(2^n)。没有任何算法可以足够块地解决这个问题！但是使用贪婪算法（近似算法）可得到一个非常接近的解。

1. 选出这样的一个广播台，即它覆盖了最多未覆盖的州。即便这个广播台覆盖了的州，也没有关系。
2. 重复第一步，知道覆盖了所有的州。

这是一种近似算法，在获得精确需求的时间太长时，可使用近似算法。判断近似算法优劣标准如下：

1. 速度有多快；
2. 得到的近似解与最优解的接近程度。

旅行商问题

在这个问题中，旅行商需要前往5个不同的城市。他需要找出前往这5个城市的最短路径，为此，必须计算每条可能的路径。

image.png

这是一个阶乘函数，当地点数量为n时，所有的可能为 n! 种。使用近似求解，可以得到一个比较合适的解，类似如下做法：随便选择触发城市，然后每次选择要去的城市时，都选择还没去过的最近的城市。

旅行商问题和集合覆盖问题有一些共同之处：你需要计算所有的解，并从中选出最小、最短的那个。这两个问题都属于NP完全问题。

动态规划

使用贪婪算法找到背包问题的解，最接近最优解，但可能不是最优解。那么如何找到最优解呢？

答案就是使用动态规划！动态规划算法工作原理：先解决子问题，在逐步解决大问题。

01背包问题 - 动态规划

还是继续上面的背包，假设你是一个小偷，背着可以装4磅东西的背包。你可盗窃的商品有如下三件。

image.png

	1磅的背包	2磅的背包	3磅的背包	4磅的背包
吉他	1500$	1500$	1500$	1500$
音响	1500$	1500$	1500$	3000$
笔记本电脑	1500$	1500$	2000$	3500$ 『最优解』

public class HelloWorld {

    public static void main(String[] args) {
        /**
         * 物品的个数
         */
        int n = 3;
        /**
         * 每个物品的价值
         */
        int value[] = {3000, 2000, 1500};
        /**
         * 每个物品的重量 和上面的一一对应
         */
        int weight[] = {4, 3, 1};
        /**
         * 袋子的容积
         */
        int w = 4;
        /**
         * 用二维数组表示表格,记录不同容量的背包的处理结果
         */
        int dp[][] = new int[n + 1][w + 1];

        for (int i = 1; i <= n; i++) {
            // i是物品在 value 和 weight 的 index
            for (int cw = 1; cw <= w; cw++) {
                //cw是当前袋子的容量
                if (weight[i - 1] <= cw) {        //表示这个物品可以装
                    // valueAfterPut 放入该物品后的背包价值 ; dp[i - 1][cw] 不装这个物品的背包价值
                    // 动态规划的思想就是在这里体现的, 容量大的背包会运用容量小的背包的结果，减少计算次数
                    int valueAfterPut = value[i - 1] + dp[i - 1][cw - weight[i - 1]];
                    dp[i][cw] = Math.max(valueAfterPut, dp[i - 1][cw]);
                } else {
                    //当前这个物品装不下 ，那就取之前的最优解
                    dp[i][cw] = dp[i - 1][cw];
                }
            }
        }
        System.out.println("袋子装的物品的最大价值:" + dp[n][w]);
    }
}

最长公共子串

image.png

public class HelloWorld {

    public static void main(String[] args) {
        String stringA = "FOSH";
        String stringB = "FORT";
        int longestCommonSubsequenceLength = 0;
        Location longestCommonSubsequenceLocation = null;

        int[][] pd = new int[stringB.length() + 1][stringA.length() + 1];
        for (int i = 1; i <= stringB.length(); i++) {
            char charBItem = stringB.charAt(i - 1);
            for (int j = 1; j <= stringA.length(); j++) {
                char charAItem = stringA.charAt(j - 1);
                if (charBItem == charAItem) {
                    // 两个字符一样
                    // 看一下是首个相同的字符,还是连续的
                    if (pd[i - 1][j - 1] != 0) {
                        pd[i][j] = pd[i - 1][j - 1] + 1;
                        if (longestCommonSubsequenceLength < pd[i][j]) {
                            longestCommonSubsequenceLength = pd[i][j];
                            longestCommonSubsequenceLocation = new Location(i, j);
                        }
                    } else {
                        pd[i][j] = 1;
                        longestCommonSubsequenceLength = pd[i][j];
                        longestCommonSubsequenceLocation = new Location(i, j);
                    }
                }
            }
        }
        System.out.println("最长公共子串长度 longestCommonSubsequenceLength : " + longestCommonSubsequenceLength);
        System.out.println("最长公共子串位置 longestCommonSubsequenceLocation : " + longestCommonSubsequenceLocation);
    }


    public static class Location {

        private int x;

        private int y;

        public Location(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public String toString() {
            return "Location{" +
                    "x=" + x +
                    ", y=" + y +
                    '}';
        }
    }
}

K最近邻算法

流程 : 特征抽取 -> 回归 -> 挑选合适的特征

1. 分类就是编组
2. 回归就是预测结果
3. 特征抽取就是意味着将物品转换为一系列可比较的数字

使用场景

1. 推荐系统：类似根据电影的浏览历史推荐电影、根据电影评价推荐电影
2. 机器学习
   1. OCR（光学字符识别）
   2. 垃圾邮件过滤器：朴素贝叶斯分类器
   3. 预测股票市场