“This is the third day of my participation in the Gwen Challenge in November. Check out the details: The last Gwen Challenge in 2021.”

Hello everyone, I am quick-frozen fish 🐟, a front end of water system 💦, like colorful whistle 💐, continuous sand sculpture 🌲, I am a good brother of the next door Cold grass Whale, I just started to write an article. If you like my article, you can follow ➕ to like it, inject energy into me, and grow with me

Preface 🌧 ️

Algorithms are unfamiliar and familiar to the front-end people, and often we don’t value them as much as the back-end engineers do. But in fact, algorithms have an unshakable position for every programmer.

Because the development process is to convert the actual problem into the computer can recognize the instructions, that is, “data structure” said, “design the data structure, in the application of algorithms on the line”.

The quality of writing instructions will directly affect the performance of the program, and instructions are composed of data structure and algorithm, so the design of data structure and algorithm basically determines the quality of the final program.

In addition, when reading the source code, the lack of understanding of algorithms and data structures makes it difficult to understand why the author wrote the way he did.

In today’s environment, algorithms have become an indispensable skill for front-end engineers. If we want to move beyond being application engineers writing business code, we need to understand algorithms and data structures.

Of course, learning is also focused, as the front end we do not need to fully grasp the algorithm like back-end development, some of the more partial, not practical type and solution method, as long as a little understanding.

The title 🦀

417. Pacific Atlantic current problems

The difficulty of medium

Given a matrix of m x n nonnegative integers to represent the heights of cells on a continent. The Pacific Ocean is on the left and upper boundary of the continents, while the Atlantic Ocean is on the right and lower boundary of the continents.

It is stipulated that water can only flow in four directions: up, down, left and right, and can only flow from high to low or at the same height.

Find the coordinates of the land units where water flows to both the Pacific and Atlantic oceans.

Tip:

  1. The order of output coordinates is not important

  2. M and n are both less than 150

Example:

Given the following 5x5 matrix: Pacific ~ ~ ~ ~ ~ ~ 1 2 3 (5) * 2 ~ 3 3 (4) (4) * 2 ~ 4 (5) 3 1 * 2 ~ (6) (7) ~ (5) 1, 4, 5 * 1 1 2 4 * * * * * * to: [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (pictured above with parentheses unit).Copy the code

🌵

  • Think of a matrix as a graph.

  • To traverse the map upstream from the coastline, you can trace the coordinates of an ocean.

How to solve the problem 🐂

  • Create two new matrices and separate the coordinates that can be saved to the two oceans.

  • From the shoreline, multi-pipe, simultaneously depth-first traversal diagram, filling the matrix above. (Like casting a wide net)

  • Walk d through the two matrices to find coordinates that can be left over to the Atlantic and Pacific oceans.

Source 🔥

/ * * *@param {number[][]} heights
 * @return {number[][]}* /
var pacificAtlantic = function(heights) {
    console.log(heights)
   const matrix=heights
   if(! matrix || ! matrix[0]) {return[]; }/ / line
   const m=matrix.length
   / / column
   const n=matrix[0].length;
   const flow1=Array.from({length:m},() = >new Array(n).fill(false))
   const flow2=Array.from({length:m},() = >new Array(n).fill(false))
    
    const dfs=(r,c,flow) = >{
        flow[r][c]=true;
        [[r-1,c],[r+1,c],[r,c-1],[r,c+1]].forEach(([nr,nc]) = >{
            if(
                // Make sure it's in the matrix
                nr >= 0 && nr < m &&
                nc >= 0 && nc < n && 
                // Ensure that no access has been made! flow[nr][nc] &&// Be sure to swim against the currentmatrix[nr][nc] >= matrix[r][c] ){ dfs(nr,nc,flow); }})}// Up the river along the shoreline
    for(let r=0; r<m; r+=1){
        dfs(r,0,flow1)
        dfs(r,n-1,flow2)
    }
    for(let c=0; c<n; c+=1){
        dfs(0,c,flow1);
        dfs(m-1,c,flow2);
    }
    // Collect coordinates that can be saved up to two oceans
    const res=[];
    for(let r=0; r<m; r+=1) {for(let c=0; c<n; c+=1) {if(flow1[r][c] && flow2[r][c]){ res.push([r,c]); }}}return res
};
Copy the code

Time complexity :O(m* N)

Space complexity :O(m* N)

Conclusion 🌞

So the “LeetCode” 417- Pacific Atlantic water flow problem ⚡️ is over, there is no shortcut to algorithm, can only write more practice, more summary, the purpose of the article is actually very simple, is to urge myself to complete algorithm practice and summary and output, dishes are not important, but love 🔥, I hope everyone can like my essay, and I also hope to know more like-minded friends through the article. If you also like to toss, welcome to add my friend, sand sculpture together, together progress.

Making 🤖 : sudongyu

Personal blog 👨💻: Frozen fish blog

Vx 👦 : sudongyuer

Write in the last

Guys, if you like my words, give 🐟🐟 a thumbs up 👍 or follow ➕ to support me the most.

Add me on wechat: Sudongyuer, invite you into the group and learning the front together, become a better engineer ~ (group of qr code here – > front to go to bed early, qr code has expired, see the links to the boiling point in the comments, I will put the latest qr code in the comments section, of course, can also add me WeChat I pull you into the group, after all, I also am interesting front end, I also not bad 🌟 ~