四个算法问题

Contents

• Stock best selling point problem
• Counting sort algorithm
• Count the frequency of words in Wang Feng's lyrics
• Use heap to achieve dijkstra

1.Stock best selling point problem

1-1 problem solution

Calculate the maximum return, the rule is that the time of selling can not be earlier than buying, create an array, update the minimum value of the array in min, update the maximum difference in turn, record the maximum difference is the maximum benefit.

1-2 Time complexity analysis

O(n). Use min to record the minimum value, max to record the maximum difference, min and max are updated in one traversal, there is a total of one cycle, so the time complexity is O(n)

1-3 Source code

public class heapDjikstra {
    public static void main(String[] args) {
        int [] a = {5, 2, 7, 3, 2, 5, 3, 9, 1};
        System.out.println("最大收益是："+maxProfit(a));
    }
    public static int maxProfit(int[] prices) {
        if (prices == null ||prices.length<1) {
            return 0;
        }else {
            int max= 0;          
            int min= prices[0];  
            for (int i = 0; i < prices.length; i++) {
                if (prices[i]<min) {
                    min = prices[i]; 
                    System.out.println("最新买点是："+prices[i]);
                }
                if (max<prices[i]-min) {
                    max = prices[i]-min;
                    System.out.println("最新卖点是："+prices[i]);
                }
                System.out.println("最终买点是："+ min);
                System.out.println("最终卖点是："+ max);
            }
            return max;
        }
    }
}

1-4 Test results

result.png

2.Counting sort algorithm

2-1 problem solution

Assumes that each of the elements is an integer in the range 1 to k, for some integer k. When k = O(n), the Counting-sort runs in O(n) time. The basic idea of Counting sort is to determine, for each input elements x, the number of elements less than x. This information can be used to place directly into its correct position.
Specific steps:
1.Find X smaller than A in the set
2.Put A in X+1 and delete A in the linear table

step

2-2 Time complexity analysis

Because the algorithm uses only simple for loops, without recursion or subroutine calls, it is straightforward to analyze. The initialization of the count array, and the second for loop which performs a prefix sum on the count array, each iterate at most k + 1 times and therefore take O(k) time. The other two for loops, and the initialization of the output array, each take O(n) time. Therefore, the time for the whole algorithm is the sum of the times for these steps, O(n + k), approximate to O(n).

2-3 Source code

import java.io.*;
import java.util.*;
        

class Countingsort {

     public static void main(String[] args) {
        int arr[] = {9, 7, 1, 8, 2, 10, 7, 3, 1, 9, 7, 4, 3, 9, 6};
        System.out.print("Initial Array   : ");
        printArray(arr);
        countingsort(arr);
        }
     public static void printArray(int[] arr) {
        for(int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
              }
            System.out.println();
              }
     public static void  countingsort(int arr[]) {
        int count[] = new int[11]; 
             for(int i = 0; i < arr.length; i++)
                  count[arr[i]]++;
             for(int i = 1; i < count.length; i++)
                  count[i] += count[i - 1];
             System.out.print("Counting Array  : ");
             printArray(count);
             int output[] = new int[arr.length];
             for(int i = 0; i < arr.length; i++) {
                  output[count[arr[i]] - 1] = arr[i];
                  count[arr[i]]--;
                }
                System.out.print("After Sorting   : ");
                printArray(output);
              }
            }

2-4 Test results

Result.png

3.Count the frequency of words in Wang Feng's lyrics

3-1 problem solution

Calculating the frequency is not difficult. The difficulty is how to divide the word. This is beyond the scope of my ability. It is solved by the method on the network. Of course, it is also efficient in the statistical process. I sort it by value and use the Sort() method of Collections for TreeMap.

Thought

1. Read the lyrics text file
2. Count the number of occurrences of each word in the text
3. Sort and print the 10 most frequently words
4. Write the result to a txt file

Step

1. Input and output of file content by using input stream and output stream
2. Save the contents of the file in StringBuffer
3. Separate the strings with String's split() method and store them in an array
4. Traverse the array and store it in Map<String, Integer>
5. Sort the value of TreeMap using the sort() method of Collections

Java Chinese word segmentation - Hanlp(Han Language Processing)
HanLP is a Java toolkit consisting of a series of models and algorithms that aim to popularize the application of natural language processing in production environments. It is not just a participle, but a complete function such as lexical analysis, syntactic analysis, and semantic understanding. HanLP features full-featured, high-performance, clear architecture, new corpus, and customizable features.

HanLP is completely open source, including dictionaries. Without relying on other jars, the underlying uses a series of high-speed data structures, such as the dual array Trie tree, DAWG, AhoCorasickDoubleArrayTrie, etc. These basic components are open source.

