What is “ARTS”? Algorithm: at least one Leetcode Algorithm problem per week; Review: Read and comment on at least one technical article in English; Tip: Learn at least one technical skill; Share: To Share a technical article with ideas and thoughts.


Algorithm

LeetCode 317. Shortest Distance from All Buildings

Ideas on a 2 d matrix analysis the shortest path problem, suggest a similar first consider breadth first search the shortest path problem, why not here said the depth first search, we pray for the shortest distance between two coordinates, if use deep search, a path search down you cannot guarantee the shortest path through the point is the current, If you are forced to find all possible paths, this time complexity is particularly high; For a wide search, we only need an array to record the coordinates we pass through, ensuring that each point is accessed only once, and this access is the shortest distance from the point to the starting point.

This problem has a particularly odd places, for the first time do generally is unexpected, title description is for a space (0), (1) to all buildings of the shortest distance, we will take it for granted from start to find open architecture, so that each space to find it again, and finally choose the youngest in all space, but have you thought about a problem, Is there more buildings or more empty Spaces on this map? If you want to, and saw a few test cases, you will find that the number of bits (0) over the figure than (1) the number of construction, every search is equivalent to iterate through all the points, if searched from space as a starting point, then the search is greater than the number of search from construction as the starting point, so it need a bit of reverse thinking, from the building began to search, One difference is that we need to add up the distance from each empty space to the building, which is not hard to understand


Reference code

private class Pair {
    int x, y;
    Pair(int x, int y) {
        this.x = x;
        this.y = y; }}private int[] dirX = {0.0.1, -1};
private int[] dirY = {1, -1.0.0};

public int shortestDistance(int[][] grid) {
    if (grid.length == 0 || grid[0].length == 0) {
        return -1;
    }
    
    int m = grid.length;
    int n = grid[0].length;
    
    int[][] distance = new int[m][n];
    int[][] counts = new int[m][n];
    
    int count = 0;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (grid[i][j] == 1) { bfsMark(grid, distance, counts, i, j); count++; }}}int min = Integer.MAX_VALUE;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) { 
            if(distance[i][j] ! =0&& counts[i][j] == count) { min = Math.min(min, distance[i][j]); }}}return min == Integer.MAX_VALUE ? -1 : min;
}

private void bfsMark(int[][] grid, int[][] distance, int[][] counts, int i, int j) {
    Queue<Pair> queue = new LinkedList<>();
    
    int m = grid.length;
    int n = grid[0].length;
    
    boolean[][] visited = new boolean[m][n];
    
    queue.offer(new Pair(i, j));
    visited[i][j] = true;
    
    int length = 1;
    while(! queue.isEmpty()) {int size = queue.size();
        
        for (int s = 0; s < size; ++s) {
            Pair cur = queue.poll();
            
            for (int k = 0; k < 4; ++k) {
                int curX = cur.x + dirX[k];
                int curY = cur.y + dirY[k];

                if (curX < 0 || curY < 0|| curX >= m || curY >= n || visited[curX][curY] || grid[curX][curY] ! =0) {
                    continue;
                }

                queue.offer(new Pair(curX, curY));
                distance[curX][curY] += length;
                visited[curX][curY] = true; counts[curX][curY]++; } } length++; }}Copy the code


Review

Some tips for learning computer languages:

The One Programming Language to Rule Them All

The question of which language to learn tends to attract people’s attention. In the general view, it is better to learn a language that is quick and effective. It is better to use a wide range of languages. People tend to be in a rush. If they can learn something that takes them a year, it’s better if they can learn it in a month. They think about how to take shortcuts and choose things that are easy for them to learn. Over time, this will become a habit, and you may look at yourself and actually learn very little.

The author mentioned in the article, the best language is logic, how to understand this sentence, in fact, all languages to the bottom of the computer will be transformed into a sequence of instructions, there is no difference, we want to let the computer to help us solve problems, we need to understand the computer’s “thinking logic”. The biggest difference between man and computer communication and interpersonal communication lies in the degree of detailed description for a problem, we communicate with normal people, we don’t need to describe particularly fine, especially specific, as if to tell a person how to go to a place, we will say “go straight ahead to the XX road, turn right, then take the XX bus, to XX stand it”, Because people’s understanding of the world or the physical state of things is essentially the same, we can all read, we can recognize bus stops, you can say a few nouns, I’ve seen them most of the time, you don’t need to add. Computer is not the case, but it just start what also don’t know, it can’t read, don’t know what is right, also don’t know what is the bus, if it is the first time doing this, you have to be very careful and tell it without missing each details, of course, you can make it memory, but you have to tell it, don’t know it by default. You don’t have to deal with a computer very often, and when you suddenly ask it to do something, you sometimes feel at a loss, but that’s normal. We should learn to use the thinking logic of the computer to deal with the computer, this is the computer major to do. Dealing with a computer for a long time, understand the logic of it, you will find this way to let you very dependable, because it is said that one is one, it is very honest, as long as according to certain steps we will be able to get some results, and it has never made a mistake, if you write applications appear problem, the 99.999999% is your problem, you don’t need to guess who is the problem, You just have to find and solve the problem.

How to learn computer thinking logic, or basic ah, this is a said hundreds of times will not change the topic, from the basic learning, learning those will not change the algorithm and data structure, design ideas, code logic can let you not be abandoned by this era, but also let you see the truth in this era.


Tip

Vagrant is a tool for quickly building virtual environments. It runs on Oracle’s VirtualBox, and its configuration is written in the Vagrant File, which records some of its common configurations

Vagrant.configure("2") do |config|
  config.vm.hostname = "ubuntu"
  config.vm.box = "base"
  Assign a private IP address so that the virtual machine's localhost can be accessed from the HOST
  config.vm.network "private_network", ip: "192.168.50.4"
  # Share files
  config.vm.synced_folder "path in host..."."path in virtal machine"
  config.vm.provider "virtualbox" do |vb|
    vb.name = "pyh3326"
    vb.gui = false
    vb.memory = "1024"
  end
end
Copy the code

Vagrant’s initialization, login, reload, and shutdown commands are:

>$ vagrant up
>$ vagrant ssh
>$ vagrant reload
>$ vagrant halt
Copy the code

Remember not to shut down the virtual machine


Share

Recently, I saw the Bloom Filter data structure, and I was often asked about it in interviews. This time, I will write it in the share

Analysis of principle and application of Bloom filter