?LeetCode周賽 3468. 可行數組的數目——暴力與數學?

示例 1：
輸入：original = [1,2,3,4], bounds = [[1,2],[2,3],[3,4],[4,5]]
輸出：2
解釋：
可能的數組為：
[1, 2, 3, 4]
[2, 3, 4, 5]

示例 2：
輸入：original = [1,2,3,4], bounds = [[1,10],[2,9],[3,8],[4,7]]
輸出：4
解釋：
可能的數組為：
[1, 2, 3, 4]
[2, 3, 4, 5]
[3, 4, 5, 6]
[4, 5, 6, 7]

提示：
2 <= n == original.length <= 105
1 <= original[i] <= 109
bounds.length == n
bounds[i].length == 2
1 <= bounds[i][0] <= bounds[i][1] <= 109

題解：

暴力法+數學法 具體見代碼注釋

代碼：

// 暴力  超時
// 思路為一旦copy[0]確定 則copy數組即確定 因各元素間距由original可提前算出
// 故僅對copy[0]的值進行模擬 從u0遍歷到v0 
// 同時判斷按照上述情況得到的copy數組如copy[1] copy[2]等是否滿足他們的ui和vi限制即可
// 即由于各元素間距固定 故多個需要遍歷的變量可以變為進遍歷單一變量copy[0] 再加以對所有可能的數組進行驗證即可
class Solution1 {public int countArrays(int[] original, int[][] bounds) {int len = original.length;int res = 0;int[] next_len = new int[len];for(int i=1;i<len;i++){next_len[i] = original[i] - original[i-1];}int L = bounds[0][0];int R = bounds[0][1];while(L <= R){int[] temp = new int[len];temp[0] = L;for(int i=1;i<len;i++){temp[i] = temp[i-1] + next_len[i];}boolean flag = true;for(int i=1;i<bounds.length;i++){if(temp[i] >= bounds[i][0] && temp[i] <= bounds[i][1]){continue;}else{flag = false;break;}}if(flag){res++; }L++;}return res;}
}// 數學 算出copy[0]的實際可取值范圍即為關鍵
// 公式化簡可知 copy[i] = copy[0] + di 即copy的任一元素均可由copy[0]推演得到
// 故 ui <= copy[i] <= vi ---> ui-di <= copy[0] <= vi-di
// 則上述式子即為copy[0]的取值范圍限制 對所有情況的i均算出 取交集即可
class Solution {public int countArrays(int[] original, int[][] bounds) {int len = original.length;// 先定義copy[0]取值范圍為本身的限制 即此時為最寬泛情況// 即先進行u0-d0 <= copy[0] <= v0-d0第一層限制int L = bounds[0][0];int R = bounds[0][1];// 后面遍歷bounds 依次得到ui和vi 對copy[0]區間進行縮小for(int i=1;i<len;i++){int di = original[i] - original[0];int ui = bounds[i][0];int vi = bounds[i][1];L = Math.max(L,ui-di);R = Math.min(R,vi-di);}// 若最后得到為負 則代表無符合題目條件的數組 故返回0return R-L+1 > 0 ? R-L+1 : 0;}
}

結果：