leetCode解题报告5道题(七)

- 日理万妓 2022-08-27 05:45 157阅读 0赞

### 题目一：Interleaving String ###

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,  
Given:  
s1 = `"aabcc"`,  
s2 = `"dbbca"`,

When s3 = `"aadbbcbcac"`, return true.  
When s3 = `"aadbbbaccc"`, return false.

**分析：**

这道题是一道明显的DP题目，由于在这之前DP类型做得比较少，所以这道题目可能分析得不是那么好，网友们见谅哈！

![SouthEast][]

居然题目是一个DP动态规划的题目，那么必定有一个状态转移方程式。

如果我们用一个boolean flags\[\]\[\] 二维数组来存储状态信息

flags\[i\]\[j\] 表示取S1中的前i个数和取S2中的前j个数

flags\[i\]\[j\] == true : 表示S3的前(i+j)长度的子串还是满足S1和S2交叉结合的

flags\[i\]\[j\] == false: 表示不满足

首先我们来讲下直到S3前面(i+j)长度的子串还满足可以由S1和S2交叉构成的

**条件是(flags\[i\]\[j-1\] == true && S2\[j-1\] == S3\[i+j-1\] ) || (flags\[i-1\]\[j\] == true && S1\[i-1\] == S3\[i+j-1\] )**

最后我们所要的结果就是当S1取S1.length长度，而S2取S2.length长度时，看是否满足，即flags\[S1.length\]\[S2.length\]是否为true

AC代码：

public class Solution {
        public boolean isInterleave(String s1, String s2, String s3) {
            int len1 = s1.length();
            int len2 = s2.length();
            int len3 = s3.length();
            //长度不等直接干掉
            if (len3 != (len2+len1)){
                return false;
            }
            //状态存储的二维数组
            boolean flags[][] = new boolean[len1+1][len2+1];
            flags[0][0] = true;
            
            for (int i=1; i<=len1; ++i){
                flags[i][0] = flags[i-1][0] && (s1.charAt(i-1) == s3.charAt(i-1));
            }
            for (int j=1; j<=len2; ++j){
                flags[0][j] = flags[0][j-1] && (s2.charAt(j-1) == s3.charAt(j-1));
            }
            
            for (int i=1; i<=len1; ++i){
                for (int j=1; j<=len2; ++j){
                    flags[i][j] = ((flags[i][j-1] && s2.charAt(j-1) == s3.charAt(i+j-1)) 
                            || (flags[i-1][j] && s1.charAt(i-1) == s3.charAt(i+j-1)));
                }
            }
            return flags[len1][len2];
        }
    }

### **题目二：Validate Binary Search Tree** ###

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

*  The left subtree of a node contains only nodes with keys less than the node's key.
 *  The right subtree of a node contains only nodes with keys greater than the node's key.
 *  Both the left and right subtrees must also be binary search trees.

confused what `"{1,#,2,3}"` means? [> read more on how binary tree is serialized on OJ.][read more on how binary tree is serialized on OJ.]

**分析：**

题目要求我们判断一下一棵树，是否满足搜索二叉树的性质:

1、树的左边的所有结点都不能大于根的值

2、树的右边的所有结点都不能小于根的值

这题还是比较简单的递归问题哈。只是要注意的情况如下

5             15

null  null    6     20

这种情况是不满足二叉搜索树的性质的，因为数值6在数值10的右侧，但6<10这样是不符合定义的。

因此当我们要判断左子树的时候，必须把

**左子树中所有结点与root结点的值做比较，如果其中有一个大于root结点的值，那么就不满足题意**

**右子树中所有结点与root结点的值做比较，如果其中一个小于root结点的值，那么也不满足题意。**

AC代码：

