矩阵问题
LC73 矩阵置零
 LC54 螺旋矩阵
 LC59 螺旋矩阵II
LC48 旋转图像
 LC74 Search a 2D Matrix
LC240 Search a 2D Matrix II
LC378 Kth Smallest Element in a Sorted Matrix

基本运算
LC371 两整数之和
 LC369, 给单链表加一
 LC55 加一
 LC2 两数相加
 LC415 字符串相加
 LC445 两数相加II
LC43 字符串相乘
 LC29 两数相除
 LC50 快速幂
 LC96 Sqrt(x)

浮点数比较
LC149 直线上最多的点数

日期间隔

溢出处理：
LC7 整数反转

进制转换：
LC13 罗马数字转整数 [优先匹配2字符]
❓LC168 Excel表列名称 [没有0，商借1给余数]

常见数列：
LC118 二项式系数
 LC119 二项式系数II

随机数：
LC470 用Rand7()实现Rand10()

日期间隔

矩阵

矩阵查找

LC74 Search a 2D Matrix
LC240 Search a 2D Matrix II
见二分查找#矩阵查找

LC378 Kth Smallest Element in a Sorted Matrix
见顺序统计量#矩阵上的TopK

矩阵置零

LC73 矩阵置零

最开始的想法：遍历矩阵的每一个元素，记录下所有要置零的行号和列号。之后再对这些行和列置零。最差情况为所有行和列都需要置零，则空间复杂度为$O(M + N)$。
改进：是否能把这最多(M + N)整合进原矩阵，又不损失原矩阵的信息呢？
我们的遍历顺序是从小到大的，因此我们只要把(M + N)的信息记录在我们已经遍历过的地方就可以了。最直接的办法就是记录在第一行和第一列。但是第一行加上第一列总共有(M + N - 1)个元素，我们还需要再用额外一个元素，就可以记录(M + N)个信息了。
设矩阵A大小为M x N

遍历第一行和第一列，将第一行是否需要置0记录在A[0,0]，将第一列是否需要置零记录在额外的空间上。
按从小到大的顺序遍历第i行第j列，如果A[i,j] = 0，则把A[0, j]和A[i, 0]变为0
检查第(2 … M)行第一个元素，如果是零，将该行置0
检查第一行第(2 … N)个元素，如果是零，将该列置0
现在我们可以处理第一行和第一列了：
检查A左上角元素，如果是0，将第一行置0
检查额外空间上记录的第一列是否需要置零，如果需要，将第一列置0

关于在C++的vector上使用memset
memset on vector C++, stackoverflow

If your vector contains POD types, it is safe to use memset on it - the storage of a vector is guaranteed to be contiguous.
memset(&vec[0], 0, sizeof(vec[0]) * vec.size());
Edit: Sorry to throw an undefined term at you - POD stands for Plain Old Data, i.e. the types that were available in C and the structures built from them.
Edit again: As pointed out in the comments, even though bool is a simple data type, vector<bool> is an interesting exception and will fail miserably if you try to use memset on it.

code

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        if(matrix.empty() || matrix.front().empty())
            return;
        
        auto m = matrix.size();
        auto n = matrix.front().size();
        auto isFirstColSetZero = false;

        for(size_t i = 0; i < m; ++i)
        {
            // check if any element on the first col is zero
            if(matrix[i][0] == 0) isFirstColSetZero = true;

            // then check other cols
            for(size_t j = 1; j < n; ++j)
            {
                if(matrix[i][j] == 0)
                {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }

        for(size_t i = 1; i < m; ++i)
        {
            if(matrix[i][0] == 0)
                memset(&matrix[i][0], 0, sizeof(matrix[i][0]) * n);
        }

        for(size_t j = 1; j < n; ++j)
        {
            if(matrix[0][j] == 0)
            {
                for(size_t i = 0; i < m; ++i)
                {
                    matrix[i][j] = 0;
                }
            }
        }
        
        // check first row
        if(matrix[0][0] == 0)
        {
            memset(&matrix[0][0], 0, sizeof(matrix[0][0]) * n);
        }

        // check first col
        if(isFirstColSetZero)
        {
            for(size_t i = 0; i < m; ++i)
            {
                matrix[i][0] = 0;
            }
        }
    }
};

矩阵遍历

LC54 螺旋矩阵

C++详细题解, Leetcode题解

设定上下左右边界：
- up = 0, bot = m - 1, left = 0, right = n - 1
按照右下左上的顺时针顺序遍历。
- 向右遍历到右边界后，向下移动上边界。
- 向下遍历到下边界后，向左移动右边界。
- 向左遍历到左边界后，向上移动下边界。
- 向上遍历到上边界后，向右移动左边界。
在移动边界时，如果发现上下边界交错或左右边界交错 —> 遍历结束，停止遍历。

