JAVA数据结构三:变态跳台阶 矩阵覆盖

//变态跳台阶 //一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

//思路: // 0:0 // 1:(1) // 2:(1,1)(2) // 3:(1,1,1)(2,1)(1,2)(3)
// 4:(1,1,1,1)(2,1,1)(1,2,1)(3,1)(1,1,2)(1,3)(2,2)(4) // //
显然,除了0,其他都是2^(n-1); // OJ并未检查小于等于0的情况,所以也可将该界外判断去掉。 // //
n级台阶,第一步有n种跳法:1,2,3,…,n // 跳1级,剩下的有F(n-1)种。 //
跳2级,剩下的有F(n-2)种。 // … // 跳n级,剩下的有F(0)=1种。 //
所以F(n)=F(n-1)+F(n-2)+…+F(0) // 因为F(n-1)=F(n-2)+F(n-3)+…+F(0)
// 所以F(n)=2*F(n-1)

package nowcoder.offer.cn;

/**
 * @author xumaosheng
 * @date 2019/9/9 19:38
 */
public class _09AbnormalJumpSteps {
	public static void main(String[] args) {
		Solution1 solution5 = new _09AbnormalJumpSteps().new Solution1();
		int result = solution5.JumpFloorII(5);
		System.out.println(result);
	}

	public class Solution1 {
		public int JumpFloorII(int target) {
			if (target <= 0) {
				return 0;
			}
			int temp = 1;
			while (target >= 2) {
				temp *= 2;
				target--;
			}
			return temp;
		}
	}

	public class Solution2 {
		public int JumpFloorII(int target) {
			if (target <= 0) {
				return 0;
			}
			return (int) Math.pow(2, target - 1);
		}
	}

	public class Solution3 {
		public int JumpFloorII(int target) {
			if (target <= 0) {
				return 0;
			}
			return 1 << (target - 1);
		}
	}

	public class Solution4 {
		public int JumpFloorII(int target) {
			if (target <= 0) {
				return 0;
			} else if (target == 1) {
				return 1;
			}
			return 2 * JumpFloorII(target - 1);
		}
	}

	public class Solution5 {
		public int JumpFloorII(int target) {
			int result = 0;
			if (target <= 0) {
				return 0;
			} else if (target <= 2) {
				return target;
			} else {
				for (int i = 3; i < target; i++) {
					result = result + JumpFloorII(i);
				}
				return result + 1;
			}

		}
	}
}

//矩形覆盖
//我们可以用2**1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2n的大矩形,总共有多少种方法?

//思路: //
其实,倒数第一列要么就是1个2**1的矩形竖着放,要么就是2个横着放的。如果是竖着放的,那么剩下的就是n-1个小矩形,放法是F(n-1)种;如果是横着放的,放法就是F*(n-2)。
// // 这样子看,其实这个就是前面的跳台阶问题。 // // 那么就同样有三种解法,此处只写出一种。 // //
若n1,则返回1; // // 若n2,则返回2; // // 否则,返回F(n-1)+ F(n-2)

package nowcoder.offer.cn;

/**
 * @author xumaosheng
 * @date 2019/9/9 19:41
 */
public class _10RectangleCover {
	public static void main(String[] args) {
		Solution solution = new _10RectangleCover().new Solution();
		int result = solution.RectCover(4);
		System.out.println(result);
	}

	public class Solution {
		public int RectCover(int target) {
			if (target <= 2) {
				return target;
			} else {
				return RectCover(target - 1) + RectCover(target - 2);
			}
		}
	}
}
TAG: JAVA

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:http://www.itniuboke.com/article/22198.html