学渣的刷题笔记

上来就是一道Hard，不是我的本意，但是我在翻阅狗家面筋。虽然狗家不会要我这个渣，但是梦想还是要有的嘛，万一，见鬼了呢！本渣表示这道题看题用了一个小时，百度了好久，才看明白题目。。。感谢百度上各个大神的博客让我看懂了题。。。 题目： Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays. Note: If n is the length of array, assume the following constraints are satisfied: 1 ≤ n ≤ 1000 1 ≤ m ≤ min(50, n) Examples: Input: nums = [7,2,5,10,8] m = 2 Output: 18 Explanation: There are four ways to split nums into two subarrays. The best way is to split it into [7,2,5] and [10,8], where the largest sum among the two subarrays is only 18. 题目大意： 题目很简单，一个数组，让我们把这个数组切割成m个subarray，每个subarray求和，要使得这m个subarray里，和最大的array，和最小。换句话说，让我们最小化n个subarray中的 最大值。原谅我的翻译能力。。。题目链接在这里 Leetcode401 。 解题思路： 第一思路（本渣的第一思路，一定是最辣鸡的办法，没有之一），暴力破解法。但是，这个复杂度实在是太高了，高到我觉得至少是n方，这个编辑器n方怎么打也不知道。。。于是，我想也没想，就去看大神的解法了。最普遍的就是二分搜索。以前一直以为二分搜索是用来搜索有序数组的，今天才知道还有这个巧妙的用处。值得注意的是呢，这个方

本人学渣一枚。一年前算法一窍不通，后为生计奔波，遂走上CS大法好的道路。在这条不归路上走了几米，生计算是有了着落，但学渣的属性并没有改变。严格意义上讲，连渣都算不上，基本是个学沫，学渣还沉底在下面有个渣，而学沫，就是飘在上面的沫沫。 在于算法大神交流过之后，大神一句话点醒梦中人，不，是梦中渣，本渣是操作系统不行。如果每个人都是个AI，我这款AI的算法学习能力差到爆炸，底层系统上就跟别人差出好几个linux，约等于好几十个windows，恩。。。本着只要功夫深，铁杵（学渣）磨成针的不灭信念，决心洗心革面，静心刷题，修炼内功，争取从量变到质变，打造出更好的OS。题记就先写到这里。闲言碎语不要讲，先写几道题。我会把Leetcode上AC的我的答案写上来，在加上我毫无逻辑的学弱的解题思路，抛砖引玉，要刷题的各位亲，大家一起加油！