code

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        // deal with empty matrices
        if(matrix.empty() || matrix.front().empty()) return {};
        // initialize boundaries
        int up = 0;
        int bot = matrix.size() - 1;
        int left  = 0;
        int right = matrix.front().size() - 1;
        // result vector
        auto res = vector<int>{};

        while(true)
        {
            // move to right
            for(int i = left; i <= right; ++i) res.push_back(matrix[up][i]);
            if(++up > bot) break;
            for(int i = up; i <= bot; ++i) res.push_back(matrix[i][right]);
            if(--right < left) break;
            for(int i = right; i >= left; --i) res.push_back(matrix[bot][i]);
            if(--bot < up) break;
            for(int i = bot; i >= up; --i) res.push_back(matrix[i][left]);
            if(++left > right) break;
        }

        return res;
    }
};

使用size_t来做逆向遍历时，一定要注意下溢。

常见的size_t下溢处理：

--right < left 改为 right-- < left + 1
for(int i = right; i >= left; --i) 改为 for(int i = right + 1; i-- >= left + 1;)

反向遍历的时候还是尽量用reverse_iterator不要用size_t了。用的话就一定要提高警惕性。

code

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        // deal with empty matrices
        if(matrix.empty() || matrix.front().empty()) return {};
        // initialize boundaries
        size_t up = 0;
        size_t bot = matrix.size() - 1;
        size_t left  = 0;
        size_t right = matrix.front().size() - 1;
        // result vector
        auto res = vector<int>{};

        while(true)
        {
            // move to right
            for(size_t i = left; i <= right; ++i) res.push_back(matrix[up][i]);
            if(++up > bot) break;
            for(size_t i = up; i <= bot; ++i) res.push_back(matrix[i][right]);
            if(right-- < left + 1) break;
            for(size_t i = right + 1; i-- >= left + 1;) res.push_back(matrix[bot][i]);
            if(bot-- < up + 1) break;
            for(size_t i = bot + 1; i-- >= up + 1; ) res.push_back(matrix[i][left]);
            if(++left > right) break;
        }

        return res;
    }
};

LC59 螺旋矩阵II

同上题，只不过这次是填充。

code

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        // define the matrix
        auto m = vector<vector<int>>(n, vector<int>(n, 0));
        int up = 0;
        int bot = n - 1;
        int left = 0;
        int right = n - 1;

        int num = 0;

        while(true)
        {
            for(int i = left; i <= right; ++i) m[up][i] = ++num;
            if(++up > bot) break;
            for(int i = up; i <= bot; ++i) m[i][right] = ++num;
            if(--right < left) break;
            for(int i = right; i >= left; --i) m[bot][i] = ++num;
            if(--bot < up) break;
            for(int i = bot; i >= up; --i) m[i][left] = ++num;
            if(++left > right) break;
        }

        return m;
    }
};

矩阵转置

LC48 旋转图像

思路1：先转置再逐行reverse。假设$\mathbb{R}^{N\timesN}$方阵，共做swap $\frac{(1 + (N - 1))(N-1)}{2} + N^2 / 2 = N^2 - N/2$次

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        for(size_t i = 0; i < matrix.size(); ++i)
        {
            for(size_t j = i + 1; j < matrix.size(); ++j)
            {
                swap(matrix[i][j], matrix[j][i]);
            }
        }

        for(auto& row : matrix)
        {
            reverse(row.begin(), row.end());
        }
    }
};

思路二：
每次在四元组(a,b,c,d)，其中a为左上角，设其为(i,j)内顺时针转动：

i每增加1，矩阵都缩小1
j每增加1，所有的点都顺时针移动1。a向右，b向下，c向左，d向上
a在左上角(i, j)
b一开始在右上角(0, n - 1)，向下动。一定位于矩阵的最右边那一行(0 + n - 1 - i)，而且j增加1就往下移动一格，所以猜测是(j, n - 1 - i)
c一开始在右下角(n - 1, n - 1)，向左动。一定位于矩阵的最后一行，j增加1就向左一行，所以(n - 1 - i, n - 1 - j)
d一开始在左下角(n - 1, 0)，向上动。一定位于矩阵最左边那一列，j增加1就向上一行(n - 1 - j, i);
i 在 0 到 (n + 1)/2 变化。j 在 0 到 n/2 变化。

基本运算

位运算实现加法

LC371 两整数之和

题目的思路就是运用了【XOR是不进位加法】和【位与之后左移一位是进位】：

