leetCode解题报告5道题(二)

末蓝、 2022-08-26 08:13 160阅读 0赞

leetcode上比较简单的几道题，不想分开写几篇博文来记录哈，所以写在一起了!!

虽然几道题都比较简单，但感觉自己写得不好，希望博文如果被哪位大神看到，可以留言下写下你的做法！

题目一：

### Maximum Depth of Binary Tree ###

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

题意：给你一个二叉树的根结点，求出树的深度！（递归）

/**
     * Definition for binary tree
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public int maxDepth(TreeNode root) {
            return findMaxDepth(root);
        }
        
        public int findMaxDepth(TreeNode node){
            if (node == null)   //结点为null，返回0
                return 0;
            if (node.left == null && node.right == null)   //如果为叶子结点：返回深度1
                return 1;
            int leftDepth = findMaxDepth(node.left);    //求出左子树的最大深度
            int rightDepth = findMaxDepth(node.right);  //求出右子树的最大深度
            return leftDepth > rightDepth ? leftDepth+1 : rightDepth+1; //比较左右子树的深度，取最大值+1 得出整个子树的深度
        }
    }

题目二：

### Sum Root to Leaf Numbers ###

Given a binary tree containing digits from `0-9` only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path `1->2->3` which represents the number `123`.

Find the total sum of all root-to-leaf numbers.

For example,

1
       / \
      2   3

The root-to-leaf path `1->2` represents the number `12`.  
The root-to-leaf path `1->3` represents the number `13`.

Return the sum = 12 + 13 = `25`.

题意:给你一棵二叉树，请你输出所有路径的和，路径上的结点的值连接起来组成这条路径的值（简单的递归算法）

/**
     * Definition for binary tree
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        
        public int calSum(TreeNode root, int sum){
            if (root == null)
                return sum;
            if (root.left == null && root.right == null) //循环结束条件
                return sum * 10 + root.val;
            int leftChildSum = 0;
            int rightChildSum = 0;
            if (root.left != null){
       //递归调用
                leftChildSum = calSum(root.left, sum * 10 + root.val);
            }
            if (root.right != null){
       //递归调用
                rightChildSum = calSum(root.right, sum * 10 + root.val);
            }
            
            return (leftChildSum + rightChildSum);
        }
        
        public int sumNumbers(TreeNode root) {
            if (root == null)
                return 0;
            return calSum(root, 0);
        }
    }

题目三：

### Unique Binary Search Trees ###

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,  
Given n = 3, there are a total of 5 unique BST's.

1         3     3      2      1
        \       /     /      / \      \
         3     2     1      1   3      2
        /     /       \                 \
       2     1         2                 3

题意：给你一个数n, 这个n表示二叉树拥有1,2,....,n这n个节点，让你去求不相等的又满足BST（二叉搜索树）特性的二叉树有多少种情况。

分析：递归问题哈

这道题是递归的意思在这里面  
 \* 情况:  
 \* n=1  : 只有一种可能，则返回1  
 \* n=2  : 两种可能返回2;  
 \* n=3  : 返回5;  
 \* n>3  : 我们知道，如果一个问题特别大，我们会想办法把它分解成小问题来解决  
 \* 我们取特殊情况n=4来做下分析  
 \* 如果n=4, 二叉树根结点的值可以是：1,2,3,4这四种情况  
 \*   
 \* 设root.val 用 i来表示, for循环 i < n, 左子树上的结点数量: i-1, 右子树上的结点数量: n-i  
 \*   
 \* 而当i=1的时候，左子树结点Number: i-1=0 ，右子树结点Number: n-i=4-1=3  
 \* 此时这种情况得到的二叉树个数便转换成了求右边3个结点拥有的情况数量(递归)  
 \*   
 \* 而当i = 2的时候，左子树结点Number: i-1=1 ，右子树结点Number: n-i=4-2=2  
 \* 此时这种情况得到的二叉树个数便转换成了求左边情况的个数\*右边情况的个数（组合数学）  
 \* \[当然如果左边或者右边有一方为0的话，就返回一支子树的数量就行了\]  
 \*   
 \* 而当i = 3的时候，左子树结点Number: i-1=2 ，右子树结点Number: n-i=4-3=1  
 \* 此时这种情况得到的二叉树个数便转换成了求左边情况的个数\*右边情况的个数（组合数学）  
 \* \[当然如果左边或者右边有一方为0的话，就返回一支子树的数量就行了\]  
 \*   
 \* 而当i = 4的时候，左子树结点Number: i-1=3 ，右子树结点Number: n-i=4-4=0  
 \* 此时这种情况得到的二叉树个数便转换成了求左边3个结点拥有的情况数量(递归)  
 \*   
 \* 最终所有情况加起来就是 n = 4的所有二叉树数目

AC代码：

package copylist;
    
    /**
     * 
     * @Description:  [leetcode Unique Binary Search Trees]
     * @Author:       [胖虎]   
     * @CreateDate:   [2014-4-3 下午8:19:44]
     * @CsdnUrl:      [http://blog.csdn.net/ljphhj]
     */
    public class Solution {
        public int numTrees(int n) {
            
            if (n == 0 || n == 1)
                return n;
                
            return calSum(n);
        }
        public int calSum(int n){
            int sum = 0;
            if (n == 1)
                return 1;
            if (n == 2)
                return 2;
            if (n == 3)
                return 5;
            /*求出所有root.val = i的情况，然后相加就是n的二叉树的所有情况*/
            for (int i=1; i<=n; ++i){
                sum += deal(i-1,n-i);
            }
            return sum;
        }
        /*
         * 计算左右子树的情况数,并求出整体的情况数
         * 
         * */
        public int deal(int leftnumber, int rightnumber){
            int sumleft = 0;
            int sumright = 0;
            
            int sum = 0;
            if (leftnumber == 1 || leftnumber == 0)
            	sumleft += leftnumber;
            else{
            	sumleft += calSum(leftnumber);
            }
            if (rightnumber == 1 || rightnumber == 0)
            	sumright += rightnumber;
            else{
            	sumright += calSum(rightnumber);
            }
            /*如果有一个子树上没有节点，则返回另一个子树的数量即可*/
            if (sumleft == 0)
            	return sumright;
            if (sumright == 0)
            	return sumleft;
            
            sum = sumleft * sumright;	//组合数学：总数等于左右子树的情况数的乘积
            
            return sum;
        }
        
        public static void main(String[] args) {
        	Solution s = new Solution();
    		System.out.println(s.numTrees(1));
    		System.out.println(s.numTrees(2));
    		System.out.println(s.numTrees(3));
    		System.out.println(s.numTrees(4));
    		System.out.println(s.numTrees(5));
    	}
    }

