4. 编程算法

4.1. 找出数组中的特异数字（Single Number）

1 个数字出现奇数次，其余数字出现偶数次。Hint：异或运算。
2 个数字出现奇数次，其余数字出现偶数次。Hint：先做异或运算，得到的是这两个数的异或结果；找到该结果的二进制表示中为 1 的某一位，根据该位为 0/1 将数组分为两组，分别做异或运算。

https://www.jianshu.com/p/e1331664c8cf
1 个数字出现 $1$ 次，其余数字出现 $k$ 次。Hint：利用大小为 32 的数组，统计二进制各位出现 1 的次数，对 $k$ 取模；最终 32 位数组的值就是 Single Number 的二进制表示。

https://cloud.tencent.com/developer/article/1131946
一般情形：1 个数字出现 $p$ 次，其余数字出现 $k$ 次。

https://blog.csdn.net/wlwh90/article/details/89712795

https://cloud.tencent.com/developer/article/1131945

https://leetcode.com/problems/single-number-ii/discuss/43295/Detailed-explanation-and-generalization-of-the-bitwise-operation-method-for-single-numbers

4.2. 均匀分布生成其他分布的方法

Hint：中心极限定理。

https://blog.csdn.net/haolexiao/article/details/60511164

4.3. 海量数据处理

Hint：哈希方法，把大文件划分成小文件，读进内存依次处理，如果需要统计频率/个数，再用哈希表；Bitmap，用一个（或几个）比特位来标记某个元素对应的值。

// Bitmap

#include <iostream>
#include <bitset>
using namespace std;

const int BITSPERWORD = 32;
const int SHIFT = 5;        // i / 32 = i >> 5
const int MASK = 0x1f;      // i % 32 = i & 0x1f
const int N = 10000;
int a[1 + N/BITSPERWORD];

// 设置第 i 位为 1
inline void set(int i)
{
    a[i >> SHIFT] |= 1 << (i & MASK);
}
// 设置第 i 位为 0
inline void clear(int i)
{
    a[i >> SHIFT] &= ~ (1 << (i & MASK));
}
// 检查第 i 位的值是否为 0
inline int test(int i)
{
    return a[i >> SHIFT] & (1 << (i & MASK));
}

int main()
{
    set(40);
    cout << bitset<BITSPERWORD>(a[40 >> SHIFT]) << endl; // 00000000000000000000000100000000
    cout << test(40) << endl;
    return 0;
}

面试题集锦

https://blog.csdn.net/v_july_v/article/details/6685962
大文件中返回频数最高的100个词

https://blog.csdn.net/tiankong_/article/details/77240283

4.4. 链表

对每一个节点操作之前，应先考虑该节点是否为空。

[LeetCode] Reverse Linked List 反转链表。Hint：方法一，逐个反转；方法二，递归；方法三，使用栈保存节点的值，反向赋给所有节点。

struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

// 方法一，逐个反转
ListNode* reverseList(ListNode* head)
{
    if(!head || !head->next) return head;
    ListNode* curr = head->next;
    head->next = nullptr;
    while(curr)
    {
        ListNode* post = curr->next;
        curr->next = head;
        head = curr;
        curr = post;
    }
    return head;
}

// 方法二，递归
ListNode* reverseList(ListNode* head)
{
    if(head == nullptr || head->next == nullptr) return head;
    else
    {
        ListNode* newHead = reverseList(head->next);
        head->next->next = head; // head 指向的下一个节点是 newHead 的最后一个节点
        head->next = nullptr;
        return newHead;
    }
}

// 方法三，使用栈保存节点的值，占用 O(n) 额外空间
ListNode* reverseList(ListNode* head)
{
    if(head == nullptr || head->next == nullptr) return head;
    stack<int> stk;
    ListNode* p = head;
    while(p)
    {
        stk.emplace(p->val);
        p = p->next;
    }
    p = head;
    while(p)
    {
        p->val = stk.top();
        stk.pop();
        p = p->next;
    }
    return head;
}

[LeetCode] Reverse Nodes in k-Group 从头节点开始，每 $k$ 个节点为一组进行反转。Hint：对每一组节点调用反转函数。延伸：从尾节点开始，每 $k$ 个节点为一组进行反转。Hint：先反转整个链表；按上述方法反转每一组；再反转整个链表。

https://leetcode.com/problems/reverse-nodes-in-k-group/

// 从头节点开始分组

class Solution
{
public:
    ListNode* reverseKGroup(ListNode* head, int k)
    {
        return reverseK(head, k);
    }
private:
    ListNode* reverseAll(ListNode* head)
    {
        if(!head || !head->next) return head;
        ListNode* newHead = reverseAll(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newHead;
    }
    ListNode* reverseK(ListNode* head, int k)
    {
        if(!head || !head->next) return head;
        ListNode* p = head;
        for(int i = 1; i < k; ++i)
        {
            p = p->next;
            if(!p) return head;
        }
        ListNode* secondHead = reverseK(p->next, k);
        p->next = nullptr; // 第一组的尾节点置为 NULL，便于直接调用 reverseAll
        ListNode* newHead = reverseAll(head);
        head->next = secondHead; // 反转之后，head 成为第一组的尾节点
        return newHead;
    }
};

// 从尾节点开始分组

ListNode* reverseKGroup(ListNode* head, int k)
{
    ListNode* newHead = reverseAll(head);
    newHead = reverseK(newHead, k);
    newHead = reverseAll(newHead);
    return newHead;
}

求有环单链表中的环长、环起点、链表长。Hint：快慢指针。

https://www.cnblogs.com/xudong-bupt/p/3667729.html

// 判断链表是否有环

class Solution
{
public:
    bool hasCycle(ListNode *head)
    {
        if(!head || !head->next) return false;
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast) return true;
        }
        return false;
    }
};

判断两个链表是否相交并找出交点。Hint：方法一，先求两个链表的长度差，双指针法；方法二，分别用栈保存两个链表的节点的地址（指针），从后往前比较。如果只需要判断两个链表是否相交，只需判断两个链表最后一个节点是否相同。

https://blog.csdn.net/jiary5201314/article/details/50990349

单链表 $\mathcal{O}(1)$ 时间删除给定节点。Hint：交换当前节点与下一个节点的值，删除下一个节点。

https://blog.csdn.net/qq_35546040/article/details/80341136

bool removeNode(ListNode* pNode)
{
    if(pNode == nullptr) return true;
    if(pNode->next == nullptr) return false;
    pNode->val = pNode->next->val;
    pNode->next = pNode->next->next;
    return true;
}
// 注：如果需要删除最后一个节点，直接令 pNode->next = nullptr 是无法改变实参的（传值调用），可以将形参定义成指向指针的指针
// 必须从链表头节点开始遍历，找到该节点的前驱节点
// 还要考虑该链表只有一个节点的情形
// 另外，可以在该函数内 delete 该指针，但是需要确保在其他地方不再需要访问 pNode 指向的内容

输出该链表中倒数第 $k$ 个节点。Hint：双指针法，第一个指针先走 $k-1$ 步，然后第二个指针从头节点开始，与第一个指针同步往后移；当第一个指针移到最后一个节点，第二个指针即指向倒数第 $k$ 个节点。延伸：删除倒数第 $k$ 个节点，需要注意删除头节点的情况。

ListNode* FindKthToTail(ListNode* pListHead, unsigned int k)
{
    if(!pListHead || k == 0) return nullptr;

    unsigned int tk = 1;
    ListNode* p = pListHead;
    while(tk < k)
    {
        p = p->next;
        if(!p) return nullptr;
        tk += 1;
    }

    ListNode* pk = pListHead;
    while(p->next)
    {
        p = p->next;
        pk = pk->next;
    }
    return pk;
}

// 删除倒数第 k 个节点
ListNode* removeNthFromEnd(ListNode* head, int n)
{
    if(!head || n <= 0) return head;
    ListNode* pre = head;
    ListNode* post = head;
    for(int i = 0; i < n; ++i)
    {
        post = post->next;
        if(!post)
        {
            if(i < n-1) return head;
            else
            // 删除头节点
            {
                pre = head->next;
                delete(head);
                return pre;
            }
        }
    }
    while(post->next)
    {
        pre = pre->next;
        post = post->next;
    }
    post = pre->next->next;
    delete(pre->next);
    pre->next = post;
    return head;
}

[LeetCode] Sort List 链表排序。Hint：方法一，快速排序或归并排序；方法二，遍历链表把值存入数组，使用数组的排序方法，再把值赋回链表。

https://leetcode.com/problems/sort-list/

// 快速排序

class Solution
{
public:
    ListNode* sortList(ListNode* head)
    {
        quickSort(head, nullptr);
        return head;
    }
private:
    // 由于链表无法反向遍历，需要重新考虑如何交换两个位置的数值
    // pre 指向 curr 的前一个数，或者指向第一个比 key 大的数的前一个数
    // 当 curr 指向的数比 key 小，pre 移到下一位，交换两者的值
    ListNode* partion(ListNode* head, ListNode* tail)
    {
        int key = head->val;
        ListNode* pre = head;
        ListNode* curr = head->next;
        while(curr != tail)
        {
            if(curr->val < key)
            {
                pre = pre->next;
                swap(pre->val, curr->val);
            }
            curr = curr->next;
        }
        swap(head->val, pre->val);
        return pre;
    }
    void quickSort(ListNode* head, ListNode* tail)
    {
        if(head == tail || (head->next) == tail) return;
        ListNode* mid = partion(head, tail);
        quickSort(head, mid);
        quickSort(mid->next, tail);
    }
};

// 归并排序

class Solution
{
private:
    ListNode* getMid(ListNode* head)
    {
        if(!head || !head->next) return head;
        ListNode* slow = head;
        ListNode* fast = head->next;
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
    ListNode* merge(ListNode* head1, ListNode* head2)
    {
        // 可以 new 一个节点作为临时头节点，代码会更简洁，但是会增加空间开销、降低时间效率
        if(!head1) return head2;
        if(!head2) return head1;
        ListNode* tmp_head;
        if(head1->val <= head2->val)
        {
            tmp_head = head1;
            head1 = head1->next;
        }
        else
        {
            tmp_head = head2;
            head2 = head2->next;
        }
        ListNode* p = tmp_head;
        while(head1 && head2)
        {
            if(head1->val <= head2->val)
            {
                p->next = head1;
                head1 = head1->next;
            }
            else
            {
                p->next = head2;
                head2 = head2->next;
            }
            p = p->next;
        }
        if(head1) p->next = head1;
        if(head2) p->next = head2;
        return tmp_head;
    }
    ListNode* mergeSort(ListNode* head)
    {
        if(!head || !head->next) return head;
        ListNode* mid = getMid(head);
        ListNode* head_post = mid->next;
        mid->next = nullptr;
        head = mergeSort(head);
        head_post = mergeSort(head_post);
        return merge(head, head_post);
    }
public:
    ListNode* sortList(ListNode* head)
    {
        return mergeSort(head);
    }
};

将二叉搜索树转换为升序排序的双向链表。Hint：中序遍历。

struct TreeNode
{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution
{
public:
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        pRootOfTree = converTree2List(pRootOfTree);
        return pRootOfTree;
    }
private:
    // 返回的是转换之后的链表的头节点
    TreeNode* converTree2List(TreeNode* root)
    {
        if(!root) return nullptr;

        TreeNode* l = converTree2List(root->left);
        while(l && l->right) l = l->right; // 根节点应该接在左子树链表的尾节点之后
        if(l) l->right = root;
        root->left = l;

        TreeNode* r = converTree2List(root->right);
        if(r) r->left = root;
        root->right = r; // 根节点应该接在右子树链表的头节点之前

        while(root->left) root = root->left; // 找到头节点
        return root;
    }
};

删除链表中的重复节点。Hint：可能会删除头节点；注意尾节点处是否有重复元素。

class Solution
{
public:
    ListNode* deleteDuplicates(ListNode* head)
    {
        if(!head || !head->next) return head;
        ListNode* tmp_head = new ListNode(-1);
        tmp_head->next = head;
        ListNode* pre = tmp_head;
        ListNode* curr = head;
        while(curr && curr->next)
        {
            if(curr->val == curr->next->val)
            {
                while(curr->next && curr->val == curr->next->val) curr = curr->next;
                curr = curr->next;
                if(!curr || !curr->next) pre->next = curr;
            }
            else
            {
                pre->next = curr;
                pre = curr;
                curr = curr->next;
            }
        }
        head = tmp_head->next;
        delete(tmp_head); tmp_head = nullptr;
        return head;
    }
};

重组链表，首尾交错，L0→L1→…→Ln-1→Ln 转换为 L0→Ln→L1→Ln-1→L2→Ln-2→…。Hint：首先，链表中间截断；然后，第二段链表翻转；最后，合并两个子链表。

class Solution
{
public:
    void reorderList(ListNode* head)
    {
        if(!head || !head->next || !head->next->next) return;

        // 第一步：找到中间节点
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }

        // 第二步：翻转第二段链表
        ListNode* secondHead = slow->next;
        slow->next = nullptr; // 第一段链表的尾节点
        ListNode* p = secondHead->next;
        secondHead->next = nullptr; // 第二段链表的尾节点
        ListNode* q;
        while(p)
        {
            q = p->next;
            p->next = secondHead;
            secondHead = p;
            p = q;
        }

        // 第三步：交叉合并两个子链表
        ListNode* h1 = head;
        ListNode* h2 = secondHead;
        while(h1 && h2)
        {
            ListNode* h1Post = h1->next;
            ListNode* h2Post = h2->next;
            h1->next = h2;
            h2->next = h1Post;
            h1 = h1Post;
            h2 = h2Post;
        }
    }
};

[LeetCode] Partition List 分割链表，小于 $x$ 的排前面，不小于 $x$ 的排后面。Hint：建立两个新的链表，一个链表连接小于 $x$ 的节点，另一个链表连接其他节点，最后把这两个链表串起来。

https://leetcode.com/problems/partition-list/

class Solution
{
public:
    ListNode* partition(ListNode* head, int x)
    {
        if(!head || !head->next) return head;
        ListNode* h1 = new ListNode(x);
        ListNode* p1 = h1;
        ListNode* h2 = new ListNode(x);
        ListNode* p2 = h2;
        ListNode* q = head;
        while(q)
        {
            if(q->val < x)
            {
                p1->next = q;
                p1 = p1->next;
            }
            else
            {
                p2->next = q;
                p2 = p2->next;
            }
            q = q->next;
        }
        p2->next = nullptr; // 尾节点置为空
        p1->next = h2->next;
        head = h1->next;
        delete h1;
        delete h2;
        return head;
    }
};

4.5. [LeetCode] Sort Colors 三颜色排序

https://blog.csdn.net/princexiexiaofeng/article/details/79645511

class Solution
{
public:
    void sortColors(vector<int>& nums)
    {
        if(nums.size() <= 1) return;
        int left = 0;
        int right = nums.size() - 1;
        for(int mid = left; mid <= right; ++mid)
        {
            while(nums[mid] == 2 && mid < right)
            {
                swap(nums[mid], nums[right]);
                right--;
            }
            while(nums[mid] == 0 && mid > left)
            {
                swap(nums[mid], nums[left]);
                left++;
            }
        }
    }
};

// 注：要先判断 nums[mid] == 2，再判断 nums[mid] == 0，否则会出错，如 [1,2,0]
// 因为 2 是往后交换，0 是往前交换；2 交换得到的可能是 0，但可以保证 0 交换得到的不会是 2，因为 2 在 0 之前被处理了
// 如果判断顺序反过来，2 交换得到的 0 不会被处理

4.6. 找到数组第 $k$ 大的数

https://leetcode.com/problems/kth-largest-element-in-an-array/

排序。时间复杂度 $\mathcal{O}(N \log N)$ 。
伪排序：$k$ 次遍历数组，每次从剩余数字中找一个最大值。时间复杂度 $\mathcal{O}(kN)$ 。
借助大小为 $k$ 的最小堆。时间复杂度 $\mathcal{O}(N \log k)$ 。

快排思想。时间复杂度 $\mathcal{O}(N)$ 。

class Solution
{
public:
    int partition(vector<int>& nums, int i, int j)
    {
        int pivot = nums[i];
        int l = i+1;
        int r = j;
        while(true)
        {
            while(l <= j && nums[l] < pivot) l++;
            while(r > i && nums[r] > pivot) r--;
            if(l >= r) break;
            swap(nums[l], nums[r]);
            l++;
            r--;
        }
        swap(nums[i], nums[r]);
        return r;
    }
    // partition 可用如下更简洁的形式
    int partition(vector<int>& nums, int i, int j)
    {
        int pivot = nums[i];
        int l = i;
        int r = j+1;
        while(true)
        {
            while(nums[++l] < pivot && l < j);
            while(nums[--r] > pivot);
            if(l >= r) break;
            swap(nums[l], nums[r]);
        }
        swap(nums[i], nums[r]);
        return r;
    }