先对两个数做XOR —> sum
再对两个数做位与后左移一位 —> carry。
用前两步的结果(sum 和 carry)再重复前面两步，直到第二步不再产生进位。

来自剑指Offer 56，以17和5为例子
十进制(XOR替换为不进位加法，位与左移替换为进位)：

| SUM | CARRY |
| ----| ----- |
| 12  | 10    |
| 20  | 0     |

二进制：(5: 00101, 17: 10001)

| SUM  | CARRY |
| ---- | ----- |
| 10100| 00010 |
| 10110| 00000 |

注意Leetcode里面不允许负数左移，所以需要cast一下

code Leetcode版本

class Solution {
public:
    int getSum(int num1, int num2){
        while(num2)
        {
            num1 = num1 ^ num2;
            num2 = static_cast<uint32_t>((num1 ^ num2) & num2) << 1;
        }
        return num1;
    }
};

大数加法

大数加法的思路：

从两个数的最低位开始
设一个变量为carry = 0
当第一个数没遍历完或第二个数没遍历完或 carry != 0
- 设一个临时变量tmp = carry
- 如果第一个数没遍历完tmp +=第一个数这一位，第一个数前进一位
- 如果第二个数没遍历完tmp +=第二个数这一位，第二个数前进一位
- 相加结果为tmp % 10，推入一个数组中
- 进位结果为tmp / 10
把之前储存结果的数组逆序即可

LC369, 给单链表加一

看了大数加法优化后的code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* plusOne(ListNode* head) {
        head = rotateList(head);
        auto newHead = head;
        ListNode* beforeHead = nullptr;
        int tmp = 1;
        while(head)
        {
            tmp += head->val;
            head->val = tmp % 10;
            tmp = tmp / 10;

            beforeHead = head;
            head = head->next;
        }

        if(tmp)
        {
            beforeHead->next = new ListNode{1};
        }

        return rotateList(newHead);
    }

    ListNode* rotateList(ListNode* head)
    {
        ListNode* newHead = nullptr;
        while(head)
        {
            auto next = head->next;
            head->next = newHead;
            newHead = head;
            head = next;            
        }

        return newHead;
    }
};

非常蠢的code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* plusOne(ListNode* head) {
        head = rotateList(head);
        auto ptr = head;
        auto carry = false;
        // the last digit
        ptr->val = ptr->val + 1;
        if(ptr->val == 10)
        {
            carry = true;
            ptr->val = 0;
        }

        ptr = ptr->next;

        if(!ptr)
        {
            if(carry)
            {
                head->next = new ListNode{1};
                return rotateList(head);            
            }
            else
            {
                return rotateList(head);
            }
        }

        while(ptr && ptr->next)
        {
            ptr->val = ptr->val + carry;
            if(ptr->val == 10)
            {
                ptr->val = 0;
                carry = true;
            }else
            {
                carry = false;
            }
            ptr = ptr->next;
        }

        // the first digit
        ptr->val = ptr->val + carry;
        if(ptr->val == 10)
        {
            ptr->next = new ListNode{1};
            ptr->val = 0;
        }

        return rotateList(head);
    }

    ListNode* rotateList(ListNode* head)
    {
        ListNode* newHead = nullptr;
        while(head)
        {
            auto next = head->next;
            head->next = newHead;
            newHead = head;
            head = next;            
        }

        return newHead;
    }
};

LC55 加一

在数组上实现加一。初始化carry = 1，反向遍历数组进行大数加法。如果数组遍历完成后依然有carry == 1，则说明需要在数组头部再插入一个1。

code

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int carry = 1;
        for(auto it = digits.rbegin(); 
            it != digits.rend() && carry; 
            ++it)
        {
            auto tmp = carry;
            tmp += *it;
            *it = tmp % 10;
            carry = tmp / 10;
        }

        if(carry)
        {
            digits.resize(digits.size() + 1);
            
            copy_backward(digits.begin(), digits.end() - 1, digits.end());
            digits.front() = carry;
        }

        return digits;
    }
};

LC2 两数相加

这个题已经帮你翻转过来了，非常轻松

code

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        auto dummy = ListNode{INT_MIN};
        auto np = &dummy;
        auto carry = 0;
        while(l1 || l2 || carry)
        {
            auto sum = carry;

            if(l1)
            {
                //backup
                auto next1 = l1->next;
                //slice
                l1->next = nullptr;
                // transform 
                sum += l1->val;
                // forward
                l1 = next1;
            }

            if(l2)
            {
                //backup
                auto next2 = l2->next;
                //slice
                l2->next = nullptr;
                // transform 
                sum += l2->val;
                // forward
                l2 = next2;
            }

            // splice
            auto tp = new ListNode{sum % 10};
            carry = sum / 10;
            np->next = tp;

            // forward
            np = np->next;
        }

        return dummy.next;

    }
};