see more in HanLP

3-2 Time complexity analysis

Divide the word - can't analysis
Statistical frequency (sort) - O(nlogn)

3-3 Source code

Lyrics list: I can't put the file here so I put it on the platform.
//The lyrics are my own sorted into a txt

import com.hankcs.hanlp.HanLP;
import com.hankcs.hanlp.seg.common.Term;
import com.hankcs.hanlp.suggest.Suggester;
import com.hankcs.hanlp.tokenizer.NLPTokenizer;

import java.io.*;
import java.util.*;
import java.util.Map.Entry;

public class CountOccurrenceOfWords {
    public static void main(String[] args) {
        long t1 = System.currentTimeMillis();
        String s;
        String fileName1 = "c:/java/lyrics.txt";
        String fileName2 = "c:/java/result.txt";
        try {
            BufferedReader br = new BufferedReader(new FileReader(fileName1));
            BufferedWriter bw = new BufferedWriter(new FileWriter(fileName2));
            StringBuffer sb = new StringBuffer();
            //将文件内容存入StringBuffer中
            while((s = br.readLine()) != null) {
                sb.append(s);
            }
            String str = sb.toString().toLowerCase();
            //分隔字符串并存入数组
            String[] elements = str.split("[^a-zA-Z0-9]+");
            int count = 0;
            Map<String, Integer> myTreeMap = new TreeMap<String, Integer>();
            //遍历数组将其存入Map<String, Integer>中
            for(int i = 0; i < elements.length; i++) {
                if(myTreeMap.containsKey(elements[i])) {
                    count = myTreeMap.get(elements[i]);
                    myTreeMap.put(elements[i], count + 1);
                }
                else {
                    myTreeMap.put(elements[i], 1);
                }
            }                                          
            //将map.entrySet()转换成list
            List<Map.Entry<String, Integer>> list = new ArrayList<Map.Entry<String, Integer>>(myTreeMap.entrySet());
            //通过比较器实现排序
            Collections.sort(list, new Comparator<Map.Entry<String, Integer>>() {
                //降序排序
                public int compare(Entry<String, Integer> o1, Entry<String, Integer> o2) {
                    return o2.getValue().compareTo(o1.getValue());
                }
            });
            int num = 1;
            for(Map.Entry<String, Integer> map : list) {
                if(num <= 10) {
                              List<String> sentenceList = HanLP.extractSummary(document, 3);
                              //直接把结果打印在控制台
                              System.out.println("出现次数第" + num + "的词语为：" + map.getKey() + "，出现频率为" + map.getValue() + "次");
                    bw.newLine();
                    System.out.println(map.getKey() + ":" + map.getValue());
                    num++;
                }
                else break;
            }
            bw.write("耗时：" + (System.currentTimeMillis() - t1) + "ms");
            br.close();
            bw.close();
            System.out.println("耗时：" + (System.currentTimeMillis() - t1) + "ms");
        } catch (FileNotFoundException e) {
            System.out.println("找不到指定文件！");
        } catch (IOException e) {                                    
            System.out.println("文件读取错误！");
        }
    }
}

3-4 Test results

result.png

4.Use heap to achieve dijkstra

4-1 problem solution

Djikstra is a way to solve the shortest path problem and finish it with the heap implementation.Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks.Dijkstra's algorithm to find the shortest path between a and b. It picks the unvisited vertex with the lowest distance, calculates the distance through it to each unvisited neighbor, and updates the neighbor's distance if smaller. Mark visited (set to red) when done with neighbors.

4-2 Time complexity analysis

General: O(|V2|) V is the number of nodes
Build a heap : O(n)
Use heap: O(|E|+|V|log|V|) E is the number of edges, V is the number of nodes

4-3 Source code

Implementation By heap

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

import de.vogella.algorithms.dijkstra.model.Edge;
import de.vogella.algorithms.dijkstra.model.Graph;
import de.vogella.algorithms.dijkstra.model.Vertex;

public class heapDjikstra {

    private final List<Vertex> nodes;
    private final List<Edge> edges;
    private Set<Vertex> settledNodes;
    private Set<Vertex> unSettledNodes;
    private Map<Vertex, Vertex> predecessors;
    private Map<Vertex, Integer> distance;

    public DijkstraAlgorithm(Graph graph) {
        this.nodes = new ArrayList<Vertex>(graph.getVertexes());
        this.edges = new ArrayList<Edge>(graph.getEdges());
    }

    public void execute(Vertex source) {
        settledNodes = new HashSet<Vertex>();
        unSettledNodes = new HashSet<Vertex>();
        distance = new HashMap<Vertex, Integer>();
        predecessors = new HashMap<Vertex, Vertex>();
        distance.put(source, 0);
        unSettledNodes.add(source);
        while (unSettledNodes.size() > 0) {
            Vertex node = getMinimum(unSettledNodes);
            settledNodes.add(node);
            unSettledNodes.remove(node);
            findMinimalDistances(node);
        }
    }

