526互联

11.22打卡

发布时间 2023-11-22 16:05:13作者: forever_fate

1.  不同的二叉搜索树（96）

假设 n 个节点存在二叉排序树的个数是 G (n)，令 f(i) 为以 i 为根的二叉搜索树的个数，则
G(n)= f(1) + f(2) + f(3) + f(4) + ... + f(n)

当 i 为根节点时，其左子树节点个数为 i-1 个，右子树节点为 n-i，则
f(i)=G(i−1)∗G(n−i)f(i) 

综合两个公式可以得到 卡特兰数 公式
G(n)=G(0)∗G(n−1)+G(1)∗(n−2)+...+G(n−1)∗G(0)G(n) = G(0)*G(n-1)+G(1)*(n-2)+...+G(n-1)*G(0)G(n)=G(0)∗G(n−1)+G(1)∗(n−2)+...+G(n−1)∗G(0)

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];

        
    }
}

2. 交错字符串（97）

给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。

两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
  char[] cs1=s1.toCharArray();
        char[] cs2= s2.toCharArray();
        char[] cs3 = s3.toCharArray();
        int n=s1.length(),m=s2.length(),l=s3.length();
        if(n+m!=l) return false;
        boolean[][] f = new boolean[n+10][n+10];
        f[0][0]= true;
        for (int i = 1; i <=n && f[i-1][0] ; i++) {
            f[i][0]=cs1[i-1]==cs3[i-1];
        }
        for (int i = 1; i <=m && f[0][i-1] ; i++) {
            f[0][i]=cs2[i-1]==cs3[i-1];
        }
        for (int i = 1; i <=n ; i++) {
            for (int j = 1; j <=m ; j++) {
                f[i][j]=(f[i-1][j]&&cs1[i-1]==cs3[i+j-1])||(cs2[j-1]==cs3[i+j-1]&&f[i][j-1]);
            }
        }
        return f[n][m];
    }
}

3. 验证二叉搜索树（98）

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

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

  • 节点的左子树只包含 小于 当前节点的数。
  • 节点的右子树只包含 大于 当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private long pre = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if (root == null)
            return true;
            // 访问左子树
        if (!isValidBST(root.left)) {
            return false;
        }
// 访问当前节点：如果当前节点小于等于中序遍历的前一个节点，说明不满足BST，返回 false；否则继续遍历。
        if (root.val <= pre)
            return false;
        pre = root.val;
        // 更新上一节点，访问右子树
        return isValidBST(root.right);

    }
}

4. 恢复二叉搜索树（99）

给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
       TreeNode a=null,b=null,last= null;
    public void recoverTree(TreeNode root) {
      dfsrecoverTree(root);//找到逆序对互换
        int val  =a.val;
        a.val=b.val;
        b.val=val;
    }

    private void dfsrecoverTree(TreeNode root) {
        if(root==null)return;
        dfsrecoverTree(root.left);
        if(last!=null&& last.val>root.val){
            if(a==null){
                //是首次满足条件，即 a == null，此时上一节点 last 必然是两个互换节点之一，而当前 root 只能说是待定，因为有可能是 last 和 root 实现互换，也有可能是 last 和后续的某个节点实现互换。 此时有 a = last, b = root
                a=last;
                b=root;
            }else {
                //若是非首次满足条件，即 a != null，此时当前节点 root 必然是两个互换节点中的另外一个。 此时有 b = root
                b=root;
            }
        }
        last=root;
        dfsrecoverTree(root.right);
    
    }
}