猩猩的乐园

原题说明

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

nums1 = [1, 3]
nums2 = [2]
The median is 2.0

nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5

解题思路

这道题的最优解比较难想到. 想到之后, 也要注意处理边界条件.

这里我们使用Divide and Conquer的方法: 首先抽象出一个函数, 用于寻找两个数组(由小到大)合并之后的第k个元素. 由于两个数组都是排好序的, 只需要比较他们的第k / 2个元素, 较小的那个元素至多排在合并后的第k - 1个位置, 因此该元素以及其左边的元素不可能为合并后的第k个元素, 均可以排除. 由此我们可以反复调用函数得到最终结果. 边界条件的处理请见代码.

这道题还可以使用二分搜索的办法, 但实际上掌握一种就足以应付面试了, 这里介绍的方法思路相对比较清晰. 读者如果对另一种方法感兴趣, 可以参考这里.

示例代码 (cpp)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    int findKth(vector<int> nums1, vector<int> nums2, int k) {
        int m = nums1.size(), n = nums2.size();
        if (m > n) {
            return findKth(nums2, nums1, k);
        }
        if (!m) {  // 较短的数组为空, 则直接返回另一个数组的第k个元素
            return nums2[k - 1];
        }
        if (k == 1) {
            return min(nums1[0], nums2[0]);
        }
        int i = min(m, k / 2), j = min(n, k / 2);
        if (nums1[i - 1] < nums2[i - 1]) {
            return findKth(vector<int>(nums1.begin() + i, nums1.end()), nums2, k - i);
        }
        return findKth(nums1, vector<int>(nums2.begin() + j, nums2.end()), k - j);
    }
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        return (findKth(nums1, nums2, (m + n + 1) / 2) + findKth(nums1, nums2, (m + n + 2) / 2)) / 2.0;
    }
};

示例代码 (python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution(object):
    def findKth(self, nums1, nums2, k):
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1
        
        if len(nums1) == 0:
            return nums2[k - 1]
        
        if k == 1:
            return min(nums1[0], nums2[0])
        
        k1 = min(len(nums1), k / 2)
        k2 = min(len(nums2), k / 2)
        if nums1[k1 - 1] < nums2[k1 - 1]:
            return self.findKth(nums1[k1:], nums2, k - k1)
        else:
            return self.findKth(nums1, nums2[k2:], k - k2)
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        return (self.findKth(nums1, nums2, (len(nums1) + len(nums2) + 1) / 2) \
                + self.findKth(nums1, nums2, (len(nums1) + len(nums2) + 2) / 2)) / 2.

复杂度分析

时间复杂度: O(log(m+n))
空间复杂度: O(1)

归纳总结

这道题没有见过的话不太容易一下子想到. 面试中遇到不要太高兴直接写答案, 要分析思路. 如果类似难度的题目没有遇到过也不要紧张, 面试官很可能会给出提示, 比如面试官如果提示目标复杂度是log量级的, 那么就应该想到可能是二分搜索或者Divide and Conquer的解法.

原题说明

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3.

解题思路

这道题需要用一个Hash Table来记录当前字符上一次出现的index, 用一个变量left记录以当前字符结尾的符合题目条件的substring的左侧index. 注意left初始值为-1, 表示以当前字符结尾的符合题目条件的substring的起始位置等于s的起始位置 (index为0).

示例代码 (cpp)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> mapping;
        int ret = 0, left = -1;
        for (int i = 0; i < s.size(); ++i) {
            if (mapping.count(s[i])) {
                left = max(left, mapping[s[i]]);
            }
            mapping[s[i]] = i;
            ret = max(ret, i - left);
        }
        return ret;
    }
};

