LeetCode 85. Maximal Rectangle

Aug 17, 2016

题目描述:

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.

For example, given the following matrix:

1
2
3
4
5
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 6.

本来我想直接用动态规划, 但是做起来非常麻烦. 然后想起了上一道题Largest Rectangle in Histogram是本题解决的步骤之一, 先用动态规划法计算出matrix中每个元素的高(就是该元素和该元素之上的1的个数), 然后以行为单位计算最大的矩形面积.

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
class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int row = matrix.size(), col;
        if(row == 0) return 0;
        col = matrix[0].size();
        vector<vector<int>> heights(row, vector<int>(col, 0));
        for(int j = 0; j < col; j++){
            heights[0][j] = (matrix[0][j] == '1' ? 1 : 0);
        }
        for(int i = 1; i < row; i++){
            for(int j = 0; j < col; j++){
                heights[i][j] = (matrix[i][j] == '1' ? heights[i - 1][j] + 1 : 0);
            }
        }
        int maxArea = 0;
        for(int i = 0; i < row; i++){
            maxArea = max(maxArea, largestRectangleArea(heights[i]));
        }
        return maxArea;
    }
    
    int largestRectangleArea(vector<int>& heights) {
        vector<int> s;
        heights.push_back(0);
        int ret = 0;
        for(int i = 0; i < heights.size(); i++){
            if(s.empty() || heights[i] > heights[s.back()]){
                s.push_back(i);
            }
            else{
                while(!s.empty() && heights[s.back()] >= heights[i]){
                    int h = heights[s.back()];
                    s.pop_back();
                    int w = s.empty() ? i : i - s.back() - 1;
                    ret = max(ret, w * h);
                }
                s.push_back(i);
            }
        }
        return ret;
    }
};

LeetCode 385. Mini Parser

Aug 16, 2016

题目描述:

Given a nested list of integers represented as a string, implement a parser to deserialize it.

Each element is either an integer, or a list – whose elements may also be integers or other lists.

Note: You may assume that the string is well-formed:

  • String is non-empty.
  • String does not contain white spaces.
  • String contains only digits 0-9, [, - ,, ].

Example 1:

1
2
3
4
Given s = "324",

You should return a NestedInteger object which contains a single integer 324.

Example 2:

1
2
3
4
5
6
7
8
9
Given s = "[123,[456,[789]]]",

Return a NestedInteger object containing a nested list with 2 elements:

1. An integer containing value 123.
2. A nested list containing two elements:
    i.  An integer containing value 456.
    ii. A nested list with one element:
         a. An integer containing value 789.

题目要求把一个合法的字符串转换为对应的嵌套的数据格式, 一开始我想使用递归, 但是在处理嵌套的问题上遇到了麻烦, 所以改为使用栈来做.

把每一层嵌套视为栈的一个元素, 每遇到一个[就入栈一个新的NestedInteger, 然后遇到数字就把它加入到栈顶的NestedInteger中去, 遇到]就把栈顶的元素弹出, 加入到新的栈顶中, 如果弹出栈顶后栈为空说明处理结束.

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
54
55
56
57
58
59
60
/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * class NestedInteger {
 *   public:
 *     // Constructor initializes an empty nested list.
 *     NestedInteger();
 *
 *     // Constructor initializes a single integer.
 *     NestedInteger(int value);
 *
 *     // Return true if this NestedInteger holds a single integer, rather than a nested list.
 *     bool isInteger() const;
 *
 *     // Return the single integer that this NestedInteger holds, if it holds a single integer
 *     // The result is undefined if this NestedInteger holds a nested list
 *     int getInteger() const;
 *
 *     // Set this NestedInteger to hold a single integer.
 *     void setInteger(int value);
 *
 *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 *     void add(const NestedInteger &ni);
 *
 *     // Return the nested list that this NestedInteger holds, if it holds a nested list
 *     // The result is undefined if this NestedInteger holds a single integer
 *     const vector<NestedInteger> &getList() const;
 * };
 */
class Solution {
public:
    NestedInteger deserialize(string s) {
        vector<NestedInteger> nestedIntSt;
        for(int i = 0; i < s.length(); i++){
            if(s[i] == '['){
                NestedInteger tmp;
                nestedIntSt.push_back(tmp);
            }
            else if(s[i] == ']'){
                NestedInteger tmp = nestedIntSt.back();
                nestedIntSt.pop_back();
                if(!nestedIntSt.empty()) nestedIntSt.back().add(tmp);
                else return tmp;
            }
            else if((s[i] == '-' || isDigit(s[i])) && !nestedIntSt.empty()){
                int start = i, end = i + 1;
                while(isDigit(s[end])){
                    end++;
                }
                nestedIntSt.back().add(stoi(s.substr(start, end - start)));
                i = end - 1;
            }
        }
        return NestedInteger(stoi(s)); // 如果循环中没有返回, 说明字符串中只包含一个数字
    }
    
