[数据结构与算法]2021-08-03

64. 求1+2+…+n

题目要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

算法思想：

• if(A && B) // 若 A 为 false ，则 B 的判断不会执行（即短路），直接判定 A && B 为 false；
• if(A || B) // 若 A 为 true ，则 B 的判断不会执行（即短路），直接判定 A || B 为 true；
  本题中，n > 1 && sumNums(n - 1) // 当 n = 1 时 n > 1 不成立 ，此时 “短路” ，终止后续递归。

代码：

class Solution {
    public int sumNums(int n) {
        //判断大于0是为了把前后都变为bool表达式
        boolean x = n>1 && (n+=sumNums(n-1))>0;
        return n;
    }
}

55 - II. 平衡二叉树

代码：

写一个函数计算树的高度。首先判断该二叉树的左右子树高度是否满足要求，然后判断左右子树是否为二叉平衡树。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null)    return true;
        if(Math.abs(height(root.left)-height(root.right)) <= 1)
            return isBalanced(root.left) && isBalanced(root.right);
        return false;
    }
    int height(TreeNode root){
        if(root == null)    return 0;
        return Math.max(height(root.left),height(root.right))+1;
    }
}

法二：

1.若节点左右子树高度差满足平衡二叉树定义，返回节点深度，否则返回-1。

class Solution {
    public boolean isBalanced(TreeNode root) {
        return recur(root) != -1;
    }
    //该函数的作用：若节点左右子树高度差满足平衡二叉树的定义，则返回节点的深度，若不满足则返回-1；
    int recur(TreeNode root){
        if(root == null)
            return 0;
        int left = recur(root.left);
        if(left == -1) return -1;
        int right = recur(root.right);
        if(right == -1) return -1;
        return Math.abs(left-right) < 2 ? Math.max(left,right)+1 : -1;
    }
}

19. 正则表达式匹配

代码：

算法思想见注释。

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length()+1, n = p.length()+1;
        //dp[i][j]表示s的前i个字母和p的前j个字母是否匹配
        boolean[][] dp = new boolean[m][n];
        //dp[0][0]代表两个空字符串，返回true
        dp[0][0] = true;
        //初始化dp[0][j]，只有当偶数位全为*时返回true
        for(int j=2; j<n; j+=2){
            dp[0][j] = dp[0][j-2] && p.charAt(j-1)=='*';
        }
        for(int i = 1; i < m; ++i){
            for(int j = 1; j < n; ++j){
                //当p的当前字符为*时，有三种情况可以返回true：
                //1.*前的字符出现零次,即s的前i个字符与p的前j-2个字符相同；
                //2.*前的字符出现多次，即s的前i-1个字符与p的前j个字符匹配成功，且s的第i个字符与p的第j-1个字符相同；
                //3.*前的字符为'.',且'.'出现多次，即s的前i-1个字符与p的前j个字符匹配成功且p的第j-1个字符为.
                if(p.charAt(j-1) == '*'){
                    dp[i][j] = dp[i][j-2] || dp[i-1][j]&&s.charAt(i-1)==p.charAt(j-2)
                    || dp[i-1][j]&&p.charAt(j-2)=='.';
                }
                //当p的当前字符不为*时，有两种情况可以返回true：
                //1.s的第i个字符与p的第j个字符相同，且s的前i-1个字符与p的前j-1个字符匹配成功
                //2.p的第j个字符是'.'，且s的前i-1个字符与p的前j-1个字符匹配成功
                else{
                    dp[i][j] = s.charAt(i-1)==p.charAt(j-1)&&dp[i-1][j-1] || p.charAt(j-1)=='.'&&dp[i-1][j-1];
                }
            }
        }
        return dp[m-1][n-1];
    }
}