Problem 1: the number of islands

Given a matrix of 01’s, 1 represents land, 0 represents ocean, and if two 1s are next to each other, then they belong to the same island. We’re only thinking about up, down, right, and left as neighbors. Island: Adjacent lands can form an island (adjacent: up, down, left and right) determine the number of islands.

The question bank address: www.nowcoder.com/practice/0c…

Ideas:

DFS is used for traversal. When land is found, continue to search for the upper and lower parts of this position. If land is still found, change the ‘1’ representing land in the matrix to ‘0’. In this way, the land will not be counted again in the subsequent traversal.

BFS, DFS introduction, can focus on a look

Reference links: developer.aliyun.com/article/756…

Depth First Search (DFS) and Breath First Search (Breath First Search) are two very important algorithms in graph theory. They are widely used in topology sorting, pathfinding (mazes), Search engines, crawlers and so on

Js implementation

*/ function solve(grid) {let lands = 0 for (let h = 0; h < grid.length; h++) { for (let w = 0; w < grid[0].length; w++) { if (grid[h][w] == 1) { lands++ dfs(grid, h, w) } } } return lands } function dfs(grid, h, w) { grid[h][w] = 0 if (h - 1 >= 0 && grid[h - 1][w] == 1) { dfs(grid, h - 1, w) } if (h + 1 < grid.length && grid[h + 1][w] == 1) { dfs(grid, h + 1, w) } if (w - 1 >= 0 && grid[h][w - 1] == 1) { dfs(grid, h, w - 1) } if (w + 1 < grid[0].length && grid[h][w + 1] == 1) { dfs(grid, h, w + 1) } }Copy the code

Problem two: word division

Given a non-empty string s and a list wordDict containing non-empty words, determine whether S can be split by Spaces into one or more words that appear in the dictionary.

Description:

  • You can reuse the words in the dictionary when splitting.
  • You can assume that there are no duplicate words in the dictionary

The sample

Input: s = "leetcode", wordDict = ["leet", "code"] Output: true Explanation: Returns true because "leetcode" can be split into "leetcode".Copy the code

Question bank address: leetcode.com/problems/wo…

The train of thought: the dynamic programming, the reference links: zhuanlan.zhihu.com/p/365698607

Js:

/ * * *@param {string} s
 * @param {string[]} wordDict
 * @return {boolean}* /
 var wordBreak = function(s, wordDict) {
  const wordSet = new Set(wordDict)
  const dp = new Array(s.length + 1).fill(false)
  dp[0] = true
  for(let i=1; i<=s.length; i++) {for(let j=0; j<i; j++) {if(dp[j] && wordSet.has(s.substring(j, i))) {
        dp[i] = true
        break}}}return dp[s.length]
    
};
Copy the code

Problem three: Reverse linked lists

Enter a linked list, reverse the list, output the new list header.

The question bank address: www.nowcoder.com/practice/75…

Input: {1,2,3} return value: {3,2,1}Copy the code

Ideas: