第一题: 剑指 Offer 12. 矩阵中的路径

LeetCode: 剑指 Offer 12. 矩阵中的路径

描述:
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

例如，在下面的 3×4 的矩阵中包含单词 “ABCCED”（单词中的字母已标出）。

解题思路:

1. 这里使用回溯解法.
2. 创建一个二维的 boolean数组, 记录当前哪些鲁走过. 如果当前已经走过了, 直接返回 false
3. 如果当前遍历的字符不是要求的单词中的字符, 那么也返回 false
4. 如果当前遍历到 word的最后一个字符, 表示能够找到这么一条路径, 返回 true
5. 当遍历到 board[i][j] 的时候, 将该位置的 boolean 数组置为 true , 在回溯的时候, 将该boolean 置回 false
6. 递归要从四个方向去递归, (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 不是。

解题思路:

1. 动态规划解题
2. 状态 F(i) : 和为 i 的完全平方数的最少数量
3. 状态转移方程: F(i) = Math.min( F( i - j * j ) + 1, F(i) )
4. 初始状态: F(0) = 0
5. 返回结果: 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 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

解题思路:

1. 使用动态规划解题
2. 状态 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 ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

• 节点的左子树只包含 小于 当前节点的数。
• 节点的右子树只包含 大于 当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

解题思路:

1. 这里使用中序遍历的方式
2. 每次比较当前根节点值是否大于该节点的值, 如果不大于, 表示中序遍历不是有序的, 就返回false
3. 分别遍历左右子树.
4. 注意题目中给的返回, 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 中最长的回文子串。

解题思路:

1. 这里使用动态规划解题
2. 状态 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 ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

解题思路:

1. 同上一题一样, 也是动态规划
2. 这题只需要把满足要求的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;
    }
}