/**
     * Definition for binary tree
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public boolean isValidBST(TreeNode root) {
            if (root == null){
                return true;
            }
            if (root.left == null && root.right == null){
                return true;
            }
            
            return solveValidBST(root.left, true, root.val) && solveValidBST(root.right, false, root.val);
        }
        /**
         * root: 当前结点
         * isLeft: 属于根节点的左边还是右边
         * compareValue: 根结点的值
         */
        public boolean solveValidBST(TreeNode root, boolean isLeft, int compareValue){
            
            if (root == null){
                return true;
            }
            //1: 判断是否满足   左<中<右
            boolean flag = true;
            if (root.left != null && root.left.val >= root.val){
                flag = false;
            }
            if (root.right != null && root.right.val <= root.val){
                flag = false;
            }
            
            //2: 判断是否满足所有的左<根  和  所有的右>根
            if (isLeft){
                if (compareValue <= root.val){
                   flag = false; 
                }
            }else{
                if (compareValue >= root.val){
                   flag = false; 
                }
            }
            boolean leftSubTre = solveValidBST(root.left, isLeft, compareValue);
            boolean rightSubTre = solveValidBST(root.right, isLeft, compareValue);
            return flag && leftSubTre && rightSubTre;
        }
    }

### **题目三：** ###

### Sqrt(x) ###

Implement `int sqrt(int x)`.

Compute and return the square root of x.

**分析：**

题目要求我们计算出一个int类型的数值的开平方的结果(注意：要的结果也是int型，而并非是double哦！)

我们先来分析下一种**错误的解法TLE**:

**//如果数值x够大，所需的循环次数太多了**

**for (int i=0; i<=x; ++i)\{**

**if (i \* i == x)\{**

**return i;**

**\}**

**  if (i \* i > x)\{**

**            return i-1; **

** \}**

**\}**

因此我们必须想出一种更快的方法,我们将这些数和对应的开方的数写下来,观察一下规律！

![SouthEast 1][]

这样我们可以发现，数字1所能涵盖x数有3个，数字2能涵盖的x数有5个，数字3能涵盖的x数有7个.........

这样子我们要求一个数x的平方根的int值，只需要用x循环减去3,5,7,9......，并用num记录下当前是数字几了，直到x的值小于等于0，这时候这个num就是我们要得到的结果了。

AC代码：

public class Solution {
        public int sqrt(int x) {
            if (x == 0)
                return 0;
                
            int step = 3;
            int num = 1;
            x = x - step;
            while (x > 0){
                num++;
                step += 2;
                x -= step;
            }
            return num;
        }
    }

不能因为做题而做题哈，我们顺便看一下返回double类型的sqrt怎么写！

一个采用牛顿迭代法的函数
    double sqrt(double number) 
    {
            if(number<=0)return 0;
            //设置初始值i，i值越接近sqrt(number)，所需循环次数越少
            double i = 1; //一个快速算法是：int exp;double i=ldexp(frexp(number,&exp),(exp>>1));
            double j = number/i;
            while((i<j?j-i:i-j)>1e-9)//随着循环次数的增加，i与j将非常接近
            {
                    i = (i+j)/2;
                    j = number/i ;
            }
            return i;
    }
    
    原理见：
    
    泰勒级数展开法：f(x)=sqrt(x)在x=1处展开，得：
    f(x) = 1+(1/2)×(x-1)+(0.5)×(-0.5)/2!×(x-1)²+(0.5)×(-0.5)×(-1.5)/3!×(x-1)³……
    非常不建议使用级数展开，因为当数字比较大时收敛实在慢

### **题目四：** ###

### Recover Binary Search Tree ###

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:  
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

confused what `"{1,#,2,3}"` means? [> read more on how binary tree is serialized on OJ.][read more on how binary tree is serialized on OJ. 1]

**分析：**

题目给我们一棵树，这棵树中有两个结点的位置出现了错误（将它们两个的值交换之后就可以得到正确的二叉搜索树），让我们把这两个结点找出来，之后把它们交换得到正确的BST。要求不能够改变树原来的结构。

这道题目，我们分析下二叉搜索树的性质，可以知道，当我们用树的"中序遍历"遍历这棵树的时候，我们应该要得到一个呈增长的一个数列，但是如果这棵树有两个结点的值的位置不对的话，必定就会破坏这个增长数列。

举个例子

1    4

我们得到的中序遍历结果是: 1 ->  2  -> 4 （增长的趋势）

而如果是

4     1

我们得到的中序遍历结果是: 4 -> 2  -> 1 (没有呈增长趋势)