LC445 两数相加II

这个题是单链表，并且数字不是逆序放置，也不让修改链表，将链表逆序。

思路：
无论如何都得从小往大加，只能通过两个栈来帮助逆序了。有些解法通过递归来逆序，然而我觉得还不如显式用栈来减少函数调用开销。毫无意义的一个题。

code

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        stack<int> stack1{};
        stack<int> stack2{};
        push_stack(l1, stack1);
        push_stack(l2, stack2);
        int carry = 0;

        auto dummy = ListNode{INT_MIN};
        auto end   = &dummy;

        while(!stack1.empty() || !stack2.empty() || carry)
        {
            int tmp = carry;
            if(!stack1.empty())
            {
                tmp += stack1.top();
                stack1.pop();
            }

            if(!stack2.empty())
            {
                tmp += stack2.top();
                stack2.pop();
            }
            
            end->next = new ListNode{tmp % 10};
            end = end->next;
            carry = tmp / 10;
        }

        return reverseList(dummy.next);
    }

    ListNode* reverseList(ListNode* head)
    {
        ListNode* ptr = nullptr;
        while(head)
        {
            auto next = head->next;
            head->next = ptr;
            ptr = head;
            head = next;
        }
        return ptr;
    }

    void push_stack(ListNode* head, stack<int>& s)
    {
        while(head)
        {
            s.push(head->val);
            head = head->next;
        }
    }
};

LC415 字符串相加

code

class Solution {
public:
    string addStrings(string num1, string num2) {
        auto res = string();
        auto carry = 0;
        for(auto it1 = num1.rbegin(), it2 = num2.rbegin();
            it1 != num1.rend() || it2 != num2.rend() || carry != 0;)
        {
            auto tmp = carry;

            if (it1 != num1.rend())
            {
                tmp += *it1 - '0';
                ++it1;
            }

            if (it2 != num2.rend())
            {
                tmp += *it2 - '0';
                ++it2;
            }
            
            res += to_string(tmp % 10);
            carry = tmp / 10;

        }
        reverse(res.begin(), res.end());
        return res;
    }
};

LC67 二进制求和

大数加法的二进制版本

code

class Solution {
public:
    string addBinary(string a, string b) {
        auto res = string{};
        int  carry = 0;

        auto it1 = a.rbegin();
        auto it2 = b.rbegin();

        while(it1 != a.rend() || it2 != b.rend() || carry)
        {
            int tmp = carry;
            if(it1 != a.rend())
            {
                tmp += (*it1 - '0');
                ++it1;
            }

            if(it2 != b.rend())
            {
                tmp += (*it2 - '0');
                ++it2;
            }

            res.append(to_string(tmp % 2));
            carry = tmp / 2;
        }

        reverse(res.begin(), res.end());

        return res;
    }
};

乘法

LC43 字符串相乘

思路一：普通竖式乘法。

用一个数字从后往前的每一位，乘上另一个数字从后往前的每一位。每次前进一位不要忘了补0。之后再用大数加法将结果加起来。速度非常的慢。

code

class Solution {
public:
    string multiply(string num1, string num2) {
        
        if(num1 == "0" || num2 == "0") return "0";
        if(num1.size() < num2.size()) return multiply(num2, num1);
        int base = 0;
        string res{};
        res += '0';
        for(auto i = num1.rbegin(); i != num1.rend(); ++i)
        {
            int carry = 0;
            string t{};
            auto j = num2.rbegin();
            while(j != num2.rend() || carry)
            {
                int tmp = carry;
                if(j != num2.rend())
                {
                    tmp += (*i - '0') * (*j - '0');
                    ++j;
                }
                t += to_string(tmp % 10);
                carry = tmp / 10;
            }
            reverse(t.begin(), t.end());
            // add zeros
            for(int i = 0; i < base; ++i)
            {
                t += '0';
            }
            res = addStrings(res, t);
            ++base;
        }
        return res;
    }

    string addStrings(string num1, string num2) {
        auto res = string();
        auto carry = 0;
        for(auto it1 = num1.rbegin(), it2 = num2.rbegin();
            it1 != num1.rend() || it2 != num2.rend() || carry != 0;)
        {
            auto tmp = carry;

            if (it1 != num1.rend())
            {
                tmp += *it1 - '0';
                ++it1;
            }

            if (it2 != num2.rend())
            {
                tmp += *it2 - '0';
                ++it2;
            }
            
            res += to_string(tmp % 10);
            carry = tmp / 10;

        }
        reverse(res.begin(), res.end());
        return res;
    }
};

思路二：改进的竖式乘法
Easiest JAVA Solution with Graph Explanation

M位的数和N位的数相乘，结果最多M+N位，比如(123(3位) x 999(3位) < 123 x 1000 = 123000(6位))
从左往右数，第一个数的第i位和第二个数的第j位相乘，结果最多也只能是两位数。并且应该被放置在i + j和i + j + 1位上。
我们仍然从右往左算，但要注意进位。在从右往左的过程中，只有i + j + 1和原来的地方有重叠。

注意：

在这题当中第一次用到逆序的size_t做index，不可以像下面这么写

// this is wrong!
for(size_t i = container.size() - 1; i >= 0; --i)
{
    ...
}

因为当 i == 0时，--i还会再发动一次，这就导致size_t类型直接下溢。

正确的写法是

for(size_t i = container.size(); i--;)
{
    ...
}

直接把decreasing放在条件处，并使用后置形式。这样在第一次进入循环时，i == container.size() - 1，并且最后一次时也不会下溢。

code

class Solution {
public:
    string multiply(string num1, string num2) {
        // num1 has M digits, num2 has N digits
        // then the num1 * num2 has at most M + N digits
        if(num1 == "0" || num2 == "0") return "0";
        vector<int> res(num1.size() + num2.size(), 0);

        // watch out: reverse size_t indices will underflow
        for(size_t i = num1.size(); i--;)
        {
            // watch out: reverse size_t indices will underflow
            for(size_t j = num2.size(); j--;)
            {
                int tmp = (num1[i] - '0') * (num2[j] - '0');
                auto idx1 = i + j;
                auto idx2 = i + j + 1;
                tmp += res[i + j + 1];
                res[i + j] += tmp / 10;
                res[i + j + 1] = tmp % 10;
            }
        }

        string res_str{};
        // avoid leading zeros
        for(auto it = find_if(res.begin(), res.end(), [](int x){
            return x != 0;
        });
            it != res.end(); ++it)
        {
            res_str += to_string(*it);
        }

        return res_str;
    }

};

不用乘除取余做除法

LC29 Divide Two Integers

因为不允许使用int64_t，导致边界条件判断非常复杂。再加上LeetCode编译器不允许负数位移，可以说是LeetCode恶心之最。TODO

求整数的平方根

LC96 Sqrt(x)

见二分查找#数学上的二分查找##求整数的平方根

快速幂

LC50 快速幂

将幂指数n分解为二进制数，之后进行运算。
举例：
$11 = 1011_{2}$
$x^11 = x^{1 \times 2^0 + 1\times 2^1 + 0 \times 2^2 + 1 \times 2^3} = x^0 \times x^1 \times x^3$

思路：
将幂指数不断右移，查询最后一位，如果是1，就乘上对应的项即可。

注意：

需要处理负数。
神经病一样的测试用例：指数为INT_MIN

code

class Solution {
public:
    double myPow(double x, int pow) {
        // pow could be INT_MIN
        // we cannot reverse the sign of INT_MIN if pow is type int.
        int64_t n = pow;
        // deal with negative power
        if(n < 0)
        {
            x = 1. / x;
            n = -n;
        }
        
        // compute 
        double res = 1.;
        while(n)
        {
            if(n & 1) res *= x;
            n >>= 1;
            x*=x;
        }
        return res;
    }
};

浮点数比较

如何正确比较浮点数

What is the most effective way for float and double comparison? : stackoverflow

bool approximatelyEqual(float a, float b, float epsilon)
{
    return fabs(a - b) <= ( (fabs(a) < fabs(b) ? fabs(b) : fabs(a)) * epsilon);
}

bool essentiallyEqual(float a, float b, float epsilon)
{
    return fabs(a - b) <= ( (fabs(a) > fabs(b) ? fabs(b) : fabs(a)) * epsilon);
}

bool definitelyGreaterThan(float a, float b, float epsilon)
{
    return (a - b) > ( (fabs(a) < fabs(b) ? fabs(b) : fabs(a)) * epsilon);
}

bool definitelyLessThan(float a, float b, float epsilon)
{
    return (b - a) > ( (fabs(a) < fabs(b) ? fabs(b) : fabs(a)) * epsilon);
}

直线上最多的点数

LC149 直线上最多的点数
方法一：
解决浮点数比较的最好办法，就是尽量不要去比较。
思路：对于每一个点$p_i$，遍历所有其他的点$p_j$，统计斜率相等的个数的最大值。遍历所有的点，计算所有最大值的最大值即为所求。
注意：

