第一题: 剑指 Offer 12. 矩阵中的路径
LeetCode: 剑指 Offer 12. 矩阵中的路径
描述:
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
例如，在下面的 3×4 的矩阵中包含单词 “ABCCED”（单词中的字母已标出）。
解题思路:
- 这里使用回溯解法.
- 创建一个二维的
boolean数组, 记录当前哪些鲁走过. 如果当前已经走过了, 直接返回false- 如果当前遍历的字符不是要求的单词中的字符, 那么也返回
false- 如果当前遍历到
word的最后一个字符, 表示能够找到这么一条路径, 返回true- 当遍历到
board[i][j]的时候, 将该位置的boolean数组置为true, 在回溯的时候, 将该boolean置回false- 递归要从四个方向去递归,
(i+1,j) , (i,j+1) , (i-1,j) , (i, j-1)
代码实现:
class Solution {
public boolean exist(char[][] board, String word) {
boolean[][] tmp = new boolean[board.length][board[0].length];
for (int i = 0; i < board.length; i++) {
for(int j = 0; j < board[0].length; j++) {
if(dfs(board,word,tmp,i,j,0)){
return true;
}
}
}
return false;
}
public boolean dfs(char[][] board, String word,boolean[][] tmp, int i, int j, int index) {
// 如果坐标不合法 返回false
// 如果对应的字符不一致, 返回false
// 如果已经被使用过了, 返回false
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || word.charAt(index) != board[i][j] || tmp[i][j]){
return false;
}
// 这里表示有一条路径了
if (index == word.length()-1) {
return true;
}
tmp[i][j] = true;
// 这里从四个方向去找, 只要有一条满足了, 就为true
boolean ans = dfs(board,word,tmp,i+1,j,index+1) || dfs(board,word,tmp,i,j+1,index+1) || dfs(board,word,tmp,i-1,j,index+1) || dfs(board,word,tmp,i,j-1,index+1);
tmp[i][j] = false;
return ans;
}
}
第二题: 279. 完全平方数
LeetCode: 279. 完全平方数
描述:
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
解题思路:
- 动态规划解题
- 状态 F(i) : 和为 i 的完全平方数的最少数量
- 状态转移方程: F(i) = Math.min( F( i - j * j ) + 1, F(i) )
- 初始状态: F(0) = 0
- 返回结果: F(n)
代码实现:
class Solution {
public int numSquares(int n) {
int[] dp = new int[n+1];
dp[0] = 0;
for(int i = 1; i <= n ; i++) {
// 这里首先要让他是最坏的情况. 例如dp[3] = 1 + 1 + 1 = 3
dp[i] = i;
for(int j = 1; j*j <= i ; j++) {
dp[i] = Math.min(dp[i - j * j] + 1, dp[i]);
}
}
return dp[n];
}
}
第三题: 96. 不同的二叉搜索树
LeetCode: 96. 不同的二叉搜索树
描述:
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
解题思路:
- 使用动态规划解题
- 状态 F(i) : i个节点存在的二叉排序树的个数
- 状态转移方程:
- 当 j 为根节点时候, 左子树的节点为
j-1个, 右子树的节点为i-j个- F(i) += F(j-1) * F(i-j)
- 初始状态 F(0) = 1, F(1) = 1
- 返回结果: F(n)
代码实现:
class Solution {
public int numTrees(int n) {
int[] dp = new int[n+1];
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i < n + 1; i++) {
for(int j = 1; j < i + 1; j++) {
dp[i] += dp[j-1] * dp[i-j];
}
}
return dp[n];
}
}
第四题: 98. 验证二叉搜索树
LeetCode: 98. 验证二叉搜索树
描述:
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
解题思路:
- 这里使用中序遍历的方式
- 每次比较当前根节点值是否大于该节点的值, 如果不大于, 表示中序遍历不是有序的, 就返回false
- 分别遍历左右子树.
- 注意题目中给的返回, int会溢出
代码实现:
class Solution {
private long pre = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
if(root == null) return true;
if(!isValidBST(root.left)) {
return false;
}
if(root.val <= pre) {
return false;
}
pre = root.val;
return isValidBST(root.right);
}
}
第五题: 5. 最长回文子串
LeetCode: 5. 最长回文子串
描述:
给你一个字符串 s，找到 s 中最长的回文子串。
解题思路:
- 这里使用动态规划解题
- 状态 F(i,j) : i到j, 是否是回文串
- 状态转移方程:
- i == j, dp[i][j] = true
- i + 1 == j, dp[i][j] = s.charAt(i) == s.charAt(j)
- dp[i][j] = s.charAt(i) == s.charAt(j) && dp[i+1][j-1]
- 初始状态: i == j, dp[i][j] = true
- 返回结果, 最长的 j - i + 1, 返回 s.substring(i,j+1)
代码实现:
class Solution {
public String longestPalindrome(String s) {
if(s.length() == 1) return s;
boolean[][] dp = new boolean[s.length()][s.length()];
int maxLen = 1;
String ans = new String();
// 注意这里的遍历, 从后往前来
for(int i = s.length()-1; i >= 0; i--) {
for(int j = i; j < s.length(); j++) {
if(i == j) dp[i][j] = true;
else if(i+1 == j) dp[i][j] = s.charAt(i) == s.charAt(j);
else dp[i][j] = s.charAt(i) == s.charAt(j) && dp[i+1][j-1];
if(dp[i][j]){
if(j - i + 1 >= maxLen) {
maxLen = j - i + 1;
ans = s.substring(i,j+1);
}
}
}
}
return ans;
}
}
第六题: 647. 回文子串
LeetCode: 647. 回文子串
描述:
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
解题思路:
- 同上一题一样, 也是动态规划
- 这题只需要把满足要求的count++一下
代码实现:
class Solution {
public int countSubstrings(String s) {
boolean[][] dp = new boolean[s.length()][s.length()];
int count = 0;
for(int i = s.length() - 1; i >= 0; i--) {
for(int j = i; j < s.length(); j++) {
if(i == j) {
count++;
dp[i][j] = true;
}else if(i+1 == j && s.charAt(i) == s.charAt(j)) {
count++;
dp[i][j] = true;
}else if(i+1 < j && s.charAt(i) == s.charAt(j) && dp[i+1][j-1]) {
count++;
dp[i][j] = true;
}
}
}
return count;
}
}
转载：https://blog.csdn.net/wwzzzzzzzzzzzzz/article/details/125705437
查看评论