打表技巧和矩阵处理技巧
打表技巧和矩阵处理技巧
打表法
1）问题如果返回值不太多，可以用 hardcode 的方式列出，作为程序的一部分
2）一个大问题解决时底层频繁使用规模不大的小问题的解，如果小问题的返回值满足条件 1，可以把小问题的解列成一张表，作为程序的一部分
3）打表找规律（打表法） 特征： - 某个面试题，输入参数类型简单，并且只有一个实际参数 - 要求返回值类型也简单，并且只有一个 - 满足上面两点，就可以先用暴力方法，把输入参数对应的返回值打印出来看一下，进而优化 code
题目一
小虎去买苹果，商店只提供两种类型的塑料袋，每种类型都有任意数量。
1） 能装下 6 个苹果的袋子
2） 能装下 8 个苹果的袋子
小虎可以自由使用两种袋子来装苹果，但是小虎有强迫症，他要求自己使用的袋子数量必须最少，且使用的每个袋子必须装满。
给定一个正整数 N,返回至少使用多少袋子。如果 N 无法让使用的每个袋子必须装满，返回-1
暴力求解：
假设 N=100，100/8=12余4,4 个无法装到 6 号袋子中，返回-1，因为最多时 12 个 8 号袋子，我们依次减 8 号袋子，当 11 个 8 号袋子时，8*11=88,100-88=12,12 个苹果正好可以被两个 6 号袋子放满，最后结果返回 13（11 个 8 号+2 个 6 号袋子）
打表法
由于此题目满足打表法的 1，2 特征，我们先用 1-100 个苹果试一下
function main() {
for (let apple = 1; apple < 100; apple++) {
console.log(apple, minBags(apple));
}
}
function minBags(N) {
const num1 = 8;
const num2 = 6;
let bag8 = Math.floor(N / num1);
let bag6 = 0;
if (bag8 == 0) {
return N == num2 ? 1 : -1;
}
if ((N % num1) % num2 == 0) {
bag6 = (N % num1) / num2;
return bag6 + bag8;
}
while (--bag8 >= 0) {
if ((N - bag8 * num1) % num2 == 0) {
bag6 = (N - bag8 * num1) / num2;
return bag6 + bag8;
}
}
return -1;
}
main();
1 -1
2 -1
3 -1
4 -1
5 -1
6 1
7 -1
8 1
9 -1
10 -1
11 -1
12 2
13 -1
14 2
15 -1
16 2
17 -1
18 3
19 -1
20 3
21 -1
22 3
23 -1
24 3
25 -1
26 4
27 -1
28 4
29 -1
30 4
31 -1
32 4
33 -1
34 5
35 -1
36 5
37 -1
38 5
39 -1
40 5
41 -1
42 6
43 -1
44 6
45 -1
46 6
47 -1
48 6
49 -1
50 7
51 -1
52 7
53 -1
54 7
55 -1
56 7
57 -1
58 8
59 -1
60 8
61 -1
62 8
63 -1
64 8
65 -1
66 9
67 -1
68 9
69 -1
70 9
71 -1
72 9
73 -1
74 10
75 -1
76 10
77 -1
78 10
79 -1
80 10
81 -1
82 11
83 -1
84 11
85 -1
86 11
87 -1
88 11
89 -1
90 12
91 -1
92 12
93 -1
94 12
95 -1
96 12
97 -1
98 13
99 -1
我们可以根据结果找到规律，当 apple 数量小于 17 的时候无任何规律，我们定制这里的内容，当苹果的数量大于 17 的时候就有一定的规律，所以最终我们的代码如下：
function minBagAwesome(){
if((apple&1)!==0){ //奇数直接返回-1
return -1
}
if(apple<18){ //定制
return apple==0?0:(apple==6||apple||8)?(apple==12||apple==14||apple==16)?2:-1
}
return (apple-18)/8+3 //规律
}
题目二 给定一个正整数 N，表示有 N 份青草统一堆放,在仓库里有一只牛和一只羊，牛先吃，羊后吃，它俩轮流吃草,不管是牛还是羊，每一轮能吃的草量必须是： 1 , 4 , 16 , 64 … （ 4 的某次方）谁最先把草吃完，谁获胜假设牛和羊都绝顶聪明，都想赢，都会做出理性的决定 根据唯一的参数 N ，返回谁会赢
假设有 0 份草，则羊赢 假设有 1 份草，牛吃 1，羊无可吃，则牛赢 假设有 2 份草，牛吃 1，羊吃 1，牛无草可吃，羊赢 假设有 3 份草，牛吃 1，羊吃 1，牛再吃 1，羊无草可吃，牛赢 假设有 4 份草，牛吃 4，羊无可吃，牛赢 假设有 5 份草，牛吃 4，羊吃 1(或牛吃 1，羊吃 4)，羊赢
题目三 定义一种数：可以表示成若干（数量＞ 1） 连续正数和的数 比如： 5 = 2+3, 5 就是这样的数 12=3+4+5, 12 就是这样的数 1 不是这样的数，因为要求数量大于 1 个、连续正数和 2=1+1 2 也不是，因为等号右边不是连续正数 给定一个参数 N,返回是不是可以表示成若干连续正数和的数
暴力解打表
function fn(N, num) {
let sum = 0;
for (let i = 1; i <= num; i++) {
//第一次相加初始值的和
sum = sum + i;
}
let end = num + 1;
for (let i = 1; i < 1000; i++) {
//每次前后指针右移动一位求和
if (sum == N) {
return "success" + end + "," + num;
}
if (sum > N) {
return "fail" + end + "," + num;
}
sum = sum - i + end;
end++;
}
}
for (let j = 2; j < 100; j++) {
for (let i = 2; i < 100; i++) {
const result = fn(j, i);
if (result.includes("success")) {
console.log("可以", result);
break;
}
}
}
根据运行结果发现当结果时 2 的次幂的时候是无法被连续个数累加的，其他数都可以
function isMSum(num) {
if (num < 3) {
return false;
}
//不是2的某次幂
return (num & (num - 1)) != 0;
}
矩阵处理技巧
核心技巧：找到coding上的宏观调度
zigzag打印矩阵
转圈打印矩阵
原地宣战正方形矩阵