阅读 31

Arts 第三十八周(12/2~ 12/8)

ARTS是什么?
Algorithm:每周至少做一个leetcode的算法题;
Review:阅读并点评至少一篇英文技术文章;
Tip:学习至少一个技术技巧;
Share:分享一篇有观点和思考的技术文章。

Algorithm

LC 410. Split Array Largest Sum

题目解析

题目意思很简单,让你把输入数组分成 m 个子数组,并且求出 m 个子数组中的最大子数组和,问如何分才能使得这个值最小,输出这个值。

一般像这种求最值的题目都可以往动规的方向去思考,一开始是想着往区间类动态规划的方向去拆解问题,但最后发现 m 这个信息没有办法在状态中表示,于是试着重新定义状态,dp[i][j] 表示把 array[i...n] 拆成 j 个子数组,子数组当中的最小值,于是可以画出搜索树:

                    array[0...n] 分成 m 份
                    /           ...       \
            array[0] +                  array[0...n-m] +              
    array[1...n] 分成 m - 1 份 ...   array[n-m+1, n] 分成 m - 1 份
            ...                             ...
复制代码

搜索树一出来,基本上就可以用记忆化搜索来解,但是这里还有一个小技巧,就是我们在求子数组和的时候我们可以借助前缀和数组来求解,这样会比较节省时间。这样下来时间复杂度是 O(m*n^2),也很好解释,我们有 m * n 个状态,每个状态我们要试着去分 n 次。

这道题目还有一个二分法的解法,不看答案或者提示的话很难想到,因为这种二分是按值来二分,我们要求解的答案肯定是在 min(array[0]...array[n])sum(array) 之间,我们不断尝试这个区间里面的值,看能否满足要求就好。二分的复杂度比较直观,O(n * log(sum(array))),从 leetcode 的运行时间结果对比来看,二分要优于动态规划的解法,再一次体会了 log 级别的时间复杂度和线性时间复杂度相比,要快很多。


参考代码(动态规划)

public int splitArray(int[] nums, int m) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    
    int n = nums.length;
    
    int[] sumArray = new int[n + 1];
    
    // 求解前缀和数组
    sumArray[0] = 0;
    for (int i = 1; i <= n; ++i) {
        sumArray[i] = sumArray[i - 1] + nums[i - 1];
    }
    
    return divide(sumArray, m, new int[n][m + 1], 0);
}

private int divide(int[] sumArray,
                   int subArrayCount,
                   int[][] memo,
                   int startIndex) {        
    if (subArrayCount == 1) {
        return sumArray[sumArray.length - 1] - sumArray[startIndex];
    }
    
    if (memo[startIndex][subArrayCount] != 0) {
        return memo[startIndex][subArrayCount];
    }
    
    int result = Integer.MAX_VALUE;
    for (int i = startIndex + 1; i < sumArray.length - 1; ++i) {
        // array[startIndex]...array[i - 1] 为一个子数组 
        int left = sumArray[i] - sumArray[startIndex];
        
        // array[i]...array[n] 继续拆分
        int right = divide(sumArray, subArrayCount - 1, memo, i);
        
        result = Math.min(result, Math.max(left, right));
    }
    
    memo[startIndex][subArrayCount] = result;
    
    return result;
}
复制代码

参考代码(二分)

public int splitArray(int[] nums, int m) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    
    int n = nums.length;
    
    int totalSum = 0;
    for (int num : nums) {
        totalSum += num;
    }
    
    int left = 0, right = totalSum;
    int result = Integer.MAX_VALUE;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int count = 1;
        int curSum = 0;
        int maxSum = 0;
        for (int i = 0; i < n; ++i) {
            if (curSum + nums[i] > mid) {
                count++;
                curSum = nums[i];
            } else {
                curSum += nums[i];
            }
            maxSum = Math.max(maxSum, curSum);
        }
        
        // 如果按当前的值来分,恰好可以分成 m 份,记录答案
        // 这里我们不能直接输出,要继续缩小答案在进行二分
        if (count == m) {
            result = Math.min(maxSum, result);
            right = mid - 1;
        } 
        // 当前子数组的数量小于 m,说明尝试的 “答案” 大了
        else if (count < m) {
            right = mid - 1;
        } 
        // 当前子数组的数量大于 m,说明尝试的 “答案” 小了
        else {
            left = mid + 1;
        }
    }
    
    return result;
}
复制代码