    bool isDigit(char ch){
        return ch >= '0' && ch <= '9';
    }
};

LeetCode 84. Largest Rectangle in Histogram

Aug 15, 2016

题目描述:

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

img

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

img

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example, Given heights = [2,1,5,6,2,3], return 10.

这道题目使用栈来解决, 方法是每读入一个高度就判断该高度左边有哪些高度所组成的矩形到此为止, 最终得到的是一个单调递增的序列.

这篇解答写的比较详细: http://www.cnblogs.com/boring09/p/4231906.html

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        vector<int> s;
        heights.push_back(0);
        int ret = 0;
        for(int i = 0; i < heights.size(); i++){
            if(s.empty() || heights[i] > heights[s.back()]){
                s.push_back(i);
            }
            else{
                while(!s.empty() && heights[s.back()] >= heights[i]){
                    int h = heights[s.back()];
                    s.pop_back();
                    int w = s.empty() ? i : i - s.back() - 1;
                    ret = max(ret, w * h);
                }
                s.push_back(i);
            }
        }
        return ret;
    }
};

LeetCode 83. Remove Duplicates from Sorted List

Aug 14, 2016

题目描述:

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example, Given 1->1->2, return 1->2. Given 1->1->2->3->3, return 1->2->3.

删除连表中的重复元素, 比较简单. 要注意不能造成内存泄漏.

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        ListNode *node = head, *true_next;
        
        while(node){
            while(node->next != NULL && node->next->val == node->val){
                ListNode *toDel = node->next;
                node->next = node->next->next;
                delete toDel;
            }
            node = node->next;
        }
        
        return head;
    }
};

LeetCode 82. Remove Duplicates from Sorted List II

Aug 14, 2016

题目描述:

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example, Given 1->2->3->3->4->4->5, return 1->2->5. Given 1->1->1->2->3, return 2->3.

删除一个有序序列中的所有出现重复的元素. 与去除重复元素相比, 问题在于头节点的问题, 在这个问题中头结点可能会发生变化, 因此先创建一个临时头结点指向真正的头结点. 出现初伏元素的时候就把所有相同的元素删除.

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* p1, *p2 = head;
        ListNode *re = new ListNode(0);
        re->next = head;
        p1 = re;
        
        while(p2 != nullptr){
            if(p2->next != nullptr && p2->val == p2->next->val){
                int dup_val = p2->val;
                while(p2 != nullptr && p2->val == dup_val){
                    ListNode *toDel = p2;
                    p2 = p2->next;
                    delete toDel;
                }
                p1->next = p2;
            }
            else{
                p1 = p2;
                p2 = p2->next;
            }
        }
        return re->next;
    }
};

LeetCode 81. Search in Rotated Sorted Array II

Aug 14, 2016

题目描述:

Follow up for “Search in Rotated Sorted Array”: What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

仍然使用二分搜索, 数组中可能出现重复元素并没有什么影响.

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
class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int mid = nums.size();
        for(int i = 0; i < nums.size() - 1; i++){
            if(nums[i] > nums[i + 1]){
                mid = i + 1;
                break;
            }
        }
        if(target == nums[0]) return true;
        else if(target > nums[0]) return binSearch(nums, 0, mid, target);
        else return binSearch(nums, mid, nums.size(), target);
    }
    
    bool binSearch(vector<int> &nums, int left, int right, int target){
        int mid = (left + right) / 2;
        while(left < right){
            if(nums[mid] == target){
                return true;
            }
            else if(nums[mid] < target){
                left = mid + 1;
            }
            else{
                right = mid;
            }
            mid = (left + right) / 2;
        }
        return false;
    }
};

LeetCode 80. Remove Duplicates from Sorted Array II

Aug 13, 2016

题目描述:

Follow up for “Remove Duplicates”: What if duplicates are allowed at most twice?

For example, Given sorted array nums = [1,1,1,2,2,3],

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn’t matter what you leave beyond the new length.

O(n)空间复杂度, O(n)时间复杂度的方法是使用另一个数组来保存去除超过两个重复元素之后的结果.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size() < 2)
            return nums.size();
        int tp = 1;
        vector<int> t = {nums[0], nums[1]};
        t.resize(nums.size());
        for(int np = 2; np < nums.size(); np++){
            if(t[tp] < nums[np] || (t[tp] == nums[np] && t[tp - 1] < nums[np])){
                t[++tp] = (nums[np]);
            }
        }
        swap(nums, t);
        return tp + 1;
    }
};