斜率用浮点数表示会出现精度问题。可以采用分数表示：
- 设A = x2 - x2, B = y2 - y1
- 如果A = 0，统一令B = INT_MAX
- 如果B = 0, 统一令A = INT_MAX
- 如果 A != 0 && B != 0
  - 计算A和B的最大公约数，可以用<numeric>库中的std::gcd(C++17)
  - A和B都除最大公约数约分。
  - 注意A和B的符号，如果A和B都为负或 B负A正，翻转A和B的符号。
测试用例中有重复的点。我们需要记录重复的点的个数，最后加到$p_i$的斜率相等个数最大值上。

code

class Solution {
private:
    using slope = tuple<int, int>;
public:
    int maxPoints(vector<vector<int>>& points) {
        if(points.empty())    return 0;
        if(points.size() < 2) return 1;
        if(points.size() < 3) return points.size();
        int res = 0;
        for(auto i = points.begin(); i != points.end(); ++i)
        {
            int duplicateCnt = 0;
            int pointMax = 0;
            auto slopes = map<slope, int>{};

            for(auto j = i + 1; j != points.end(); ++j)
            {
                if( (*i)[0] == (*j)[0] && (*i)[1] == (*j)[1] )
                {
                    ++duplicateCnt;
                    continue;
                }

                auto s = slopeFromPts((*i)[0], (*i)[1],(*j)[0],(*j)[1]);
                ++slopes[s];
                pointMax = max(pointMax, slopes[s]);
            }
            res = max(res, pointMax + duplicateCnt + 1);
        }
        return res;
    }
    static inline slope slopeFromPts(int x1, int y1, int x2, int y2)
    {
        // y = (y1 - y2) / (x1 - x2) * x + B
        int A1 = y1 - y2;
        int A2 = x1 - x2;

        if(A1 == 0)
        {
            A2 = INT_MAX;
        }
        else if(A2 == 0)
        {
            A1 = INT_MAX;
        }
        else
        {
            int g  = gcd(A1, A2);
            A1 /= g;
            A2 /= g;
            if ((A1 < 0 && A2 < 0) || (A1 > 0 && A2 < 0)){A1 = -A1; A2 = -A2;}
        }

        return {A1, A2};
    }
};

Leetcode上的double精度不够，必须得用long double才能通过一些测试。

code

class Solution {
private:
    using slope = long double;
public:
    int maxPoints(vector<vector<int>>& points) {
        if(points.empty())    return 0;
        if(points.size() < 2) return 1;
        if(points.size() < 3) return points.size();
        int res = 0;
        for(auto i = points.begin(); i != points.end(); ++i)
        {
            int duplicateCnt = 0;
            int pointMax = 0;
            auto cmp = [](slope a, slope b)
            {
                return b - a > (fabs(a) < fabs(b) ? fabs(b) : fabs(a)) * LDBL_EPSILON;
            };
            auto slopes = map<slope, int, decltype(cmp)>{cmp};

            for(auto j = i + 1; j != points.end(); ++j)
            {
                if( (*i)[0] == (*j)[0] && (*i)[1] == (*j)[1] )
                {
                    ++duplicateCnt;
                    continue;
                }

                auto s = slopeFromPts((*i)[0], (*i)[1],(*j)[0],(*j)[1]);
                ++slopes[s];
                pointMax = max(pointMax, slopes[s]);
            }
            res = max(res, pointMax + duplicateCnt + 1);
        }
        return res;
    }
    static inline slope slopeFromPts(slope x1, slope y1, slope x2, slope y2)
    {
        return approximatelyEqual(x1,x2) ? LDBL_MAX : (y2 - y1) / (x2 - x1);
    }

    static inline bool approximatelyEqual(slope a, slope b)
    {
        return fabs(a - b) <= ((fabs(a) < fabs(b) ? fabs(b) : fabs(a)) * LDBL_EPSILON);
    }
};

溢出处理

整数反转

LC7 整数反转

思路：把一个数mod 10取个位，再除10去掉个位。把结果乘10，再把个位加到结果上。
注意：res = res * 10 + pop这一步会溢出。分四种情况：

如果res > INT_MAX / 10必然溢出。
如果res == INT_MAX / 10则pop > 7溢出。
如果res < INT_MIN / 10必然溢出。
如果res == INT_MIN / 10则pop < -8溢出。

code

