java实现关键字搜索匹配算法 java进阶搜索 |
您所在的位置：网站首页 › word查找数字和字母 › java实现关键字搜索匹配算法 java进阶搜索 |
java实现关键字搜索匹配算法 java进阶搜索
文章目录1.搜索问题79.单词搜索212.单词搜索Ⅱ130.被围绕的区域200.岛屿的数量22.括号生成113. 路径总和Ⅱ剑指 Offer 13. 机器人的运动范围 1.搜索问题79.单词搜索 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。 示例一：
示例二：
示例三：
思路： 回溯算法+状态重置 使用布尔变量marked判断是否找到字符 代码实现： class Solution { int rows, cols; // 定义行和列 char[][] board; char[] word; boolean[][] marked; // 用来存储是否搜索到字母 int[][] next = new int[][]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; //用来搜索上下左右，顺序不重要 public boolean exist(char[][] board, String word) { this.rows = board.length; this.cols = board[0].length; this.board = board; this.word = word.toCharArray(); this.marked = new boolean[rows][cols]; for(int row = 0; row < rows; row++){ for(int col = 0; col < cols; col++){ if(search(0, row, col)){ return true; } } } return false; } public boolean search(int pos, int row, int col){ //pos为word的位置，row和col为行列 // 先写明特殊情况 if(row < 0 || row >= rows || col < 0 || col >= cols || marked[row][col]){ return false; } if(board[row][col] != word[pos]){ //找不到这个字母 return false; } if(pos == word.length-1){ //搜索到最后一位 return true; } marked[row][col] = true; for(int[] ne : next){ // 上下左右搜索 if(search(pos+1, row+ne[0], col+ne[1])){ return true; } } marked[row][col] = false; return false; } }另一种写法： class Solution { private boolean find = false; // 返回最终结果 public boolean exist(char[][] board, String word) { if (board == null) return false; int m = board.length, n = board[0].length; boolean[][] visited = new boolean[m][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { dfs(i, j, board, word, visited, 0); } } return find; } private void dfs(int i, int j, char[][] board, String word, boolean[][] visited, int pos) { // visited表示当前格子是否被搜索过 // pos记录目标单词的字符索引，只有棋盘字符和pos指向字符一致时，才继续搜索 // 终止条件即为pos = word.length() - 1 int m = board.length, n = board[0].length; // 超出边界，已访问过，已找到, 棋盘字符与目标字符不一致 if (i < 0 || j < 0 || i >= m || j >= n || visited[i][j] || find || board[i][j] != word.charAt(pos)) return; // 终止条件 if (pos == word.length() - 1) { find = true; return ; } visited[i][j] = true; // 修改当前状态 dfs(i + 1, j, board, word, visited, pos + 1); dfs(i - 1, j, board, word, visited, pos + 1); dfs(i, j + 1, board, word, visited, pos + 1); dfs(i, j - 1, board, word, visited, pos + 1); visited[i][j] = false; // 撤销修改 } }212.单词搜索Ⅱ这道题力扣设为困难，可以在Ⅰ的基础上进行解题，只是复杂度有点高。 给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words，找出所有同时在二维网格和字典中出现的单词。 单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。 示例一：
示例二：
解题思想： 在第一题的基础上搜索单词，仍然是DFS回溯，需要加一层循环，遍历String数组中的每一个单词，这就导致了复杂度的变大。 这里使用了HashSet去重，然后需要将HashSet转化为list: List list = new ArrayList(res); // 将hashset转为list代码实现： class Solution { int rows, cols; // 定义行和列 char[][] board; char[] word; boolean[][] marked; // 用来存储是否搜索到字母 int[][] next = new int[][]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; //用来搜索上下左右，顺序不重要 public List findWords(char[][] board, String[] words) { this.rows = board.length; this.cols = board[0].length; this.board = board; this.marked = new boolean[rows][cols]; HashSet res = new HashSet(); //使用hashset去重 for(int row = 0; row < rows; row++){ for(int col = 0; col < cols; col++){ for(int i = 0; i < words.length; i++){ this.word = words[i].toCharArray(); dfs(res, 0, row, col); } } } List list = new ArrayList(res); // 将hashset转为list return list; } public void dfs(HashSet res, int pos, int row, int col){ if(row < 0 || row >= rows || col < 0 || col >= cols || marked[row][col]){ return; } if(board[row][col] != word[pos]){ return; } if(pos == word.length-1){ String s = String.valueOf(word); // char字符数组转String res.add(s); return; } marked[row][col] = true; // 判断字符是否搜索过 for(int[] ne : next){ // 上下左右搜索,左去过就不能再右回来 dfs(res, pos+1, row+ne[0], col+ne[1]); } marked[row][col] = false; } }按上一题的另一种写法则超时： class Solution { public List findWords(char[][] board, String[] words) { int m = board.length, n = board[0].length; boolean[][] visited = new boolean[m][n]; HashSet res = new HashSet(); //使用hashset去重 char[] word; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < words.length; k++) { word = words[k].toCharArray(); dfs(i, j, 0, board, word, visited, res); } } } List list = new ArrayList(res); // 将hashset转为list return list; } private void dfs (int i, int j, int pos, char[][] board, char[] word, boolean[][] visited, HashSet res) { int m = board.length, n = board[0].length; if (i < 0 || j < 0 || i >= m || j >= n || visited[i][j] || board[i][j] != word[pos]) { return ; } if (pos == word.length - 1) { String s = String.valueOf(word); res.add(s); return ; } visited[i][j] = true; dfs(i + 1, j, pos + 1, board, word, visited, res); dfs(i - 1, j, pos + 1, board, word, visited, res); dfs(i, j + 1, pos + 1, board, word, visited, res); dfs(i, j - 1, pos + 1, board, word, visited, res); visited[i][j] = false; } }130.被围绕的区域给你一个 m x n 的矩阵 board ，由若干字符 ‘X’ 和 ‘O’ ，找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。 示例一：
示例二： 输入：board = [["X"]] 输出：[["X"]]思路： 首先对边界上每一个’O’做深度优先搜索，将与其相连的所有’O’改为’A’。然后遍历矩阵，将矩阵中所有’O’改为’X’,将矩阵中所有’A’变为’O’ 代码实现： class Solution { public void solve(char[][] board) { if(board == null || board.length==0) return; int row = board.length; int col = board[0].length; // 遍历四条边界，将与其相连的所有O改为A for(int i =0; i < row; i++){ //遍历第一列和最后一列 dfs(board, i, 0); dfs(board, i, col-1); } for(int j =0; j < col; j++){ //遍历第一行和最后一行 dfs(board, 0, j); dfs(board, row-1, j); } // 遍历整个board，将O改为X，将A改为O for(int i = 0; i < row; i++){ for(int j = 0; j < col; j++){ if(board[i][j] == 'O') board[i][j] = 'X'; if(board[i][j] == 'A') board[i][j] = 'O'; } } return; } public void dfs(char[][] board, int i, int j){ if(i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j]!='O') return; board[i][j] = 'A'; dfs(board, i-1, j); dfs(board, i+1, j); dfs(board, i, j-1); dfs(board, i, j+1); return; } }200.岛屿的数量给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 此外，你可以假设该网格的四条边均被水包围。 示例一： 输入：grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] 输出：1示例二： 输入：grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] 输出：3解题思路： 遍历整个网格，如果位置为1，以其为起点深度优先搜索，搜索的过程中，每个搜索到的1都会标记成0，最后岛屿的数量就是深度优先搜索的次数。 代码实现： class Solution { public int numIslands(char[][] grid) { int row = grid.length; int col = grid[0].length; int nums = 0; if(grid == null || row == 0) return 0; for(int i = 0; i < row; i++){ for(int j = 0; j < col; j++){ // 循环遍历整个网格，遇到’1‘，nums++; if(grid[i][j] == '1'){ nums++; dfs(grid, i , j); // 以该点为起点，深度优先搜索，遇到1就改为0 } } } return nums; } public void dfs(char[][] grid, int i, int j){ int row = grid.length; int col = grid[0].length; if(i < 0 || j < 0 || i >= row || j >= col || grid[i][j]=='0'){ return; } grid[i][j] = '0'; dfs(grid, i-1, j); dfs(grid, i+1, j); dfs(grid, i, j-1); dfs(grid, i, j+1); } }22.括号生成数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。 有效括号组合需满足：左括号必须以正确的顺序闭合。 示例一： 输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]示例二： 输入：n = 1 输出：["()"]思路： DFS+剪枝 剪枝：先左括号后右括号 代码实现： class Solution { public List generateParenthesis(int n) { List res = new ArrayList(); dfs(res, "", n, n); return res; } public void dfs(List res, String ans, int i, int j){ if(i == 0 && j == 0){ // 左右括号都不剩余了，递归终止 res.add(ans); return; } if(i > 0){ // 如果左括号还剩余的话，可以拼接左括号 dfs(res, ans+"(", i-1, j); } if(j > i){ // 如果右括号剩余多于左括号剩余的话，可以拼接右括号 dfs(res, ans+")", i, j-1); } } }113. 路径总和Ⅱ给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。 叶子节点 是指没有子节点的节点。 示例一：
示例二：
示例 3： 输入：root = [1,2], targetSum = 0 输出：[]思路： DFS+回溯，判断当为叶子节点且和为targetSum加入到LinkedList中，二叉树类的问题使用LinkedList存储，然后dfs左子树和右子树 枚举每一条从根节点到叶子节点的路径。当我们遍历到叶子节点，且此时路径和恰为目标和时，我们就找到了一条满足条件的路径 // 与二叉树相关的构建LinkedList List res = new LinkedList(); Deque path = new LinkedList();代码实现： class Solution { // 与二叉树相关的构建LinkedList List res = new LinkedList(); Deque path = new LinkedList(); public List pathSum(TreeNode root, int targetSum) { dfs(root, targetSum); return res; } public void dfs(TreeNode root, int targetSum){ if(root == null){ return; } path.offerLast(root.val); //Java LinkedList offerLast()将指定的元素插入LinkedList的末尾 targetSum -= root.val; if(root.left == null && root.right == null && targetSum == 0){ // 叶子结点，且等于targetSum res.add(new LinkedList(path)); } dfs(root.left, targetSum); dfs(root.right, targetSum); path.pollLast(); // 回溯 } }剑指 Offer 13. 机器人的运动范围
思路： 常规深度优先搜索算法，超出边界或者不满足条件或者已经使用过，则直接return。 然后修改visited数组，上下左右回溯。 class Solution { public int movingCount(int m, int n, int k) { // 深度优先搜索 boolean[][] visited = new boolean[m][n]; int res = dfs(0, 0, m, n, k, visited); return res; } private int dfs(int i, int j, int m, int n, int k, boolean[][] visited) { if (i < 0 || i >= m || j < 0 || j >= n || (i / 10 + i % 10 + j / 10 + j % 10) > k || visited[i][j]) { return 0; } visited[i][j] = true; return dfs(i + 1, j, m, n, k, visited) + dfs(i - 1, j, m, n, k, visited) + dfs(i, j + 1, m, n, k, visited) + dfs(i, j - 1, m, n, k, visited) + 1; } }
|
【本文地址】
公司简介
联系我们
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |