241. Different Ways to Add Parentheses241. Different Ways to Add Parentheses

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.

Example 1:

Input: "2-1-1"
Output: [0, 2]
Explanation: 
((2-1)-1) = 0 
(2-(1-1)) = 2

Example 2:

Input: "2*3-4*5" Output: [-34, -14, -10, -10, 10] Explanation:  (2*(3-(4*5))) = -34  ((2*3)-(4*5)) = -14  ((2*(3-4))*5) = -10  (2*((3-4)*5)) = -10  (((2*3)-4)*5) = 10241. Different Ways to Add Parentheses

给定一个包含+-*的运算字符串，求所有加括号的方案计算到的值。
采用分治法的思路，尝试在每个操作符分成两个部分，这就相当于分别把操作符左右两边括起来单独计算。然后left和right分开进行递归，最后merge。递归的终止条件是当字符串中不包含操作符时，直接返回这个字符串对应的数值。
分治法很经典的例子。
代码如下：

class Solution {
private:
    int operate(int a, int b, char c)
    {
        switch (c) {
        case ‘+’:
            return a + b;
        case ‘-‘:
            return a – b;
        case ‘*’:
            return a * b;
        }
    }
public:
    vector<int> diffWaysToCompute(string input)
    {
        int n = input.size();
        vector<int> ans;
        bool found = false;
        for (int i = 0; i < n; ++i) {
            if (input[i] == ‘+’ || input[i] == ‘-‘ || input[i] == ‘*’) {
                found = true;
                vector<int> lefts = diffWaysToCompute(input.substr(0, i));
                vector<int> rights = diffWaysToCompute(input.substr(i + 1));
                for (int j = 0; j < lefts.size(); ++j) {
                    for (int k = 0; k < rights.size(); ++k) {
                        ans.push_back(operate(lefts[j], rights[k], input[i]));
                    }
                }
            }
        }
        if (!found)
            return { atoi(input.c_str()) };
        return ans;
    }
};

本代码提交AC，用时3MS。

LeetCode Fraction Addition and Subtraction Given a string representing an expression of fraction addition and subtraction, you need to return the calculation result in string format. The final result should be irreducible fraction. If your final result is an integer, say 2, you need to change it to the format of fraction that has denominator 1. So in this case, 2 should be converted to 2/1. Example 1:

Input:"-1/2+1/2"
Output: "0/1"

Input:"-1/2+1/2+1/3"
Output: "1/3"

Input:"1/3-1/2"
Output: "-1/6"

Input:"5/3+1/3"
Output: "2/1"

1. The input string only contains '0' to '9', '/', '+' and '-'. So does the output.
2. Each fraction (input and output) has format ±numerator/denominator. If the first input fraction or the output is positive, then '+' will be omitted.
3. The input only contains valid irreducible fractions, where the numerator and denominator of each fraction will always be in the range [1,10]. If the denominator is 1, it means this fraction is actually an integer in a fraction format defined above.
4. The number of given fractions will be in the range [1,10].
5. The numerator and denominator of the final result are guaranteed to be valid and in the range of 32-bit int.

378. Kth Smallest Element in a Sorted Matrix 378. Kth Smallest Element in a Sorted Matrix

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Example:

matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,

return 13.

Note:
You may assume k is always valid, 1 ≤ k ≤ n². 378. Kth Smallest Element in a Sorted Matrix

给定一个矩阵，该矩阵每行和每列都是有序的，要找出第k小的数。 如果只利用每行或者每列是有序的，则可以使用堆解决。我们以行为例，那么每行都是有序的，则相当于把所有行进行n路归并，然后找到第k小的数。所以我们构建一个最小堆，首先把所有行的首元素放到堆中，然后n路归并k次，每次弹出堆顶元素（即当前最小值），然后把原堆顶元素所在行的下一个元素放入堆中。k次归并结束之后，堆顶元素即为第k小的元素。 代码如下：

