题目一：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代码：
public class Solution {
public boolean isNumber(String s) {
int start = 0;
int len = s.length();
int end = len-1;
boolean flags = false;//直到处理到当前字符的时候是合法(true)还是非法(false)
boolean exitsE = false;//是否已经存在“e”
int doin = 0; //小数点的个数
//去除前面的空格 ' '
while (start < len){
if (s.charAt(start) == ' '){
start++;
}else{
break;
}
}
//去除后面的空格 ' '
while (end >= 0){
if (s.charAt(end) == ' '){
end--;
}else{
break;
}
}
//从第一个不是空格的位置开始，到最后一个不是空格的位置
for (int index=start; index<=end; ++index){
char c = s.charAt(index);
//如果开头是"+"或者"-", 那么是可以的！~~~ O(∩_∩)O
if (index == start && (s.charAt(index) == '-' || s.charAt(index) == '+')){
continue;
}
//如果"+"或者"-"紧跟在"e"或者“E”之后也是可以的！
if ((s.charAt(index) == '-' || s.charAt(index) == '+') && (s.charAt(index-1) == 'e' || s.charAt(index-1) == 'E')){
flags = false;
}else if(!((c >= '0' && c <= '9') || c == '.' || c == 'e' || c == 'E')){
//除了上面的"+"和"-"之外，如果字符不满足在 0~9 或者 . 或者 e 或者 E中的一个的话,则不合法
return false;
}else{
//如果遇到数字flags则设为合法
if ((c >= '0' && c <= '9')){
flags = true;
}else if (c == 'e' || c == 'E'){
//如果exitsE==true 表示之前的字符串已经出现过 e 或者 "E" 了,这样就有两个e了，不合法
if (exitsE){
return false;
}
exitsE = true;
//如果flags == true,表示前面有出现过数字
if (flags){
flags = false;//在把flags设置为false, 用来判断e之后是否还有出现数字
}else{
return false;
}
}else if (c == '.'){
//e后面的数字必须是整数，则如果小数点在e之后的话，直接不合法
if (exitsE){
return false;
}
//如果小数点的个数大于1则不合法
doin++;
if (doin > 1)
return false;
}else{
}
}
}
return flags;
}
}
题目二：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代码：
public class Solution {
public boolean canJump(int[] A) {
int len = A.length;
int index = 0;
int pos = 0;//第一个元素能到的位置
while (index < len){
if (pos < index){
//beyond
return false;
}else{
//before or equals pos
if (A[index] + index > pos){
pos = A[index] + index;
}
}
index++;
}
return true;
}
}
题目三：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代码：
public class Solution {
public int jump(int[] A) {
int len = A.length;
if (len == 1)
return 0;
int max = A[0];
int index = 1;
int pos = A[0];
int n = 1;
while (index < len){
if (pos >= len-1){
break;//如果pos已经可以到最后一个位置的话,结束
}
//before or equals pos
if (A[index] + index > max && index <= pos){
max = A[index] + index;//记录最大值
}
if (index == pos){
if (max > pos){
pos = max;
n++;
}
}
index++;
}
return n;
}
}
题目四：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[][]=
1 2 3 4
7 8 1 3
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代码：