leetCode解题报告5道题(四)

报告5道题(四)"/>

leetCode解题报告5道题(四)

题目一：

Longest Consecutive Sequence

 

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

题意：给你一个数组，让你求出最大的连续序列的长度，我们的第一反应肯定都是排序，但是看到它最后一句话的要求“你的算法比较复杂度是O(n)的”，但是我一直不敢确定我的算法的复杂度是O(n)，但是AC过了，如果没记错HashMap是基于红黑树的吧？那么它的插入应该是O(lgN)，这样的话我这个算法应该复杂度是O(NlogN)，如果你在这题上有自己的见解，希望可以给我留言，让我也学习一下！

分析：居然这个题目要我们求的是最大连续序列的长度，有重复的数字怎么办？又考虑到算法的效率，我们采用HashMap来存储对应的数字，重复的数字就不会被存储下来了，首先我们初始化Map集合，以数组中的值作为key, 所有的value都初始化为1

要查询一个数的最大连续序列，其实无非就是循环它的左侧，再循环它的右侧，两边去查找，直到值不存在于Map集合中，这时候这个数还有它的左右两边的那些数所能组成的最大连续序列就确定了，因此它左右侧的值也可以不用再求解了（Map中的value置为-1表示不需要求解的值。），如果这步漏了会出现TLE哦！！

Longest Consecutive Sequence

AC代码：

package copylist;import java.util.HashMap;
import java.util.Map;
/*** * @Description:  [求最大连续序列长度]* @Author:       [胖虎]   * @CreateDate:   [2014-4-5 下午3:12:21]* @CsdnUrl:      []*/
public class Solution {Map<Integer,Integer> map = new HashMap<Integer,Integer>();public int longestConsecutive(int[] num) {if (num.length == 0)return 0;/*初始化Map集合*/for (int i=0; i<num.length; ++i){map.put(num[i], 1);}return findMaxNum(num);}public int findMaxNum(int[] arrays){int max = Integer.MIN_VALUE;/*判断数组中的所有元素*/for (int i=0; i<arrays.length; ++i){int sum = 0;int key = arrays[i]; //取出对应的值（即map中的key）//如果这个key还没有被求解过if (map.get(key) != -1){map.put(key, -1);	//置为已求解过sum++;				/*求左右两侧*/int left = key - 1;int right = key + 1;while (map.containsKey(left) && map.get(left) != -1){map.put(left, -1);left = left - 1;sum++;}while (map.containsKey(right) && map.get(right) != -1){map.put(right, -1);right = right + 1;sum++;}}if (sum > max){max = sum;}}return max;}
}

题目二：

Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

分析：这题是判断给定字符串是否是回文串的，要我们只考虑字母和数字哈，其他的字符都当成不存在就可以了。还有字母的话忽略大小写。

个人觉得这就是考ASCII码表吧！

我们只要两个下标一个从左往右(leftIndex) , 一个从右往左(rightIndex), 如果当前遇到的是非字母或者数字的字符的话，对应下标做增(leftIndex)或者减(rightIndex), 直到leftIndex < rightIndex就结束了整个字符串的所有字符的访问。

java中，如果你要判断一个字符是字母或者数字可以用这个函数：Character.isLetterOrDigit(char c)

以下代码，为了凸显ASCII码，我不用java自带的这个函数哈！

ASCII码表图：

Valid Palindrome

AC代码：

public class Solution {public boolean isPalindrome(String s) {int len = s.length();if (len == 0)return true;/*初始化左右两个下标*/int leftIndex = 0;int rightIndex = len-1;/*迭代, 结束的条件是leftIndex < rightIndex 表示整个字符串的字符都访问过了*/while (rightIndex >= leftIndex){/*得到当前左右下标各自指向的字符的ASCII码*/int leftInt = (int)(s.charAt(leftIndex));int rightInt = (int)(s.charAt(rightIndex));/*如果左下标指向的字符不属于数字或者字母，下标往后移*/if (( !(65 <= leftInt && leftInt <= 90) && !(97 <= leftInt && leftInt <= 122) && !(48 <= leftInt && leftInt <= 57) )){leftIndex++;    continue;}/*如果右下标指向的字符不属于数字或者字母，下标往前移*/if (( !(65 <= rightInt && rightInt<= 90) && !(97 <= rightInt && rightInt<= 122) && !(48 <= rightInt && rightInt <= 57) )){rightIndex--;continue;}/*判断条件，字母的话忽略大小写*/if( (rightInt == leftInt)|| Math.abs(rightInt - leftInt) == 32 ){leftIndex++;rightIndex--;}else{return false;}}return true;}
}

题目三：

Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