Review

The Super Simple Strategy For Greater Focus

这篇文章讲述的是如何变得更加 “专注”,当今社会,丰富多彩,我们的时间可以用在各种各样的事情上面,我们很难长时间集中注意力在一件事情上面,很多时候,你的内心会不由自主地去关注身边很多琐碎的事情,比如有没有邮件通知,微信谁又发朋友圈了,今天晚上吃什么,之前的事情结果如何。。。

是我们真的不知道如何去 “专注” 吗?文章中有一句话说的我非常认同,原话是:

Most people don’t have trouble with focusing. They have trouble with deciding.

难的其实并不是专注本身,而是如何选择,选择手头哪一件事情去专注,往往我们想把手头所有的事情都做好,但是结果却是没有做好一件事。 文章中提到,我们很难,甚至是不可能同时集中注意力在好几件事上,当然认知类的事情除外,比如说看电影,吃零食,做家务,一般像是编程、读书、写作这类需要深度思考的事情,同时去做多个只会适得其反,很没有效率。

说了这么多,那么到底该怎么去做到 “专注” 呢?文章中也给了一句话:

We go where we look.

翻译过来就是 “我们朝着我们眼中的方向前进”,既然我们无法做到同时集中注意力做好多件事,那么我们就集中注意力做好一件事吧,这件事的选择也非常简单,就选择那些你觉得值得你做,能给你带来深远意义的事情,但是记住,一次只选一件事,做好这件事,甚至把它深入你的习惯中,然后再考虑其他的事。


Tip

这周记录一下用 JavaScript 写 for 循环时发现的问题

最普通的 for 循环是:

const array = ['1', '2', '3'];
for (let i = 0; i < array.length; i++) {
  // do something
}
复制代码

但是这种写法有时会看着比较累赘,特别是我们需要对一个结构里面的元素进行遍历的时候,这个时候我们可以使用下面的写法

for (const val in array) {
  // do something
}
复制代码

但是上面的写法在某些情况下还是不理想,因此这个时候我们可以考虑使用 forEach

const array = ['1', '2', '3'];
array.forEach(val => {
    // do something
})
复制代码

这种写法和之前不同之处在于它和 callback 函数做了结合,和之前相比,这种写法的优点在于结构清晰明了,还可以借助 JavaScript 异步的优势,但是缺点是无法做到用简单的 break 终止循环。

这里有一个非常容易误导人的地方,总结一下:

const array = ['1', '2', '3'];
array.forEach(val => {
    console.log(val);
})
console.log(100);

// 打印结果
// 1
// 2
// 3
// 100
复制代码

100 是最后打印的,证明程序是顺序执行的,但是如果在循环里面添加一些 I/O 处理,比如下面的代码:

let array = ['1', '2', '3'];
array.forEach(async (val) => {
    console.log(val);
    const a = await(1);
    console.log(a);
})
console.log(100);
// 打印结果
// 1
// 2
// 3
// 100
// 1
// 1
// 1
复制代码

在这里我们用 async/await 模拟了一下 I/O,你可以看到最后的结果和之前不一样之处。总结下来就是如果 forEach 中有 I/O 请求的话,JavaScript 会利用非阻塞 I/O 的性质,callback 函数的非阻塞部分会先执行,阻塞部分会在整个主函数结束后进行,其他的简单代码逻辑会和顺序执行的时候一样,和 forEach 类似的还有内置函数 map


Share

别让自己“墙”了自己

这周没时间写文章,分享皓叔的一篇文章,主要讲的还是选择的问题,很多时候,选择比努力更重要,没有选择就努力去创造机会让自己去拥有更多的选择,不要给自己的人生设限,这样人生才会有更多的可能性,也会见到更大的世界,认识更多地志同道合的人。

关注下面的标签,发现更多相似文章
评论