单词接龙
字典 wordList 中从单词 beginWord_ _和 endWord 的 **转换序列 **是一个按下述规格形成的序列：
给你两个单词_ beginWord _和 endWord 和一个字典 wordList ，找到从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0。示例 1：输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] 输出：5 解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。示例 2：输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"] 输出：0 解释：endWord "cog" 不在字典中，所以无法进行转换。
提示：
1 <= beginWord.length <= 10
endWord.length == beginWord.length
1 <= wordList.length <= 5000
wordList[i].length == beginWord.length
beginWord、endWord 和 wordList[i] 由小写英文字母组成
beginWord != endWord
wordList 中的所有字符串 互不相同
public class Solution { HashMap<String, List<String>> mapPositive = new HashMap<String, List<String>>(); HashMap<String, List<String>> mapNegative = new HashMap<String, List<String>>(); HashMap<String, Boolean> mapVisit = new HashMap<String, Boolean>(); int result = Integer.MAX_VALUE; public int ladderLength(String beginWord, String endWord, List<String> wordList) { for (int i = 0; i < wordList.size(); i++) { addWordToMap(wordList.get(i)); } addWordToMap(beginWord); mapVisit.put(beginWord, true); findEnd(beginWord, endWord, 1); if (result == Integer.MAX_VALUE) { return 0; } return result; } private void addWordToMap(String word) { int length = word.length(); if (length == 0) { return; } char[] chars = word.toCharArray(); for (int i = 0; i < length; i++) { char now = chars[i]; chars[i] = '*'; String regex = new String(chars); List<String> list; if (mapPositive.containsKey(word)) { list = mapPositive.get(word); } else { list = new ArrayList<String>(); mapPositive.put(word, list); } list.add(regex); if (mapNegative.containsKey(regex)) { list = mapNegative.get(regex); } else { list = new ArrayList<String>(); mapNegative.put(regex, list); } list.add(word); chars[i] = now; } mapVisit.put(word, false); } private void findEnd(String nowWord, String endWord, int nowStep) { if (endWord.equals(nowWord)) { if (nowStep < result) { result = nowStep; } return; } List<String> candidates = getCandidates(nowWord); if (candidates == null || candidates.size() == 0) { return; } for (int i = 0; i < candidates.size(); i++) { String now = candidates.get(i); mapVisit.put(now, true); findEnd(now, endWord, nowStep + 1); mapVisit.put(now, false); } } private List<String> getCandidates(String word) { List<String> list = mapPositive.get(word); if (list == null) { return new ArrayList<String>(); } Set<String> set = new HashSet<String>(); for (int i = 0; i < list.size(); i++) { String regex = list.get(i); List<String> regexList = mapNegative.get(regex); if (regexList == null) { continue; } for (int j = 0; j < regexList.size(); j++) { String now = regexList.get(j); if (mapVisit.get(now) == false) { set.add(now); } } } List<String> candidates = new ArrayList<String>(); for (String string : set) { candidates.add(string); } return candidates; }}
复制代码
矩阵中的最长递增路径
给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。对于每个单元格，你可以往上，下，左，右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。
示例 1：
输入：matrix = [[9,9,4],[6,6,8],[2,1,1]] 输出：4 解释：最长递增路径为 [1, 2, 6, 9]。示例 2：
输入：matrix = [[3,4,5],[3,2,6],[2,2,1]] 输出：4 解释：最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。示例 3：输入：matrix = [[1]] 输出：1
提示：
class Solution { public int longestIncreasingPath(int[][] matrix) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0) { return 0; } int max = 0; int row = matrix.length; int col = matrix[0].length; int[][] dp = new int[row][col]; for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { max = Math.max(max, loop(matrix, Integer.MIN_VALUE, dp, i, j)); } } return max; } private int loop(int[][] mat, int pre, int[][] dp, int i, int j) { if (i < 0 || j < 0 || i >= mat.length || j >= mat[0].length || mat[i][j] <= pre) { return 0; } if (dp[i][j] != 0) { return dp[i][j]; } int max = 0; max = Math.max(max, loop(mat, mat[i][j], dp, i - 1, j)); max = Math.max(max, loop(mat, mat[i][j], dp, i + 1, j)); max = Math.max(max, loop(mat, mat[i][j], dp, i, j - 1)); max = Math.max(max, loop(mat, mat[i][j], dp, i, j + 1)); dp[i][j] = max + 1; return dp[i][j]; }}
复制代码
Z 字形变换
将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：P A H N A P L S I I G Y I R 之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。请你实现这个将字符串进行指定行数变换的函数：string convert(string s, int numRows);
示例 1：输入：s = "PAYPALISHIRING", numRows = 3 输出："PAHNAPLSIIGYIR"示例 2：输入：s = "PAYPALISHIRING", numRows = 4 输出："PINALSIGYAHRPI" 解释： P I N A L S I G Y A H R P I 示例 3：输入：s = "A", numRows = 1 输出："A"
提示：
class Solution { public String convert(String s, int numRows) { if (numRows == 1) return s; int len = s.length(); if (len <= numRows) return s; int cycle_len = 2 * numRows - 2; int full_cycles = len / cycle_len; int left = len % cycle_len; StringBuilder r = new StringBuilder(); int i; for (i = 0; i < full_cycles; ++i) { r.append(s.charAt(i * cycle_len)); } if (left > 0) { r.append(s.charAt(i * cycle_len)); } for (i = 0; i < numRows - 2; ++i) { int j; for (j = 0; j < full_cycles; ++j) { r.append(s.charAt(j * cycle_len + i + 1)); r.append(s.charAt(j * cycle_len + i + 1 + cycle_len - 2 * (i + 1))); } if (left > 0) { if (j * cycle_len + i + 1 < len) r.append(s.charAt(j * cycle_len + i + 1)); if (j * cycle_len + i + 1 + cycle_len - 2 * (i + 1) < len) r.append(s.charAt(j * cycle_len + i + 1 + cycle_len - 2 * (i + 1))); } } for (i = 0; i < full_cycles; ++i) r.append(s.charAt(i * cycle_len + numRows - 1)); if (left >= numRows) r.append(s.charAt(i * cycle_len + numRows - 1)); return r.toString(); }}
复制代码
本文内容到此结束了，
如有收获欢迎点赞👍收藏💖关注✔️，您的鼓励是我最大的动力。
如有错误❌疑问💬欢迎各位大佬指出。
主页：共饮一杯无的博客汇总👨💻
保持热爱，奔赴下一场山海。🏃🏃🏃
评论