       1/ \2   3

Return 6.

分析：题目给我们一颗二叉树，要求我们在二叉树中要选出一个结点(start)到另一个结点(end)，使得这条路径上的所有结点的值加起来达到最大。

情况图解（只画出几种情况，其他的都类似）：

由上这些情况，我们规定Null结点的值为Interget.MIN_VALUE（无穷小） 

情况1： 代表的是左子树的值已经可以比左子树+根结点的值 还有 右子树+根结点的值来得大了，这时候这条路径就可以作为最大值的路径了

情况2： 子树中的某个区域构成的路径大于整个二叉树的其他路径总和

情况3： 二叉树的左右两边+根结点的值是最大值

情况4：二叉树中只有一个结点（无论值是正，负）都只能是最大值

情况5：最大值过根结点

ps:为了方便大家看几种情况数，才画了这么多个情况，实际上1,2,3种情况就够了哈！

解题思路： 这题主要是情况有很多种，一定要每种情况都分析到，不然的话，写代码很容易出错.

下面让我们来分析下解题的思路：

1、Null结点对应的值为无穷小（Interget.MIN_VALUE），保证情况4的成立

2、每个子树里面都有可能“左+根+右”的值大于“左+根”或者“右加根”，则我们可以求出这个值（max），代表这个子树所能达到的最大值。这个值再跟现在已经得到的最大值做比较。

3、步骤2已经讲了每个子树都有一个最大值，如果这个最大值满足了最大值路径，那么赋值给当前最大值，否则的话，我们需要得到一个这棵子树过一边的最大值（即“root.val + 左子树的最大值” 或者 “root.val + 右子树的最大值” 或者 "root.val")，因为如果你这棵子树没办法构成最大值路径的话，那么只能由你的上一级树再去做操作了，但是如果你交给上一级树做操作，那么你就不能再同时经过左右两个子树了，你只能选择如果root.val + leftsum > root.val (左+中 > 中) 并且 root.val + leftsum > root.val + rightsum （左+中 > 右）那么你就返回经过“左子树”和“根结点”的这条路径的值给上一级。

递归处理，最后就可以得到结果了，不知道有没有描述清楚，代码里面会注释的哈，看代码理解吧！！

Binary Tree Maximum Path Sum 

AC代码：

/*** Definition for binary tree* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
public class Solution {/*当前得到的最大值*/private int maxSum = Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {solveSum(root);return maxSum;}/*递归函数*/public int solveSum(TreeNode root) {/*如果为Null结点，返回无穷大*/if (root == null)return Integer.MIN_VALUE;int max = 0;int leftsum = solveSum(root.left);int rightsum = solveSum(root.right);int sumLeftRootRight = root.val;/*下面是为了求出当前这个树中可能的最大路径(可能包括左+中+右)*///beginif (leftsum > 0){sumLeftRootRight += leftsum;}if (rightsum > 0){sumLeftRootRight += rightsum;}//求出这个树中的最大路径值max = leftsum > rightsum ? leftsum > sumLeftRootRight ? leftsum : sumLeftRootRight : rightsum > sumLeftRootRight ? rightsum : sumLeftRootRight;//如果这个值大于当前最大值if (max > maxSum){maxSum = max;}//end//把经过根结点的一条最大值的路径返回给上一级//注意:居然要给上一级，那么过这棵子树的根结点的路径的情况//1. 就一个root结点就最大了//2. 过了root结点，再过root.left子树的最大路径，最大//3. 过了root结点，再过root.right子树的最大路径，最大//passed root node maxsum;int rootMaxSum = root.val;rootMaxSum += leftsum > rightsum ? leftsum > 0 ? leftsum : 0 : rightsum > 0 ? rightsum : 0;return rootMaxSum;}
}

题目四：

Reverse Words in a String

 

Given an input string, reverse the string word by word.

For example,
Given s = "the sky is blue",
return "blue is sky the".

分析：题目给我们一个字符串，然后让我们把字符串里面的单词做一下颠倒，每个单词间用空格隔开，但是没有跟我们讲可能出现多少个空格。因此这个题目要考虑的主要是用例的情况

1、s == null    -->  return null;

2、s == "" || s== " "     -->  return "";

3、s == "   a   b "      --> return "b a";

主要的几种情况分析出来之后，我们就知道，给我们的这个待处理的字符串，必须要前trim() 掉两旁的空格。

然后我们选择遍历这个字符串s,把相邻的空格去掉（因为相邻的空格，题目要求之后输出也只输出一个，不能多输出！）

这样子这题目，基本上已经很清楚要怎么做了，由于我用的是JAVA实现，所以我想谈及一下关于题目中用到的

知识点：String,StringBuffer,StringBuilder的区别？

相信大家看到过很多比较String和StringBuffer区别的文章，也明白这两者的区别，然而自从Java 5.0发布以后，我们的比较列表上将多出一个对象了，这就是StringBuilder类。String类是不可变类，任何对String的改变都会引发新的String对象的生成；而StringBuffer则是可变类，任何对它所指代的字符串的改变都不会产生新的对象，可变和不可变类这一对对象已经齐全了，那么为什么还要引入新的StringBuilder类干吗？

如果你读过《Think in Java》，而且对里面描述HashTable和HashMap区别的那部分章节比较熟悉的话，你一定也明白了原因所在。对，就是支持线程同步保证线程安全而导致性能下降的问题。HashTable是线程安全的，很多方法都是synchronized方法，而HashMap不是线程安全的，但其在单线程程序中的性能比HashTable要高。StringBuffer和StringBuilder类的区别也在于此，新引入的StringBuilder类不是线程安全的，但其在单线程中的性能比StringBuffer高。

AC代码：

public class Solution {public String reverseWords(String s) {if (s == null || s.equals("")){return s;}StringBuffer buffer = new StringBuffer();s = s.trim();//取出两边的空格/*把相邻的空格去除掉*/for (int i=0; i<s.length(); ++i){if (s.charAt(i) == ' ' && buffer.toString().charAt(buffer.toString().length()-1) == ' '){;}else{buffer.append(s.charAt(i));}}/*存储逆序的字符串*/StringBuilder reverseStr = new StringBuilder("");/*根据空格来做分割*/String[] arrays = buffer.toString().split(" ");for (int i=arrays.length-1; i>=0; --i){if (!reverseStr.toString().equals("")){reverseStr.append(" ");}reverseStr.append(arrays[i]);}return reverseStr.toString();}
}

题目五：

Unique Binary Search Trees II

(这个题目的姐妹题：Unique Binary Search Trees I的题解) 

Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.

For example,
Given n = 3, your program should return all 5 unique BST's shown below.

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

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

分析：题目给我们一个数字n, 要让我们求出从 1....n的这些数字所能构成的BST(二叉搜索树)的情况，把这些情况构成的二叉树的结构作为返回值返回！

我们知道，数字n，它能构成的二叉搜索树的情况无外乎为下面几种

当rootValue = 1, 则 左子树 ：null   右子树为：2 ~~ n 的组合（递归一下）

当rootValue = 3, 则 左子树 ：1 ~~ 2 的组合    右子树为： 4 ~~ n的组合

当rootValue = n, 则 左子树 ：1 ~~ n-1的组合   右子树为：null

这样，我们知道，如果要找出一个数字n的所有二叉搜索树的情况，那么就是要考虑到 根结点分别为：1 ~~ n的情况，然后每种情况下的  左右子树也还是一个组合， 比如当根结点值为i 的时候，左子树的情况有m种， 右子树的情况有k种，那么根结点值为 i 时，所能构成的二叉搜索树的总数就是 m * k种。

有了这个思路之后，我们直接看代码理解吧！！

AC代码：

package copylist;import java.util.ArrayList;class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val = x;left = null;right = null;}
}
/*** * @Description:  [leetcode : Unique Binary Search Trees II ]* @Author:       [胖虎]   * @CreateDate:   [2014-4-9 上午11:01:15]* @CsdnUrl:      []*/
public class Solution {public ArrayList<TreeNode> generateTrees(int n) {ArrayList<TreeNode> result = new ArrayList<TreeNode>();if (n == 0){result.add(null);return result;}result = generateTree(1,n);return result;}/*生成left ~~ right的二叉搜索树的情况*/public ArrayList<TreeNode> generateTree(int left, int right){ArrayList<TreeNode> result = new ArrayList<TreeNode>();if (right < left){result.add(null);return result;}/*遍历root值分别为 left ~~ right的情况*/for (int rootvalue=left; rootvalue<=right; ++rootvalue){/*把左，右子树各自可能的情况分别放在两个集合中.*/ArrayList<TreeNode> leftResult = generateTree(left, rootvalue-1);ArrayList<TreeNode> rightResult = generateTree(rootvalue+1, right);/*两个集合的组合数为最后的结果*/for (int j=0; j<leftResult.size(); ++j){for (int k=0; k<rightResult.size(); ++k){TreeNode rootNode = new TreeNode(rootvalue);rootNode.left = leftResult.get(j);rootNode.right = rightResult.get(k);result.add(rootNode);}}}return result;}public static void main(String[] args) {Solution s = new Solution();ArrayList<TreeNode> list = s.generateTrees(4);}
}