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"

Example 2:

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

Example 3:

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

Example 4:

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

Note:

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.

---

给定一个只包含+-/的运算字符串，要求求出这个字符串的值，并且用最简分数的形式表示。 参考这篇博客，没什么技巧，就是用代码模拟手算的过程。首先求出所有分母的最小公倍数，然后通分，使得所有数的分母都相同，最后把所有通分过的分子加起来，得到结果。最最后一步就是把分子和分母约分。 这些步骤中涉及到求最小公倍数和最大公约数。最大公约数的求法gcd是必须掌握的，另外再根据gcd(x,y)*lcm(x,y)=x*y的性质，可以求到最小公倍数lcm(x,y)。 代码如下： [cpp] class Solution { private: int gcd(int x, int y) { while (y) { int tmp = x % y; x = y; y = tmp; } return x; } int lcm(int x, int y) { return x * y / gcd(x, y); } public: string fractionAddition(string expression) { vector<int> num, denom; // 分子，分母 expression += "+"; // 哨兵 int i = 0, j = 0; bool isnum = true; for (j = 0; j < expression.size(); ++j) { if (j != 0 && (expression[j] == ‘/’ || expression[j] == ‘-‘ || expression[j] == ‘+’)) { int one = atoi(expression.substr(i, j – i).c_str()); if (isnum)num.push_back(one); else denom.push_back(one); isnum = !isnum; if (expression[j] == ‘/’) i = j + 1; else i = j; } } int fm = 1; for (int i = 0; i < denom.size(); ++i)fm = lcm(fm, denom[i]); int fz = 0; for (int i = 0; i < num.size(); ++i)fz += num[i] * (fm / denom[i]); int g = 0; if (fz < 0) g = gcd(-fz, fm); else g = gcd(fz, fm); return to_string(fz / g) + "/" + to_string(fm / g); } }; [/cpp] 本代码提交AC，用时3MS。]]>

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.

Example 1:

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.

Example 2:

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.

---

给定房子和加热器的位置，问加热器的最小半径是所少才能使所有房子都在加热的范围之内。一个加热器的加热范围是一个圆，所有加热器的加热半径都是一样的。 要保证每个房子都在加热范围之内，且加热器的半径最小，则房子i肯定被紧邻i前后的两个加热器之一覆盖，其他加热器距离i的距离肯定比紧邻i前后的两个加热器远。比如x, i, y，i表示房子坐标，x和y分别表示紧邻i的两个加热器坐标，则覆盖i的最小半径应该是min(i-x,y-i)。 所以问题就转换为对每个房子坐标i，去加热器坐标数组中找到紧邻i前后的两个加热器坐标x和y，然后根据上述公式更新结果。为了便于查找，先对加热器坐标排序，然后直接二分查找就好了。 代码如下： [cpp] class Solution { public: int findRadius(vector<int>& houses, vector<int>& heaters) { sort(heaters.begin(), heaters.end()); int ans = 0; for (int i = 0; i < houses.size(); ++i) { int &pos = houses[i]; int r = INT_MAX; auto lb = lower_bound(heaters.begin(), heaters.end(), pos); if (lb > heaters.begin())r = min(r, pos – *(lb – 1)); auto ub = lower_bound(heaters.begin(), heaters.end(), pos); if (ub < heaters.end())r = min(r, *ub – pos); ans = max(ans, r); } return ans; } }; [/cpp] 本代码提交AC，用时89MS。 还可以自己写二分查找代码，如下： [cpp] class Solution { private: int my_lower_bound(vector<int>& v, int target) { int l = 0, r = v.size() – 1; while (l <= r) { int m = l + (r – l) / 2; if (target > v[m])l = m + 1; else r = m – 1; } return l; } public: int findRadius(vector<int>& houses, vector<int>& heaters) { sort(heaters.begin(), heaters.end()); int ans = 0, n = houses.size(), m = heaters.size(); for (int i = 0; i < n; ++i) { int &pos = houses[i]; int r = INT_MAX; int lb = my_lower_bound(heaters, pos); if (lb > 0)r = min(r, pos – heaters[lb – 1]); if (lb < m)r = min(r, heaters[lb] – pos); ans = max(ans, r); } return ans; } }; [/cpp] 本代码提交AC，用时76MS。]]>

LeetCode Subtree of Another Tree Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node’s descendants. The tree s could also be considered as a subtree of itself. Example 1: Given tree s:

     3
    / \
   4   5
  / \
 1   2

Given tree t:

   4
  / \
 1   2

Return true, because t has the same structure and node values with a subtree of s. Example 2: Given tree s:

     3
    / \
   4   5
  / \
 1   2
    /
   0

Given tree t:

   4
  / \
 1   2

Return false.

---

判断二叉树t是否是二叉树s的子树。如果t是s从node0开始的子树，则t必须和node0子树完全一样，node0不能有多余的孩子，比如样例2中node0的子树多有一个节点0，所以是False。 首先写一个子程序check判断子树s和t是否相等，然后在主程序中使用先序遍历s，如果发现s的某个节点node0的值和t的根节点相等，则可以进入check(node0,t)判断node0子树是否和t相等。 代码如下： [cpp] class Solution { private: bool check(TreeNode* s, TreeNode* t) { if ((s == NULL && t != NULL) || (s != NULL&&t == NULL))return false; if (s == NULL && t == NULL)return true; //s!=NULL&&t!=NULL return (s->val == t->val) && check(s->left, t->left) && check(s->right, t->right); } public: bool isSubtree(TreeNode* s, TreeNode* t) { if (t == NULL)return true; if (s == NULL)return false; queue<TreeNode*> q; q.push(s); while (!q.empty()) { TreeNode *tmp = q.front(); q.pop(); if (tmp->val == t->val) { if (check(tmp, t))return true; } if (tmp->left != NULL)q.push(tmp->left); if (tmp->right != NULL)q.push(tmp->right); } return false; } }; [/cpp] 本代码提交AC，用时29MS。 还有一种更简洁漂亮的解法。如果t是s的子树，有三种情况，t要么和s完全相等check(s,t)，要么等于s的某个左子树isSubtree(s->left,t)，要么等于s的某个右子树isSubtree(s->right,t)。所以主程序和子程序都可以递归。 代码如下： [cpp] class Solution { private: bool check(TreeNode* s, TreeNode* t) { if ((s == NULL && t != NULL) || (s != NULL&&t == NULL))return false; if (s == NULL && t == NULL)return true; //s!=NULL&&t!=NULL return (s->val == t->val) && check(s->left, t->left) && check(s->right, t->right); } public: bool isSubtree(TreeNode* s, TreeNode* t) { if (t == NULL)return true; if (s == NULL)return false; if (check(s, t))return true; return isSubtree(s->left, t) || isSubtree(s->right, t); } }; [/cpp] 本代码提交AC，用时32MS。]]>