根據對數器找規律、根據數據量猜題目解法

題目一

小虎去買蘋果，商店只提供兩種類型的塑料袋，每種類型都有任意數量。1）能裝下6個蘋果的袋子2）能裝下8個蘋果的袋子小虎可以自由使用兩種袋子來裝蘋果，但是小虎有強迫癥，他要求自己使用的袋子數量必須最少，且使用的每個袋子必須裝滿。給定一個正整數N，返回至少使用多少袋子。如果N無法讓使用的每個袋子必須裝滿，返回-1

先想一個暴力解：
1）如果蘋果數小于0則直接返回-1
2）先給6號袋定義一個初始值
3）給八號袋裝滿看最多需要多少個八號袋子
3）然后求余下多少個看能否被6號袋子搞定如果能就得到答案
4）如果不能被6號袋子，則需要八號袋子少一個rest加8個
從而寫出如下代碼：

	public static int minBags(int apple) {if (apple < 0) {return -1;}int bag8 = (apple >> 3);int rest = apple - (bag8 << 3);while(bag8 >= 0) {// rest 個if(rest % 6 ==0) {return bag8 + (rest / 6);} else {bag8--;rest += 8;}}return -1;}public static void main(String[] args) {for(int apple = 1; apple < 200;apple++) {System.out.println(apple + " : "+ minBags(apple));}}

將如上代碼跑一下得到如圖控制臺輸出：

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
100 : 13
101 : -1
102 : 13
103 : -1
104 : 13
105 : -1
106 : 14
107 : -1
108 : 14
109 : -1
110 : 14
111 : -1
112 : 14
113 : -1
114 : 15
115 : -1
116 : 15
117 : -1
118 : 15
119 : -1
120 : 15
121 : -1
122 : 16
123 : -1
124 : 16
125 : -1
126 : 16
127 : -1
128 : 16
129 : -1
130 : 17
131 : -1
132 : 17
133 : -1
134 : 17
135 : -1
136 : 17
137 : -1
138 : 18
139 : -1
140 : 18
141 : -1
142 : 18
143 : -1
144 : 18
145 : -1
146 : 19
147 : -1
148 : 19
149 : -1
150 : 19
151 : -1
152 : 19
153 : -1
154 : 20
155 : -1
156 : 20
157 : -1
158 : 20
159 : -1
160 : 20
161 : -1
162 : 21
163 : -1
164 : 21
165 : -1
166 : 21
167 : -1
168 : 21
169 : -1
170 : 22
171 : -1
172 : 22
173 : -1
174 : 22
175 : -1
176 : 22
177 : -1
178 : 23
179 : -1
180 : 23
181 : -1
182 : 23
183 : -1
184 : 23
185 : -1
186 : 24
187 : -1
188 : 24
189 : -1
190 : 24
191 : -1
192 : 24
193 : -1
194 : 25
195 : -1
196 : 25
197 : -1
198 : 25
199 : -1Process finished with exit code 0

發現從18-25偶數返回3，奇數返回-1
從26-33，偶數返回4，奇數返回-1
從34-41 偶數返回5，奇數返回-1
假設
18-25是第0組 -> 0+3
26-33是第1組- > 1+3
依次類推最終可得如下代碼：

O(1)的時間復雜度解決

	public static int minBagAwesome(int apple) {if ((apple & 1) != 0) { // 如果是奇數，返回-1return -1;}if (apple < 18) {return apple == 0 ? 0 : (apple == 6 || apple == 8) ? 1: (apple == 12 || apple == 14 || apple == 16) ? 2 : -1;}return (apple - 18) / 8 + 3;}

題目二

給定一個正整數N，表示有N份青草統一堆放在倉庫里有一只牛和一只羊，牛先吃，羊后吃，它倆輪流吃草不管是牛還是羊，每一輪能吃的草量必須是：1，4，16，64…(4的某次方)誰最先把草吃完，誰獲勝假設牛和羊都絕頂聰明，都想贏，都會做出理性的決定根據唯一的參數N，返回誰會贏
這道題在博弈論的視角下是無選擇的，先手一定會考慮一定能贏的情況，后手也不會失誤

在這里插入圖片描述
前四分份草的結果。

可以寫如下代碼：

	// 如果n份草，最終先手贏，返回"先手"// 如果n份草，最終后手贏，返回"后手"public static String whoWin(int n) {//先寫hardCodeif (n < 5) {//0或2的時候后手贏return n == 0 || n == 2 ? "后手" : "先手";}// 進到這個過程里來，當前的先手，先選（和全局的先手無關）int want = 1;while (want <= n) {//如果后續的過程種，當前這個過程的先手贏了if (whoWin(n - want).equals("后手")) {return "先手";}//防止want溢出，如果want小于等于n/4那么want乘以4一定安全if (want <= (n / 4)) {want *= 4;} else {break;}}return "后手";}public static void main(String[] args) {for (int i = 0; i <= 50; i++) {System.out.println(i + " : " + whoWin(i));}}

發現按照后先后先先的規律出現

0 : 后手
1 : 先手
2 : 后手
3 : 先手
4 : 先手
5 : 后手
6 : 先手
7 : 后手
8 : 先手
9 : 先手
10 : 后手
11 : 先手
12 : 后手
13 : 先手
14 : 先手
15 : 后手
16 : 先手
17 : 后手
18 : 先手
19 : 先手
20 : 后手
21 : 先手
22 : 后手
23 : 先手
24 : 先手
25 : 后手
26 : 先手
27 : 后手
28 : 先手
29 : 先手
30 : 后手
31 : 先手
32 : 后手
33 : 先手
34 : 先手
35 : 后手
36 : 先手
37 : 后手
38 : 先手
39 : 先手
40 : 后手
41 : 先手
42 : 后手
43 : 先手
44 : 先手
45 : 后手
46 : 先手
47 : 后手
48 : 先手
49 : 先手
50 : 后手Process finished with exit code 0

根據上面得出的結論可以推導出如下代碼：

public static String winner2(int n) {if (n % 5 == 0 || n % 5 == 2) {return "后手";} else {return "先手";}}

題目三

定義一種數：可以表示成若干（數量>1）連續正數和的數比如: 5 = 2+3，5就是這樣的數 12 = 3+4+5，12就是這樣的數 1不是這樣的數，因為要求數量大于1個、連續正數和 2 = 1 + 1，2也不是，因為等號右邊不是連續正數給定一個參數N，返回是不是可以表示成若干連續正數和的數

暴力：
一個n看能否被1開頭的連續數搞出來
1個n看能否被2開頭的連續數搞出來
依次遞推。

寫出如下代碼：

public static boolean isMSum1(int num) {//從某個數開始一直加加到某一個數小于num，某一個數的下一個數加上大于num//則表示以當前數開始的連續和不能組成numfor (int start = 1; start <= num; start++) {int sum = start;for (int j = start + 1; j <= num; j++) {if (sum + j > num) {break;}if (sum + j == num) {return true;}sum += j;}}return false;}public static void main(String[] args) {for (int num = 1; num < 200; num++) {System.out.println(num + " : " + isMSum1(num));}}

得到：

1 : false
2 : false
3 : true
4 : false
5 : true
6 : true
7 : true
8 : false
9 : true
10 : true
11 : true
12 : true
13 : true
14 : true
15 : true
16 : false
17 : true
18 : true
19 : true
20 : true
21 : true
22 : true
23 : true
24 : true
25 : true
26 : true
27 : true
28 : true
29 : true
30 : true
31 : true
32 : false
33 : true
34 : true
35 : true
36 : true
37 : true
38 : true
39 : true
40 : true
41 : true
42 : true
43 : true
44 : true
45 : true
46 : true
47 : true
48 : true
49 : true
50 : true
51 : true
52 : true
53 : true
54 : true
55 : true
56 : true
57 : true
58 : true
59 : true
60 : true
61 : true
62 : true
63 : true
64 : false
65 : true
66 : true
67 : true
68 : true
69 : true
70 : true
71 : true
72 : true
73 : true
74 : true
75 : true
76 : true
77 : true
78 : true
79 : true
80 : true
81 : true
82 : true
83 : true
84 : true
85 : true
86 : true
87 : true
88 : true
89 : true
90 : true
91 : true
92 : true
93 : true
94 : true
95 : true
96 : true
97 : true
98 : true
99 : true
100 : true
101 : true
102 : true
103 : true
104 : true
105 : true
106 : true
107 : true
108 : true
109 : true
110 : true
111 : true
112 : true
113 : true
114 : true
115 : true
116 : true
117 : true
118 : true
119 : true
120 : true
121 : true
122 : true
123 : true
124 : true
125 : true
126 : true
127 : true
128 : false
129 : true
130 : true
131 : true
132 : true
133 : true
134 : true
135 : true
136 : true
137 : true
138 : true
139 : true
140 : true
141 : true
142 : true
143 : true
144 : true
145 : true
146 : true
147 : true
148 : true
149 : true
150 : true
151 : true
152 : true
153 : true
154 : true
155 : true
156 : true
157 : true
158 : true
159 : true
160 : true
161 : true
162 : true
163 : true
164 : true
165 : true
166 : true
167 : true
168 : true
169 : true
170 : true
171 : true
172 : true
173 : true
174 : true
175 : true
176 : true
177 : true
178 : true
179 : true
180 : true
181 : true
182 : true
183 : true
184 : true
185 : true
186 : true
187 : true
188 : true
189 : true
190 : true
191 : true
192 : true
193 : true
194 : true
195 : true
196 : true
197 : true
198 : true
199 : true

發現只要是2的某次方那么這個數就返回false，那么只需要判斷某個數的二進制是否只有一個1即可，將某個數的最右側的1取出來和它自己比較如果相等則是2的n次方
num&(~num+1)

	public static boolean isMSum2(int num) {//		return num == (num & (~num + 1));
//
//		return num == (num & (-num));return (num & (num - 1)) != 0;}public static void main(String[] args) {for (int num = 1; num < 200; num++) {System.out.println(num + " : " + isMSum1(num));}System.out.println("test begin");for (int num = 1; num < 5000; num++) {if (isMSum1(num) != isMSum2(num)) {System.out.println("Oops!");}}System.out.println("test end");}

總結

1）某個面試題，輸入參數類型簡單，并且只有一個實際參數2）要求的返回值類型也簡單，并且只有一個
3）用暴力方法，把輸入參數對應的返回值，打印出來看看，進而優化code

根據數據規模猜解法

1）C/C++，1秒處理的指令條數為10的8次方
2）Java等語言，1~4秒處理的指令條數為10的8次方、
3）這里就有大量的空間了！

題目五

int[] d，d[i]：i號怪獸的能力 int[]
p，p[i]：i號怪獸要求的錢
開始時你的能力是0，你的目標是從0號怪獸開始，通過所有的怪獸。如果你當前的能力，小于i號怪獸的能力，你必須付出p[i]的錢，賄賂這個怪獸，然后怪獸就會加入你，他的能力直接累加到你的能力上；如果你當前的能力，大于等于i號怪獸的能力，你可以選擇直接通過，你的能力并不會下降，你也可以選擇賄賂這個怪獸，然后怪獸就會加入你，他的能力直接累加到你的能力上。返回通過所有的怪獸，需要花的最小錢數。

遞歸解法：

	// int[] d d[i]：i號怪獸的武力// int[] p p[i]：i號怪獸要求的錢// ability 當前你所具有的能力// index 來到了第index個怪獸的面前// 目前，你的能力是ability，你來到了index號怪獸的面前，如果要通過后續所有的怪獸，// 請返回需要花的最少錢數public static long process1(int[] d, int[] p, int ability, int index) {if (index == d.length) {return 0;}//必須要花錢的情況if (ability < d[index]) {//記錄花的錢										當前能力加怪獸的能力，去打后面的怪獸return p[index] + process1(d, p, ability + d[index], index + 1);} else { // ability >= d[index] 可以賄賂，也可以不賄賂return Math.min(//花錢p[index] + process1(d, p, ability + d[index], index + 1),
//不花錢0 + process1(d, p, ability, index + 1));}}public static long func1(int[] d, int[] p) {return process1(d, p, 0, 0);}

第二種解法：
先定義一張表i表示第i號怪獸，j表示所要花的錢數，從0號怪獸到i號怪獸我花的錢為多少的時候我的能力最大，并且要嚴格花費j元，如果沒有嚴格花j元則為-1，并且我在0-i-1的位置上已花費了j元，那么我通過i-1位置對應的能力一定要大于i號怪獸的能力。
如dp[100][130],表示我想從0號怪獸通關到100號怪獸嚴格花費130元，假設100號怪獸能力是50，賄賂它的錢是30。
第一種情況：不想賄賂100號怪獸一定是0-99號怪獸賄賂花了130，如果dp[99][130] = -1，則dp[100][130]也是-1，如果dp[99][130]=80則可以直接通過的得到dp[100][130]為80的能力。
第二種情況：賄賂100號怪獸，假設當前怪獸能力為x，花的是y
要整體湊出j元
那么dp[i-1][j-y] 不等于 -1

	// 從0....index號怪獸，花的錢，必須嚴格==money// 如果通過不了，返回-1// 如果可以通過，返回能通過情況下的最大能力值public static long process2(int[] d, int[] p, int index, int money) {if (index == -1) { // 一個怪獸也沒遇到呢return money == 0 ? 0 : -1;}// index >= 0// 1) 不賄賂當前index號怪獸long preMaxAbility = process2(d, p, index - 1, money);long p1 = -1;//如果之前的能力不為-1并且之前的能力大于等于當前的能力則記錄一個p1if (preMaxAbility != -1 && preMaxAbility >= d[index]) {p1 = preMaxAbility;}// 2) 賄賂當前的怪獸 當前的錢 p[index]long preMaxAbility2 = process2(d, p, index - 1, money - p[index]);long p2 = -1;if (preMaxAbility2 != -1) {p2 = d[index] + preMaxAbility2;}return Math.max(p1, p2);}public static int minMoney2(int[] d, int[] p) {int allMoney = 0;for (int i = 0; i < p.length; i++) {allMoney += p[i];}int N = d.length;for (int money = 0; money < allMoney; money++) {if (process2(d, p, N - 1, money) != -1) {return money;}}return allMoney;}public static long func3(int[] d, int[] p) {int sum = 0;for (int num : p) {sum += num;}// dp[i][j]含義：// 能經過0～i的怪獸，且花錢為j（花錢的嚴格等于j）時的武力值最大是多少？// 如果dp[i][j]==-1，表示經過0～i的怪獸，花錢為j是無法通過的，或者之前的錢怎么組合也得不到正好為j的錢數int[][] dp = new int[d.length][sum + 1];for (int i = 0; i < dp.length; i++) {for (int j = 0; j <= sum; j++) {dp[i][j] = -1;}}// 經過0～i的怪獸，花錢數一定為p[0]，達到武力值d[0]的地步。其他第0行的狀態一律是無效的dp[0][p[0]] = d[0];for (int i = 1; i < d.length; i++) {for (int j = 0; j <= sum; j++) {// 可能性一，為當前怪獸花錢// 存在條件：// j - p[i]要不越界，并且在錢數為j - p[i]時，要能通過0～i-1的怪獸，并且錢數組合是有效的。if (j >= p[i] && dp[i - 1][j - p[i]] != -1) {dp[i][j] = dp[i - 1][j - p[i]] + d[i];}// 可能性二，不為當前怪獸花錢// 存在條件：// 0~i-1怪獸在花錢為j的情況下，能保證通過當前i位置的怪獸if (dp[i - 1][j] >= d[i]) {// 兩種可能性中，選武力值最大的dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);}}}int ans = 0;// dp表最后一行上，dp[N-1][j]代表：// 能經過0～N-1的怪獸，且花錢為j（花錢的嚴格等于j）時的武力值最大是多少？// 那么最后一行上，最左側的不為-1的列數(j)，就是答案for (int j = 0; j <= sum; j++) {if (dp[d.length - 1][j] != -1) {ans = j;break;}}return ans;}

先定義1張表
dpp[i][j] 從0號怪獸通關到第i號怪獸我的能力要大于等于j至少要花多少錢
在這里插入圖片描述

public static long func2(int[] d, int[] p) {int sum = 0;for (int num : d) {sum += num;}long[][] dp = new long[d.length + 1][sum + 1];for (int i = 0; i <= sum; i++) {dp[0][i] = 0;}for (int cur = d.length - 1; cur >= 0; cur--) {for (int hp = 0; hp <= sum; hp++) {// 如果這種情況發生，那么這個hp必然是遞歸過程中不會出現的狀態// 既然動態規劃是嘗試過程的優化，嘗試過程碰不到的狀態，不必計算if (hp + d[cur] > sum) {continue;}if (hp < d[cur]) {dp[cur][hp] = p[cur] + dp[cur + 1][hp + d[cur]];} else {dp[cur][hp] = Math.min(p[cur] + dp[cur + 1][hp + d[cur]], dp[cur + 1][hp]);}}}return dp[0][0];}