leetCode答题报告之5道基础题II
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
我们来看下这两题的题目和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.
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.
就是题目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));
}
}