leetCode解题报告5道题(十)

题目一：Valid Number

Validate if a given string is numeric.

Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true

Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.

分析：

这道题目很容易理解，但是主要要考虑到多种情况哈.

下面我们来分析下有哪些情况需要考虑到

1、空格不能出现在数字之间(即一开始我们要消除掉字符串前后的"空格",那么之后如果再出现空格那就不满足题意了)

2、小数点和e最多只能出现一次("." 和"e" (或者"E")), 如："..2"和"0e1e1"这样的字符串都是不合法的.

3、字符e之前必须有数字，e之后也要有数字, 如: "e1"或者"0e"这样的字符串也不合法

4、正负号要么出现在数字的最前面，要么出现在紧接着e后面("+"或者"-" 只能在“去除空格之后的字符串”的首字母出现 或者 紧跟在"e"的后面出现) 如： "  +123.1  " 或者 "  -12  " 或者 " 0e+6 "或者"  10e-2 "这些都是合法的

5、"e"后面的数字不能是小数(即e之后不能出现小数点)

分析完这些所有的情况，那么我们就可以开始写代码了。看代码理解吧~~~~

AC代码：

题目二：Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

分析：

这道题目的意思挺容易理解的，我们主要讲下解法:

老规矩，我喜欢通过例子来说明解法哈，如果 A=[2, 0, 2, 0, 1]       len = A.length;

我们先从第一个位置A[0]开始，然后我们用一个pos来记录现在第一个位置所能到达的最远距离。

pos = A[0] = 2;

然后我们用一个index (index < len)来记录当前的下标位置，第一个A[0]处理了之后 index++, 

如果index > pos 则表示现在这个index的位置已经是 第一个元素所不能到达的地方了，这样子的话就不可能走到最后一个元素，则返回false

如果index <= pos 则 如果 A[index] + i > pos (第一个元素能走到更远的位置了)，更新一下pos的值。

AC代码：

题目三：Jump Game II

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

分析：

这题跟上面的那道题比较像，只不过有点像贪心法，每一步都要走最远的那种情况，所以每一次我们都需要把所有能走到的所有位置先走一遍，看哪个最远。

AC代码：

题目四：Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

分析：

这道题目可以看做是一个动态规划的题目吧，我们举个例子

如果grid[][]=

2  5  6  10

我们从右下方的元素开始，往前推

当我们判断到  grid[2][2] == 6 时，它到右下方结点的距离为 6 + 10 = 16， 存入grid[2][2]=16;

当我们判断到 10 上方的那个元素 grid[1][3] == 3时，它到右下方结点的距离为 3 + 10 = 13， 存入grid[1][3]=13;

当判断到 grid[1][2] == 1时， 它到右下方的距离，就是 grid[1][3] 和 grid[2][2]中比较小的那个值 再加上自身的值，即grid[1][2] += min{grid[1][3] (当前元素右边的元素) , grid[2][2] (当前元素下边的元素)};

AC代码：

题目五：Largest Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.

分析：

1、暴力法：

初看题目，很容易给人想到的方法就是暴力法，也就是说对每个 index < len 都找到从index 往左 和 往右，直到height[index] > height[left]  和 height[index] > height[right], 然后 把int temp = height[index] * (right - left + 1) ， 如果temp > max, 则更新max的值，但是这样的话一下子就TLE超时了。

TLE代码：

2、借助辅助栈：

居然暴力法不行，那我们可以知道它主要的时间消耗其实是在寻找左边的left, 和右边的right上面，这样的话有没有什么办法把这块时间节省下来，在我们遍历的过程中确定好left, right的值呢？

我们采用辅助栈( 栈中存放矩形的下标 )来做这道题目可以解决它哈。

算法描述：

1、定义一个空栈

2、遍历数组 index < n

2.1、遍历到index的时候，如果“栈为空”或者height[stack.peek()] <= height[index], 这时候把 index 压入到stack中，并index++

2.2、如果不满足2.1的情况，那么证明栈顶元素p对应的height值比当前index对应的height值来得小，这样的话弹出栈顶元素，并算出以栈顶元素为height所能得到的最大的矩形面积，这时候就是用辅助栈的关键地方了，针对这个情况，它的left位置就是它在栈中的下一个位置（如果没有，则表示left是0，即左边界从0开始），而它的右边界right位置就是当前index的值。

看到这里，肯定迷糊了吧，想想只有当  “栈为空”或者height[stack.peek()] <= height[index] 的时候我们才会把index值压入栈中，也就是说如果把栈从上往下看，必定上面的值对应的height会比下面的大或者相等，这样下面的那个元素对应的值就必定是left的值，同理因为当 当前height[stack.peek()] > height[index] , 我们才进行计算面积的工作，这样子的话这个index就是stack.peek()取到的这个位置对应height 的right右边界咯.

AC代码：