    private void findMinimalDistances(Vertex node) {
        List<Vertex> adjacentNodes = getNeighbors(node);
        for (Vertex target : adjacentNodes) {
            if (getShortestDistance(target) > getShortestDistance(node)
                    + getDistance(node, target)) {
                distance.put(target, getShortestDistance(node)
                        + getDistance(node, target));
                predecessors.put(target, node);
                unSettledNodes.add(target);
            }
        }

    }

    private int getDistance(Vertex node, Vertex target) {
        for (Edge edge : edges) {
            if (edge.getSource().equals(node)
                    && edge.getDestination().equals(target)) {
                return edge.getWeight();
            }
        }
        throw new RuntimeException("Should not happen");
    }

    private List<Vertex> getNeighbors(Vertex node) {
        List<Vertex> neighbors = new ArrayList<Vertex>();
        for (Edge edge : edges) {
            if (edge.getSource().equals(node)
                    && !isSettled(edge.getDestination())) {
                neighbors.add(edge.getDestination());
            }
        }
        return neighbors;
    }

    private Vertex getMinimum(Set<Vertex> vertexes) {
        Vertex minimum = null;
        for (Vertex vertex : vertexes) {
            if (minimum == null) {
                minimum = vertex;
            } else {
                if (getShortestDistance(vertex) < getShortestDistance(minimum)) {
                    minimum = vertex;
                }
            }
        }
        return minimum;
    }

    private boolean isSettled(Vertex vertex) {
        return settledNodes.contains(vertex);
    }

    private int getShortestDistance(Vertex destination) {
        Integer d = distance.get(destination);
        if (d == null) {
            return Integer.MAX_VALUE;
        } else {
            return d;
        }
    }

    public LinkedList<Vertex> getPath(Vertex target) {
        LinkedList<Vertex> path = new LinkedList<Vertex>();
        Vertex step = target;
        if (predecessors.get(step) == null) {
            return null;
        }
        path.add(step);
        while (predecessors.get(step) != null) {
            step = predecessors.get(step);
            path.add(step);
        }
        Collections.reverse(path);
        return path;
    }

}

Test

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

import org.junit.Test;

import de.vogella.algorithms.dijkstra.engine.DijkstraAlgorithm;
import de.vogella.algorithms.dijkstra.model.Edge;
import de.vogella.algorithms.dijkstra.model.Graph;
import de.vogella.algorithms.dijkstra.model.Vertex;

import static org.junit.Assert.assertNotNull;
import static org.junit.Assert.assertTrue;

public class TestDijkstraAlgorithm {

    private List<Vertex> nodes;
    private List<Edge> edges;

    public void testExcute() {
        nodes = new ArrayList<Vertex>();
        edges = new ArrayList<Edge>();
        for (int i = 0; i < 11; i++) {
            Vertex location = new Vertex("Node_" + i, "Node_" + i);
            nodes.add(location);
        }
        //Graph graph = new Graph(nodes, edges);
       public static void main (String[] args) 
    { 
       int graph[][] = new int[][]{{0, 4, 0, 0, 0, 0, 0, 8, 0}, 
                                  {4, 0, 8, 0, 0, 0, 0, 11, 0}, 
                                  {0, 8, 0, 7, 0, 4, 0, 0, 2}, 
                                  {0, 0, 7, 0, 9, 14, 0, 0, 0}, 
                                  {0, 0, 0, 9, 0, 10, 0, 0, 0}, 
                                  {0, 0, 4, 14, 10, 0, 2, 0, 0}, 
                                  {0, 0, 0, 0, 0, 2, 0, 1, 6}, 
                                  {8, 11, 0, 0, 0, 0, 1, 0, 7}, 
                                  {0, 0, 2, 0, 0, 0, 6, 7, 0} 
                                 }; 
        ShortestPath t = new ShortestPath(); 
        t.dijkstra(graph, 0); 
    } 
        dijkstra.execute(nodes.get(0));
        LinkedList<Vertex> path = dijkstra.getPath(nodes.get(10));

        assertNotNull(path);
        assertTrue(path.size() > 0);

        for (Vertex vertex : path) {
            System.out.println(vertex);
        }

    }

    private void addLane(String laneId, int sourceLocNo, int destLocNo,
            int duration) {
        Edge lane = new Edge(laneId,nodes.get(sourceLocNo), nodes.get(destLocNo), duration );
        edges.add(lane);
    }
}

4-4 Test results

result.png