题目四：

### N-Queens && N-Queens II ###

这两个题目是类似的：都是N皇后问题，我之前有一篇文章写的就是总结递归问题和分治思想的，那里面对N皇后问题进行了很详细的解说，所以这里就不重复了。

博文链接：[本文专注于<递归算法和分治思想>\[胖虎学习算法系列\]][Link 1][http://blog.csdn.net/ljphhj/article/details/22799189][Link 1]

我们来看下这两题的题目和AC代码：

题目1（N\-queens）：

The n\-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

![8-queens.png][]

Given an integer n, return all distinct solutions to the n\-queens puzzle.

Each solution contains a distinct board configuration of the n\-queens' placement, where `'Q'` and `'.'` both indicate a queen and an empty space respectively.

For example,  
There exist two distinct solutions to the 4-queens puzzle:

[
     [".Q..",  // Solution 1
      "...Q",
      "Q...",
      "..Q."],
    
     ["..Q.",  // Solution 2
      "Q...",
      "...Q",
      ".Q.."]
    ]

AC代码：

package copylist;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    
    /**
     * 典型的N皇后问题
     * @Description:  [leetcode N-Queens]
     * @Author:       [胖虎]   
     * @CreateDate:   [2014-4-3 下午8:19:44]
     * @CsdnUrl:      [http://blog.csdn.net/ljphhj]
     */
    public class Solution {
    	private ArrayList<String[]> result = new ArrayList<String[]>();
        private int[][] conflicts;
        private int[] queens;	//int[row] = col
    	private int count = 0;
    	private int n;
    	
    	public ArrayList<String[]> solveNQueens(int n) {
    		if(n == 0)
    			return result;
    		//init
    		conflicts = new int[n][n];
    		queens = new int[n];
    		this.n = n;
    		solve(0);
    		return result;
        }
    	
        public void solve(int row){
        	
        	for (int col=0; col<n; ++col){
        		if (conflicts[row][col] == 0){
        			queens[row] = col;
        			//add conflict
        			for (int i=row+1; i<n; ++i){
        				//"|"
        				conflicts[i][col]++;
        				//"\"
        				if ((col - (i - row)) >= 0){
        					conflicts[i][(col - (i - row))]++;
        				}
        				//"/"
        				if ((col + (i - row)) < n){
        					conflicts[i][(col + (i - row))]++;
        				}
        			}
        			
        			if (row == n-1){
        				String[] strings = new String[n];
        				for(int i=0; i<n; ++i){
        					strings[i] = "";
        					for (int j=0; j<n; ++j){
        						if (j == queens[i]){
        							strings[i] += "Q";
        						}else{
        							strings[i] += ".";
        						}
        					}
        				}
        				result.add(strings);
        			}else{
        				solve(row+1);
        			}
        			
        			//remove conflict
        			for (int i=row+1; i<n; ++i){
        				//"|"
        				conflicts[i][col]--;
        				//"\"
        				if ((col - (i - row)) >= 0){
        					conflicts[i][(col - (i - row))]--;
        				}
        				//"/"
        				if ((col + (i - row)) < n){
        					conflicts[i][(col + (i - row))]--;
        				}
        			}
        		}
        	}
        	
        }
        
        
        public static void main(String[] args) {
        	Solution s = new Solution();
        	ArrayList<String[]> list = s.solveNQueens(8);
        	int i=0;
        	for (String[] string : list) {
        		System.out.println("解法" + ++i + "：");
    			for (String string2 : string) {
    				System.out.println(string2);
    			}
    		}
    	}
    }

题目2（N \-queens II ）：

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

![8-queens.png][]

就是题目1的答案哈，只不过它要返回的值是所有解的个数，我们都能得到所有解，还怕得不到个数么？

AC代码：

public class Solution {
        private int[][] conflicts;
    	private int count = 0;
    	private int n;
    	
    	public void solveNQueens(int n) {
    		if(n == 0)
    			return;
    		//init
    		conflicts = new int[n][n];
    		this.n = n;
    		solve(0);
        }
    	
        public void solve(int row){
        	
        	for (int col=0; col<n; ++col){
        		if (conflicts[row][col] == 0){
        			//add conflict
        			for (int i=row+1; i<n; ++i){
        				//"|"
        				conflicts[i][col]++;
        				//"\"
        				if ((col - (i - row)) >= 0){
        					conflicts[i][(col - (i - row))]++;
        				}
        				//"/"
        				if ((col + (i - row)) < n){
        					conflicts[i][(col + (i - row))]++;
        				}
        			}
        			
        			if (row == n-1){
        				count++;
        			}else{
        				solve(row+1);
        			}
        			
        			//remove conflict
        			for (int i=row+1; i<n; ++i){
        				//"|"
        				conflicts[i][col]--;
        				//"\"
        				if ((col - (i - row)) >= 0){
        					conflicts[i][(col - (i - row))]--;
        				}
        				//"/"
        				if ((col + (i - row)) < n){
        					conflicts[i][(col + (i - row))]--;
        				}
        			}
        		}
        	}
        	
        }
        public int totalNQueens(int n) {
            solveNQueens(n);
            return count;
        }
    }

题目五：

### Pow(x, n) ###

题目：Implement pow(x, n).

分析：要我们实现一个pow这样的函数，哈哈，用JAVA用惯了，突然要你实现api里面的其中一个函数，是不是觉得很无语哈，不过这题明显是有陷阱的

如果你用for循环，去做n次 x 的乘法运算，那肯定是会超时的，那如何算会比较快呢?

我们想到初高中的数学公式

1、X^n = (X^2) ^ (n/2) \[当n是偶数的时候\]

2、X^n = X \* (X^2) ^ ((n-1)/2) \[当n是奇数的时候\]

这样子我们就可以把这个问题转换成 递归或者分治思想这样的题目啦!

很奇妙吧！看AC代码哈~~

package copylist;
    /**
     * 
     * @Description:  [pow(x,n)的java实现代码]
     * @Author:       [胖虎]   
     * @CreateDate:   [2014-4-3 下午10:24:57]
     * @CsdnUrl:      [http://blog.csdn.net/ljphhj]
     */
    public class Solution {
        public double pow(double x, int n) {
        	//如果n<0 那么结果是等于 x^n的倒数,即 1/x^n
        	//为了方便运算，我们先把n统一成正数
            int y = n > 0 ? n : -n;
            if (n == 0){
            	// x^0 = 1;
            	return 1;
            }
            if (n == 1){
            	// x^1 = x;
            	return x;
            }
            double result;
            if (y % 2 == 0){
            	result = pow(x*x, y / 2);
            }else{
            	result = pow(x*x, (y-1) / 2) * x;
            }
            return n > 0 ? result : 1.0 / result;
        }
        
        public static void main(String[] args) {
        	System.out.println(new Solution().pow(34.00515, -3));
    	}
    }

[Link 1]: http://blog.csdn.net/ljphhj/article/details/22799189
[8-queens.png]: http://www.leetcode.com/wp-content/uploads/2012/03/8-queens.png