class Solution {
private:
    struct Node {
        int val, row, col;
        Node(int v = 0, int r = 0, int c = 0)
            : val(v)
            , row(r)
            , col(c){};
        friend bool operator<(const Node& n1, const Node& n2) { return n1.val > n2.val; }
    };
public:
    int kthSmallest(vector<vector<int> >& matrix, int k)
    {
        int n = matrix.size();
        priority_queue<Node> pn;
        for (int i = 0; i < n; ++i)
            pn.push(Node(matrix[i][0], i, 0));
        Node t;
        while (k–) {
            t = pn.top();
            pn.pop();
            if (t.col < n – 1)
                pn.push(Node(matrix[t.row][t.col + 1], t.row, t.col + 1));
        }
        return t.val;
    }
};

本代码提交AC，用时45MS。时间复杂度是O(klgn)，堆的大小为n，每次归并调整堆需要lgn时间，一共需要归并k次，所以总的时间复杂度是O(klgn)。
另外用二分的方法可以同时利用行有序和列有序的特点。这种矩阵可以看成一个曲面，曲面的最低点为左上角元素left，最高点为右下角元素right，所以曲面就是从左上角向上延伸到右下角（想象一下MATLAB画的图）。那么第k小的数肯定在[left,right]范围内，我们可以二分查找这个区间。假设中点是mid，则我们在每一行找找比mid小的数有多少个，加起来如果等于cnt，则说明mid这个数排在第cnt位。因为每一行也是有序的，所以可以直接用upper_bound查找第一个比mid大的数。
代码如下：

class Solution {
public:
    int kthSmallest(vector<vector<int> >& matrix, int k)
    {
        int n = matrix.size(), left = matrix[0][0], right = matrix[n – 1][n – 1];
        while (left <= right) {
            int mid = left + (right – left) / 2;
            int cnt = 0;
            for (int i = 0; i < n; ++i) {
                cnt += upper_bound(matrix[i].begin(), matrix[i].end(), mid) – matrix[i].begin();
            }
            if (cnt < k)
                left = mid + 1;
            else
                right = mid – 1;
        }
        return left;
    }
};

本代码提交AC，用时43MS。时间复杂度是O(lgX nlgn)，X为[left,right]的区间大小，ngln是对于每个mid，都需要在每一行二分查找比mid小的数的个数。
还可以将上述复杂度降为O(lgX n)。就是在找cnt，不需要每一行都二分查找，我们可以从矩阵的左下角往右上角阶梯查找，如果要查找的数更大，则往右移，否则往上移，每次查询只需要O(n)的时间，所以总时间是O(lgX n)。
代码如下：

class Solution {
private:
    int count_less_equal(vector<vector<int> >& matrix, int num)
    {
        int n = matrix.size(), i = n – 1, j = 0, cnt = 0;
        while (i >= 0 && j < n) {
            if (matrix[i][j] <= num) {
                cnt += i + 1;
                ++j;
            }
            else
                –i;
        }
        return cnt;
    }
public:
    int kthSmallest(vector<vector<int> >& matrix, int k)
    {
        int n = matrix.size(), left = matrix[0][0], right = matrix[n – 1][n – 1];
        while (left <= right) {
            int mid = left + (right – left) / 2;
            int cnt = count_less_equal(matrix, mid);
            if (cnt < k)
                left = mid + 1;
            else
                right = mid – 1;
        }
        return left;
    }
};

本代码提交AC，用时39MS。

LeetCode Heaters Winter is coming! Your first job during the contest is to design a standard heater with fixed warm radius to warm all the houses. Now, you are given positions of houses and heaters on a horizontal line, find out minimum radius of heaters so that all houses could be covered by those heaters. So, your input will be the positions of houses and heaters seperately, and your expected output will be the minimum radius standard of heaters. Note:

1. Numbers of houses and heaters you are given are non-negative and will not exceed 25000.
2. Positions of houses and heaters you are given are non-negative and will not exceed 10^9.
3. As long as a house is in the heaters’ warm radius range, it can be warmed.
4. All the heaters follow your radius standard and the warm radius will the same.

Input: [1,2,3],[2]
Output: 1
Explanation: The only heater was placed in the position 2, and if we use the radius 1 standard, then all the houses can be warmed.

Input: [1,2,3,4],[1,4]
Output: 1
Explanation: The two heater was placed in the position 1 and 4. We need to use radius 1 standard, then all the houses can be warmed.