ARTS-第42周

发表于

ARTS （第42周）

隔了许久，最近又重温红黑树，发现积累的越多，再去理解会更容易。

Algorithm 算法

变态跳台阶

1
2
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
https://www.nowcoder.com/practice/22243d016f6b47f2a6928b4313c85387?tpId=13&tqId=11162&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

解法1

递归穷举

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 穷举递归 
	public int JumpFloor_2(int target) {
		if (target == 1) {
			return 1;
		}
		if (target == 2)
			return 2;

		int sum = 1;
		for (int i = 1; i < target; i++) {
			sum += JumpFloor_2(i);
		}
		return sum;
	}

解法2

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 动态规划
	public int JumpFloorII(int target) {
		if (target < 2) {
			return target;
		}
		int[] dp = new int[target + 1];
		// dp[0]=0;
		dp[1] = 1;
		dp[2] = 2;
		int temp = 0;
		for (int i = 3; i <= target; i++) {
			temp = 0;
			// 从穷举写法里的循环里得出的转移方程
			for (int j = 1; j < i; j++) {
				temp += dp[j];
			}
			dp[i] = temp + 1;// +1是考虑一次跳N步的情况
		}
		// System.out.println(Arrays.toString(dp));
		return dp[target];
	}

解法3

归纳公式

牛客网的TLE用户，https://www.nowcoder.com/profile/2075893

链接：https://www.nowcoder.com/questionTerminal/22243d016f6b47f2a6928b4313c85387?answerType=1&f=discussion

来源：牛客网

1
2
3
4
5
// 看到的别人的解法 Orz 归纳了公式
	public int JumpFloorOrz(int target) {
		return 1 << (target - 1);
		// return (int)Math.pow(2,target-1);
	}

矩形覆盖

1
2
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
https://www.nowcoder.com/practice/72a5a919508a4251859fb2cfb987a0e6?tpId=13&tqId=11163&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

解法1

穷举递归

1
2
3
4
5
6
7
8
9
10
11
// 穷举递归
	public int RectCover_(int target) {
		// 每次增加的列，
		// 1、竖着放对应的情况与 为 n-1
		// 2、横着放对应的情况与为 n-2
		if (target <= 3) {
			return target;
		} else {
			return RectCover_(target - 1) + RectCover_(target - 2);
		}
	}

解法2

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 动态规划
	public int RectCover(int target) {
		if (target <= 3) {
			return target;
		}
		int[] dp = new int[target + 1];
		dp[1] = 1;
		dp[2] = 2;
		dp[3] = 3;
		for (int i = 4; i < dp.length; i++) {
			dp[i] = dp[i - 1] + dp[i - 2];
		}
		return dp[target];
	}

二进制中1的个数

1
2
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
https://www.nowcoder.com/practice/8ee967e43c2c4ec193b040ea7fbb10b8?tpId=13&tqId=11164&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

解法1

循环每个位，每个位都比对过去

1
2
3
4
5
6
7
8
9
10
11
public int NumberOf1(int n) {
		// int size = n < 0 ? 1 : 0;
		int size = 0;
		for (int i = 0; i < 32; i++) {
			int p = 1 << i;
			if ((n & p) != 0) {
				size++;
			}
		}
		return size;
	}

解法2

看到的别人的解法

用户：菩提旭光，https://www.nowcoder.com/profile/837579

这里减一的操作：
1、如果二进制末尾是1 -1就会直接消掉这个1 然后做&运算 就会使n的二进制里的1减少一个
2、如果末尾不是1 就会向前借个1 ，就会使二进制最右边的的1变成0，然后这个1右边的位置都变成1
如1100-1 就会变成1011，然后做&运算 同样会使n的二进制里的1减少一个
所以这里的效果是每次消掉1个二进制里的1

链接：https://www.nowcoder.com/questionTerminal/8ee967e43c2c4ec193b040ea7fbb10b8?f=discussion
来源：牛客网

public int NumberOf1_copy(int n) {
        int count = 0;
        int s = 0;
        while (n != 0) {
            s++;
            count++;

            n = n & (n - 1);
        }
        System.out.println("->" + s);
        return count;
    }

Review 英文文章

https://vuejs.org/v2/guide/components-registration.html

vue 组件的注册

Tip 技巧

每一种数据结构 深入进去就会发现很多特性

就比如二叉树的几种遍历方式

参考

https://blog.csdn.net/liuchaoxuan/article/details/79448956 二叉树的遍历及其用途

Share 分享

https://blog.csdn.net/liuchaoxuan/article/details/79448956 二叉树的遍历及其用途