    // T(n) = T(n/2) + O(n)，时间复杂度 O(n)
    int quicksort(vector<int>& nums, int a, int b, int k)
    {
        int p = partition(nums, a, b);
        if(b - p + 1 == k) return p;
        if(b - p + 1 < k) return quicksort(nums, a, p-1, k - (b - p + 1));
        else return quicksort(nums, p+1, b, k);
    }
    int findKthLargest(vector<int>& nums, int k)
    {
        int k_id = quicksort(nums, 0, nums.size()-1, k);
        return nums[k_id];
    }
};

4.7. [LeetCode] Best Time to Buy and Sell Stock 买卖股票的最佳时间

最多一次交易

http://www.cnblogs.com/grandyang/p/4280131.html

class Solution
{
public:
    int maxProfit(vector<int>& prices)
    {
        if(prices.size() <= 1) return 0;
        int profit = 0;
        int minimal = INT_MAX;
        for(int p: prices)
        {
            profit = max(profit, p - minimal);
            minimal = min(p, minimal);
        }
        return profit;
    }
};

无限次交易

http://www.cnblogs.com/grandyang/p/4280803.html

class Solution
{
public:
    int maxProfit(vector<int>& prices)
    {
        if(prices.size() <= 1) return 0;
        int profit = 0;
        for(int i = 0; i < prices.size() - 1; ++i) profit += max(prices[i+1] - prices[i], 0);
        return profit;
    }
};

最多两次交易

http://www.cnblogs.com/grandyang/p/4281975.html
最多k次交易

http://www.cnblogs.com/grandyang/p/4295761.html

https://blog.csdn.net/linhuanmars/article/details/23236995

交易冷却

https://www.cnblogs.com/grandyang/p/4997417.html

// buy[i] = max(buy[i-1], cool[i-1] - prices[i])
// sell[i] = max(sell[i-1], buy[i-1] + prices[i])
// cool[i] = sell[i-1] => buy[i] = max(buy[i-1], sell[i-2] - prices[i])

class Solution
{
public:
    int maxProfit(vector<int>& prices)
    {
        if(prices.size() <= 1) return 0;
        int pre_sell = 0;
        int sell = 0;
        int pre_buy = INT_MIN;
        int buy = 0;
        for(int p : prices)
        {
            buy = max(pre_buy, pre_sell - p); // 这里的 pre_sell 其实是 pre_pre_sell
            pre_sell = sell; // pre_sell 更新晚一步
            sell = max(pre_sell, pre_buy + p);
            pre_buy = buy;
        }
        return sell;
    }
};

4.8. [LeetCode] Partition Equal Subset Sum 数组分成两个子集，和相等

https://leetcode.com/problems/partition-equal-subset-sum/