示例代码 (python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        iLeft = -1
        ret = 0
        charDict = dict()
        for iRight in range(len(s)):
            if s[iRight] in charDict and charDict[s[iRight]] >= iLeft:
                iLeft = charDict[s[iRight]]
            charDict[s[iRight]] = iRight
            if iRight - iLeft > ret:
                    ret = iRight - iLeft
        return ret

复杂度分析

时间复杂度: O(n) 其中n为s的长度
空间复杂度: O(1) 因为不同字符的数量有限(一般来说为256), 所以mapping的大小是恒定的

归纳总结

这道题中的mapping可以用vector<int>代替unordered_map, 但是作者倾向于使用后者, 因为更有普遍性, 不容易与面试官产生分歧(比如面试官默认s只有26个字母, 那么hard code字符数为256就容易产生分歧), 即使一定要hard code字符数, 也需要和面试官说明.

这道题的思路产生过程并不直接, 面试中如果一下子想不清楚, 建议可以带一个例子, 一步步手动推导结果, 从中或许能够找到一些灵感, 至少也可以让面试官看到思考过程.

原题说明

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

解题思路

这道题考察对链表的熟练使用, 以及对边界条件的处理能力. 实际上Leetcode上有很多类似的题目, 同学们可以总结一套自己的模板, 这样面试中比较容易和面试官说清楚思路, 也可以避免出错.

本文的模板(c++)主要有以下几个需要注意的地方:

• 用一个dummy node来指向返回节点
• 用一个变量carry来记住进位
• while循环有三个, 第一个是两个链表都没有走完的情况, 另两个是其中一个没有走完的情况
• 最后要记得判断一下carry不为零的情况, 这样还要再加一个节点

该模板思路清晰, 但代码量稍多. 在python版中, 提供了另一种解法. 这种解法以l1 || l2 || carry 为终止条件, 写法上更为简洁.

示例代码 (cpp)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int carry = 0;
        ListNode* dummy = new ListNode(-1);
        ListNode* node = dummy;
        while (l1 && l2) {
            int tmp = l1->val + l2->val + carry;
            int val = tmp % 10;
            carry = tmp / 10;
            node->next = new ListNode(val);
            node = node->next;
            l1 = l1->next;
            l2 = l2->next;
        }
        while (l1) {
            int tmp = l1->val + carry;
            int val = tmp % 10;
            carry = tmp / 10;
            node->next = new ListNode(val);
            node = node->next;
            l1 = l1->next;
        }
        while (l2) {
            int tmp = l2->val + carry;
            int val = tmp % 10;
            carry = tmp / 10;
            node->next = new ListNode(val);
            node = node->next;
            l2 = l2->next;
        }
        if (carry) {
            node->next = new ListNode(carry);
        }
        return dummy->next;
    }
};

示例代码 (python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        dummy = ListNode(0)
        curr = dummy
        carry = 0
        while(l1 is not None or l2 is not None or carry):
            curr_val = 0
            curr_val += l1.val if l1 is not None else 0
            curr_val += l2.val if l2 is not None else 0
            l1 = l1.next if l1 is not None else None
            l2 = l2.next if l2 is not None else None
            curr_val += carry
            carry = curr_val > 9
            curr.next = ListNode(curr_val - carry * 10)
            curr = curr.next
        return dummy.next

复杂度分析

时间复杂度: O(max(m, n)), m和n分别是链表l1和l2的长度
空间复杂度: O(max(m, n))

归纳总结

面试中遇到这道题, 写完一定要用特殊例子检查一下. 因为本题思路很直接, 但是边界条件较多, 如果有边界条件没有考虑到会减分.

本文提供了两个模板, 同学们选择比较顺手的作为模板即可, 没有必要来回切换.

原题说明

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

解题思路

这是一道非常经典的面试题. 由于被面的太多, 现在一般会考察这道题的变种, 但是原题也还是经常出现在电话面试中, 或者被当做热身题.

这道题的O(n)解法是利用hash table来存储遍历过的元素, 对于当前的元素nums[i], 我们只需要判断target - nums[i]是否在哈希表中即可.

这道题可能会有follow up问能否不用额外空间, 那么就需要牺牲时间复杂度: 可以先排序, 然后用双指针两头扫遍历一遍即可, 这个方法此处不做赘述, 在Three Sum中会详细介绍.

示例代码 (cpp)

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> mapping;
        for (int i = 0; i < nums.size(); ++i) {
            if (mapping.count(target - nums[i])) {
                return {mapping[target - nums[i]], i};
            }
            mapping[nums[i]] = i;
        }
        return {-1, -1};
    }
};