class Solution {
public:
    int reverse(int x) {
        int rev = 0;
        while(x)
        {
            int pop = x % 10;
            x /= 10;
            // rev = rev * 10 + pop : this will overflow
            // situation1: INT_MAX = 2147483647
            if(rev > INT_MAX / 10 || (rev == INT_MAX && pop > 7))
                return 0;
            // situation2: INT_MIN = -2147483648
            if(rev < INT_MIN / 10 || (rev == INT_MIN && pop < -8))
                return 0;
            rev = rev * 10 + pop;
        }

        return rev;
        
    }
};

进制转换

十进制转换为N进制

除N取余，逆序排列。

LC168 Excel表列名称

'A' - 'Z'表示1 ~ 26的数字。但是没有0。如果取余出现了0，就要从商中借1给余数，让余数变为26。

class Solution {
public:
    string convertToTitle(int n) {
        auto ans = string{};
        while(n)
        {
            auto remainder = n % 26;
            n  = n / 26;
            
            if(remainder == 0)
            {
                --n;
                remainder = 26;
            }

            ans += static_cast<char>(remainder - 1) + 'A';
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

罗马数字

LC13 罗马数字转整数

罗马数字转换就是从左到右累加的过程。

每次优先读取两个字符类的数字：IV = 4, IX = 9, XL = 40, XC = 90, CD = 400, CM = 900
如果无法匹配两个字符，就尝试匹配一个字符：I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1000
将所有匹配制作成hashmap即可。

code

class Solution {
private:
    unordered_map<string, int> romanIntMap;
public:
    Solution()
    : romanIntMap{
        {"I", 1},
        {"V", 5},
        {"X", 10},
        {"L", 50},
        {"C", 100},
        {"D", 500},
        {"M", 1000},
        {"IV", 4},
        {"IX", 9},
        {"XL", 40},
        {"XC", 90},
        {"CD", 400},
        {"CM", 900}
    }
    {}
    int romanToInt(string s) {
        int ans = 0;

        for(size_t i = 0; i < s.size();)
        {
            size_t match = 2;
            // try to match two chars(or one if not enough)
            auto str = s.substr(i, match);
            // if we cannot match two, we just match one instead
            if(!romanIntMap.count(str))
            {
                --match;
                str = s.substr(i, match);
            }
            ans += romanIntMap[str];
            i += match;
        }

        return ans;
    }
};

常见数列

二项式系数

二项式系数是$(1 + x)^n$展开后，$x$的系数。其第$n$行第$i$项为组合数$C_n^i$的值：
$(1 + x)^0 = 1$
$(1 + x)^1 = x + 1$
$(1 + x)^2 = x^2 + 2x + 1$
$(1 + x)^3 = x^3 + 3x^2 + 3x + 1$
$\cdots$

计算二项式系数时，可以初始化第0行为1。其后每一行的第一个和最后一个元素都为1。除首尾外，第n行的第i个元素为b[n][i] = b[n - 1][i - 1] + b[n - 1][i]，只和前一行相关。

LC118 二项式系数

生成二项式系数的前$n$行。

code

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        if(numRows == 0) return {};
        auto res = vector<vector<int>>(1, vector<int>(1, 1));
        for(;--numRows;)
        {
            auto&& row = vector<int>(res.back().size() + 1, 1);
            
            for(size_t j = 1; j < row.size() - 1; ++j)
            {
                row[j] = res.back()[j - 1] + res.back()[j]; 
            }

            res.emplace_back(move(row));
        }
        return res;
    }
};

LC119 二项式系数II

生成二项式系数的第$k$行。反向填表即可。

code

class Solution {
public:
    vector<int> getRow(int k) {
        auto res = vector<int>(k + 1, 1);

        for(int i = 1; i < k; ++i)
        {
            for(int j = i; j > 0; --j)
            {
                res[j] = res[j - 1] + res[j];
            }
        }

        return res;

    }
};

卡塔兰数

LC96 不同的二叉搜索树

每次我们选一个i当作根节点的时候，其实左右子树的数量和左右区间的具体范围无关，只和左右区间的大小有关。因此我们可以总结出下面的式子：
设$G(n)$为以$1 \cdots n$为节点的二叉搜索树个数，那么以第$0< i <= n$个数字为根结点，左右子树能够产生的组合个数是：

$G(n - i) * G(i - 1)$

那么总的个数就是：

$G(n) = \sum_{i = 1}^{n} G(n - i) * G(i - 1)$

定义边界条件

$G(0) = 1$, $G(1) = 1$

不难看出这是一个动态规划问题，为了避免重复计算，我们可以记录已经计算过的结果。或者从底向上填表。这个题因为状态转移方程中涉及之前所有的状态，所以似乎不能进行很好的空间复杂度的优化。

DP自底向上填表

class Solution {
public:
    int numTrees(int n) {
        // DP chart
        auto nums = vector<int>{};
        // stop conditions: G(0) == 1, G(1) == 1
        nums.push_back(1);
        nums.push_back(1);

        for(int i = 2; i <= n; ++i)
        {
            auto sum = 0;
            for(int j = 1; j <= i; ++j)
            {
                sum += nums[i - j] * nums[j - 1];
            }
            nums.push_back(sum);
        }
        return nums.back();
    }
};

事实上$G(n)$被称为卡塔兰数，递推公式可以写作$Gn = \frac{4n + 2}{n + 2}G{n -1}$，$G_0 = 1$。通项公式为$G_n = \frac{(2n)!}{(n+1)!n!}$。因此，我们可以在线性时间内，常数空间复杂度的情况下算出$G_n$。

随机数

拒绝采样

LC470 用Rand7()实现Rand10()

参考由rand7生成rand10以及随机数生成方法的讨论 - 毕达哥拉斯半圆

思路一：
调用两次Rand7()，将会生成共$7 \times 7 = 49$种有序数对。我们拒绝采样其中9种有序数对，则剩下的有序数对出现的概率都为$\frac{1}{40}$。我们将剩下的有序数对每10个一组依次对应[1,10]的一个值。

+----------------------+                 +---------------+
| | 1| 2| 3| 4| 5| 6| 7|                 | |1|2|3|4|5|6|7|
+----------------------+                 +---------------+
|1| 1| 2| 3| 4| 5| 6| 7|                 |1|2|3|4|5|6|7|8|
+----------------------+                 +---------------+
|2| 8| 9|10|11|12|13|14|                 |2|9|A|1|2|3|4|5|
+----------------------+                 +---------------+
|3|15|16|17|18|19|20|21|   mod 10) + 1   |3|6|7|8|9|A|1|2|
+----------------------+ +------------>  +---------------+
|4|22|23|24|25|26|27|28|   reject >=41   |4|3|4|5|6|7|8|9|
+----------------------+                 +---------------+
|5|29|30|31|32|33|34|35|                 |5|A|1|2|3|4|5|6|
+----------------------+                 +---------------+
|6|36|37|38|39|40|41|42|                 |6|7|8|9|A|1|X|X|
+----------------------+                 +---------------+
|7|43|44|45|46|47|48|49|                 |7|X|X|X|X|X|X|X|
+----------------------+                 +---------------+

