自動前幾天筆試阿里之后，我痛定思痛！為啥總共兩個題目，你就整出來一個，而且Case通過率0.00%？ 這不是完敗嗎！
所以我開始我的刷題 目標是好多好多題目，LeetCode還有劍指Offer，加油。
現(xiàn)在開始整理 LeetCode杯 2020 春季個人賽
第1題來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/na-ying-bi/
第2題來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/chuan-di-xin-xi
第3題來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/ju-qing-hong-fa-shi-jian/
第4題來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/zui-xiao-tiao-yue-ci-shu/
第5題來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/er-cha-shu-ren-wu-diao-du/
第1題：拿硬幣
桌上有 n 堆力扣幣，每堆的數(shù)量保存在數(shù)組 coins 中。我們每次可以選擇任意一堆，拿走其中的一枚或者兩枚，求拿完所有力扣幣的最少次數(shù)。
示例 1：
輸入：[4,2,1]
輸出：4
解釋：第一堆力扣幣最少需要拿 2 次，第二堆最少需要拿 1 次，第三堆最少需要拿 1 次，總共 4 次即可拿完。
示例 2：
輸入：[2,3,10]
輸出：8
限制：
- 1 <= n <= 4
- 1 <= coins[i] <= 10
題目分析
1.保存在數(shù)組之中，可以拿任意一堆，然后每次1-2個硬幣。那就是先按照多的拿？剩下的1就一次，如果只有只就拿一次
2.偽代碼 如下
- 在數(shù)組外定義總共的次數(shù) count = 0 循環(huán)遍歷數(shù)組，取出每個位置的值
1.1 把取出的值 取模 2 if(coins[i]%2==0) 就是偶數(shù)，需要拿 count += coins[i] / 2
1.2 如果是 if(coins[i]%2==1) 就是奇數(shù)，需要拿 count += coins[i] / 2 +1 因為 Java中去整數(shù)會向下取整，所以需要多加一個1- 返回結(jié)果 count
3.代碼實現(xiàn) minCount2 是裝x寫法，本質(zhì)一樣
public class _2020_04_18_01_TakeCoins {
public static void main(String[] args) {
int[] num = {4, 2, 1};
int result = minCount2(num);
System.out.println(result);
}
public static int minCount2(int[] coins) {
int resultCounts = 0;
for (int i = 0; i < coins.length; i++) {
resultCounts += (coins[i] % 2 == 0) ? (coins[i] / 2) : (coins[i] / 2 + 1);
}
return resultCounts;
}
public static int minCount(int[] coins) {
if (coins == null || coins.length < 1 || coins.length > 4) {
throw new RuntimeException("參數(shù)不合法");
}
int resultCounts = 0;
for (int i = 0; i < coins.length; i++) {
if (coins[i] < 1 || coins[i] > 10) {
throw new RuntimeException("參數(shù)不合法");
}
if (coins[i] % 2 == 0) {
//如果等于0 就是偶數(shù) 就需要拿偶數(shù)次
resultCounts += coins[i] / 2;
} else {
//是奇數(shù)
resultCounts += coins[i] / 2 + 1;
}
}
return resultCounts;
}
}
第2題：傳遞信息
小朋友 A 在和 ta 的小伙伴們玩?zhèn)餍畔⒂螒?，游戲?guī)則如下：
- 有 n 名玩家，所有玩家編號分別為 0 ～ n-1，其中小朋友 A 的編號為 0
- 每個玩家都有固定的若干個可傳信息的其他玩家（也可能沒有）。傳信息的關(guān)系是單向的（比如 A 可以向 B 傳信息，但 B 不能向 A 傳信息）。
- 每輪信息必須需要傳遞給另一個人，且信息可重復經(jīng)過同一個人
給定總玩家數(shù) n，以及按 [玩家編號,對應(yīng)可傳遞玩家編號] 關(guān)系組成的二維數(shù)組 relation。返回信息從小 A (編號 0 ) 經(jīng)過 k 輪傳遞到編號為 n-1 的小伙伴處的方案數(shù)；若不能到達，返回 0。
示例 1：
輸入：n = 5, relation = [[0,2],[2,1],[3,4],[2,3],[1,4],[2,0],[0,4]], k = 3
輸出：3
解釋：信息從小 A 編號 0 處開始，經(jīng) 3 輪傳遞，到達編號 4。共有 3 種方案，分別是 0->2->0->4， 0->2->1->4， 0->2->3->4。
示例 2：
輸入：n = 3, relation = [[0,2],[2,1]], k = 2
輸出：0
解釋：信息不能從小 A 處經(jīng)過 2 輪傳遞到編號 2
限制：
- 2 <= n <= 10
- 1 <= k <= 5
- 1 <= relation.length <= 90, 且 relation[i].length == 2
- 0 <= relation[i][0],relation[i][1] < n 且 relation[i][0] != relation[i][1]
題目分析
我當時在做這個題目的時候，真的是毫無頭緒，感覺像是圖，然后又在紙上畫樹，圖的遍歷，不會了，阿里的筆試也是死于圖的遍歷。 這題就是DFS算法，話不多說，
直接上代碼了，我也解釋不清楚。
代碼實現(xiàn)
public class _2020_04_18_02_TransmitInformation {
public static void main(String[] args) {
int n = 5, k = 3;
int[][] relation = {{0, 2}, {2, 1}, {3, 4}, {2, 3}, {1, 4}, {2, 0}, {0, 4}};
int result = numWays(n, relation, k);
System.out.println(result);
}
public static int numWays(int n, int[][] relation, int k) {
return dfs(n, relation, k, n - 1);
}
public static int dfs(int n, int[][] relation, int k, int tail) {
if (k == 1) {
int count = 0;
for (int i = 0; i < relation.length; i++) {
if (relation[i][1] == tail && relation[i][0] == 0) {
count++;
}
}
return count;
}
int count = 0;
for (int i = 0; i < relation.length; i++) {
int time = 0;
if (relation[i][1] == tail) {
time += dfs(n, relation, k - 1, relation[i][0]);
}
count += time;
}
return count;
}
}
第3題：劇情觸發(fā)時間
在戰(zhàn)略游戲中，玩家往往需要發(fā)展自己的勢力來觸發(fā)各種新的劇情。一個勢力的主要屬性有三種，分別是文明等級（C），資源儲備（R）以及人口數(shù)量（H）。在游戲開始時（第 0 天），三種屬性的值均為 0。
隨著游戲進程的進行，每一天玩家的三種屬性都會對應(yīng)增加，我們用一個二維數(shù)組 increase 來表示每天的增加情況。這個二維數(shù)組的每個元素是一個長度為 3 的一維數(shù)組，例如 [[1,2,1],[3,4,2]] 表示第一天三種屬性分別增加 1,2,1 而第二天分別增加 3,4,2。
所有劇情的觸發(fā)條件也用一個二維數(shù)組 requirements 表示。這個二維數(shù)組的每個元素是一個長度為 3 的一維數(shù)組，對于某個劇情的觸發(fā)條件 c[i], r[i], h[i]，如果當前 C >= c[i] 且 R >= r[i] 且 H >= h[i] ，則劇情會被觸發(fā)。
根據(jù)所給信息，請計算每個劇情的觸發(fā)時間，并以一個數(shù)組返回。如果某個劇情不會被觸發(fā)，則該劇情對應(yīng)的觸發(fā)時間為 -1 。
示例 1：
輸入： increase = [[2,8,4],[2,5,0],[10,9,8]] requirements = [[2,11,3],[15,10,7],[9,17,12],[8,1,14]]
輸出: [2,-1,3,-1]
解釋：
初始時，C = 0，R = 0，H = 0
第 1 天，C = 2，R = 8，H = 4
第 2 天，C = 4，R = 13，H = 4，此時觸發(fā)劇情 0
第 3 天，C = 14，R = 22，H = 12，此時觸發(fā)劇情 2
劇情 1 和 3 無法觸發(fā)。
示例 2：
輸入： increase = [[0,4,5],[4,8,8],[8,6,1],[10,10,0]] requirements = [[12,11,16],[20,2,6],[9,2,6],[10,18,3],[8,14,9]]
輸出: [-1,4,3,3,3]
示例 3：
輸入： increase = [[1,1,1]] requirements = [[0,0,0]]
輸出: [0]
限制：
- 1 <= increase.length <= 10000
- 1 <= requirements.length <= 100000
- 0 <= increase[i] <= 10
- 0 <= requirements[i] <= 100000
題目分析
這個題目我當時看的第一眼就是想到，把要求計算出來，然后一個一個去減法，求出值，但是有一個地方一直做不做來，就是控制指定天數(shù)是指定的方案。然后評論區(qū)的大哥們有的是使用二分法，我糊涂了，沒明白。
代碼演示
public class _2020_04_18_03_PlotTriggerTime {
public static void main(String[] args) {
int[][] increase = {{2, 8, 4}, {2, 5, 0}, {10, 9, 8}};
int[][] requirements = {{2, 11, 3}, {15, 10, 7}, {9, 17, 12}, {8, 1, 14}};
int[] triggerTime = getTriggerTime2(increase, requirements);
for (int trig : triggerTime) {
System.out.print(trig + " ");
}
}
public static int[] getTriggerTime(int[][] increase, int[][] requirements) {
int[] result = new int[requirements.length];
Arrays.fill(result, -1);
for (int i = 1; i < increase.length; i++) {
increase[i][0] += increase[i - 1][0];
increase[i][1] += increase[i - 1][1];
increase[i][2] += increase[i - 1][2];
}
for (int i = 0; i < requirements.length; i++) {
if (isEqual(requirements[i], new int[]{0, 0, 0})) {
result[i] = 0;
}
}
for (int i = 0; i < requirements.length; i++) {
if (result[i] != -1) {
continue;
}
int left = 0;
int right = increase.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (isDay(increase[mid], requirements[i])) {
right = mid - 1;
} else {
left = mid + 1;
}
if (left >= 0 && left < increase.length && isDay(increase[left], requirements[i])) {
result[i] = left + 1;
}
}
}
return result;
}
public static boolean isDay(int[] incr, int req[]) {
return incr[0] >= req[0] && incr[1] >= req[1] && incr[2] >= req[2];
}
public static boolean isEqual(int[] incr, int[] req) {
return incr[0] == req[0] && incr[1] == req[1] && incr[2] == req[2];
}
public static int[] getTriggerTime2(int[][] increase, int[][] requirements) {
Integer[] ans = new Integer[requirements.length];
for (int day = 0; day <= increase.length; day++) {
boolean hasRemain = false;
for (int i = 0; i < requirements.length; i++) {
if (day == 0) {
if (requirements[i][0] == 0 && requirements[i][1] == 0 && requirements[i][2] == 0) {
ans[i] = 0;
} else {
continue;
}
}
if (ans[i] != null) {
continue;
}
hasRemain = true;
requirements[i][0] -= increase[day - 1][0];
requirements[i][1] -= increase[day - 1][1];
requirements[i][2] -= increase[day - 1][2];
if (requirements[i][0] <= 0 && requirements[i][1] <= 0 && requirements[i][2] <= 0) {
ans[i] = day;
}
}
if (day != 0 && !hasRemain) {
break;
}
}
int[] realAns = new int[requirements.length];
for (int i = 0; i < ans.length; i++) {
if (ans[i] == null) {
realAns[i] = -1;
} else {
realAns[i] = ans[i];
}
}
return realAns;
}
}
PS:關(guān)于二分查找法 給個 不錯的文章 https://labuladong.gitbook.io/algo/di-ling-zhang-bi-du-xi-lie/er-fen-cha-zhao-xiang-jie
第4題：最小跳躍次數(shù)
為了給刷題的同學一些獎勵，力扣團隊引入了一個彈簧游戲機。游戲機由 N 個特殊彈簧排成一排，編號為 0 到 N-1。初始有一個小球在編號 0 的彈簧處。若小球在編號為 i 的彈簧處，通過按動彈簧，可以選擇把小球向右彈射 jump[i] 的距離，或者向左彈射到任意左側(cè)彈簧的位置。也就是說，在編號為 i 彈簧處按動彈簧，小球可以彈向 0 到 i-1 中任意彈簧或者 i+jump[i] 的彈簧（若 i+jump[i]>=N ，則表示小球彈出了機器）。小球位于編號 0 處的彈簧時不能再向左彈。
為了獲得獎勵，你需要將小球彈出機器。請求出最少需要按動多少次彈簧，可以將小球從編號 0 彈簧彈出整個機器，即向右越過編號 N-1 的彈簧。
示例 1：
輸入：jump = [2, 5, 1, 1, 1, 1
輸出：3
解釋：小 Z 最少需要按動 3 次彈簧，小球依次到達的順序為 0 -> 2 -> 1 -> 6，最終小球彈出了機器。
限制：
- 1 <= jump.length <= 10^6
- 1 <= jump[i] <= 10000
題目分析
這個是個動態(tài)規(guī)劃題目，我又不會了，來看大佬的解答
從右向左計算dp值(從后向前)，當前位置如果為i 則它如果直接跳到右邊（前面）去就是dp[jump[i]+i]+1（這個值已經(jīng)計算過了），計算出當前位置dp[i]之后，當前位置i可以影響 i+1到dp[j] >= dp[i]+1位置上的值（因為某個位置可以跳到左邊任意位置）注意遍歷到dp[j]>=dp[i]+1即可。
作者：dongyangliu
鏈接：https://leetcode-cn.com/problems/zui-xiao-tiao-yue-ci-shu/solution/jian-dan-yi-dong-de-dong-tai-gui-hua-wan-fa-by-don/
來源：力扣（LeetCode）
代碼演示
public class _2020_04_18_04_MinimumNumberOfJumps {
public static void main(String[] args) {
int[] jump = {2, 5, 1, 1, 1, 1};
System.out.println(minJump(jump));
}
public static int minJump(int[] jump) {
//dp[]數(shù)組 每一位 代表該位到跳出的最少次數(shù)
int[] dp = new int[jump.length];
dp[jump.length - 1] = 1;
for (int i = jump.length - 2; i >= 0; i--) {
//遍歷當前位置更新后影響到的后面的位置，只需要更新到dp[j] >= dp[i] + 1 即可
//如果遍歷到某dp[j]<dp[i]+1就不需要向右遍歷了,因為j到dp.length的值會被當前遍歷到的dp[j]更新而不是dp[i]+1
dp[i] = jump[i] + i >= jump.length ? 1 : dp[jump[i] + i] + 1;
for (int j = i + 1; j < dp.length && dp[j] >= dp[i] + 1; j++) {
dp[j] = dp[i] + 1;
}
}
System.out.println(Arrays.toString(dp));
return dp[0];
}
}
第5題：二叉樹任務(wù)調(diào)度
任務(wù)調(diào)度優(yōu)化是計算機性能優(yōu)化的關(guān)鍵任務(wù)之一。在任務(wù)眾多時，不同的調(diào)度策略可能會得到不同的總體執(zhí)行時間，因此尋求一個最優(yōu)的調(diào)度方案是非常有必要的。
通常任務(wù)之間是存在依賴關(guān)系的，即對于某個任務(wù)，你需要先完成他的前導任務(wù)（如果非空），才能開始執(zhí)行該任務(wù)。我們保證任務(wù)的依賴關(guān)系是一棵二叉樹，其中 root 為根任務(wù)，root.left 和 root.right 為他的兩個前導任務(wù)（可能為空），root.val 為其自身的執(zhí)行時間。
在一個 CPU 核執(zhí)行某個任務(wù)時，我們可以在任何時刻暫停當前任務(wù)的執(zhí)行，并保留當前執(zhí)行進度。在下次繼續(xù)執(zhí)行該任務(wù)時，會從之前停留的進度開始繼續(xù)執(zhí)行。暫停的時間可以不是整數(shù)。
現(xiàn)在，系統(tǒng)有兩個 CPU 核，即我們可以同時執(zhí)行兩個任務(wù)，但是同一個任務(wù)不能同時在兩個核上執(zhí)行。給定這顆任務(wù)樹，請求出所有任務(wù)執(zhí)行完畢的最小時間。
示例 1：
輸入：root = [47, 74, 31]
輸出：121
解釋：根節(jié)點的左右節(jié)點可以并行執(zhí)行31分鐘，剩下的43+47分鐘只能串行執(zhí)行，因此總體執(zhí)行時間是121分鐘。
示例 2：
輸入：root = [15, 21, null, 24, null, 27, 26]
輸出：87
示例3：
輸入：root = [1,3,2,null,null,4,4]
輸出：7.5
限制：
- 1 <= 節(jié)點數(shù)量 <= 1000
- 1 <= 單節(jié)點執(zhí)行時間 <= 1000
思路分析
我不會我就CV了一份來emmm 大佬真的強
解題思路
任務(wù)調(diào)度存在依賴關(guān)系，任何一個node節(jié)點任務(wù)，都依賴于node.left和node.right前置節(jié)點任務(wù)的完成。所以，這是一個很明顯的后序遍歷思路。
這里很多人應(yīng)該都會想到遞歸左右子樹，獲取左右子樹的最小執(zhí)行時間的較大值+當前節(jié)點的時間，得到解。
于是乎，卡在了測試用例3的7.5中。
上面思想類似貪心選擇，局部最優(yōu)，統(tǒng)一起來，不一定是整體最優(yōu)。因為任務(wù)是可以暫時中斷的，在這個情況下，我們可以把所有的前置任務(wù)看成一個整體來思考，摒棄細節(jié)，這樣思路會清晰一些。
其他題解也說了大體的思路，就是如果left>right，就要把left多出來的串行時間往right的并行時間里攤，反之亦然。
這里我談一下自己的理解，也許存在問題，也希望各位大佬可以指正。
首先，假設(shè)不存在多個cpu的情況(即只有一個cpu)，要執(zhí)行完所有的前置任務(wù)，那前置任務(wù)的總時間肯定是preTime = sum(node.left) + sum(node.right)preTime=sum(node.left)+sum(node.right)。這時，我們將preTime看成一個整體。
那么現(xiàn)在變成雙核CPU了。一個整體的preTime開始雙核并行了，那么一個整體下的preTime是多少呢？
很顯然，是preTime/2
是不是豁然開朗了？在前置任務(wù)最為理想的情況下，所有任務(wù)都能一直并行，不存在串行時間。這個類似于動態(tài)規(guī)劃的前置條件。至于前置任務(wù)再往前的任務(wù)，和任務(wù)它到底是怎么分配時間的，怎么去分攤時間，我們并不關(guān)心，總之，你能在preTime/2的時間內(nèi)完成，就OK了。如果CPU核心更多，就是preTime/n。
當然，前置任務(wù)最優(yōu)的解preTime/2，是一個理想情況，具體的任務(wù)執(zhí)行，是非常有可能達不到這種情況。比如題目的測試用例1。
所以，每個節(jié)點的任務(wù)執(zhí)行時間的最小值，應(yīng)該是Max(time(node.left),time(node.right),preTime/2) + node.valMax(time(node.left),time(node.right),preTime/2)+node.val。
即左子樹執(zhí)行完成的最小時間、右子樹執(zhí)行完成的最小時間、左右子樹全部節(jié)點并行執(zhí)行的時間，三者的最大值，再加上當前節(jié)點的任務(wù)時間。
最后將最優(yōu)時間往根節(jié)點遞推。抵達根節(jié)點后的最優(yōu)解，就是全局的最優(yōu)解。
作者：burning-summer
鏈接：https://leetcode-cn.com/problems/er-cha-shu-ren-wu-diao-du/solution/hou-xu-bian-li-di-gui-fan-hui-zuo-you-zi-shu-zui-y/
來源：力扣（LeetCode）
代碼實現(xiàn)
public class _2020_04_18_05_BinaryTreeTaskScheduling {
/**
* LCP 10. 二叉樹任務(wù)調(diào)度
*
* @param root
* @return
*/
public double minimalExecTime(TreeNode root) {
double[] res = execTime(root, 2);
return res[0];
}
/**
* 獲取node最小執(zhí)行時間
*
* @param node node
* @param n 并行數(shù)
* @return [0]執(zhí)行完當前節(jié)點最小耗時，[1]當前node為根的時間串行之和
*/
private double[] execTime(TreeNode node, int n) {
if (node == null) {
// [0]執(zhí)行完當前節(jié)點最小耗時，[1]當前node為根的時間串行之和
return new double[]{0.0D, 0.0D};
}
// 獲取左右子樹的值
double[] leftTime = execTime(node.left, n);
double[] rightTime = execTime(node.right, n);
// 左右子樹節(jié)點之和
double sum = leftTime[1] + rightTime[1];
// 當前節(jié)點執(zhí)行完的最小消耗時間
double minTime = Math.max(Math.max(leftTime[0], rightTime[0]), sum / n) + node.val;
return new double[]{minTime, sum + node.val};
}
}
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