示例代码 (python)

1
2
3
4
5
6
7
8
9
10
11
12

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        numsIdxDict = dict()
        for i in range(len(nums)):
            if (target - nums[i]) in numsIdxDict:
                return [i, numsIdxDict[(target - nums[i])]]
            numsIdxDict[nums[i]] = i

复杂度分析

时间复杂度: O(n) n为nums数组长度
空间复杂度: O(n)

归纳总结

面试中如果遇到这道题, 也不要太高兴直接开始写答案, 还是要好好分析思路, 问清楚要求, 比如是不是一定有解, 可能有多少解, 能不能用额外空间等等.

原题说明

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

Example:
Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7]
Explanation:

1
2
3
4
5
6
7
8

Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Note:
You may assume k is always valid, 1 ≤ k ≤ input array’s size for non-empty array.

Follow up:
Could you solve it in linear time?

解题思路

这是一道比较好的面试题, 因为用priority queue的方法是容易想到的, 但是在实现的过程中也需要考虑一些边界条件, 比如刚开始扫的时候队列中少于k个数怎么处理, 什么时候结束等等. 这样方便面试官考察基本的coding能力.

对于followup, 相对来说要难一些, 用了双向队列(deque)结构来存储当前sliding window, 类似的问题有[LeetCode 316] Remove Duplicate Letters 移除重复字母
, [Leetcode 739] Daily Temperatures. 如果面试中能够想到的话, 就很接近Strong Hire了.

为了方便更新sliding window以及取出当前最大元素, 我们用的数据结构是deque. deque存储的是nums中对应元素的index. 主要思路是使得deque中的元素由老到新, 由大到小排列, 并且只存储之后可能会成为最大值的元素. 具体的方法是: 首先将超出窗口范围的老元素从队列头移出, 每次新扫到的元素与队列尾元素比较, 如果新的元素大, 则pop当前队尾元素(因为被pop的元素在窗口内必然小于新元素, 所以之后任意一步都不会成为最大值), 不然则直接插入新元素. 这样每走一步, 当前的deque头元素即为窗口中的最大值.

示例代码 (cpp)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> dq;
        vector<int> rets;
        for (int i = 0; i < nums.size(); ++i) {
            if (i >= k) {
                if (dq.front() == i - k) {
                    dq.pop_front();
                }
            }
            while (!dq.empty() && nums[i] > nums[dq.back()]) {
                dq.pop_back();
            }
            dq.push_back(i);
            if (i >= k - 1) {
                rets.push_back(nums[dq.front()]);
            }
        }
        return rets;
    }
};