这样子我们需要调换的两个位置是哪两个呢，很明显应该是   4  和  1的位置。

根据这样分析，我们用一个stack来存储中序遍历的结果，最后依次从栈顶往下扫，当遇到值大于栈顶的，表示不满足增长的规律，然后再一直往下直到找到这些大于栈顶的这些数中，最大的一个。即为我们要交换的数，具体看代码

AC代码：

/**
     * Definition for binary tree
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
     /**
      * 作者：胖虎 
      * csdn: http://blog.csdn.net/ljphhj 
      */
    public class Solution {
        //存放值对应的结点
        private HashMap<Integer, TreeNode> map = new HashMap<Integer, TreeNode>();
        //栈：存放中序遍历的结果
        private Stack<Integer> stack = new Stack<Integer>();
        
        public void recoverTree(TreeNode root) {
            
            if (root == null || ((root.left == null) && (root.right == null))){
                return ;
            }
            
            MiddleOrderTralTree(root);
            int popNum = 0;
            if (!stack.empty()){
                popNum = stack.pop();
            }
            
            while (!stack.empty()){
                int nowNum = stack.pop();
                //存在了违反“增长趋势"的情况了.
                if (nowNum > popNum){
                    //栈的元素一直往下找，直到找到违反“增长趋势”的元素中最大的那一个
                    while (!stack.empty()){
                        int temp = stack.pop();
                        if (temp > popNum){
                            nowNum = temp;
                        }else{
                            break;
                        }
                    }
                    
                    TreeNode mistakeOne = (TreeNode)map.get(nowNum);
                    TreeNode mistakeTwo = (TreeNode)map.get(popNum);
                    int temp = mistakeOne.val;
                    mistakeOne.val = mistakeTwo.val;
                    mistakeTwo.val = temp;
                    return ;
                }
                popNum = nowNum;
            }
        }
        //中序遍历
        public void MiddleOrderTralTree(TreeNode root){
            if (root.left != null){
                MiddleOrderTralTree(root.left);
            }   
            //值放入栈中，并把 值，Object 存放到map中
            stack.push(root.val);
            map.put(root.val, root);
            
            if (root.right != null){
                MiddleOrderTralTree(root.right);
            }   
        }
        
    }

### **题目五：** ###

### Climbing Stairs ###

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

**分析:**

这个题目是很早的一个题目了，考察的其实就是斐波拉切数列的变形哈.

我们知道斐波那契数列的话是

**f(0) = 0;**

**f(1) = 1;**

**f(n) = f(n-1) + f(n-2)  (n >= 2)**

我们分析下我们这道题目：

如果N=0时，自然为0种

如果N=1时，这个家伙只有一种爬楼梯的方法

如果N=2时，他的选择有：1.一步步的爬   2.两步的 这样就有两种

但N=3时，他的选择可以是  1、先爬1步(然后剩下的处理跟两个台阶的一样咯)    2、先爬2步(剩下的处理跟一个台阶的一样咯)

.......

**我们可以推导出这样的式子**

**f(0) = 0;**

**f(1) = 1;**

**f(2) = 2;**

**f(n) = f(n-1) + f(n-2);   (n>=3)**

AC代码： （千万别想着用递归的方法，会TLE）

public class Solution {
        private int nums[];
        public int climbStairs(int n) {
            if (n == 0 || n == 1 || n == 2){
                return n;
            }
            nums = new int[n+1];
            nums[0] = 0;
            nums[1] = 1;
            nums[2] = 2;
            for (int i=3; i<=n; ++i){
                nums[i] = nums[i-1] + nums[i-2];
            }
            return nums[n];
        }
    }

[SouthEast]: /images/20220824/7b110563f0fd46e19ff2d63342e1ae2a.png
[read more on how binary tree is serialized on OJ.]: http://oj.leetcode.com/problems/validate-binary-search-tree/#
[SouthEast 1]: /images/20220824/1de318dea838441d9a2513d4376bef38.png
[read more on how binary tree is serialized on OJ. 1]: http://oj.leetcode.com/problems/recover-binary-search-tree/#