class Solution(object):
    def backtrack(self, nums, sum_nums, sum_current, i): ## self
        if sum_current == sum_nums / 2:
            return True
        if i == len(nums):
            return False
        if self.backtrack(nums, sum_nums, sum_current+nums[i], i+1): ## self
            return True
        if self.backtrack(nums, sum_nums, sum_current, i+1): ## self
            return True
        return False

    def canPartition(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if len(nums) <= 1:
            return False
        sum_nums = sum(nums)
        if sum_nums % 2:
            return False
        return self.backtrack(nums, sum_nums, 0, 0) ## self

4.9. [LeetCode] Find All Anagrams in a String 统计变位词出现的位置

Hint：采用滑动窗口和 计数器 进行比较。

https://leetcode.com/problems/find-all-anagrams-in-a-string/

/* https://leetcode.com/problems/find-all-anagrams-in-a-string/discuss/92027/C%2B%2B-O(n)-sliding-window-concise-solution-with-explanation */

class Solution
{
public:
    vector<int> findAnagrams(string s, string p)
    {
        vector<int> vec;
        if(s.size()<p.size() || (s.empty() && p.empty())) return vec;
        vector<int> p_counter(26, 0), s_counter(26, 0);
        for(int i = 0; i < p.size(); ++i)
        {
            ++p_counter[p[i]-'a'];
            ++s_counter[s[i]-'a'];
        }
        if(p_counter == s_counter) vec.push_back(0);
        for(int i = p.size(); i < s.size(); ++i)
        {
            --s_counter[s[i-p.size()]-'a'];
            ++s_counter[s[i]-'a'];
            if(s_counter == p_counter) vec.push_back(i-p.size()+1);
        }
        return vec;
    }
};

4.10. 寻找重复数

数值范围为 $\{ 1,2,3,...,n \}$ ，有的出现 2 次，有的出现 1 次。Hint：把数组元素的值当做下标，由于元素存在重复，因此必然会 重复多次访问同一个位置 。从另一个角度讲，访问序列中存在“环”。排序的时间复杂度高，哈希不满足空间复杂度为 $\mathcal{O}(1)$ 的要求。

[LeetCode] Find the Duplicate Number 找到一个重复数字（共有 $n+1$ 个数）。

https://leetcode.com/problems/find-the-duplicate-number/

http://www.cnblogs.com/grandyang/p/4843654.html

// 解法一：快慢指针，寻找某个“环”的入口
class Solution
{
public:
    int findDuplicate(vector<int>& nums)
    {
        int slow = 0, fast = 0, t = 0;
        while (true)
        {
            slow = nums[slow]; // 注意，这里下标没有减 1
            fast = nums[nums[fast]];
            if (slow == fast) break;
        }
        while (true)
        {
            slow = nums[slow];
            t = nums[t];
            if (slow == t) break;
        }
        return slow;
    }
};

// 解法二：不断交换位置，找到第一个重复访问的元素
class Solution
{
public:
    int findDuplicate(vector<int>& nums)
    {
        int duplicate = -1;
        for(int k = 0; k < nums.size(); ++k)
        {
            while(nums[k]-1 != k)
            {
                if(nums[k] == nums[nums[k]-1])
                {
                    duplicate = nums[k];
                    break;
                }
                swap(nums[k], nums[nums[k]-1]);
                // 一次交换之后，下标为 nums[k]-1 的元素就等于 nums[k] 了。
            }
            if(duplicate != -1) break;
        }
        return duplicate;
    }
};

[LeetCode] Find All Duplicates in an Array 找到所有重复数字（共有 $n$ 个数）。

https://leetcode.com/problems/find-all-duplicates-in-an-array/

http://www.cnblogs.com/grandyang/p/6209746.html

// 解法一：将访问过的元素置为相反数（负数），如果下次访问到一个负数，说明这个元素被重复访问
class Solution
{
public:
    vector<int> findDuplicates(vector<int>& nums)
    {
        vector<int> res;
        for (int i = 0; i < nums.size(); ++i)
        {
            int idx = abs(nums[i]) - 1;
            if (nums[idx] < 0) res.push_back(idx + 1);
            else nums[idx] = -nums[idx];
        }
        return res;
    }
};

// 解法二：不断交换位置使得 i == nums[i]-1
class Solution
{
public:
    vector<int> findDuplicates(vector<int>& nums)
    {
        vector<int> duplicate;
        for(int i = 0; i < nums.size(); ++i)
        {
            while(nums[nums[i] - 1] != nums[i]) swap(nums[i], nums[nums[i] - 1]);
        }
        for(int i = 0; i < nums.size(); ++i)
        {
            if(i != nums[i] - 1) duplicate.push_back(nums[i]);
        }
        return duplicate;
    }
};

[LeetCode] First Missing Positive 找到第一个消失的正整数。Hint：假设数组长度为 $n$ ，则第一个消失的正整数所在区间是 $[1, n+1]$ ，注意：输入数组中可能存在负数和0。延伸：找到第一个大于 $K$ 的正整数。Hint：可知目标数所在区间是 $[K+1, K+n+1]$ ；先删除数组中不在该区间的整数；其余数都减 $K$ ，范围变成 $[1, n+1]$ ，后续解法同上。

https://leetcode.com/problems/first-missing-positive/

// 解法一：将访问过的元素置为相反数（负数）
class Solution
{
public:
    int firstMissingPositive(vector<int>& nums)
    {
        int n = nums.size();
        for(auto& m: nums) if(m <= 0) m = n + 1; // 先处理非正整数，全部置为 n+1
        for(auto& m: nums)
        {
            int i = abs(m) - 1;
            if(i < n && nums[i] > 0) nums[i] = -nums[i];
        }
        for(int i = 0; i < n; ++i)
        {
            if(nums[i] > 0) return i+1;
        }
        return n + 1;
    }
};

// 解法二：不断交换位置使得 i == nums[i]-1
class Solution
{
public:
    int firstMissingPositive(vector<int>& nums)
    {
        int n = nums.size();
        for(auto& m: nums)
        {
            while(m > 0 && m <= n && m != nums[m-1]) swap(m, nums[m-1]);
        }
        for(int i = 0; i < n; ++i)
        {
            if(nums[i] != i + 1) return i+1;
        }
        return n+1;
    }
};

4.11. [LeetCode] Spiral Matrix 环形打印矩阵

https://leetcode.com/problems/spiral-matrix/

class Solution
{
public:
    void tranverseMatrixAccorindTo4Directions(vector<vector<int>> &matrix, const unsigned int row, const unsigned int col, int start, vector<int>& vec)
    {
        // 特别注意
        // 如果把 start, endX, endY, k 声明为 unsigned int 类型，在减到 0 的时候可能会死循环，因为 unsigned int 类型不会小于 0。

        int endX = row - 1 - start;
        int endY = col - 1 - start;

        // 1 向右
        for(int k = start; k <= endY; ++k) vec.push_back(matrix[start][k]);

        // 2 向下
        for(int k = start+1; k <= endX; ++k) vec.push_back(matrix[k][endY]);

        // 3 向左：要求至少存在两行（不加判断会重复扫描同一行）
        if(endX > start) for(int k = endY-1; k >= start; --k) vec.push_back(matrix[endX][k]);

        // 4 向上：要求至少存在两列（不加判断会重复扫描同一列）
        if(endY > start) for(int k = endX-1; k > start; --k) vec.push_back(matrix[k][start]);

    }
    vector<int> spiralOrder(vector<vector<int>>& matrix)
    {
        vector<int> vec;
        unsigned int row = matrix.size();
        if(row == 0) return vec;
        unsigned int col = matrix[0].size();
        if(col == 0) return vec;
        int start = 0;
        // 循环中止条件：圈数判断（ (start,start) 是每一圈的入口坐标）
        while(start * 2 < row && start * 2 < col)
        {
            tranverseMatrixAccorindTo4Directions(matrix, row, col, start, vec);
            ++start;
        }
        return vec;
    }
};

4.12. [LeetCode] Longest Consecutive Sequence 最长连续序列

Hint：方法一，排序；方法二，对于每个元素 $n$ ，搜索 $n+1$ 是否在数组中，使用 hash/set 可以获得 $\mathcal{O}(1)$ 的查找复杂度。

https://leetcode.com/problems/longest-consecutive-sequence/

class Solution(object):
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        longest = 0
        num_set = set(nums)

        for num in nums:
            if num-1 not in num_set:
                current_long = 1
                while num + 1 in num_set:
                    current_long += 1
                    num += 1
                longest = max(longest, current_long)

        num_set.clear()

        return longest

4.13. 跳跃的蚂蚱

从 0 点出发，往正或负向跳跃，第一次跳跃一个单位，之后每次跳跃距离比上一次多一个单位，跳跃多少次可到到达坐标 $x$ 处？ Hint：走 $n$ 步之后能到达的坐标是一个公差为 2 的等差数列（如 $n=2$ ，可到达 $\{-3,-1,1,3\}$ ）。只需找到最小的 $n$ 使得

\[(1+2+...+n) - x = \frac{n(n+1)}{2} - x\]

是非负偶数。跳到 $x$ 和跳到 $-x$ 的次数相同，因此只考虑 $x$ 为正的情况。

https://www.zhihu.com/question/50790221

// 作者：Rukia
// 链接：https://www.zhihu.com/question/50790221/answer/125213696

int minStep(int x)
{
  if (x == 0) return 0;
  if (x < 0) x = -x;
  int n = sqrt(2*x); // 快速找到一个接近答案的 n
  while ((n+1)*n/2-x & 1 || (n+1)*n/2 < x) // & 的优先级低
          ++n;
  return n;
}

4.14. 求 $n$ 的阶乘末尾有多少个 $0$

Hint：1 个 $5$ 和1个 $2$ 搭配可以得到 1 个 $0$ ；$2$ 的个数比 $5$ 多，因此只关心 $5$ 的个数；$25$ 包含 2 个 $5$ ，$125$ 包含 3 个 $5$ …。

class Solution
{
public:
    int trailingZeroes(int n)
    {
        if(n <= 0) return 0;
        int res = 0;
        while(n)
        {
            res += n / 5;
            n /= 5;
        }
        return res;
    }
};

4.15. 求一个整数的二进制表示中 $1$ 的个数

Hint：移位操作；负数可能造成死循环。

C++中，指定移位次数大于或等于对象类型的比特数（如 int 型的 32 位），或者对负数进行左移操作，结果都是未定义的 。例如：n >> 32 是未定义的，但是允许 n >>= 1 执行无限次，这是安全的。

// 方法一：不断右移 n。如果 n 是负数，需要保持最高位为 1，不断移位后这个数字会变成 0xFFFFFFFF 而陷入死循环。
int numberOf1(int n)
{
  int cnt = 0;
  while(n)
  {
    if(n & 1) cnt++;
    n >>= 1;
  }
  return cnt;
}

// 方法二：n 不动，左移一个比较子。
int numberOf1(int n)
{
  int cnt = 0;
  unsigned int flag = 1;
  while(flag) // 连续左移32次之后为0
  {
    if(n & flag) cnt++;
    flag <<= 1;
  }
  return cnt;
}

// 方法三：把一个整数减 1，再和原整数做逻辑与运算，会把该整数最右边的一个 1 变成 0。
int numberOf1(int n)
{
  int cnt = 0;
  while(n)
  {
    cnt++;
    n = (n - 1) & n;
  }
  return cnt;
}

4.16. [LeetCode] Subarray Sum Equals K 子数组和为 $K$

Hint：依次求数组的前 $n$ 项和 $s[n]$ ，$n \in [0, N]$ （注意：0 也在内），将和作为哈希表的 key，和的值出现次数作为 value；如果存在 $s[i]−s[j]=K \ (i \gt j)$ ，则 $s[i]$ 和 $s[j]$ 都应该在哈希表中。

https://leetcode.com/problems/subarray-sum-equals-k/

## https://leetcode.com/problems/subarray-sum-equals-k/solution/ : Approach #4 Using hashmap

from collections import defaultdict
class Solution(object):
    def subarraySum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """

        if len(nums) == 0:
            return 0

        N = len(nums)

        sum_to_num = defaultdict(int)
        sum_to_num[0] = 1 ## 前 0 项和

        cnt = 0
        tmp_sum = 0
        for n in nums:
            tmp_sum += n
            diff = tmp_sum - k
            cnt += sum_to_num[diff]
            sum_to_num[tmp_sum] += 1

        return cnt

4.17. 使用位运算进行加法运算

Hint：原位加法运算等效为 ^ 运算，进位等效为 & 和 移位 的复合。 注：C++不允许对负数进行左移运算。

https://leetcode.com/problems/sum-of-two-integers/

class Solution
{
public:
    int getSum(int a, int b)
    {
        int sum, carry;
        do
        {
            sum = (a ^ b);
            carry = (a & b & INT_MAX) << 1; // & INT_MAX 操作保证移位前的数是正数，否则结果是未定义的。
            a = sum;
            b = carry;
        }while(b != 0);
        return a;
    }
};

from numpy import int32

class Solution(object):
    def getSum(self, a, b):
        """
        :type a: int
        :type b: int
        :rtype: int
        """
        a, b = int32(a), int32(b)

        while True:
            a, b = a ^ b, (a & b) << 1
            print a, b
            if b == 0:
                break

        return int(a)

## 注意，这里并没有与 0x7fffffff 做 & 运算
## 假设 a & b = -16，-16 & 0x7fffffff = 2147483632
## C++ 中，对 2147483632 左移1位使得最高位符号位为 1，得到 -32
## python中，2147483632的符号位为 0，继续左移1位，会直接做大整数运算，得到 4294967264L，导致不能得到正确结果
## python 中，使用type()查看数据类型时发现，有时候系统会把 int32 转化为 int64，或者 int64 转为 int32，疑惑中。。。

4.18. [LeetCode] Longest Substring with At Least K Repeating Characters 包含重复字符的最长子串

Hint：由于该字符串只包含小写字母，因此直接使用长度为26的静态数组来统计字符频率更为简洁高效，不需要使用map。

https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/

// https://www.cnblogs.com/grandyang/p/5852352.html
// 使用一个int型（32位）的mask，指示各字符频率是否到达k
// 以每一个字符作为起点，往后统计。时间复杂度 O(N^2)
// mask第 idx 位从 0 -> 1，表示对应字符出现了，但是未达到k次
// mask第 idx 位从 1 -> 0，表示对应字符已经出现了k次
// mask变成 0，表示这段子串满足要求

class Solution
{
public:
    int longestSubstring(string s, int k)
    {
        int ans = 0;
        int start = 0;
        while(start + k <= s.size())
        {
            int hash[26] = {0};
            int mask = 0;
            int next_start = start + 1;
            for(int end = start; end < s.size(); ++end)
            {
                int idx = s[end] - 'a';
                ++hash[idx];
                if(hash[idx] < k) mask |= (1 << idx); // 0 -> 1
                else mask &= ~(1 << idx);             // 1 -> 0
                if(mask == 0)
                {
                    ans = max(ans, end - start + 1);
                    next_start = end + 1;
                }
            }
            start = next_start;
        }
        return ans;
    }
};

4.19. 几个数的和

[LeetCode] Two Sum 两数之和为目标值。Hint：哈希，时间复杂度 $\mathcal{O}(N)$ 。

https://leetcode.com/problems/two-sum/

class Solution
{
public:
    vector<int> twoSum(vector<int>& nums, int target)
    {
        vector<int> res;
        map<int, int> hash;
        for(size_t k = 0; k < nums.size(); k++) hash[nums[k]] = k;
        for(size_t k = 0; k < nums.size(); k++)
        {
            if(hash.find(target - nums[k]) != hash.end())
            {
                if(hash[target - nums[k]] > k) // 避免重复统计同一对
                {
                    res.push_back(k);
                    res.push_back(hash[target - nums[k]]);
                }
            }
        }
        return res;
    }
};

[LeetCode] 3Sum 3 个数之和为 0。Hint：先排序；双指针；时间复杂度 $\mathcal{O}(N^2)$ 。

https://leetcode.com/problems/3sum/

class Solution
{
public:
    vector<vector<int>> threeSum(vector<int>& nums)
    {
        vector<vector<int>> result;
        if(nums.size()<3) return result;
        sort(nums.begin(), nums.end());
        unsigned int n = nums.size();
        int target = 0;
        for(unsigned int i = 0; i + 2 < n; ++i)
        {
            if(i > 0 && nums[i] == nums[i-1]) continue; // 忽略重复值
            if(nums[i] + nums[i+1] + nums[i+2] > target) break; // 下界
            if(nums[i] + nums[n-2] + nums[n-1] < target) continue; // 上界
            unsigned int left = i + 1;
            unsigned int right = n - 1;
            while(left < right)
            {
                if(nums[i]+nums[left]+nums[right] == target)
                {
                    result.push_back(vector<int>{nums[i], nums[left], nums[right]});
                    // 找到之后，两个指针都需要移动，并忽略重复值
                    do{++left;}while(nums[left] == nums[left-1] && left < right);
                    do{--right;}while(nums[right] == nums[right+1] && left < right);
                }
                else if(nums[i]+nums[left]+nums[right] < target)
                {
                    do{++left;}while(nums[left] == nums[left-1] && left < right);
                }
                else
                {
                    do{--right;}while(nums[right] == nums[right+1] && left < right);
                }
            }
        }
        return result;
    }
};

[LeetCode] 4Sum 4 个数之和为目标值。Hint：先排序；双指针；时间复杂度 $\mathcal{O}(N^3)$ 。

https://leetcode.com/problems/4sum/

class Solution
{
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target)
    {
        vector<vector<int>> quad;
        if(nums.size() < 4) return quad;
        unsigned int n = nums.size();
        sort(nums.begin(), nums.end());
        for(unsigned int i = 0; i + 3 < n; ++i)
        {
            if(i > 0 && nums[i] == nums[i-1]) continue; // 忽略重复值
            if(nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target) break; // 下界
            if(nums[i] + nums[n-3] + nums[n-2] + nums[n-1] < target) continue; // 上界
            for(unsigned int j = i + 1; j + 2 < n; ++j)
            {
                if(j > i + 1 && nums[j] == nums[j-1]) continue; // 忽略重复值
                if(nums[i] + nums[j] + nums[j+1] + nums[j+2] > target) break; // 下界
                if(nums[i] + nums[j] + nums[n-2] + nums[n-1] < target) continue; // 上界
                unsigned int left = j + 1;
                unsigned int right = n - 1;
                while(left < right)
                {
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if(sum == target)
                    {
                        quad.push_back(vector<int>{nums[i], nums[j], nums[left], nums[right]});
                        // 找到之后，两个指针都需要移动，并忽略重复值
                        do
                        {
                            ++left;
                        }
                        while(nums[left] == nums[left-1] && left < right);
                        do
                        {
                            --right;
                        }
                        while(nums[right] == nums[right+1] && left < right);
                    }
                    else if(sum < target)
                    {
                        do
                        {
                            ++left;
                        }
                        while(nums[left] == nums[left-1] && left < right);
                    }
                    else
                    {
                        do
                        {
                            --right;
                        }
                        while(nums[right] == nums[right+1] && left < right);
                    }
                }
            }
        }
        return quad;
    }
};

[LeetCode] 4Sum II 4 个数和为 0 的组合数。Hint：两两之和存入哈希表，时间复杂度和空间复杂度 $\mathcal{O}(N^2)$ 。

https://leetcode.com/problems/4sum-ii/
$\color{darkgreen}{Code}$
```
1def fourSumCount(self, A, B, C, D):
2    AB = collections.Counter(a+b for a in A for b in B)
3    return sum(AB[-c-d] for c in C for d in D)
```

4.20. [LeetCode] Maximum Product Subarray 求连续子数组的最大乘积

Hint：数组中存在负数，负负得正，因此相比于连续子数组最大和问题，不仅需要记录以每个元素结尾的连续乘积的最大值，还需要记录最小值。

https://leetcode.com/problems/maximum-product-subarray/

class Solution
{
public:
    int maxProduct(vector<int>& nums)
    {
        int pre_min = nums[0];
        int pre_max = nums[0];
        int curr_min = nums[0];
        int curr_max = nums[0];
        int maxproduct = nums[0];
        for(int k = 1; k < nums.size(); ++k)
        {
            curr_min = min(nums[k], min(pre_min*nums[k], pre_max*nums[k]));
            curr_max = max(nums[k], max(pre_min*nums[k], pre_max*nums[k]));
            maxproduct = max(maxproduct, curr_max);
            pre_min = curr_min;
            pre_max = curr_max;
        }
        return maxproduct;
    }
};

4.21. 统计 1 的数目

给定一个十进制整数 $N$ ，统计从 $1$ 到 $N$ 所有的整数各位出现的 $1$ 的数目。Hint： $1$ 的数目 = 个位出现 $1$ 的数目 + 十位出现 $1$ 的数目 + 百位出现 $1$ 的数目 + ……。以百位为例：如果百位数字为0，则百位出现1的次数只由更高位决定，如12013，次数为12 * 100；如果百位数字为1，则百位出现1的次数由更高位和更低位同时决定，如12113，次数为12 * 100 + (13 + 1)；如果百位数字大于1，则百位出现1的次数只由更高位决定，如12213，次数为(12 + 1) * 100。时间复杂度 $\mathcal{O}(\log_{10}(N))$ 。

https://leetcode.com/problems/number-of-digit-one

http://www.cnblogs.com/jy02414216/archive/2011/03/09/1977724.html

typedef unsigned long long Ull;
class Solution
{
public:
    int countDigitOne(int n)
    {
        Ull factor = 1;
        Ull low, curr, high;
        Ull res = 0;
        while(n / factor)
        {
            low = n % factor;
            curr = (n / factor) % 10;
            high = n / (factor * 10);
            switch(curr)
            {
                case 0:
                    res += high * factor;
                    break;
                case 1:
                    res += high * factor + low + 1;
                    break;
                default:
                    res += (high + 1) * factor;
            }
            factor *= 10;
        }
        return res;
    }
};

4.22. 数组循环移位

循环右移 $K$ 位，时间复杂度 $\mathcal{O}(N)$ 。Hint：三次翻转。

void reverse(int *arr, int begin, int end)
{
    for(; begin < end; begin++, end--) swap(arr[begin], arr[end]);
}

void right_shift(int *arr, int N, int K)
{
    K %= N;
    reverse(arr, 0, N-K-1);
    reverse(arr, N-K, N-1);
    reverse(arr, 0, N-1);
}

4.23. [LeetCode] Divide Two Integers 整数除法

Hint：先取绝对值，做正整数之间的除法；防止溢出。

https://leetcode.com/problems/divide-two-integers/

class Solution
{
public:
    int divide(int dividend, int divisor)
    {
        if(dividend == INT_MIN && divisor == -1) return INT_MAX; // 越界则输出最大值
        if(dividend == INT_MIN && divisor == 1) return INT_MIN;
        if(dividend == INT_MIN && divisor == INT_MIN) return 1; // 枚举分子为最小整数时的情形
        if(divisor == INT_MIN) return 0;

        bool sign = (dividend>0) ^ (divisor>0) ? false : true;

        int res = 0;

        bool max_flow = false;
        if(dividend == INT_MIN)
        {
            dividend = abs(1 + INT_MIN); // 防止取绝对值之后溢出
            max_flow = true;
        }
        else dividend = abs(dividend);
        divisor = abs(divisor);

        while(dividend >= divisor)
        {
            int diff = divisor;
            int n = 1;
            while(diff <= (dividend >> 1))
            {
                diff <<= 1;
                n <<= 1;
            }
            dividend -= diff;
            res += n;
        }
        if(max_flow && dividend == divisor-1) res += 1;

        return sign? res : -res;
    }
};

4.24. [LeetCode] Fraction to Recurring Decimal 循环小数

Hint：小数除法：余数乘以10再求余；如果余数出现重复，则说明是循环小数。

https://leetcode.com/problems/fraction-to-recurring-decimal/

class Solution
{
public:
    string fractionToDecimal(int numerator, int denominator)
    {
        if(numerator == 0 || denominator == 0) return "0";
        int sign_num = numerator > 0? 1:-1;
        int sign_den = denominator > 0? 1:-1;

        long long num = abs((long long)numerator);
        long long den = abs((long long)denominator);

        long long integer = num / den;
        long long rem = num % den;

        string int_part = to_string(integer);
        if(rem) int_part += ".";

        string frac_part = "";
        unordered_map<long long, int> mp;
        int idx = 0;

        while(rem)
        {
            if(mp.find(rem) != mp.end()) // 余数重复
            {
                frac_part.insert(mp[rem], "(");
                frac_part += ")";
                break;
            }
            mp[rem] = idx++;
            frac_part += to_string((10*rem) / den);
            rem = (10*rem) % den;
        }

        string res = "";
        if(sign_num * sign_den < 0) res += "-";
        res += int_part + frac_part;
        return res;
    }
};

4.25. 旋转数组查找

Hint：采用二分查找的思路。

二分查找

// preliminary: binary search，时间复杂度 O(logN)
template<class T>
int binarySearch(T* arr, int n, const T& target)
{
    if(arr == nullptr || n <= 0) return -1;
    int low = 0;
    int high = n - 1; // 查找区间： [0, n)
    while(low <= high)
    {
        int mid = low + (high - low) / 2; // mid = (low + high)/2 可能导致溢出
        if(arr[mid] == target) return mid;
        if(arr[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

// 浮点数二分，不存在区间取整，要求达到某个精度

// 例：在区间 [low, high] 二分查找开方数

#define eps 1e-5

bool judge(double mid, double x)
{
    return mid >= x / mid;
}

double search(double low, double high, double x)
{
    while(high - low > eps)
    {
        double mid = low + (high - low) / 2;
        if(judge(mid, x)) high = mid;
        else low = mid;
    }
    return low + (high - low) / 2; // 此时 low 和 high 比较接近，取它们的均值作为最终结果
}

## 返回区间 [first, last) 内第一个不小于 target 的位置
## 如果所有数都小于 target，则返回 last
def lower_bound(a, first, last, target):
    if first > last:
        return None
    while first < last: ## [first, last)不为空
        mid = first + (last - first) // 2
        if a[mid] < target:
            first = mid + 1
        else:
            last = mid
    return first
    ## 返回 last 也行，因为 [first, last) 为空的时候它们相等

查找旋转数组最小值（含重复元素）

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/

// 方法一
// 第一个指针总指向前面递增数组的元素
// 第二个指针总指向后面递增数组的元素
// 最终两个指针指向相邻元素：第一个指针指向前面递增数组的最后一个元素，第二个指针指向后面递增数组的第一个元素（也就是最小元素）
template<class T>
int findRotateMin(T* arr, int n)
{
    if(arr == nullptr || n <= 0) return -1;
    int low = 0;
    int high = n - 1;
    while(arr[low] >= arr[high])
    {
        if(high - 1 == low) return high;

        int mid = low + (high - low) / 2;

        // 如果这三个元素相等，则在区间 [low, high] 内顺序查找
        if(arr[low] == arr[mid] && arr[mid] == arr[high]) return (min_element(arr + low, arr + high + 1) - arr);

        if(arr[mid] <= arr[high]) high = mid;
        else low = mid;
    }
    // 如果数组本身是有序的，即 arr[0] < arr[n-1]，则第一个元素就是最小值
    return 0;
}

# 方法二
# 每次比较 nums[mid] 与 nums[high]，如果两者相等，则 --high
class Solution:
    def findMin(self, nums: List[int]) -> int:
        n = len(nums)
        low = 0
        high = n - 1
        while low < high:
            mid = low + (high - low) // 2
            if nums[mid] == nums[high]:
                high -= 1
            else:
                if nums[mid] > nums[high]:
                    low = mid + 1
                else:
                    high = mid
        return nums[low]

在旋转数组查找目标值（无重复元素）

https://leetcode.com/problems/search-in-rotated-sorted-array/

// 每次比较 nums[mid] 与 nums[high]
class Solution
{
public:
    int search(vector<int>& nums, int target)
    {
        int n = nums.size();
        if(n == 0) return -1;
        int low = 0;
        int high = n - 1;
        while(low <= high)
        {
            int mid = low + (high - low) / 2;
            if(nums[mid] == target) return mid;

            if(nums[mid] < nums[high]) // 注：只有当 low == high，才会出现： mid == high，nums[mid] == nums[high]
            {
                if(nums[mid] < target && target <= nums[high]) low = mid + 1;
                else high = mid - 1;
            }
            else
            {
                if(nums[mid] > target && target >= nums[low]) high = mid - 1;
                else low = mid + 1;
            }
        }
        return -1;
    }
};

在旋转数组查找目标值（含重复元素）

https://leetcode.com/problems/search-in-rotated-sorted-array-ii/

// https://www.cnblogs.com/grandyang/p/4325840.html
// 相对于上例，需要增加一个判断：如果 nums[mid] 与 nums[high] 相等，则 --high
class Solution
{
public:
    bool search(vector<int>& nums, int target)
    {
        int n = nums.size();
        if(n == 0) return false;
        int low = 0;
        int high = n - 1;
        while(low <= high)
        {
            int mid = low + (high - low) / 2;
            if(nums[mid] == target) return true;

            if(nums[mid] == nums[high]) --high; // 增加这个判断。注：只有当 low == high，才会出现： mid == high 。

            else if(nums[mid] < nums[high])
            {
                if(nums[mid] < target && target <= nums[high]) low = mid + 1;
                else high = mid - 1;
            }
            else
            {
                if(nums[mid] > target && target >= nums[low]) high = mid - 1;
                else low = mid + 1;
            }
        }
        return false;
    }
};

4.26. [LeetCode] Maximum Gap 最大间隔

Hint：方法一，普通排序，逐个比较；方法二，桶排序。将 $n$ 个数放到 $n+1$ 个桶中，最小值放第一个桶，最大值放最后一个桶，每个桶的大小为 $\frac{max-min}{n}$ 。根据鸽巢原理，至少存在一个桶为空。最大间隔必然出现在空桶两侧，且只与左侧桶的最大值、右侧桶的最小值有关。（事实上，可以将 $n$ 个数放到 $n$ 个桶中，如果没有空桶，则刚好每个桶有且仅有一个数，最大间隔出现在相邻桶中；如果某个桶有2个数以上，说明存在有空桶，最大间隔出现在非空的相邻桶中。总之，最大间隔不会出现在一个桶中。）

https://leetcode.com/problems/maximum-gap/

// 建立 n 个桶
class Solution
{
public:
    int maximumGap(vector<int>& nums)
    {
        size_t n = nums.size();
        if(n < 2) return 0;

        int MIN = *min_element(nums.begin(), nums.end());
        int MAX = *max_element(nums.begin(), nums.end());
        if(MIN == MAX) return 0;

        vector<vector<int>> bucket(n, vector<int>(2, 0)); // 大小为 n * 2
        for(size_t k = 0; k < n; ++k)
        {
            bucket[k][0] = INT_MAX;
            bucket[k][1] = INT_MIN;
        }


        double delta = (MAX - MIN) / double(n - 1);
        for(size_t k = 0; k < n; ++k)
        {
            int idx = (nums[k] - MIN) / delta;
            bucket[idx][0] = min(nums[k], bucket[idx][0]);
            bucket[idx][1] = max(nums[k], bucket[idx][1]);
        }

        int gap = 0;
        size_t pre = 0;
        size_t curr = 1;
        while(curr < bucket.size())
        {
            if(bucket[curr][0] == INT_MAX && bucket[curr][1] == INT_MIN) curr++; // 空桶
            else
            {
                if(curr - pre >= 1)
                {
                    int pre_max = bucket[pre][1];
                    int curr_min = bucket[curr][0];
                    gap = max(gap, curr_min - pre_max);
                }
                pre = curr;
                curr++;
            }
        }
        return gap;
    }
};

4.27. 数组操作模拟大数乘法

Hint：从低位到高位，采用竖式计算，记录所有位的乘积，再将对应位的结果相加，最后进位。假设数组 $a$ 和 $b$ 从低位到高位存储了两个大数（可能存在小数点），则乘积为 $\mathrm{ans}[k] = \sum_{i+j=k} a[i] \times b[j]$ 。

def preProcess(a):
    ## input: str
    ## output: list, l
    pf = a.find('.')
    lf = 0
    if pf != -1:
        lf = len(a) - 1 - pf ## 小数位数
        a = a[:pf] + a[pf+1:] ## 去掉小数点
    a = list(a)
    a = a[::-1] ## 翻转数组，a[0] 表示最低位
    return a, lf

def strMul(a, b):
    a, la = preProcess(a)
    b, lb = preProcess(b)
    lf = la + lb

    ans = [0 for _ in range(len(a) + len(b))]
    for ia in range(len(a)):
        for ib in range(len(b)):
            ans[ia+ib] += int(a[ia]) * int(b[ib])
    carry = 0
    for i in range(len(ans)):
        tmp = ans[i] + carry
        ans[i] = tmp % 10
        carry = tmp / 10
    ans = ans[::-1] ## 翻转数组

    if lf > 0:
        ans.insert(len(ans) - lf, '.') ## 插入小数点
    if ans[0] == 0:
        ans = ans[1:] ## 最高位是 0 则去掉
    iz = len(ans)-1
    while lf > 0 and ans[iz] == 0: ## 去掉小数点末尾的 0
        iz -= 1

    s = ''
    for e in ans[:iz+1]:
        s += str(e)

    return s

4.28. [LeetCode] Number of Islands 孤岛个数

Hint：使用队列，广度优先遍历（BFS）。

延伸：从坐标 $(0, 0)$ 到 $(n-1, m-1)$ 的最短时间，只能走四邻域，$\mathrm{map}[i][j] = 1$ 表示有障碍。Hint：BFS，第一个到达的就是时间最短的。

https://leetcode.com/problems/number-of-islands/

// 孤岛个数
class Solution
{
public:
    void traverseIsland(vector<vector<char>>& grid, int m, int n, const int M, const int N)
    {
        queue<pair<int, int>> que;

        que.push(make_pair(m, n));
        grid[m][n] = '0';

        while (!que.empty())
        {
            pair<int, int> p = que.front();
            que.pop();

            for (int i = 0; i < 4; ++i)
            {
                int next_x = p.first + directions[i][0];
                int next_y = p.second + directions[i][1];
                if (0 <= next_x && next_x < M && 0 <= next_y && next_y < N && grid[next_x][next_y] == '1')
                {
                    // 入队需要改变标志位，避免后续过程中同一坐标重复入队
                    grid[next_x][next_y] = '0';
                    que.push(make_pair(next_x, next_y));
                }
            }
        }
    }

    int numIslands(vector<vector<char>>& grid)
    {
        if (grid.size()==0) return 0;
        int M = grid.size();
        int N = grid[0].size();
        int island = 0;
        for (int m = 0; m < M; ++m)
        {
            for (int n = 0; n < N; ++n)
            {
                if (grid[m][n]=='1')
                {
                    island += 1;
                    traverseIsland(grid, m, n, M, N);
                }
            }
        }
        return island;
    }
private:
    static const int directions[4][2];
};

const int Solution::directions[4][2] = {{-1,0},{0,-1},{1,0},{0,1}};

// 最短时间
// https://www.nowcoder.com/practice/365493766c514d0da0cd774d3d40fd49?tpId=8&tqId=11040&tPage=1&rp=1&ru=/ta/cracking-the-coding-interview&qru=/ta/cracking-the-coding-interview/question-ranking
// https://leetcode.com/problems/shortest-path-in-binary-matrix/

struct point
{
    int x;
    int y;
    int time;
    point(int _x, int _y, int _time): x(_x), y(_y), time(_time){}
};

class Solution
{
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid)
    {
        int n = grid.size();
        queue<point> q;
        if(grid[0][0] != 1)
        {
            q.push(point(0, 0, 1));
            grid[0][0] = 1;
        }
        while(!q.empty())
        {
            auto p = q.front();
            q.pop();
            if(p.x == n-1 && p.y == n-1) return p.time;
            for(int i = 0; i < 8; ++i)
            {
                int next_x = p.x + directions[i][0];
                int next_y = p.y + directions[i][1];
                if(0 <= next_x && next_x < n && 0 <= next_y && next_y < n && grid[next_x][next_y] != 1)
                {
                    // 入队需要改变标志位，避免后续过程中同一坐标重复入队
                    grid[next_x][next_y] = 1;
                    q.push(point(next_x, next_y, p.time+1));
                }
            }
        }
        return -1;
    }
private:
    static const int directions[8][2];
};

const int Solution::directions[8][2] = {
    {-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}
};

// 注意：当点 p 的近邻都满足条件入队之后，它们的标志位全部同时改变
// 因为当最短路径包含点 p 时，只会再包含点 p 的一个近邻，最短路径不可能多次经过点 p 的不同近邻

4.29. 回文（Palindrome）

[LeetCode] Longest Palindromic Substring 最长回文子串（子串连续）。Hint：方法一，中心扩展法，回文中心的两侧互为镜像，将每一个位置作为中心进行扩展，回文分偶数和奇数；方法二，动态规划，类似于矩阵连乘问题，逐渐增大步长。

https://leetcode.com/problems/longest-palindromic-substring/

$$ dp[i][i] = \mathrm{true} $$ $$ dp[i][j] = \begin{cases} \mathrm{true} & &\ s[i] = s[j]\ \&\&\ (i \leqslant j \leqslant i+1\ ||\ dp[i+1][j-1] = \mathrm{true}) \\ \mathrm{false} & &\ \mathrm{otherwise} \end{cases} $$

// 方法一，中心扩展法
class Solution {
public:
    void palindrome(int i, int j, string s, int& start, int& longest)
    {
        while(i >= 0 && j < s.size() && s.at(i) == s.at(j))
        {
            i--;
            j++;
        }
        i += 1;
        j -= 1;
        if(j - i + 1 > longest)
        {
            longest = j-i+1;
            start = i;
        }
    }
    string longestPalindrome(string s) {
        int len = s.size();
        if(len <= 1) return s;
        int start = 0;
        int longest = 1;
        for(int i = 0; i < len-1; ++i)
        {
            palindrome(i, i, s, start, longest);
            palindrome(i, i+1, s, start, longest);
        }
        string str;
        str.assign(s, start, longest);
        return str;
    }
};

// 方法二，动态规划
class Solution
{
public:
    string longestPalindrome(string s)
    {
        if(s.size() <= 1) return s;
        size_t len = s.size();
        vector<vector<bool>> dp(len, vector<bool>(len, false));
        size_t start = 0;
        size_t longest = 1;
        for(size_t i = 0; i < len; ++i) dp[i][i] = true;
        for(size_t gap = 0; gap < len; ++gap)
        {
            for(int i = 0; i + gap < len; ++i)
            {
                int j = i + gap;
                if(s[i] == s[j])
                {
                    if(gap <= 1 || dp[i+1][j-1])
                    {
                        dp[i][j] = true;
                        longest = j - i + 1; // 由于步长是逐渐增大的，因此最后得到的回文子串一定是最长的
                        start = i;
                    }
                    else dp[i][j] = false;
                }
            }
        }
        vector<vector<bool>>().swap(dp);
        return s.substr(start, longest);
    }
};

[LeetCode] Longest Palindromic Subsequence 最长回文子序列（子序列可以不连续）。Hint：寻找原字符串与翻转字符串的最长公共子序列，动态规划。

https://leetcode.com/problems/longest-palindromic-subsequence/

class Solution
{
public:
    // 寻找字符串 str 与其翻转字符串的最长公共子序列
    int lcsLength(string& str)
    {
        int len = str.size();
        vector<vector<int>> dp(len+1, vector<int>(len+1, 0));
        // dp[i][j] 表示前 i 个字符和后 j 个字符翻转后的最长公共子序列的长度
        for(int i = 1; i <= len; ++i)
        {
            for(int j = 1; j <= len; ++j)
            {
                if(str[i-1] == str[len-j]) dp[i][j] = dp[i-1][j-1] + 1;
                else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
        int ans = dp[len][len];
        vector<vector<int>>().swap(dp);
        return ans;
    }

    int longestPalindromeSubseq(string s)
    {
        if(s.size() <= 1) return s.size();
        return lcsLength(s);
    }
};

[LeetCode] Count Different Palindromic Subsequences 统计不同回文子序列的个数（子序列可以不连续）。

https://leetcode.com/problems/count-different-palindromic-subsequences/

https://leetcode.com/problems/count-different-palindromic-subsequences/discuss/272297/DP-C%2B%2B-Clear-solution-explained

https://blog.csdn.net/lili0710432/article/details/78659583
$\color{darkgreen}{Analysis}$

用 $dp[i][j]$ 表示字符串 $[i,j]$ 区间内的的回文子序列个数。
- $S[i] \ne S[j]$ 。下式的第三项是前两项重复计算的部分。
  
  \[dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]\]
- $S[i] = S[j]$
  
  如果相同的回文子序列可以多次统计，递推式如下。其中 $+1$ 统计的是长度为 2 的回文子序列 “ $S[i]S[j]$ ”； $+ dp[i+1][j-1]$ 统计的是以 “ $S[i]$ ”开头，以 “ $S[j]$ ”结尾，且中间部分取自区间 $[i+1,j-1]$ 的回文子序列。
  
  \[\begin{split}dp[i][j] &=\ dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1] + 1 + dp[i+1][j-1] \\ &=\ dp[i+1][j] + dp[i][j-1] + 1\end{split}\]
  
  如果只统计不同回文子序列的个数，分三种情况。
  
  若 $S[i]$ 不再出现在区间 $[i+1,j-1]$ 内，递推式如下。其中 $\times 2$ 统计了两类回文子序列：一类是以 “ $S[i]$ ”开头，以 “ $S[j]$ ”结尾，且中间部分取自区间 $[i+1,j-1]$ 的回文子序列，另一类是只取自区间 $[i+1,j-1]$ 的回文子序列； $+2$ 统计的是长度为 1 的回文子序列 “ $S[i]$ ”和长度为 2 的回文子序列 “ $S[i]S[j]$ ”。
  
  \[dp[i][j] = dp[i+1][j-1] \times 2 + 2\]
  
  若 $S[i]$ 在区间 $[i+1,j-1]$ 内又出现 1 次，递推式如下。 $+1$ 统计的是长度为 2 的回文子序列 “ $S[i]S[j]$ ”，长度为 1 的回文子序列 “ $S[i]$ ”在区间 $[i+1,j-1]$ 内已经统计过了。
  
  \[dp[i][j] = dp[i+1][j-1] \times 2 + 1\]
  
  若 $S[i]$ 在区间 $[i+1,j-1]$ 内又出现多次，设出现的第一个位置是 $l$ ，最后一个位置是 $r$ ，递推式如下。这种情况下，以 “ $S[i]$ ”开头，以 “ $S[j]$ ”结尾，且中间部分取自区间 $[i+1,j-1]$ 的回文子序列也会被重复统计。
  
  \[dp[i][j] = dp[i+1][j-1] \times 2 - dp[l+1][r-1]\]
$\color{darkgreen}{Code}$
```
 1class Solution
 2{
 3public:
 4    int countPalindromicSubsequences(string S)
 5    {
 6        int n = S.size();
 7        if(n <= 1) return n;
 8        vector<vector<long long>> dp(n, vector<long long>(n, 0)); // long long 防止溢出
 9        for(int i = 0; i < n; ++i) dp[i][i] = 1;
10
11        long long modulo = 1000000007;
12        for(int gap = 1; gap < n; ++gap)
13        {
14            for(int i = 0; i + gap < n; ++i)
15            {
16                int j = i + gap;
17                if(S[i] != S[j])
18                {
19                    dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1];
20                }
21                else
22                {
23                    dp[i][j] = dp[i+1][j-1] * 2; // 先计算这部分，避免后面重复计算
24                    int left = i + 1;
25                    int right = j - 1;
26                    while(left < j && S[left] != S[i]) left++;
27                    while(right > i && S[right] != S[i]) right--;
28
29                    if(left > right) dp[i][j] += 2;
30                    else if(left == right) dp[i][j] += 1;
31                    else dp[i][j] -= dp[left+1][right-1];
32                }
33                dp[i][j] = (dp[i][j] + modulo) % modulo; // 前面有减法操作，因此 dp[i][j] 可能是负数
34            }
35        }
36
37        int res = dp[0][n-1];
38        dp.clear();
39        dp.shrink_to_fit();
40        return res;
41    }
42};
```

[LeetCode] Palindrome Partitioning 分割字符串使所有的子串都是回文子串。Hint：回溯，从字符串起始位置往后判断回文，如果满足回文，加入子串集合，并从回文结束位置往后遍历。

https://leetcode.com/problems/palindrome-partitioning/

class Solution
{
public:
    vector<vector<string>> partition(string s)
    {
        vector<vector<string>> res;
        if(s.empty()) return res;

        // isPalindrome[i][j] 表示 s 的区间 [i,j] 是否是回文
        vector<vector<bool>> isPalindrome(s.size(), vector<bool>(s.size(), false));
        for(int gap = 0; gap < s.size(); ++gap)
        {
            for(int i = 0; i+gap < s.size(); ++i)
            {
                int j = i + gap;
                if(s[i] == s[j])
                {
                    if(gap <= 1) isPalindrome[i][j] = true;
                    else isPalindrome[i][j] = isPalindrome[i+1][j-1];
                }
                else isPalindrome[i][j] = false;
            }
        }

        vector<string> tmp;
        dfs(s, 0, tmp, res, isPalindrome);

        isPalindrome.clear();
        isPalindrome.shrink_to_fit();

        return res;
    }
private:
    void dfs(string& s, int t, vector<string>& tmp, vector<vector<string>>& res, vector<vector<bool>>& isPalindrome)
    {
        if(t == s.size())
        {
            res.push_back(tmp);
            return;
        }
        for(int i = t; i < s.size(); ++i)
        {
            if(isPalindrome[t][i])
            {
                tmp.push_back(s.substr(t, i-t+1)); // 如果满足回文，加入当前子串集合
                dfs(s, i+1, tmp, res, isPalindrome); // 回文结束位置为 i，因此下一个起始位置是 i+1
                tmp.pop_back();
            }
        }
    }
};

[LeetCode] Palindrome Partitioning II 找出最短回文分割。Hint：如果采用上题方法，会超时；使用动态规划，类似于最长上升子序列的解法。

https://leetcode.com/problems/palindrome-partitioning-ii/

class Solution {
public:
    int minCut(string s) {
        if(s.size() <= 1) return 0;

        vector<vector<bool>> isPalindrome(s.size(), vector<bool>(s.size(), false));
        for(int gap = 0; gap < s.size(); ++gap)
        {
            for(int i = 0; i+gap < s.size(); ++i)
            {
                int j = i + gap;
                if(s[i] == s[j])
                {
                    if(gap <= 1) isPalindrome[i][j] = true;
                    else isPalindrome[i][j] = isPalindrome[i+1][j-1];
                }
                else isPalindrome[i][j] = false;
            }
        }

        vector<int> dp(s.size(), 0); // dp[i] 表示区间 [0, i] 的最短回文分割
        for(int i = 1; i < s.size(); ++i)
        {
            if(isPalindrome[0][i]) dp[i] = 0;
            else
            {
                dp[i] = dp[i-1] + 1; // 直接划分 s[i] 为一个子串
                for(int j = 1; j < i; ++j)
                {
                    if(isPalindrome[j][i]) dp[i] = min(dp[i], dp[j-1] + 1); // [j, i] 为一个子串
                }
            }
        }

        int res = dp[s.size()-1];

        isPalindrome.clear(); isPalindrome.shrink_to_fit();
        dp.clear(); dp.shrink_to_fit();

        return res;
    }

};

4.30. 判断字符串 s2 是否可由 s1 旋转得到

Hint：对 s1 做循环移位，所得字符串都将是字符串 s1s1 的子串。

bool checkReverseEqual(string s1, string s2)
{
    if(s1.size()==0 || s2.size()==0) return false;
    if(s1.size() < s2.size()) return false; // s1 = "abc", s2 = "abcabc"
    string s1s1 = s1 + s1;
    if(s1s1.find(s2) == string::npos) return false;
    return true;
}

4.31. [LeetCode] Validate Binary Search Tree 检查一棵二叉树是否为二叉查找树

Hint：不仅要求左节点比当前节点小，右节点比当前节点大，而是要求左子树所有节点都小于当前节点，右子树所有节点都大于当前节点；利用二叉树的中序遍历，BST 得到的序列是升序排列的。

https://leetcode.com/problems/validate-binary-search-tree/

class Solution
{
public:
    bool isValidBST(TreeNode* root)
    {
        // 节点的值 val 是 int 型
        long long pre = (long long)(INT_MIN) - 1;
        return checkBST(root, pre);
    }
private:
    // 中序遍历，检查上一个遍历的数是否小于当前数, O(1) 空间复杂度
    bool checkBST(TreeNode* root, long long& pre)
    {
        if(!root) return true;
        if(!checkBST(root->left, pre)) return false;
        if(pre >= (long long)(root->val)) return false;
        pre = (long long)(root->val);
        return checkBST(root->right, pre);
    }
};

4.32. 判断一个数是否是奇数

Hint：考虑负数的情形；方法一，判断模 2 结果不为 0；方法二，位运算判断最低位为 1。

延伸：判断两个数是否相等（或判断某个数是否为 0），如果是浮点数，应该判断两者差的绝对值是否小于一个阈值，而不是直接使用 ==。

bool isOdd1(int x)
{
    return (x % 2) != 0;
}

bool isOdd2(int x)
{
    return (x & 1) == 1;
}

bool isEqual(double x, double y)
{
    return fabs(x - y) < 1e-6;
}

延伸：检查一个数是否是 2 的整次幂，Hint：二进制表示只有一个 1；检查一个数是否是 4 的整次幂，Hint：4 的整次幂的二进制表示中， 1 都在奇数位；检查一个数是否是 3 的整次幂，Hint：质数的整次幂的质因子只有该质数本身。

// 检查一个数是否是 2 的整次幂
bool checkPower2(int n)
{
  return n > 0 && (n & (n - 1)) == 0;
}

// 检查一个数是否是 4 的整次幂
bool checkPower4(int n)
{
  if(n > 0 && (n & (n - 1)) == 0) // 先确保是 2 的整次幂（只有一个 1）
  {
    if((n & 0x55555555) == n) return true; // 0x55555555 = 0101 0101 0101 0101 0101 0101 0101 0101
  }
  return false;
}

// 检查一个数是否是 3 的整次幂
bool checkPower3(int n)
{
  return n > 0 && 1162261467 % n == 0; // 3^19 = 1162261467 是 int 型中最大的 3 的整次幂
}

4.33. [LeetCode] Valid Number 验证一个字符串是否表示某个有效数字

Hint：完整的数字表达是“空格+正负号+整数+小数点+整数+e+正负号+整数+空格”；小数点的相邻两边至少要有一边是整数；如果出现 e，其两边都必须出现整数，但不要求相邻；如 05.e-3 是一个有效数字。

延伸：将字符串转换为整数，需要考虑：空串、正负号、无效字符、溢出。

https://leetcode.com/problems/valid-number/

// 验证一个字符串是否表示某个有效数字
class Solution
{
public:
    bool isNumber(string s)
    {
        size_t idx = 0;
        bool hasDigit = false;

        scanSpace(s, idx);
        scanSign(s, idx);
        hasDigit = scanDigit(s, idx);
        scanPoint(s, idx);
        hasDigit |= scanDigit(s, idx);
        if(hasDigit) // 小数点的相邻两边至少要有一边是整数；e 的左边必须出现整数；如果既没有小数点，又没有 e，则要求该字符串中必须包含整数。总而言之，这里必须是 true 才有可能是有效数字
        {
            if(scanExp(s, idx))
            {
                scanSign(s, idx);
                hasDigit = scanDigit(s, idx); // e 的右边必须出现整数
            }
            scanSpace(s, idx);
            if(idx == s.size() && hasDigit) return true;
        }
        return false;
    }
private:
    void scanSpace(string& s, size_t& idx)
    {
        while(idx < s.size() && s.at(idx) == ' ') ++idx;
    }
    void scanSign(string& s, size_t& idx)
    {
        if(idx < s.size() && (s.at(idx) == '+' || s.at(idx) == '-')) ++idx;
    }
    bool scanDigit(string& s, size_t& idx)
    {
        if(idx >= s.size()) return false;
        if(s.at(idx) < '0' || s.at(idx) > '9') return false;
        while(idx < s.size() && '0' <= s.at(idx) && s.at(idx) <= '9') ++idx;
        return true;
    }
    void scanPoint(string& s, size_t& idx)
    {
        if(idx < s.size() && s.at(idx) == '.') ++idx;
    }
    bool scanExp(string& s, size_t& idx)
    {
        if(idx < s.size() && s.at(idx) == 'e')
        {
            ++idx;
            return true;
        }
        return false;
    }
};

// 将字符串转换为整数
class Solution
{
public:
    int myAtoi(string str)
    {
        unsigned int idx = 0;
        scanSpace(str, idx);

        bool sign = true;
        if(idx < str.size() && str[idx] == '-' || str[idx] == '+')
        {
            if(str[idx] == '-') sign = false;
            ++idx;
        }

        long long ans = 0;
        bool hasDigit = false;
        while(idx < str.size() && '0' <= str[idx] && str[idx] <= '9')
        {
            hasDigit = true;
            ans = 10 * ans + str[idx] - '0';
            if(sign && ans > INT_MAX)
            {
                validInt = false;
                return INT_MAX;
            }
            if(!sign && -ans < INT_MIN)
            {
                validInt = false;
                return INT_MIN;
            }
            ++idx;
        }
        scanSpace(str, idx);
        if(idx == str.size() && hasDigit)
        {
            if(!sign) ans = - ans;
            validInt = true;
            return static_cast<int>(ans);
        }

        validInt = false;
        return 0;
    }
private:
    bool validInt; // 标志符，输出 0 / INT_MAX / INT_MIN 时，有可能是异常情形
    void scanSpace(string str, unsigned int& idx) // 扫描首尾空格
    {
        while(idx < str.size() && str[idx] == ' ') ++idx;
    }
};

4.34. 求 $1+2+3+ \cdots +n$ ，不使用：乘除法，判断，循环，库函数。

// 方法一，构造函数
class A
{
public:
    A()
    {
        id++;
        sum += id;
    }
    static void reset()
    {
        id = 0;
        sum = 0;
    }
    static unsigned int getSum()
    {
        return sum;
    }
private:
    static unsigned int id;
    static unsigned int sum;
};

unsigned int A::id = 0;
unsigned int A::sum = 0;

unsigned int sumFrom1ToN(unsigned int N)
{
    A::reset();

    A* arr = new A[N];
    delete[] arr;

    return A::getSum();
}

// 方法二，虚函数

class A; // 前向声明
A* arr[2]; // 这里可以声明类 A 的指针，但是不能声明类 A 的变量，类 A 还未定义

class A
{
public:
    virtual unsigned int getSum(unsigned int n)
    {
        return 0;
    }
};

class B: public A
{
public:
    unsigned int getSum(unsigned int n) override
    {
        return n + arr[!!n] -> getSum(n - 1); // !!n：当 n>0，arr[1] 调用 B::getSum(n)；当 n=0，arr[0] 调用 A::getSum(n)
    }
};

unsigned int sumFrom1ToN(unsigned int N)
{
    A a;
    B b;
    arr[0] = &a;
    arr[1] = &b;
    return arr[1] -> getSum(N);
}

4.35. [LeetCode] Lexicographical Numbers 按字典序排列 $1 \sim n$

Hint：方法一，定义排序规则，按字符串的字典序排序；方法二，回溯，递归深度只与 $n$ 的位数有关。

https://leetcode.com/problems/lexicographical-numbers/

// 方法一，定义排序规则

class Solution
{
public:
    vector<int> lexicalOrder(int n)
    {
        vector<int> res;
        if(n < 1) return res;
        res.resize(n);
        iota(res.begin(), res.end(), 1);
        sort(res.begin(), res.end(), comparator);
        return res;
    }
private:
    static bool comparator(int x, int y)
    {
        return strcmp(to_string(x).c_str(), to_string(y).c_str()) < 0 ? true: false;
    }
};

// 方法二，回溯，从高位往低位进行

class Solution
{
public:
    vector<int> lexicalOrder(int n)
    {
        vector<int> res;
        for(int high = 1; high <= 9; ++high) dfs(high, n, res); // 最高位不能为 0
        return res;
    }
private:
    void dfs(int high, int n, vector<int>& res)
    {
        if(high > n) return;
        res.push_back(high); // 只有高位，没有低位。这是同一前缀的数字中最小的数
        for(int low = 0; low <= 9; ++low) dfs(high * 10 + low, n, res); // 高位 + 低位
    }
};

延伸：找到字典序排列的第 $k$ 个数。

## 在字典树的区间 [p, p+1) 及其子区间查找
## 下一层子区间为 [p*10, (p+1)*10)
## 如果子区间内没找到，则进入兄弟区间 [p+1, p+2)

def dictOrder(n, k):
    pos = 1
    while True:
        left = pos
        right = pos + 1
        cnt = 0
        while n >= left:
            cnt += min(n+1, right) - left ## 区间大小
            left *= 10
            right *= 10
        if cnt < k:   ## 不在区间 [pos, pos+1) 及其子区间内
            k -= cnt
            pos += 1   ## 进入兄弟区间
        else:         ## 在区间 [pos, pos+1) 或其子区间内
            k -= 1
            if k == 0:
                return pos
            pos *= 10  ## 进入子区间

4.36. [LeetCode] Merge k Sorted Lists 合并 $k$ 条有序链表

Hint：建立大小为 $k$ 的小顶堆，每次弹出一个节点，并把该节点的下一个节点插入小顶堆中。时间复杂度 $\mathcal{O}(n \log k)$ ，$n$ 是节点个数。

https://leetcode.com/problems/merge-k-sorted-lists/

struct ListNode
{
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

struct comparator
{
    bool operator()(ListNode* a, ListNode* b)
    {
        return a->val > b->val; // 小顶堆
    }
};

class Solution
{
public:
    ListNode* mergeKLists(vector<ListNode*>& lists)
    {
        if(lists.size() == 0) return nullptr;
        if(lists.size() == 1) return lists[0];

        ListNode* head = new ListNode(0); // 合并链表的临时头节点

        priority_queue<ListNode*, vector<ListNode*>, comparator> pq;
        for(auto & list : lists)
        {
            if(list) pq.emplace(list); // 建堆
        }
        ListNode* curr = head;
        while(!pq.empty())
        {
            ListNode* p = pq.top();
            pq.pop();
            curr->next = p;
            curr = p;
            if(p->next) pq.push(p->next);
        }

        curr = head->next;
        delete head;
        return curr;
    }
};

4.37. [LeetCode] Max Points on a Line 统计共线的最多点数

Hint：直线需要考虑三种斜率：水平，垂直，斜线，还要考虑点重合的情形；由于浮点运算的精度问题，将斜率表示为两个整数的分数形式，保存到哈希表中。

https://leetcode.com/problems/max-points-on-a-line/

class Solution
{
public:
    int maxPoints(vector<vector<int>>& points)
    {
        int res = 0;
        for(size_t i = 0; i < points.size(); ++i) // points.size() == 0，返回 0；points.size() == 1，返回 1
        {
            unordered_map<string, int> mp; // 对每个点 i 统计其与其他点所成直线的斜率。由于这些直线都通过点 i，因此斜率相同就表示共线
            int samePointNum = 0;
            int verticalLineNum = 0;
            int horizontalLineNum = 0;
            int slantLineNum = 0;
            for(size_t j = i + 1; j < points.size(); ++j) // 往后遍历每个点
            {
                if(points[i][0] == points[j][0] && points[i][1] == points[j][1]) ++samePointNum; // 点重合
                else if(points[i][0] == points[j][0]) ++verticalLineNum; // 垂直线
                else if(points[i][1] == points[j][1]) ++horizontalLineNum; // 水平线，可以计算斜率，但是由于垂直方向差异为 0，不好计算公约数
                else // 斜线
                {
                    int dx = points[j][0] - points[i][0];
                    int dy = points[j][1] - points[i][1];
                    int g = _gcd(dy, dx);
                    dx /= g;
                    dy /= g;
                    if(dy < 0) // 符号统一令 dy > 0
                    {
                        dy = -dy;
                        dx = -dx;
                    }
                    stringstream ss;
                    ss << dx << " " << dy;
                    string slope = ss.str();
                    ss.clear();
                    if(mp.find(slope) == mp.end()) mp[slope] = 1;
                    else ++mp[slope];
                    slantLineNum = max(slantLineNum, mp[slope]);
                }
            }

            int currMax = max(slantLineNum, max(verticalLineNum, horizontalLineNum));
            currMax += samePointNum + 1; // + 1 表示点 i 本身
            res = max(res, currMax);
        }
        return res;
    }
private:
    int _gcd(int a, int b) // 辗转相除，计算最大公约数
    {
        a = abs(a);
        b = abs(b);
        if(a < b) swap(a, b);
        while(a % b)
        {
            int tmp = a;
            a = b;
            b = tmp % b;
        }
        return b;
    }
};

4.38. [LeetCode] Word Break 字符串按字典切分

Hint：回溯；动态规划；字典树。

https://leetcode.com/problems/word-break

// 方法一，回溯
// 测试用例超时
// "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab" ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]

class Solution
{
public:
    bool wordBreak(string s, vector<string>& wordDict)
    {
        if(s == "") return true;
        if(wordDict.size() == 0) return false;
        return wordFind(s, wordDict, 0);
    }
private:
    bool wordFind(string& s, vector<string>& wordDict, int k)
    {
        if(k == s.size()) return true;
        for(int w = 0; w < wordDict.size(); ++w)
        {
            if(k+wordDict[w].size()<=s.size() && s.substr(k, wordDict[w].size()) == wordDict[w])
            {
                if(wordFind(s, wordDict, k + wordDict[w].size())) return true;
            }
        }
        return false;
    }
};

// 方法二，动态规划，空间复杂度 O(n^2)
// dp[i][j] 表示字符串区间 [i, j] 的切分情况
// 解法类似于矩阵连乘问题

class Solution
{
public:
    bool wordBreak(string s, vector<string>& wordDict)
    {
        if(s.empty() || wordDict.empty()) return false;
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        for(int gap = 0; gap < n; ++gap)
        {
            for(int i = 0; i + gap < n; ++i)
            {
                int j = i + gap;
                for(string& word: wordDict)
                {
                    // 这里用 ||，只要有一个 word 匹配就行
                    if(gap + 1 == word.size()) dp[i][j] = dp[i][j] || (s.substr(i, word.size()) == word);
                    else if(gap + 1 > word.size()) dp[i][j] = dp[i][j] || (s.substr(i, word.size()) == word && dp[i+word.size()][j]);
                }
            }
        }
        return dp[0][n-1];
    }
};

// 方法三，动态规划，空间复杂度 O(n)
// dp[i] 表示字符串区间 [0, i-1] 的切分情况

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        if(s.empty() || wordDict.empty()) return false;

        int n = s.size();
        vector<bool> dp(n+1, false);
        dp[0] = true; // 初始化

        for(unsigned int i = 1; i <= n; ++i)
        {
           for(unsigned int j = 0; j < i; ++j)
           {
               if(dp[j]) // 两段子串：[0, j-1], [j, i]
               {
                   string str = s.substr(j, i-j);
                   for(string& word: wordDict)
                   {
                       if(str == word)
                       {
                           dp[i] = true;
                           break;
                       }
                   }
               }
           }
        }
        return dp[n];
    }
};

延伸：返回所有的切分方式。

https://leetcode.com/problems/word-break-ii

## 返回所有的切分方式
## 使用字典树 Trie

from collections import defaultdict

class TrieNode(object):
    def __init__(self):
        self.dict = defaultdict(TrieNode)
        self.word = False

class Trie(object):
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        child = self.root
        for letter in word:
            child = child.dict[letter]
        child.word = True

    def search(self, word):
        child = self.root
        for letter in word:
            child = child.dict.get(letter)
            if child is None:
                return False
        return child.word


class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        n = len(s)
        trie = Trie()
        ## 构建字典树
        for word in wordDict:
            trie.insert(word)
        ## 前一个切分点的下标
        pre = [[] for i in range(n+1)]
        pre[0].append(-1)
        ## 前 i 个字符的切分
        for i in range(1, n+1):
            for j in range(i):
                if pre[j] != []:
                    ## 当前子串：s[j:i]
                    if trie.search(s[j:i]):
                        pre[i].append(j)
        res = []
        seg = ""
        ## 递归获取所有切分方式
        self.combineWords(s, pre, n, seg, res)
        return res

    def combineWords(self, s, pre, t, seg, res):
        if t == 0:
            res.append(seg[:-1])
            return
        for j in pre[t]:
            self.combineWords(s, pre, j, s[j:t] + " " + seg, res)

4.39. [LeetCode] Gas Station 加油站回路

Hint：只要 gas 总和不小于 cost 总和，一定存在可以完成回路的出发点。

https://leetcode.com/problems/gas-station/

https://leetcode.com/problems/gas-station/discuss/191463/topic

class Solution
{
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost)
    {
        if(gas.size() == 0) return -1;
        int totalDiff = 0;
        int currDiff = 0;
        int start = 0;
        for(int i = 0; i < gas.size(); ++i)
        {
            totalDiff += gas[i] - cost[i];
            currDiff += gas[i] - cost[i];
            if(currDiff < 0)
            {
                start = i + 1; // 第 0 ~ i 加油站都不可能是可以完成回路的起始点
                currDiff = 0;
            }
        }
        return totalDiff >= 0 ? start: -1;
    }
};

延伸：从起点到终点的最少加油次数。Hint：贪心算法，把路过的每个加油站的油量存入优先队列，当需要加油时，弹出队列中的最大油量。

https://leetcode.com/problems/minimum-number-of-refueling-stops/

class Solution
{
public:
    int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations)
    {
        priority_queue<int, vector<int>, less<int>> que;
        int cnt = 0;
        int maxDist = startFuel;
        int i = 0;
        while(maxDist < target)
        {
            while(i < stations.size() && maxDist >= stations[i][0])
            {
                que.push(stations[i][1]);
                ++i;
            }
            if(que.empty()) return -1;
            maxDist += que.top();
            que.pop();
            cnt += 1;
        }
        return cnt;
    }
};

4.40. 最短过桥时间

$n$ 个人过桥，每次最多通过两个人（过桥时间按较长者计算），只有一个手电筒，每次过桥之后需要一个人把手电筒送回来，求最短过桥时间。Hint：耗时第 $k$ 小的人过桥有两种方案，第一，由耗时最短的人送回手电筒，并陪同过河；第二，耗时最短的人送回手电筒之后，耗时第 $k$ 小的人与耗时第 $k-1$ 小的人一起过桥，他们过桥之后，手电筒再由耗时第二短的人送回，最后耗时最短的人和耗时第二短的人一起过桥。

https://blog.csdn.net/u014113686/article/details/82464635

int minTimeCrossBridge(int* Time, int n)
{
    assert(n > 0);
    sort(Time, Time + n);
    int* dp = new int[n];
    dp[0] = Time[0];
    dp[1] = Time[1];
    for (size_t i = 2; i < n; ++i)
    {
        dp[i] = min(dp[i - 1] + Time[0] + Time[i], dp[i - 2] + Time[i] + Time[0] + 2 * Time[1]);
    }
    int res = dp[n - 1];
    delete[] dp;
    return res;
}

4.41. [LeetCode] Minimum Window Substring 字符串 S 中包含字符串 T 中所有字符的最短子串

Hint：用两个指针表示滑动窗口的起始和结尾；当窗口满足要求，则计算当前窗口的长度，然后两个指针都往后移动一步；终止条件是尾指针移动到了字符串 S 的结尾（’\0’）。

延伸：不考虑字符串 T 中重复的字符，求字符串 S 中包含字符串 T 中出现的字符的最短子串。

https://leetcode.com/problems/minimum-window-substring/

// 考虑重复

typedef unsigned int uint;
class Solution
{
public:
    string minWindow(string s, string t)
    {
        uint lenS = s.size();
        uint lenT = t.size();
        if(lenS < lenT || lenT == 0) return "";

        uint hashT[256] = {0};
        for(size_t k = 0; k < lenT; ++k)
        {
            hashT[t[k]] += 1; // 统计 T 中的字符，考虑重复
        }
        uint hashWindow[256] = {0}; // 统计 S 的滑动窗口中出现在 T 中的字符

        uint start = 0;
        uint minLen = lenS + 1;
        uint pBegin = 0;
        uint pEnd = -1; // 双指针初始化
        uint matchCnt = 0; // 统计当前滑动窗口中匹配的字符对
        while(true)
        {
            if(matchCnt == lenT) //  T 中所有字符都出现
            {
                while(hashT[s[pBegin]] == 0 || hashWindow[s[pBegin]] > hashT[s[pBegin]]) // 收紧窗口的左端，第二个条件表示窗口中包含了多余的重复字符
                {
                    --hashWindow[s[pBegin]];
                    ++pBegin;
                }
                if(pEnd - pBegin + 1 < minLen)
                {
                    minLen = pEnd - pBegin + 1;
                    start = pBegin;
                }
                --matchCnt;
                --hashWindow[s[pBegin]];
                ++pBegin; // 起始指针往后移动，相应统计量 -1
            }
            ++pEnd;
            if(pEnd == lenS) break;
            ++hashWindow[s[pEnd]];
            if(hashT[s[pEnd]] > 0 && hashWindow[s[pEnd]] <= hashT[s[pEnd]]) ++matchCnt; // 新增匹配
        }
        if(minLen == lenS + 1) return "";
        else return s.substr(start, minLen);
    }
};

// 不考虑重复

typedef unsigned int uint;
class Solution
{
public:
    string minWindow(string s, string t)
    {
        uint lenS = s.size();
        uint lenT = t.size();
        if (lenS < lenT || lenT == 0) return "";

        uint hashT[256] = { 0 };
        uint uniqueChar = 0;
        for (size_t k = 0; k < lenT; ++k)
        {
            if (hashT[t[k]] == 0) uniqueChar += 1; // 统计 T 中的字符，不考虑重复
            hashT[t[k]] = 1; // 不管出现多少次，都是 1
        }
        uint hashWindow[256] = { 0 };

        uint start = 0;
        uint minLen = lenS + 1;
        uint pBegin = 0;
        uint pEnd = -1;
        uint matchCnt = 0;
        while (true)
        {
            if (matchCnt == uniqueChar) // 匹配了 T 中所有字符
            {
                while (hashT[s[pBegin]] == 0 || hashWindow[s[pBegin]] > 1) // 收紧窗口的左端，第二个条件表示窗口中包含了多余的重复字符
                {
                    --hashWindow[s[pBegin]];
                    ++pBegin;
                }
                if (pEnd - pBegin + 1 < minLen)
                {
                    minLen = pEnd - pBegin + 1;
                    start = pBegin;
                }
                --matchCnt;
                --hashWindow[s[pBegin]];
                ++pBegin; // 起始指针往后移动，相应统计量 -1
            }
            ++pEnd;
            if (pEnd == lenS) break;
            ++hashWindow[s[pEnd]];
            if(hashT[s[pEnd]] > 0 && hashWindow[s[pEnd]] == 1) ++matchCnt; // 新增匹配
        }
        if (minLen == lenS + 1) return "";
        else return s.substr(start, minLen);
    }
};

4.42. [LeetCode] Nth Digit 第 $N$ 个数字

Hint：$k$ 位数的个数是 $9 \times 10^{k-1}$ ，例如，两位数有 $90$ 个；先确定第 $N$ 个数字是几位数，再定位到具体的数，取出相应数字。

https://leetcode.com/problems/nth-digit/

class Solution
{
public:
    int findNthDigit(int n)
    {
        int sum = 0;
        int k = 1;
        while(sum + k * 9 * pow(10, k-1) < n)
        {
            sum += k * 9 * pow(10, k-1);
            k++;
        }
        int a = (n - sum) / k;
        int b = (n - sum) % k;
        int num = pow(10, k-1) + a - 1; // 定位到具体的数
        if(b == 0) return num % 10; // 当前数的最后一位数字（个位）
        else return ((num + 1) / static_cast<int>(pow(10, k-b))) % 10; // 下一个数的第 b 位数字
    }
};

4.43. [LeetCode] Pow(x, n) 求幂

Hint：$x^{2k} = x^k \times x^k,\ x^{2k+1} = x \times x^k \times x^k$ 。

https://leetcode.com/problems/powx-n/

// 递归

double myPow(double x, int n)
{
    if(fabs(x) < 1e-7)
    {
        if(n < 0) throw logic_error("ZeroDivisionError"); // 底数为 0， 指数为负
        return 1.0;
    }
    if(n == 0) return 1;
    if(n == 1) return x;
    if(n < 0)
    {
        if(n == INT_MIN) return 1/x * myPow(1/x, - (n + 1)); // - INT_MIN 溢出
        else return myPow(1/x, - n);
    }
    double tmp = myPow(x, n/2);
    if(n % 2) return x * tmp * tmp;
    else return tmp * tmp;
}

// 迭代

double myPow(double x, int n)
{
    if(fabs(x) < 1e-7)
    {
        if(n < 0) throw logic_error("ZeroDivisionError"); // 底数为 0， 指数为负
        return 1.0;
    }

    if(n == 0) return 1.0;
    if(n == 1) return x;

    double ans = 1.0;

    if(n < 0)
    {
        x = 1/x;
        if(n == INT_MIN) // - INT_MIN 溢出
        {
            ans *= x;
            n = INT_MAX;
        }
        else n = - n;
    }

    while(n > 0)
    {
        int k = 1;
        double tmp = x;
        while(k <= n/2)
        {
            tmp *= tmp;
            k <<= 1;
        }
        n -= k;
        ans *= tmp;
    }

    return ans;
}

4.44. [LeetCode] Longest Valid Parentheses 最长有效匹配括号长度

https://leetcode.com/problems/longest-valid-parentheses/

// 方法一：动态规划
// 设 dp[i] 表示以 s[i] 结尾的最长匹配长度
// 当 s[i] = '(' ，dp[i] = 0
// 当 s[i] = ')' 且 s[i-1] = '(' ，dp[i] = dp[i-2] + 2
// 当 s[i] = ')' 且 s[i-1] = ')' ，需要找到与 s[i] 匹配的左括号的位置，而以 s[i-1] 结尾的最长匹配组的长度为 dp[i-1]，
// 因此与 s[i] 匹配的位置为 i - 1 - dp[i-1]

class Solution
{
public:
    int longestValidParentheses(string s)
    {
        if(s.size() <= 1) return 0;
        vector<int> dp(s.size(), 0);
        int res = 0;
        for(int i = 1; i < s.size(); ++i)
        {
            if(s[i] == ')')
            {
                if(s[i-1] == '(') dp[i] = i-2 >= 0 ? dp[i-2] + 2 : 2;
                else
                {
                    int left = i - 1 - dp[i-1];
                    if(left >= 0 && s[left] == '(')
                    {
                        dp[i] = left > 0 ? dp[left-1] + dp[i-1] + 2 : dp[i-1] + 2;
                    }
                }
            }
            res = max(res, dp[i]);
        }
        vector<int>().swap(dp);
        return res;
    }
};

// 方法二：栈
// 将达成匹配的括号的flag置为true
// 求flag为true的最长连续子数组
class Solution
{
public:
    int longestValidParentheses(string s)
    {
        const int LEN = s.size();
        if(LEN <= 1) return 0;
        stack<int> id_stk;
        vector<bool> match_flag(LEN, false);
        for(int k = 0; k < LEN; ++k)
        {
            if(s.at(k) == '(') id_stk.push(k);
            else if(!id_stk.empty())
            {
                match_flag[id_stk.top()] = true; // left parentheses
                match_flag[k] = true; // right parentheses
                id_stk.pop();
            }
        }
        int res = 0;
        int begin = -1;
        // longest continuous 'true'
        for(int end = 0; end < LEN; ++end)
        {
            if(match_flag[end] && begin == -1) begin = end;
            else if(begin > -1 && (end+1 == LEN or !match_flag[end+1]))
            {
                res = max(res, end - begin + 1);
                begin = -1;
            }
        }
        return res;
    }
};

4.45. 丢弃的数

从 $1,2,...,n$ 中取丢弃 $k$ 个数，剩余的数形成一个数组 $v$ ，求出丢弃的数。

$k=1$

$a = \sum_{i=1}^n i - \sum_{j=1} v_j$ 。
$k=2$

$a + b = \sum_{i=1}^n i - \sum_{j=1} v_j,\ a \times b = n! / \prod_{j=1} v_j$ 。

考虑到连乘可能溢出，可以使用平方和 $a^2 + b^2 = \sum_{i=1}^n i^2 - \sum_{j=1} v_j^2$ 。

4.46. [LeetCode] Trapping Rain Water 接雨水

Hint：方法一，水从地面往上溢，统计每一层的积水，时间复杂度 $\mathcal{O}(NH_{max})$ ；方法二，双指针，当左高右低，推进右边的指针，当左低右高，推进左边的指针。

https://leetcode.com/problems/trapping-rain-water/

// 方法一

class Solution
{
public:
    int trap(vector<int>& height)
    {
        if(height.size() <= 1) return 0;

        int maxh = *max_element(height.begin(), height.end());
        int ans = 0;
        for(int h = 1; h <= maxh; ++h)
        {
            vector<int> idx;
            for(int i = 0; i < height.size(); ++i)
            {
                if(height[i] >= h) idx.push_back(i); // 找到所有会积水的区间
            }
            if(idx.size() < 2) break;
            for(int j = 0; j < idx.size() - 1; ++j)
            {
                ans += idx[j+1] - idx[j] - 1; // 第 h 层的积水量
            }
        }
        return ans;
    }
};

// 方法二

class Solution
{
public:
    int trap(vector<int>& height)
    {
        if(height.size() <= 1) return 0;

        int ans = 0;

        int left = 0;
        int leftmax = height[0];
        int right = height.size() - 1;
        int rightmax = height[right];
        while(left < right)
        {
            if(height[left] < height[right]) // 左低右高
            {
                if(height[left] <= leftmax)
                {
                    ans += leftmax - height[left];
                    ++left;
                }
                else leftmax = height[left];
            }
            else // 左高右低
            {
                if(height[right] <= rightmax)
                {
                    ans += rightmax - height[right];
                    --right;
                }
                else rightmax = height[right];
            }
        }
        return ans;
    }
};

4.47. [LeetCode] Sudoku Solver 数独

https://leetcode.com/problems/sudoku-solver/

// code 用于编码数字出现的位置
struct code
{
    int a;
    int b;
    char digit;
    code(int _a, int _b, char _digit): a(_a), b(_b), digit(_digit){}
    bool operator<(const code& rhs) const // 两个 const
    {
        if(digit < rhs.digit) return true;
        if(digit > rhs.digit) return false;
        if(a < rhs.a) return true;
        if(a > rhs.a) return false;
        if(b < rhs.b) return true;
        return false;
    }
    /* 这里重载运算符 < 把 a，b，digit 都作为关键字，这对于后面 set 的 find 操作很关键。 */
    /* 假如只使用 digit 作为关键字，set 将把 (1,2,'1') 和 (3,5,'1') 视为相同的元素。 */
};

class Solution
{
public:
    void solveSudoku(vector<vector<char>>& board)
    {
        if(board.size() != 9 || board[0].size() != 9) return;
        set<code> used;
        for(int r = 0; r < 9; ++r)
        {
            for(int c = 0; c < 9; ++c)
            {
                if(board[r][c] != '.')
                {
                    used.emplace(code(r, -1, board[r][c])); // 第 r 行出现了 board[r][c]
                    used.emplace(code(-1, c, board[r][c])); // 第 c 列出现了 board[r][c]
                    used.emplace(code(r/3, c/3, board[r][c])); // 第 (r/3, c/3) 块出现了 board[r][c]
                }
            }
        }
        solveSudoku(board, used, 0);
    }
private:
    bool solveSudoku(vector<vector<char>>& board, set<code>& used, int t)
    {
        while(t < 81 && board[t/9][t%9] != '.') ++t;
        if(t == 81) return true;
        int r = t / 9;
        int c = t % 9;
        for(int k = 1; k <= 9; ++k)
        {
            char digit = '0' + k;
            code rowcode(r, -1, digit);
            code colcode(-1, c, digit);
            code blockcode(r/3, c/3, digit);
            if(used.find(rowcode) == used.end() && used.find(colcode) == used.end() && used.find(blockcode) == used.end())
            {
                board[r][c] = digit;
                used.emplace(rowcode);
                used.emplace(colcode);
                used.emplace(blockcode);
                if(solveSudoku(board, used, t + 1)) return true;
                used.erase(rowcode);
                used.erase(colcode);
                used.erase(blockcode);
                board[r][c] = '.'; // 擦除
            }
        }
        return false;
    }
};

4.48. [LeetCode] Median of Two Sorted Arrays 两个排序数组的中位数

Hint：方法一，归并，时间复杂度 $\mathcal{O}(m+n)$ ；方法二，二分查找，时间复杂度 $\mathcal{O}(\log (m+n))$ 。

https://leetcode.com/problems/median-of-two-sorted-arrays/

https://windliang.cc/2018/07/18/leetCode-4-Median-of-Two-Sorted-Arrays/

// 方法一

class Solution
{
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
    {
        if(nums1.empty() && nums2.empty()) return 0.0;
        int m = nums1.size();
        int n = nums2.size();
        int i = 0;
        int j = 0;
        int k = 0;
        double median;
        double premedian;
        while(true)
        {
            if(j == n || (i < m && nums1[i] <= nums2[j]))
            {
                median = nums1[i];
                ++i;
            }
            else if(i == m || (j < n && nums1[i] > nums2[j]))
            {
                median = nums2[j];
                ++j;
            }
            if((m+n)%2 == 1 && k == (m+n)/2) return median;
            if((m+n)%2 == 0 && k == (m+n)/2-1) premedian = median;
            if((m+n)%2 == 0 && k == (m+n)/2) return (premedian + median) / 2.0;
            ++k;
        }
    }
};

# 方法二

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        n1, n2 = len(nums1), len(nums2)
        n = n1 + n2
        if n & 1:
            return self.findKth(nums1, 0, n1, nums2, 0, n2, (n+1)//2)
        else:
            return (self.findKth(nums1, 0, n1, nums2, 0, n2, n//2) +
                self.findKth(nums1, 0, n1, nums2, 0, n2, n//2+1)) / 2.0

    def findKth(self, l1, i1, n1, l2, i2, n2, k):
        while True:
            if i1 == n1: return l2[i2+k-1] # 区间为空
            if i2 == n2: return l1[i1+k-1] # 区间为空
            if k == 1: return min(l1[i1], l2[i2])
            half = k // 2
            j1, j2 = min(i1+half-1, n1-1), min(i2+half-1, n2-1)
            if l1[j1] > l2[j2]:
                k -= j2 - i2 + 1
                i2 = j2 + 1
            else:
                k -= j1 - i1 + 1
                i1 = j1 + 1

4.49. 滑动窗口

[LeetCode] Sliding Window Maximum 滑动窗口最大值。Hint：使用双端队列；新加入元素如果比队尾元素小，则直接入队，否则删除队尾元素直到队空或队尾元素比新加入元素大；如果队首元素在滑动窗口之外，则删除之；队首元素就是当前窗口的最大值。

https://leetcode.com/problems/sliding-window-maximum/

class Solution
{
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k)
    {
        vector<int> win_max;
        if(nums.size() == 0 || k <= 0) return win_max;
        deque<int> que; // 双端队列，存的是元素下标
        for(int i = 0; i < k && i < nums.size(); ++i)
        {
            while(!que.empty() && nums[que.back()] <= nums[i]) que.pop_back();
            que.push_back(i);
        }
        win_max.push_back(nums[que.front()]); // 队首的是滑动窗口最大值
        for(int i = k; i < nums.size(); ++i)
        {
            while(!que.empty() && nums[que.back()] <= nums[i]) que.pop_back();
            if(!que.empty() && que.front() <= i - k) que.pop_front(); // 不属于当前滑动窗口
            que.push_back(i);
            win_max.push_back(nums[que.front()]);
        }
        return win_max;
    }
};

[LeetCode] Sliding Window Median 滑动窗口中位数。Hint：使用 multiset（包含重复元素、默认排序），加入/删除元素时调整 mid 的位置。

https://leetcode.com/problems/sliding-window-median/

// https://leetcode.com/problems/sliding-window-median/discuss/96340/O(n-log-k)-C%2B%2B-using-multiset-and-updating-middle-iterator

class Solution
{
public:
    vector<double> medianSlidingWindow(vector<int>& nums, int k)
    {
        multiset<int> window(nums.begin(), nums.begin()+k);
        auto mid = next(window.begin(), k/2); // #include<iterator>，next 返回一个迭代器，指向 window.begin() + k/2
        vector<double> medians;
        for(int i = k; i < nums.size(); ++i)
        {
            medians.push_back((double(*mid) + *prev(mid, 1 - k%2)) / 2.0); // #include<iterator>，prev 返回一个迭代器，指向 mid - (1 - k%2)

            // 比较插入/删除值与 *mid 的大小关系，共 4 种情况，相应调整 mid

            window.insert(nums[i]);
            if(nums[i] < *mid) --mid;

            if(nums[i-k] <= *mid) ++mid;
            window.erase(window.lower_bound(nums[i-k])); // 不能直接 erase(nums[i-k])，会删除所有重复元素
        }
        medians.push_back((double(*mid) + *prev(mid, 1 - k%2)) / 2.0); // 最后一个窗口的中位数

        return medians;
    }
};

[LeetCode] Find Median from Data Stream 数据流中的中位数。Hint：使用一个最大堆和一个最小堆；保证数据平均分配到两个堆中，两个堆的数据个数之差不超过1；当两个堆的数据个数是偶数（各占一半），新数据插入最小堆，否则插入最大堆（这样最小堆的数据个数总是比最大堆多1或相等）；保证最大堆中的数都不大于最小堆中的数。

https://leetcode.com/problems/find-median-from-data-stream/

class MedianFinder
{
public:
    MedianFinder() {}

    void addNum(int num)
    {
        if((max_heap.size() + min_heap.size()) & 1)
        {
            if(!min_heap.empty() && num > min_heap.top())
            {
            // 新数插入最小堆，最小堆中最小的数（堆顶）插入最大堆
                min_heap.push(num);
                num = min_heap.top();
                min_heap.pop();
            }
            max_heap.push(num);
        }
        else
        {
            if(!max_heap.empty() && num < max_heap.top())
            {
            // 新数插入最大堆，最大堆中最大的数（堆顶）插入最小堆
                max_heap.push(num);
                num = max_heap.top();
                max_heap.pop();
            }
            min_heap.push(num);
        }
    }

    double findMedian()
    {
        if((max_heap.size() + min_heap.size()) & 1) return min_heap.top();
        else return (max_heap.top() + min_heap.top()) / 2.0;
    }
private:
    priority_queue<int, vector<int>, less<int>> max_heap;
    priority_queue<int, vector<int>, greater<int>> min_heap;
};

4.50. 逆波兰式：转换与求值

https://leetcode.com/problems/evaluate-reverse-polish-notation/

/*
中缀表达式转后缀表达式（逆波兰式）
遍历中缀表达式：
1）如果遇到操作数，则直接输出。
2）如果遇到左括号，则直接压入栈中。
3）如果遇到右括号，则将栈中元素弹出，直到遇到左括号为止；左括号只弹出栈而不输出。
4）如果遇到操作符，则检查栈顶元素优先级，如果其优先级**不低于**当前操作符（左括号除外），则弹出栈顶元素并输出；
重复此过程直到：栈顶元素优先级小于当前操作符或者栈顶元素为左括号或者栈为空，然后将当前操作符压入栈中。
5）表达式处理完毕，将栈中元素依次弹出。
注意：只有遇到右括号的情况下才会弹出左括号，其他情况都不会弹出。
*/


class ReversePolishNotation
{
public:
    // 假设输入表达式一定是正确的，且只包含个位整数、+-*/、括号
    vector<char> convertRPN(const string& expr)
    {
        vector<char> rpn;
        if(expr.size() < 1) return rpn;
        stack<char> op;
        for(auto& e: expr)
        {
            if('0' <= e && e <= '9') rpn.push_back(e);
            else if(e == '(') op.push(e);
            else if(e == ')')
            {
                while(!op.empty() && op.top()!='(')
                {
                    rpn.push_back(op.top());
                    op.pop();
                }
                op.pop(); // pop '('
            }
            // + - * /
            else
            {
                while(!op.empty() && op.top()!='(' && prior.at(op.top())>=prior.at(e))
                {
                    rpn.push_back(op.top());
                    op.pop();
                }
                op.push(e);
            }
        }
        while(!op.empty())
        {
            rpn.push_back(op.top());
            op.pop();
        }
        return rpn;
    }
private:
    static const unordered_map<char, int> prior;
};

const unordered_map<char, int> ReversePolishNotation::prior = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};

/*
逆波兰式求值
遍历逆波兰式，遇到操作数就入栈；遇到操作符则出栈两个操作数执行运算，运算结果重新入栈；
遍历结束时，栈内存放的是最终运算结果。
*/

class Solution
{
public:
    int evalRPN(vector<string>& tokens)
    {
        int N = tokens.size();
        if(N == 0) return 0;
        stack<int> stk;
        int k = 0;
        int res = 0;
        while(k < N)
        {
            if(tokens[k] != "*" && tokens[k] != "-" && tokens[k] != "+" && tokens[k] != "/")
            {
                stk.push(atoi(tokens[k].c_str()));
            }
            else
            {
                int right_operand = stk.top();
                stk.pop();
                int left_operand = stk.top();
                stk.pop();
                switch(tokens[k][0])
                {
                    case '+': res = left_operand + right_operand; break;
                    case '-': res = left_operand - right_operand; break;
                    case '*': res = left_operand * right_operand; break;
                    case '/': res = left_operand / right_operand; break;
                }
                stk.push(res);
            }
            k++;
        }
        if(!stk.empty())
        {
            res = stk.top();
            stk.pop();
        }
        return res;
    }
};

4.51. 字典树/前缀树（ Trie ）

字典树/前缀树的查找时间复杂度是 $\mathcal{O}(l)$ ，创建一棵树的时间复杂度是 $\mathcal{O}(nl)$ ，其中 $l$ 是单词长度， $n$ 是字典大小。

https://leetcode.com/problems/implement-trie-prefix-tree

class TrieNode
{
public:
    TrieNode* child[26];
    bool has_word;
    TrieNode()
    {
        fill(child, child+26, nullptr);
        has_word = false;
    }
};

class Trie
{
public:
    /** Initialize your data structure here. */
    Trie()
    {
        root = new TrieNode();
    }

    /** Inserts a word into the trie. */
    void insert(string word)
    {
        TrieNode* p = root;
        for(auto& c: word)
        {
            int branch = c - 'a';
            if(p->child[branch] == nullptr) p->child[branch] = new TrieNode();
            p = p->child[branch];
        }
        p->has_word = true;
    }

    /** Returns if the word is in the trie. */
    bool search(string word)
    {
        TrieNode* p = root;
        for(auto& c: word)
        {
            int branch = c - 'a';
            if(p->child[branch] == nullptr) return false;
            p = p->child[branch];
        }
        return p->has_word;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix)
    {
        TrieNode* p = root;
        for(auto& c: prefix)
        {
            int branch = c - 'a';
            if(p->child[branch] == nullptr) return false;
            p = p->child[branch];
        }
        return true;
    }
private:
    TrieNode* root;
};

from collections import defaultdict

class TrieNode(object):
    def __init__(self):
        self.dict = defaultdict(TrieNode)
        self.word = False

class Trie(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = TrieNode()

    def insert(self, word):
        """
        Inserts a word into the trie.
        :type word: str
        :rtype: None
        """
        child = self.root
        for letter in word:
            child = child.dict[letter]
        child.word = True

    def search(self, word):
        """
        Returns if the word is in the trie.
        :type word: str
        :rtype: bool
        """
        child = self.root
        for letter in word:
            child = child.dict.get(letter)
            if child is None:
                return False
        return child.word

    def startsWith(self, prefix):
        """
        Returns if there is any word in the trie that starts with the given prefix.
        :type prefix: str
        :rtype: bool
        """
        child = self.root
        for letter in prefix:
            child = child.dict.get(letter)
            if child is None:
                return False
        return True

4.52. LRU（Least Recently Used）缓存机制

Hint：通过双向链表辅以哈希表实现；双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的；哈希表将缓存数据的 key 映射到其在双向链表中的位置；访问和插入数据的时间复杂度都是 $\mathcal{O}(1)$ 。

https://leetcode.com/problems/lru-cache/

class LRUCache
{
public:
    LRUCache(int capacity): cache_capacity(capacity){}

    int get(int key)
    {
        if(cache_loc.find(key) == cache_loc.end()) return -1;
        auto p = cache_loc[key];
        int value = p->second;
        cache.erase(p);
        cache.emplace_front(key, value); // 最新访问的数据需要移到链表头部
        cache_loc[key] = cache.begin();
        return value;
    }

    void put(int key, int value)
    {
        if(cache_loc.find(key) != cache_loc.end())
        {
            auto p = cache_loc[key];
            cache.erase(p);
            cache.emplace_front(key, value);
            cache_loc[key] = cache.begin();
            return;

        }
        if(cache.size() == cache_capacity)
        {
            auto tail = cache.back();
            cache.pop_back();
            cache_loc.erase(tail.first);
        }
        cache.emplace_front(key, value);
        cache_loc[key] = cache.begin();
    }
private:
    int cache_capacity;
    list<pair<int,int>> cache;
    unordered_map<int, list<pair<int,int>>::iterator> cache_loc;
};

4.53. [LeetCode] House Robber II 环形房屋偷盗

Hint：在区间 $[0, n-2]$ 和区间 $[1, n-1]$ 分别做动态规划。

https://leetcode-cn.com/problems/house-robber-ii/

class Solution
{
public:
    int rob(vector<int>& nums)
    {
        int n = nums.size();
        if(n == 0) return 0;
        if(n == 1) return nums[0];
        int res = 0;
        _rob(nums, 0, n-2, res);
        _rob(nums, 1, n-1, res);
        return res;
    }
private:
    void _rob(vector<int>& nums, int from, int to, int& res)
    {
        vector<int> dp(nums);
        res = max(res, nums[from]);
        for(int i = from+1; i <= to; ++i)
        {
            for(int j = from; j < i-1; ++j) dp[i] = max(dp[i], dp[j] + nums[i]);
            res = max(res, dp[i]);
        }
    }
};

4.54. [LeetCode] Serialize And Deserialize Binary Tree 序列化与反序列化二叉树

https://leetcode-cn.com/problems/h54YBf/

https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        // # 作为空节点, $ 用于分割不同节点的 val
        if(!root) return "#";
        return to_string(root->val) +
            "$" +
            serialize(root->left) +
            serialize(root->right);
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data.empty()) return nullptr;
        int i = 0;
        TreeNode* root = deserialize(data, i);
        return root;
    }
private:
    TreeNode* deserialize(string& data, int& i)
    {
        if(data[i] == '#')
        {
            // 注意这里 i 一定要自增
            ++i;
            return nullptr;
        }
        int val = scanDigit(data, i);
        TreeNode* node = new TreeNode(val);
        node->left = deserialize(data, i);
        node->right = deserialize(data, i);
        return node;
    }
    int scanDigit(string& data, int& i)
    {
        if(i == data.size()) return -9999;
        bool pos = true;
        if(data[i] == '-')
        {
            pos = false;
            i++;
        }
        int res = 0;
        while(i < data.size() && '0' <= data[i] && data[i] <= '9')
        {
            res = 10 * res + data[i] - '0';
            i++;
        }
        ++i; // 略过 $
        return pos? res: -1*res;
    }
};

4.55. [LeetCode] 生存人数：统计生存人数最多的年份

Hint：用差分数组记录出生年份和死亡年份的人数变化，差分数组的前缀和表示该年份的生存人数。

https://leetcode.cn/problems/living-people-lcci/

class Solution
{
public:
    int maxAliveYear(vector<int>& birth, vector<int>& death)
    {
        const int SY = 1900;
        const int EY = 2000;
        int count[EY - SY + 2] = {0};
        int N = birth.size();
        for(int i = 0; i < N; ++i)
        {
            count[birth[i] - SY] += 1;
            count[death[i] + 1 - SY] -= 1; // 区间 [birth[i], death[i]] 内生存人数都+1
        }
        int most = 0, year = -1;
        int sum = 0;
        for(int k = 0; k <= EY - SY; ++k)
        {
            sum += count[k];
            if(sum > most)
            {
                most = sum;
                year = k + SY;
            }
        }
        return year;
    }
};

4.56. [LeetCode] 验证栈的压入、弹出序列

Hint：如果下一个弹出的数字正好是栈顶数字，那么直接弹出；如果下一个弹出的数字不在栈顶，就把压栈序列中还没入栈的数字压入辅助栈，直到把下一个需要弹出的数字压入栈为止。如果所有的数字都压入栈了，仍然没找到下一个弹出的数字，那么该序列不可能是一个弹出序列。

https://leetcode.com/problems/validate-stack-sequences

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        stk = []
        i, j = 0, 0
        n = len(pushed)
        while i < n and j < n:
            if len(stk) > 0 and stk[-1] == popped[j]:
                stk.pop()
                j += 1
            else:
                stk.append(pushed[i])
                i += 1
        if i == n:
            while len(stk) > 0 and stk[-1] == popped[j]:
                stk.pop()
                j += 1
            if j == n: return True
        return False

4.57. [LeetCode] 和为 s 的连续正数序列

Hint：双指针。

https://leetcode.cn/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/

class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        res = []
        begin, end = 1, 2
        s = begin + end
        while begin < end:
            if s == target:
                res.append(list(range(begin, end+1)))
                s -= begin
                begin += 1
                end += 1
                s += end
            elif s < target:
                end += 1
                s += end
            else:
                s -= begin
                begin += 1
        return res

延伸：统计和为 n 的序列的个数。

https://leetcode.com/problems/consecutive-numbers-sum

\[\begin{split}x + (x+1) + \cdots + (x+k-1) & = \frac{k(2x+k-1)}{2},\ x > 0,\ k > 0 \\ & = kx + \frac{k(k-1)}{2} \\ & \geq \frac{k(k+1)}{2}\end{split}\]
$\color{darkgreen}{Code}$
1import math
2class Solution:
3    def consecutiveNumbersSum(self, n: int) -> int:
4        ans = 0
5        for k in range(1, int(math.sqrt(2*n))+1):
6            s = k*(k-1)//2
7            if (n - s) % k == 0:
8                ans += 1
9        return ans

4.58. [LeetCode] Rotting Oranges 腐败的橙子

Hint：多源 BFS，同时从各个源推进一步；双端队列。

https://leetcode.com/problems/rotting-oranges

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        if not grid or not grid[0]: return 0
        m, n = len(grid), len(grid[0])
        maxd = 100
        dq = deque()
        fresh = 0
        for x in range(m):
            for y in range(n):
                if grid[x][y] == 2:
                    dq.append((x,y))
                elif grid[x][y] == 1:
                    fresh += 1
        minutes = 0
        ## fresh = 0 就不需要再遍历了
        while len(dq) and fresh > 0:
            ## sn 代表源的数量
            sn = len(dq)
            for i in range(sn):
                x, y = dq.popleft()
                for dx, dy in [[-1,0], [0,-1], [0,1], [1,0]]:
                    _x, _y = x + dx, y + dy
                    if 0 <= _x < m and 0 <= _y < n and grid[_x][_y] == 1:
                        grid[_x][_y] = 2
                        dq.append((_x, _y))
                        fresh -= 1
            minutes += 1
        if fresh == 0: return minutes
        else: return -1

4.59. [LeetCode] Maximum Width of Binary Tree 二叉树最大宽度

Hint：层序遍历，计算每层最左边和最右边节点的序号之差作为该层的宽度。

https://leetcode.com/problems/maximum-width-of-binary-tree

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        if root is None: return 0
        dq = deque([(root, 1)])
        r = []
        while len(dq):
            n = len(dq)
            ## 为了避免溢出，每层最左侧的节点编号都从 1 开始
            ## r 保存每一层最右侧的节点的编号，其值就等于相应层的宽度
            init = dq[0][1]
            r.append(dq[-1][1] - init + 1)
            for i in range(n):
                p, idx = dq.popleft()
                idx = idx - init + 1
                if p.left:
                    ## 左节点编号
                    dq.append((p.left, idx*2))
                if p.right:
                    ## 右节点编号
                    dq.append((p.right, idx*2+1))
        return max(r)

4.60. [LeetCode] Restore The Array 从字符串恢复整数数组

Hint：动态规划；整数不能以 0 开头；注意跳过数值范围明显越界的分割方法。

https://leetcode.com/problems/restore-the-array

class Solution:
    def numberOfArrays(self, s: str, k: int) -> int:
        mod = 1000000007
        n = len(s)
        nk = len(str(k))
        dp = [0] * n
        dp[0] = 1
        for i in range(1, n):
            if s[i] != '0':
                ## s[i] 单独分割
                dp[i] = dp[i-1]
            else:
                dp[i] = 0
            ## s[j:i+1] 单独分割
            ## 不需要去遍历明显越界的 s[j:i+1]
            for j in range(max(0, i-nk), i):
                if s[j] != '0':
                    dji = int(s[j:i+1])
                    if dji <= k:
                        dp[i] += dp[j-1] if j > 0 else 1
                        dp[i] %= mod
        return dp[-1]

4.61. 重叠区间问题

一般使用贪心算法，先对序列排序；维护区间 start/end 的最小值。

[LeetCode] Non-overlapping Intervals 不重叠区间。Hint：贪心算法，总是选择结束最早的区间。

https://leetcode.com/problems/non-overlapping-intervals

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals = sorted(intervals, key=lambda x: x[1])
        pend = float("-inf")
        cnt = 0
        for start, end in intervals:
            if start >= pend:
                pend = end
            else:
                cnt += 1
        return cnt

[LeetCode] Minimum Number of Arrows to Burst Balloons 用最少数量的箭引爆气球。Hint：贪心算法。

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        points = sorted(points, key = lambda x: (x[1], x[0]))
        min_end = - 2**31 - 1
        ans = 0
        for start, end in points:
            if start > min_end:
                ## 在 x = min_end 处发射一支箭
                min_end = end
                ans += 1
        return ans

4.62. [LeetCode] Stone Game 石头游戏

Hint：记忆化递归；动态规划。

https://leetcode.com/problems/stone-game-ii

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        m = 1
        k = len(piles)
        ## 记录状态 (i, m) 的最大分
        mem = [[-1]*k for _ in range(k)]
        return self.maxScore(piles, 0, m, mem)

    def maxScore(self, piles, i, m, mem):
        if len(piles) - i <= 2*m:
            return sum(piles[i:])
        if mem[i][m] >= 0:
            return mem[i][m]
        ## 拿完 piles[i:i+x] 之后，要等对方从 i+x 开始拿，之后能拿到的最大分是 sum(piles[i+x:]) - self.maxScore(piles, i+x, max(m, x), mem)
        mem[i][m] = max([sum(piles[i:i+x]) + sum(piles[i+x:]) - self.maxScore(piles, i+x, max(m, x), mem) for x in range(1, 2*m+1)])
        return mem[i][m]

https://leetcode.com/problems/stone-game-iii

INT_MIN = -0x80000000
class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        n = len(stoneValue)
        totalScore = sum(stoneValue)
        ## 后 n 项和，避免后续重复计算
        accuScore = [0] * (n+1)
        for i in range(n-1, -1, -1):
            accuScore[i] = accuScore[i+1] + stoneValue[i]
        ## dp[i]：从第 i 堆石头开始拿能够得到的最大分
        dp = [0] * (n+1)
        for i in range(n-1, -1, -1):
            takeOne = stoneValue[i] + accuScore[i+1] - dp[i+1]
            takeTwo = INT_MIN
            if i < n - 1:
                takeTwo = sum(stoneValue[i:i+2]) + accuScore[i+2] - dp[i+2]
            takeThree = INT_MIN
            if i < n - 2:
                takeThree = sum(stoneValue[i:i+3]) + accuScore[i+3] - dp[i+3]
            dp[i] = max(takeOne, takeTwo, takeThree)

        aliceScore = dp[0] << 1
        if aliceScore == totalScore:
            return "Tie"
        if aliceScore > totalScore:
            return "Alice"
        return "Bob"

4.63. 栈和队列的实现

https://leetcode.com/problems/implement-queue-using-stacks

Hint：总在第一个栈压入最新元素，在第二个栈弹出最旧元素。

class MyQueue
{
public:
    MyQueue() {}

    void push(int x)
    {
        s1.push(x);
    }

    int pop()
    {
        int front = peek();
        s2.pop();
        return front;
    }

    int peek()
    {
        if(s2.empty())
        {
            while(!s1.empty())
            {
                s2.push(s1.top());
                s1.pop();
            }
        }
        return s2.top();
    }

    bool empty()
    {
        return s1.empty() && s2.empty();
    }
private:
    stack<int> s1;
    stack<int> s2;
};

https://leetcode.com/problems/implement-stack-using-queues

Hint：总在第一个队列压入最新元素。

class MyStack
{
public:
    MyStack() {}

    void push(int x)
    {
        // 保证 q1 数据比 q2 新
        q1.push(x);
    }

    int pop()
    {
        // 优先从 q1 弹出
        if(!q1.empty())
        {
            while(q1.size() > 1)
            {
                q2.push(q1.front());
                q1.pop();
            }
            int t = q1.front();
            q1.pop();
            return t;
        }
        else
        {
            while(q2.size() > 1)
            {
                q1.push(q2.front());
                q2.pop();
            }
            int t = q2.front();
            q2.pop();
            return t;
        }
    }

    int top()
    {
        if(!q1.empty())
        {
            while(q1.size() > 1)
            {
                q2.push(q1.front());
                q1.pop();
            }
            return q1.front();
        }
        else
        {
            while(q2.size() > 1)
            {
                q1.push(q2.front());
                q2.pop();
            }
            int t = q2.front();
            // 下面这一步很重要，保证 q2 的数据总是比 q1 旧
            q1.push(t);
            q2.pop();
            return t;
        }
    }

    bool empty()
    {
        return q1.empty() && q2.empty();
    }
private:
    queue<int> q1;
    queue<int> q2;
};

4.64. 单调栈 

单调栈（Monotonic Stack）在栈的「先进后出」规则基础上，要求从栈顶到栈底的元素单调递增/递减。一般情况下，数组的每个元素都入栈一次，且至多出栈一次，因此时间复杂度是 $\mathcal{O}(n)$ 。

[LeetCode] Daily Temperatures 每日温度。

https://leetcode.com/problems/daily-temperatures

class Solution(object):
    def dailyTemperatures(self, temperatures):
        """
        :type temperatures: List[int]
        :rtype: List[int]
        """
        n = len(temperatures)
        ans = [0] * n
        stk = []
        ## 逆序遍历，栈顶元素最小
        for i in range(n-1, -1, -1):
            while stk and temperatures[i] >= temperatures[stk[-1]]:
                stk.pop()
            if stk:
                ans[i] = stk[-1] - i
            ## 入栈
            stk.append(i)
        return ans

[LeetCode] Next Greater Element 下一个更大的元素。延伸：数组为循环数组，Hint：把原数组拷贝一遍追加在尾部，就可以模拟循环数组。

https://leetcode.com/problems/next-greater-element-i

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        ## 用字典存储已经找到的结果
        mp = {}
        stk = []
        ## 逆序遍历，栈顶元素最小
        for num in nums2[::-1]:
            while stk and num >= stk[-1]:
                stk.pop()
            if stk:
                mp[num] = stk[-1]
            else:
                mp[num] = -1
            ## 入栈
            stk.append(num)
        ans = []
        for num in nums1:
            ans.append(mp[num])
        return ans

https://leetcode.com/problems/next-greater-element-ii

class Solution(object):
    def nextGreaterElements(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        n = len(nums)
        ## 把 nums 拷贝一遍就可以模拟循环数组
        nums.extend(nums[:])
        stk = []
        ans = []
        for i in range(2*n-1, -1, -1):
            while stk and nums[i] >= stk[-1]:
                stk.pop()
            if i < n:
                if stk:
                    ans.append(stk[-1])
                else:
                    ans.append(-1)
            stk.append(nums[i])
        return ans[::-1]

[LeetCode] Largest Rectangle in Histogram 直方图中的最大矩形面积。

https://leetcode.com/problems/largest-rectangle-in-histogram

class Solution(object):
    def largestRectangleArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        if not height:
            return 0
        ## 尾部追加 -1，方便计算以最后一个 bar 结尾的矩形面积
        height.append(-1)
        ans = 0
        stk = []
        ## 栈顶元素最大
        for i in range(len(height)):
            while stk and height[i] < height[stk[-1]]:
                last = stk[-1]
                stk.pop()
                h = height[last]
                pre = stk[-1] if stk else -1
                ## 计算 [pre, i) 之间的 bar 构成的矩形面积
                ## pre = -1 代表高度最低的矩形，面积为 h * i
                ans = max(ans, h * (i - 1 - pre))
            ## 入栈
            stk.append(i)
        return ans

[LeetCode] Maximal Rectangle 矩阵中的最大矩形。Hint：以 $0 \sim i-1$ 行为底，以第 $i$ 行为顶，将问题转化为「直方图中的最大矩形面积」进行求解，其中直方图的高度为连续 1 的数量。

https://leetcode.com/problems/maximal-rectangle

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        rows, cols = len(matrix), len(matrix[0])
        height = [0] * cols
        ans = 0
        for r in range(rows):
            for c in range(cols):
                if matrix[r][c] == '1':
                    height[c] += 1
                else:
                    height[c] = 0 ## 注意，这里不是累加
            ans = max(ans, self.largestRectangleArea(height))
        return ans

    def largestRectangleArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        if not height:
            return 0
        ## 尾部追加 -1，方便计算以最后一个 bar 结尾的矩形面积
        height.append(-1)
        ans = 0
        stk = []
        ## 栈顶元素最大
        for i in range(len(height)):
            while stk and height[i] < height[stk[-1]]:
                last = stk[-1]
                stk.pop()
                h = height[last]
                pre = stk[-1] if stk else -1
                ## 计算 [pre, i) 之间的 bar 构成的矩形面积
                ## pre = -1 代表高度最低的矩形，面积为 h * i
                ans = max(ans, h * (i - 1 - pre))
            ## 入栈
            stk.append(i)
        return ans

[LeetCode] Beautiful Towers I 美丽塔。Hint：两个单调栈（正向 + 反向），动态规划。

https://leetcode.com/problems/beautiful-towers-i

class Solution:
    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:
        n = len(maxHeights)
        ## prefix[i] 表示区间 [0, i] 能构成的非递减数组的元素和最大值，且位置 i 是山顶，高度为 maxHeights[i]
        ## suffix[i] 表示区间 [i, n) 能构成的非递增数组的元素和最大值，且位置 i 是山顶，高度为 maxHeights[i]
        ## 以位置 i 为山顶的 mountain 数组的元素和为：prefix[i] + suffix[i] - maxHeights[i]
        prefix = [0] * n
        suffix = [0] * n
        ## stk 保存下标
        stk = []
        for i in range(n):
            while stk and maxHeights[stk[-1]] > maxHeights[i]:
                stk.pop()
            if not stk:
                ## 区间 [0, i] 的高度统一设为 maxHeights[i]
                prefix[i] = (i + 1) * maxHeights[i]
            else:
                ## 动态规划
                ## 区间 (stk[-1], i] 的高度统一设为 maxHeights[i]
                prefix[i] = prefix[stk[-1]] + (i - stk[-1]) * maxHeights[i]
            stk.append(i)
        stk = []
        for i in range(n-1, -1, -1):
            while stk and maxHeights[stk[-1]] > maxHeights[i]:
                stk.pop()
            if not stk:
                suffix[i] = (n - i) * maxHeights[i]
            else:
                suffix[i] = suffix[stk[-1]] + (stk[-1] - i) * maxHeights[i]
            stk.append(i)
        ans = 0
        for i in range(n):
            ans = max(ans, prefix[i] + suffix[i] - maxHeights[i])
        return ans

4.65. 单词接龙

[LeetCode] Word Ladder 单词接龙（最短路径的长度）。Hint：BFS。

https://leetcode.com/problems/word-ladder

## l 单词长度，n 单词数量
## 预先计算好两两单词之间距离的时间复杂度是 O(ln^2)，这还不包括 dfs/bfs 每次遍历距离矩阵的时间
## 遍历替换单词每一个字母的时间复杂度是 O(26ln)，基于哈希表的 set 查找时间是 O(1)

from queue import Queue
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        wordSet = set(wordList)
        q = Queue()
        q.put((beginWord, 1))
        usedSet = set([beginWord])
        while not q.empty():
            word, l = q.get()
            if word == endWord:
                return l
            for i in range(len(word)):
                ## 改变第 i 个字母
                wordP1, wordP2 = word[:i], word[i+1:]
                for c in "abcdefghijklmnopqrstuvwxyz":
                    nextWord = wordP1 + c + wordP2
                    if c != word[i] and nextWord not in usedSet and nextWord in wordSet:
                        usedSet.add(nextWord)
                        q.put((nextWord, l+1))
        return 0

[LeetCode] Word Ladder II 单词接龙（最短路径集合）。Hint：如果直接在 BFS 的时候存储路径，需要很大的空间。首先用 BFS 确定路径长度，再用 DFS 沿着路径长度递减的方向查找。

https://leetcode.com/problems/word-ladder-ii

## bfs 从 endWord 出发，这样在 dfs 的时候从 beginWord 出发、沿着 dist 减小的方向一定是通向 endWord 的方向。
## 如果 bfs 从 beginWord 出发，那么 dfs 沿着 dist 增大的方向是发散的、不一定是通向 endWord 的方向。

from queue import Queue
class Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
        self.wordSet = set(wordList)
        self.wordSet.add(beginWord) ## beginWord 加入 wordSet，需要计算路径长度
        self.distDict = {} ## 存储 endWord 到其他 word 的路径长度
        self.bfs(endWord)  ## 从 endWord 出发
        res, seq = [], []
        self.dfs(beginWord, endWord, seq, res)
        return res

    def bfs(self, startWord):
        q = Queue()
        q.put((startWord, 0))
        self.distDict[startWord] = 0
        while not q.empty():
            word, dist = q.get()
            nextWordList = self.getNextWordList(word)
            for nextWord in nextWordList:
                if nextWord not in self.distDict:
                    q.put((nextWord, dist + 1))
                    self.distDict[nextWord] = dist + 1

    def dfs(self, beginWord, endWord, seq, res):
        seq.append(beginWord)
        if beginWord == endWord:
            res.append(seq[:]) ## 注意：这里要对 seq 拷贝
        else:
            nextWordList = self.getNextWordList(beginWord)
            for nextWord in nextWordList:
                if nextWord in self.distDict and self.distDict[nextWord] == self.distDict[beginWord] - 1:
                    self.dfs(nextWord, endWord, seq, res)
        seq.pop()

    def getNextWordList(self, word):
        nextWordList = []
        for i in range(len(word)):
            wordP1, wordP2 = word[:i], word[i+1:]
            for c in "abcdefghijklmnopqrstuvwxyz":
                nextWord = wordP1 + c + wordP2
                if c != word[i] and nextWord in self.wordSet:
                    nextWordList.append(nextWord)
        return nextWordList