示例代码 (python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution(object):         
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        ret = []
        queue = collections.deque()
        for i in range(len(nums)):
            while(len(queue) and (queue[0] <= i - k)):
                queue.popleft()
            while(len(queue) and (nums[queue[-1]] < nums[i])):
                queue.pop()
            queue.append(i)
            if i >= k - 1:
                ret.append(nums[queue[0]])
        return ret

复杂度分析

时间复杂度: O(n) 其中n为nums长度
空间复杂度: O(k)

归纳总结

同学们可以将解题思路中总结的类似题目一起做一遍, 这样对于处理这类问题会有更好的理解.

原题说明

We have a grid of 1s and 0s; the 1s in a cell represent bricks. A brick will not drop if and only if it is directly connected to the top of the grid, or at least one of its (4-way) adjacent bricks will not drop.

We will do some erasures sequentially. Each time we want to do the erasure at the location (i, j), the brick (if it exists) on that location will disappear, and then some other bricks may drop because of that erasure.

Return an array representing the number of bricks that will drop after each erasure in sequence.

Example 1:
Input:
grid = [[1,0,0,0],[1,1,1,0]]
hits = [[1,0]]
Output: [2]
Explanation:
If we erase the brick at (1, 0), the brick at (1, 1) and (1, 2) will drop. So we should return 2.

Example 2:
Input:
grid = [[1,0,0,0],[1,1,0,0]]
hits = [[1,1],[1,0]]
Output: [0,0]
Explanation:
When we erase the brick at (1, 0), the brick at (1, 1) has already disappeared due to the last move. So each erasure will cause no bricks dropping. Note that the erased brick (1, 0) will not be counted as a dropped brick.

Note:

• The number of rows and columns in the grid will be in the range [1, 200].
• The number of erasures will not exceed the area of the grid.
• It is guaranteed that each erasure will be different from any other erasure, and located inside the grid.
• An erasure may refer to a location with no brick - if it does, no bricks drop.

解题思路

这道题tag里有union find的方法, 解题思路可以参考官方解答.

实际上, 用DFS一样可以给出清晰的解答. 在面试过程中, 除非利用union find可以明显简化问题, 否则不是很推荐使用. 曾经有人使用union find解答number of islands I, 就被面试官追问, union find如何删除一个节点, 如果不熟悉的话就会很被动.

这里我们提供两种DFS的思路。

方法1(c++): 每次落下一个砖块, 要从砖块的上下左右四个方向分别做DFS, 第一遍判断DFS经过的砖块是否与顶部砖块连通, 如果不连通, 则该砖块会落下, 并且所有与之相连的砖块都不与顶部砖块连通, 因此做第二遍DFS, 标记访问过的砖块为落下. 注意每一次DFS都是一次新的遍历, 因此我们使用_id的来标记第_id次DFS, 并且在新的一次遍历前更新id.

方法2(python): 将所有击落的砖块，先行去除(在Grid矩阵中-1)，接着用DFS找出所有与顶部砖块连通的砖块，并用一个矩阵connected记录(既表示已经访问过，又表示与顶部连通)。然后，从最后一块被击落的砖块向前逐一恢复。每次恢复被击落砖块时，在Grid中+1，并且判断该位置是否原来有砖块存在，是否处于顶部或者四周有没有与顶部连通的砖块存在。若满足这些条件，说明该被击落的砖块可以恢复，并且以它为起点做DFS，所有与他连通的砖块都可以被恢复，恢复的数量即为该次击落后，落下砖块的数量。

示例代码 (cpp)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

class Solution {
    vector<vector<int>> _g; // 用一个私有变量 _g 可以减少 fall 函数的参数数量
    int _m, _n;
    int _id = 1;
    vector<int> dx = {-1, 0, 0, 1};
    vector<int> dy = {0, -1, 1, 0};
    bool fall(int x, int y, bool isClear, int& cnt) {
        if (x < 0 || x >= _m || y < 0 || y >= _n) {
            return true;
        }
        if (_g[x][y] == _id || _g[x][y] == 0) {
            return true;
        }
        if (x == 0) {
            return false;
        }
        _g[x][y] = isClear ? 0 : _id;
        ++cnt;
        for (int i = 0; i < 4; ++i) {
            int xx = x + dx[i], yy = y + dy[i];
            if (!fall(xx, yy, isClear, cnt)) {
                return false;
            }
        }
        return true;
    }
public:
    vector<int> hitBricks(vector<vector<int>>& grid, vector<vector<int>>& hits) {
        _m = grid.size();
        _n = grid[0].size();
        _g.swap(grid);
        vector<int> rets;
        for (auto& hit : hits) {
            int ret = 0;
            int x = hit[0], y = hit[1];
            _g[x][y] = 0;
            for (int i = 0; i < 4; ++i) {
                ++_id;
                int xx = x + dx[i];
                int yy = y + dy[i];
                int cnt = 0;
                if (!fall(xx, yy, false, cnt)) {
                    continue;
                }
                ++_id;
                ret += cnt;
                fall(xx, yy, true, cnt);
            }
            rets.push_back(ret);
        }
        return rets;
    }    
};

示例代码 (python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

class Solution(object):
    def check_valid(self, r, c, grid):
        if r < 0 or r >= len(grid) or c < 0  or c >= len(grid[0]) or grid[r][c] < 1:
            return False
        else:
            return True
        
    def dfs_connect(self, grid, connected, r, c):
        num_connected = 1
        for rr, cc in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:
            if self.check_valid(rr, cc, grid) and not connected[rr][cc]:
                connected[rr][cc] = 1
                num_connected += self.dfs_connect(grid, connected, rr, cc)
        return num_connected
    
    def build_connection(self, grid):
        connected = [[0 for c in range(len(grid[0]))] for r in range(len(grid))]
        for c in range(len(grid[0])):
            if self.check_valid(0, c, grid):
                connected[0][c] = 1
                self.dfs_connect(grid, connected, 0, c)
        return connected
    
    def check_new_block_connection(self, r, c, grid, connected):
        if grid[r][c] < 1:
            return False
        if r == 0:
            return True
        for rr, cc in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:
            if self.check_valid(rr, cc, grid) and connected[rr][cc] == 1:
                return True
        return False
    
    def hitBricks(self, grid, hits):
        """
        :type grid: List[List[int]]
        :type hits: List[List[int]]
        :rtype: List[int]
        """
        ret = [0 for i in range(len(hits))]
        for hit in hits:
            grid[hit[0]][hit[1]] -= 1
        connected = self.build_connection(grid)
        for idx in range(len(hits)):
            r, c = hits[-1 - idx]
            grid[r][c] += 1
            if self.check_new_block_connection(r, c, grid, connected):
                connected[r][c] = 1
                add_num = self.dfs_connect(grid, connected, r, c) - 1
                ret[-1 - idx] = add_num
                
        return ret

复杂度分析

方法1：
时间复杂度: O(N * Q) 其中N是砖块数量, Q是hits的长度
空间复杂度: O(1)

方法2：
时间复杂度: O(N + Q) 其中N是砖块数量, Q是hits的长度
空间复杂度: O(N)

归纳总结

这是一道比较复杂的深度遍历问题, 如果同学一下子不会做也没有关系, 面试的时候不要紧张, 要和面试官讨论并且慢慢理清思路.

原题说明

Given a paragraph and a list of banned words, return the most frequent word that is not in the list of banned words. It is guaranteed there is at least one word that isn’t banned, and that the answer is unique.

Words in the list of banned words are given in lowercase, and free of punctuation. Words in the paragraph are not case sensitive. The answer is in lowercase.

Example:
Input:
paragraph = “Bob hit a ball, the hit BALL flew far after it was hit.”
banned = [“hit”]
Output: “ball”
Explanation:
“hit” occurs 3 times, but it is a banned word.
“ball” occurs twice (and no other word does), so it is the most frequent non-banned word in the paragraph.
Note that words in the paragraph are not case sensitive,
that punctuation is ignored (even if adjacent to words, such as “ball,”),
and that “hit” isn’t the answer even though it occurs more because it is banned.

Note:

• 1 <= paragraph.length <= 1000.
• 1 <= banned.length <= 100.
• 1 <= banned[i].length <= 10.
• The answer is unique, and written in lowercase (even if its occurrences in paragraph may have uppercase symbols, and even if it is a proper noun.)
• paragraph only consists of letters, spaces, or the punctuation symbols !?’,;.
• Different words in paragraph are always separated by a space.
• There are no hyphens or hyphenated words.
• Words only consist of letters, never apostrophes or other punctuation symbols.
  Read more »

原题说明

You have a list of points in the plane. Return the area of the largest triangle that can be formed by any 3 of the points.

Example:
Input: points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
Output: 2
Explanation:
The five points are show in the figure below. The red triangle is the largest.

Notes:

• 3 <= points.length <= 50.
• No points will be duplicated.
• -50 <= points[i][j] <= 50.
• Answers within 10^-6 of the true value will be accepted as correct.
  Read more »

原题说明

Given a binary matrix A, we want to flip the image horizontally, then invert it, and return the resulting image.

To flip an image horizontally means that each row of the image is reversed. For example, flipping [1, 1, 0] horizontally results in [0, 1, 1].

To invert an image means that each 0 is replaced by 1, and each 1 is replaced by 0. For example, inverting [0, 1, 1] results in [1, 0, 0].

Example 1:

Input: [[1,1,0],[1,0,1],[0,0,0]]
Output: [[1,0,0],[0,1,0],[1,1,1]]
Explanation: First reverse each row: [[0,1,1],[1,0,1],[0,0,0]].
Then, invert the image: [[1,0,0],[0,1,0],[1,1,1]]

Input: [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]
Output: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
Explanation: First reverse each row: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]].
Then invert the image: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]