而不使用辅助空间则是直接删除vector中对应位置的元素, 虽然这会使vector中之后的元素都前移一位, 但是在实际的测试中这种方法还快一点, 上一种方法是20ms, 而这种是16ms…

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:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size() < 2)
            return nums.size();
        int val = nums[0], dup = 1;
        for(int i = 1; i < nums.size(); i++){
            if(nums[i] > nums[i - 1]){
                val = nums[i];
                dup = 1;
            }
            else if(dup == 2){
                nums.erase(nums.begin() + i);
                i--;
            }
            else{
                dup++;
            }
        }
        return nums.size();
    }
};

LeetCode 79. Word Search

Aug 13, 2016

题目描述:

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example, Given board =

1
2
3
4
5
6
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

word = "ABCCED", -> returns true, word = "SEE", -> returns true, word = "ABCB", -> returns false.

一个搜索问题, 使用回溯+递归, 先遍历二维数组, 找到目标字符串的开头字母, 然后向上下左右四个方向搜索下一个字母, 同时标记该位置已访问, 直到找到整个字符串为止.

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
class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        if(board.empty()){
            return false;
        }
        else if(board[0].empty()){
            return false;
        }
        int row = board.size(), col = board[0].size();
        vector<vector<int>> flag(row, vector<int>(col, 0));
        int str_p = 0;
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(board[i][j] == word[str_p] && existNext(board, i, j, word, str_p + 1, flag, row, col)){
                    return true;
                }
            }
        }
        return false;
    }
    
    bool existNext(vector<vector<char>>& board, int r, int c, string &word, int p, vector<vector<int>> &flag, int row, int col){
        flag[r][c] = 1;
        bool re = false;
        if(p == word.size()){
            flag[r][c] = 0;
            return true;
        }
        if(r - 1 >= 0 && flag[r - 1][c] == 0 && board[r - 1][c] == word[p]){
            re = existNext(board, r - 1, c, word, p + 1, flag, row, col);
        }
        if(!re && c - 1 >= 0 && flag[r][c - 1] == 0 && board[r][c - 1] == word[p]){
            re = existNext(board, r, c - 1, word, p + 1, flag, row, col);
        }
        if(!re && r + 1 < row && flag[r + 1][c] == 0 && board[r + 1][c] == word[p]){
            re = existNext(board, r + 1, c, word, p + 1, flag, row, col);
        }
        if(!re && c + 1 < col && flag[r][c + 1] == 0 && board[r][c + 1] == word[p]){
            re = existNext(board, r, c + 1, word, p + 1, flag, row, col);
        }

        flag[r][c] = 0;
        return re;
    }
};

LeetCode 78. Subsets

Aug 13, 2016

题目描述:

Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example, If nums = [1,2,3], a solution is:

1
2
3
4
5
6
7
8
9
10
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

取得一个数组的所有子集, 这道题可以直接使用上一道题LeetCode 77. Combinations的方法, 上一题是从[1,n]中取得k个数, 只要把它们当作下标, 然后n从1遍历到nums.size()即可, 然后再插入一个空集.

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
class Solution {
    vector<vector<int>> kElement;
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ret(1, vector<int>());
        for(int i = 1; i <= nums.size(); i++){
            kElement.clear();
            combine(nums.size(), i);
            for(int i = 0; i < kElement.size(); i++){
                vector<int> t(kElement[i].size());
                for(int j = 0; j < kElement[i].size(); j++){
                    t[j] = nums[kElement[i][j] - 1];
                }
                ret.push_back(t);
            }
        }
        return ret;
    }
    
    void combine(int n, int k) {
        vector<int> v;
        getKElement(n, k, 1, v);
    }
    
    void getKElement(int n, int k, int start, vector<int> &v){
        if(k == 1){
            for(int i = start; i <= n; i++){
                v.push_back(i);
                kElement.push_back(v);
                v.pop_back();
            }
            return;
        }
        for(int i = start; i <= n - k + 1; i++){
            v.push_back(i);
            getKElement(n, k - 1, i + 1, v);
            v.pop_back();
        }
    }
};

LeetCode 77. Combinations

Aug 12, 2016

题目描述:

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

For example, If n = 4 and k = 2, a solution is:

1
2
3
4
5
6
7
8
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

从[1,n]中选出k个数, 这道题只要求组合, 不要求排列, 因此用递归可以比较容易的解决.

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 {
    vector<vector<int>> kElement;
public:
    vector<vector<int>> combine(int n, int k) {
        vector<int> v;
        getKElement(n, k, 1, v);
        return kElement;
    }
    
    void getKElement(int n, int k, int start, vector<int> &v){
        if(k == 1){
            for(int i = start; i <= n; i++){
                v.push_back(i);
                kElement.push_back(v);
                v.pop_back();
            }
            return;
        }
        for(int i = start; i <= n - k + 1; i++){
            v.push_back(i);
            getKElement(n, k - 1, i + 1, v);
            v.pop_back();
        }
    }
};