今天做了每日一题还有复习了一下targetSum，是必须要重新练习，不然还是没搞明白算法到底如何实现的。还有练习了一道hard题目，split Array with same average，这道题要点是要了解分出去的两个子集的平均数和这个数组的平均数是一致的，而且通过给出数组A的和（sumA）处以数组的数量lenA == 数组B除以他的数组的数量lenB，用公式表达就是sumA / lenA == sumB / lenB, 由于lenA还有lenB都是整数，那么你两边换一下就可以用 sumA * lenB / lenA == sumB 来表示你要找的sumB了，这时候用mod算 sumA *lenB % len A == 0 其实就代表你找到了sumB（因为lenB lenA都是整数）。用这个条件来判断是否搜索到了答案，然后DFS。总之今天看这道题给了我不少启发。
- Split Array with same average
用什么算法？
这道题是dfs + 剪枝，一开始完全没思路，连官方题解也没看明白，所以就去搜了一下讨论区里还有cn站的讨论区，最后在油管上面找到了个解释视频，我觉得还比较好理解，他先从最基础的暴力搜索开始讲的，然后通过剪枝来优化，基础剪枝还是会TLE（只跳过了重复的元素，但是后来这道题精髓就在于要发现子集的平均数和母集是一样的，发现之后可以通过取模来优化，这样之后DFS都快了很多。因为不满足条件的子集都被跳过了。下面是代码
public boolean splitArraySameAverage(int[] A) {
int sum = 0;
for (int i : A) {
sum += i;
}
int len = A.length;
for (int num = 1; num < A.length; num++) {
if (sum * num % len != 0) continue;
int target = sum * num / len;
if (dfs(A, num, target, 0)) {
return true;
}
}
return false;
}
private boolean dfs(int[] A, int len, int targetSum, int startIndex) {
if (len == 0 && targetSum == 0) {
return true;
}
if (len == 0 || targetSum == 0) {
return false;
}
if (startIndex == A.length) {
return false;
}
if (dfs(A, len - 1, targetSum - A[startIndex], startIndex + 1)) {
return true;
}
int i = startIndex;
while (i < A.length && A[i] == A[startIndex]) {
i++;
}
if (dfs(A, len, targetSum, i)) {
return true;
}
return false;
}
时空复杂度
由于要分出去两个子集，其中一个肯定要小于input 的一般，所以可以搜索的时候可以优化一半
Time complexity O (2 ^ (n/2) )
Space complexity O (2 ^ (n/2) )
- Longest Mountain in Array
用什么算法？
这道题一开始感觉two pointer 能做但是没思路如何实现，看了答案发现就是two pointer，但背后原理是greedy，因为给你的数组有没有峰值你判断一下就好，满足条件记录当前 end - start + 1 的值，然后保存最大值就可以了，如果找到一个mountain之后又遇到第二个mountain，那就把start 指向end就可以了，（因为end 是第二个山峰的起点）
下面是代码
public int longestMountain(int[] A) {
int len = A.length;
int res = 0, base = 0;
while (base < len) {
int end = base;
if (end + 1 < len && A[end] < A[end + 1]) {
// move end pointer to peak
while (end + 1 < len && A[end] < A[end + 1]) {
end++;
}
if (end + 1 < len && A[end] > A[end + 1]) {
// move end to the right boundary of the mountain
while (end + 1 < len && A[end] > A[end + 1]) {
end++;
}
res = Math.max(res, end - base + 1);
}
}
base = Math.max(end, base + 1);
}
return res;
}
时空复杂度
时间复杂度O(N) 就是你要扫一遍这个数组
空间复杂度O(1) 因为你没有开任何数组来保存
网友评论