• 1 <= A.length = A[0].length <= 20
• 0 <= A[i][j] <= 1

原题说明

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.

解题思路

本题给出一个数组nums和一个整数m,要求把数组nums分成连续的m份，找到所有分类中，子数组最大和的最小值。

显然，最简单的方法是可以使用DFS做暴力搜索，但是这样时间复杂度相当于从n-1个元素中抽取m-1个元素，为O(n^m)，会 TLE。

因为子数组本身是连续的，我们可以想到用动态规划 Dyanmic Programming 来设计解法。定义f[i][j]为把数组 nums[0,1,..,i]分成j份后最大子数组和的最小值。显然，我们会有以下公式:
f[i][j] = max(f[k][j-1],nums[k+1]+...+nums[i) for all valid k
用动态规划，从f[0][0]出发，最后返回f[n][m] 即可。时间复杂度为O(n^2*m)，并且空间复杂度为O(n*m)。

这里，介绍一种更好的算法，运用 Binary Search 。考虑到数组元素都是非负整数，所以答案也一定是整数。同时，答案一定存在于 0 到 数组元素和sum of array之间。因此，我们只需能够判断，对于任意一个整数mid，是否存在一个分类使得nums能分成m份，并且最大子数组的和不超过mid。如果能，我们下调Binary Search，如果不能，我们上调Binary Search。

判断的算法也很简单，我们用贪心算法Greedy。用tmpsum记录当前子数组的和，用count记录当前的分类数。如果当前元素num加上tmpsum不超过mid，更新tmpsum = tmpsum + num；如果超过mid，更新tmpsum = 0并更新count = count + 1。遍历完数组nums， 当count <= m，返回 True，反之返回False。

示例代码 (python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution:
    def splitArray(self, nums, m):
        """
        :type nums: List[int]
        :type m: int
        :rtype: int
        """
        low, high = 0, sum(nums)
        while low + 1 < high:
            mid = int(low + (high - low) /2)
            if self.determinTrue(mid, nums, m):
                high = mid
            else:
                low = mid
        return i if self.determinTrue(low, nums, m) else high
    
    def determinTrue(self, target, nums, m):
        n = len(nums)
        tmpsum, count = 0, 1
        for num in nums:
            if num > target:
                return False
            if tmpsum + num <= target:
                tmpsum += num
            else:
                tmpsum = num
                count += 1
        return count <= m

复杂度分析

每次贪心算法时间复杂度为O(n)，同时Binary Search需要的时间复杂度是O(log(sum of array))。因此总的时间复杂度为O(n*(log(sum of array)))。而空间复杂度为O(n)。

• 时间复杂度: O(n*(log(sum of array)))
• 空间复杂度: O(n)

归纳总结

当数组的和不过分大时，一般情况下，Binary Search 的时间复杂度都会优于Dyanmic Programming。当然，这里能使用 Binary Search的前提是数组元素都是非负整数而Dynamic Programming则没有这个限制 。