单词接龙
字典 wordList 中从单词 beginWord_ _和 endWord 的 **转换序列 **是一个按下述规格形成的序列：
- 序列中第一个单词是 beginWord 。
- 序列中最后一个单词是 endWord 。
- 每次转换只能改变一个字母。
- 转换过程中的中间单词必须是字典 wordList 中的单词。
给你两个单词_ 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
提示：
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 200
- 0 <= matrix[i][j] <= 231 - 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"
提示：
- 1 <= s.length <= 1000
- s 由英文字母（小写和大写）、',' 和 '.' 组成
- 1 <= numRows <= 1000
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();
}
}
本文内容到此结束了， 如有收获欢迎点赞
标签：String,int,矩阵,len,length,接龙,beginWord,endWord,刷题 From： https://blog.51cto.com/zhanjq/6037172