第一个随机数auto row = rand7()决定在左表中的行数。第二个随机数auto col = rand7()决定在左表中的列数。则表中的数字可以由行列唯一决定auto num = 7 * (row - 1) + col。如果得到的数字num > 40，就拒绝这一次采样。

设拒绝概率为$P_r$，成功产生随机数时，调用rand7()的期望次数为级数$2 \times (1 + P_r + P_r^2 + P_r^3 + \cdots)$的和。因为$P_r < 1$，所以该级数和收敛于$2 \times \frac{1}{1 - P_r}$，本例中为$2.45$。

code

class Solution {
public:
    int rand10() {
        int i = 0;
        do
        {
            i = 7 * (rand7() - 1) + rand7();
        }
        while(i > 40);
        return (i % 10) + 1;
    }
};

思路二：
通过拒绝采样，使得auto row = rand7()只能取得[1,2]，auto col = rand7()只能取得[1, 5]。

+-+--------------+
| | 1| 2| 3| 4| 5|
+----------------+
|1| 1| 2| 3| 4| 5|
+----------------+
|2| 6| 7| 8| 9|10|
+----------------+

只需返回 5 * (row - 1) + col即可。

code

class Solution {
public:
    int rand10() {
        int row, col = 0;
        do
        {
            row = rand7();
        }
        while(row > 2);
        do
        {
            col = rand7();
        }
        while(col > 5);

        return 5 * (row - 1) + col;
    }
};

两次产生随机数的事件是独立的，那么成功地产生随机数的概率为$P = \frac{5}{7} \times \frac{2}{7} = 10/49$。产生失败的概率为$P = 39/49$。则期望的调用次数为$2 \times \frac{1}{1 - \frac{39}{49}} = 9.8$次。

Xuanyi Fu Blog

数学类问题

日期间隔

矩阵

矩阵查找

矩阵置零

矩阵遍历

矩阵转置

基本运算

位运算实现加法

大数加法

乘法

不用乘除取余做除法

求整数的平方根

快速幂

浮点数比较

如何正确比较浮点数

直线上最多的点数

溢出处理

整数反转

进制转换

十进制转换为N进制

罗马数字

常见数列

二项式系数

卡塔兰数

随机数

拒绝采样