数据结构和算法刷题总结（持续更新）

void SelectSort(vector& nums)
{
    for (int i = 0; i < nums.size(); ++i)
    {
        int minIndex = i;
        for (int j = i + 1; j < nums.size(); ++j)
            minIndex = (nums[minIndex] > nums[j]) ? j : minIndex;
        ::swap(nums[minIndex], nums[i]);
    }
}

void BubleSort(vector& nums)
{
    for (int i = nums.size() - 1; i > 0; --i)
    {
        for (int j = 0; j < i; ++j)
        {
            if (nums[j] > nums[j + 1])
                ::swap(nums[j], nums[j + 1]);
        }
    }
}

void InsertSort(vector& nums)
{
    if (nums.size() <= 1)
        return;
    for (int i = 1; i < nums.size(); ++i)
    {
        for (int j = i; j > 0 && nums[j] < nums[j - 1]; --j)
            ::swap(nums[j], nums[j - 1]);
    }
}

void MergeSort(vector& nums)
{
    if (nums.size() <= 1)
        return;
    MergeSort_Process(nums, 0, nums.size() - 1);
}
void MergeSort_Process(vector& nums, int l, int r)
{
    if (l >= r)
        return;
    int mid = l + ((r - l) >> 1);
    MergeSort_Process(nums, l, mid);
    MergeSort_Process(nums, mid + 1, r);
    Merge(nums, l, r, mid);
}
void Merge(vector& nums, int l, int r, int mid)
{
    int i = l, j = mid + 1;
    vector temp(r - l + 1);
    int k = 0;
    while (i <= mid && j <= r)
    {
        if (nums[i] <= nums[j])
            temp[k++] = nums[i++];
        else
            temp[k++] = nums[j++];
    }
    while (i <= mid)
        temp[k++] = nums[i++];
    while (j <= r)
        temp[k++] = nums[j++];
    ::copy(temp.begin(), temp.end(), nums.begin() + l);
}

void QuickSort(vector& nums)
{
    if (nums.size() <= 1)
        return;
    srand((unsigned int)time(NULL));
    QuickSort_Process(nums, 0, nums.size() - 1);
}
void QuickSort_Process(vector& nums, int l, int r)
{
    if (l >= r)
        return;
    int pos = l + (rand() % (r - l + 1));
    int sr = 0, br = 0;
    Partition(nums, l, r, sr, br, pos);
    QuickSort_Process(nums, l, sr);
    QuickSort_Process(nums, br, r);
}
void Partition(vector& nums, int l, int r, int& sr, int& br, int pos)
{
    int val = nums[pos];
    sr = l - 1, br = r + 1;
    int i = l;
    while (i < br)
    {
        if (nums[i] < val)
            ::swap(nums[i++], nums[++sr]);
        else if (nums[i] == val)
            ++i;
        else
            ::swap(nums[i], nums[--br]);
    }
}

void Heapify(vector& nums, int heapSize, int i = 0)
{
    int left = 2 * i + 1, right = left + 1;
    while (left < heapSize)
    {
        int maxIndex = (right < heapSize && nums[right] > nums[left]) ? right : left;
        maxIndex = (nums[maxIndex] < nums[i]) ? i : maxIndex;
        if (i == maxIndex)
            return;
        ::swap(nums[i], nums[maxIndex]);
        i = maxIndex;
        left = 2 * i + 1;
        right = left + 1;
    }
}
void HeapSort(vector& nums)
{
    if (nums.size() <= 1)
        return;

    int heapSize = nums.size();
    for (int i = heapSize - 1; i >= 0; --i)
        Heapify(nums, heapSize, i);

    while (heapSize > 0)
    {
        ::swap(nums[0], nums[--heapSize]);
        Heapify(nums, heapSize);
    }
}

// 基数排序
int GetMaxDigit(const vector& nums)
{
    int maxNum = ::max_element(nums.begin(), nums.end());
    int res = 0;
    while (maxNum != 0)
    {
        maxNum /= 10;
        ++res;
    }
    return res;
}
int GetDigit(int num, int d)
{
    while (d > 1)
    {
        --d;
        num /= 10;
    }
    return num % 10;
}
void RadixSort(vector& nums)
{
    if (nums.size() <= 1)
        return;
    int d = GetMaxDigit(nums);
    vector> buckets(10, queue());

    for (int i = 0; i < d; ++i)
    {
        int index = 0;
        for (int j = 0; j < nums.size(); ++j)
            buckets[GetDigit(nums[j], i + 1)].push(nums[j]);
        for (int j = 0; j < 10; ++j)
        {
            while (!buckets[j].empty())
            {
                nums[index++] = buckets[j].front();
                buckets[j].pop();
            }
        }
    }
}

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNode dummyHead;
    ListNode* cur = &dummyHead, *p = list1, *q = list2;
    while (p != nullptr && q != nullptr)
    {
        if (p->val <= q->val)
        {
            cur->next = p;
            p = p->next;
        }
        else
        {
            cur->next = q;
            q = q->next;
        }
        cur = cur->next;
    }
    if (p != nullptr)
        cur->next = p;
    if (q != nullptr)
        cur->next = q;
    return dummyHead.next;
}

ListNode* partition(ListNode* head, int x) {
    if (head == nullptr)
        return nullptr;
    ListNode lessDummy,     // 存放小于x的链表 
    greaterDummy;       // 存放大于等于x的链表
    ListNode* p1 = &lessDummy, *p2 = &greaterDummy;
    ListNode* p = head;
    while (p != nullptr)
    {
        if (p->val < x)
        {
            p1->next = p;
            p1 = p1->next;
        }  
        else
        {
            p2->next = p;
            p2 = p2->next;
        }
        // 断开原链表的连接
        ListNode* temp = p->next;
        p->next = nullptr;
        p = temp;
    }
    p1->next = greaterDummy.next;
    return lessDummy.next;
}

ListNode* removeNthFromEnd(ListNode* head, int n) {
    if (head == nullptr || n <= 0)
        return head;
    ListNode* fast = head, *slow = head;
    int count = 0;
    while (count < n)
    {
        ++count;
        fast = fast->next;
    }
    if (fast == nullptr)    // 倒数第n个结点
    {
        ListNode* res = head->next;
        delete head;
        head = nullptr;
        return res;
    }
    while (fast->next != nullptr)
    {
        fast = fast->next;
        slow = slow->next;
    }
    ListNode* pNext= slow->next;
    slow->next = pNext->next;
    delete pNext;
    pNext = nullptr;

    return head;
}

ListNode* middleNode(ListNode* head) {
    if (head == nullptr)
        return nullptr;
    if (head->next == nullptr)
        return head;
    ListNode* fast = head, *slow = head;
    while (fast != nullptr && fast->next != nullptr)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

ListNode *detectCycle(ListNode *head) {
    if (head == nullptr || head->next == nullptr)
        return nullptr;

    ListNode* fast = head, *slow = head;
    do
    {
        if (fast == nullptr || fast->next == nullptr)
            return nullptr;
        fast = fast->next->next;
        slow = slow->next;
    } while (fast != slow);

    slow = head;
    while (slow != fast)
    {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

// 1. 哈希表法
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    unordered_set record;
    while (headA != nullptr)
    {
        record.insert(headA);
        headA = headA->next;
    }
    while (headB != nullptr)
    {
        if (record.count(headB) != 0)
            return headB;
        headB = headB->next;
    }
    return nullptr;
}

// 2. 双指针法
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    if (headA == nullptr || headB == nullptr)
        return nullptr;
    ListNode* p = headA, *q = headB;
    int lenA = 0, lenB = 0;
    while (p->next != nullptr)
    {
        p = p->next;
        ++lenA;
    }
    while (q->next != nullptr)
    {
        q = q->next;
        ++lenB;
    }

    // 无相交
    if (p != q) 
        return nullptr;

    int delta = abs(lenA - lenB);
    p = (lenA > lenB) ? headA : headB;
    q = (p == headA) ? headB : headA;

    // 长的那根链表先走
    while (delta > 0)
    {
        --delta;
        p = p->next;
    }
    // 然后再一起走
    while (p != q)
    {
        p = p->next;
        q = q->next;
    }
    return p;
}

// 方法一：三指针法
ListNode* reverseList(ListNode* head) {
    if (head == nullptr)
        return nullptr;
    ListNode* pPre = head, *pCur = head->next, *pNext;
    pPre->next = nullptr;
    while (pCur != nullptr)
    {
        pNext = pCur->next;
        pCur->next = pPre;
        pPre = pCur;
        pCur = pNext;
    }
    return pPre;
}

// 方法二：头插法
ListNode* reverseList(ListNode* head) {
    if (head == nullptr)
        return nullptr;

    ListNode* tail = head;
    while (tail->next != nullptr)
        tail = tail->next;

    ListNode* p = head, *pNext;
    while (p != tail)
    {
        pNext = p->next;
        p->next = tail->next;
        tail->next = p;
        p = pNext;
    }

    return tail;
}

// 方法三：递归
ListNode* reverseList(ListNode* head) {
    if (head == nullptr || head->next == nullptr)
        return head;

    ListNode* nextList = reverseList(head->next);
    head->next->next = head;
    head->next = nullptr;
    return nextList;
}

/** 复杂链表结构定义如下：
*   class Node {
*   public:
*       int val;
*       Node* next;
*       Node* random;
*    
*       Node(int _val) {
*           val = _val;
*           next = NULL;
*           random = NULL;
*       }
* };
*
*/

// 方法一：哈希表法     时间复杂度：O(n)  空间复杂度：O(n)
Node* copyRandomList(Node* head) {
    if (head == nullptr)
        return nullptr;
    unordered_map record;
    Node* cur = head;

    // 构建原链表结点与拷贝链表结点的对应关系
    while (cur != nullptr)
    {
        Node* copyNode = new Node(cur->val);
        record.insert(make_pair(cur, copyNode));
        cur = cur->next;
    }

    // 连接rand和next
    cur = head;
    while (cur != nullptr)
    {
        record[cur]->random = record[cur->random];
        record[cur]->next = record[cur->next];
        cur = cur->next;
    }

    return record[head];
}

// 方法二：链表关系映射（利用链表位置关系以代替哈希表）   时间复杂度：O(n)  空间复杂度：O(1)
Node* copyRandomList(Node* head) {
    if (head == nullptr)
        return nullptr;
    Node* cur = head;

    // 创建拷贝结点并连接在被拷贝的结点后   1 -> 1' -> 2' -> 2' -> ...
    while (cur != nullptr)
    {
        Node* pNext = cur->next;
        Node* copyNode = new Node(cur->val);
        copyNode->next = cur->next;
        cur->next = copyNode;
        cur = pNext;
    }

    // 构建rand关系
    cur = head;
    while (cur != nullptr)
    {
        Node* copyNode = cur->next;
        copyNode->random = (cur->random == nullptr) ? nullptr : cur->random->next;
        cur = cur->next->next;
    }

    // 构建next
    cur = head;
    Node* res = head->next;  // 保存结果，因为原链表在循环中会被恢复，不再指向copyNode
    while (cur != nullptr)
    {
        Node* pNext = cur->next->next;
        Node* copyNode = cur->next;
        copyNode->next = (pNext == nullptr) ? nullptr : pNext->next;
        cur->next = pNext;  // 恢复原链表
        cur = pNext;
    }

    return res;
}

int removeDuplicates(vector& nums) {
    if (nums.size() <= 1)
        return nums.size();
    int slow = 0, fast = 1;
    int len = nums.size();
    int k = 0;
    while (fast < len)
    {
        if (nums[slow] != nums[fast])
        {
            nums[k++] = nums[slow];
            slow = fast;
        }
        ++fast;
    }
    nums[k++] = nums[slow];
    return k;
}

void moveZeroes(vector& nums) {
    if (nums.size() == 0)
        return;
    int fast = 0, slow = 0;
    int len = nums.size();
    while (fast < len)
    {
        if (nums[fast] != 0)
            nums[slow++] = nums[fast];
        ++fast;
    }
    while (slow < len)
        nums[slow++] = 0;
}

vector exchange(vector& nums) {
    if (nums.size() <= 1)
        return nums;
    int oddRange = -1, i = 0;
    int len = nums.size();
    while (i < len)
    {
        if ((nums[i] & 0x1) == 1)   // 奇数
            ::swap(nums[i++], nums[++oddRange]);
        else  // 偶数
            ++i;
    }
    return nums;
}

vector twoSum(vector& numbers, int target) {
    int left = 0, right = numbers.size() - 1;
    while (left < right)
    {
        if (numbers[left] + numbers[right] < target)
            ++left;
        else if (numbers[left] + numbers[right] > target)
            --right;
        else
            return vector{left + 1, right + 1};
    }
    return vector{0, 0};
}

string longestPalindrome(string s) {
    string res;
    for (int i = 0; i < s.size(); ++i)
    {
        // 奇数情况
        string p1 = Palindrome(s, i, i);
        // 偶数情况
        string p2 = Palindrome(s, i, i + 1);
        // 取较大者
        res = res.size() > p1.size() ? res : p1;
        res = res.size() > p2.size() ? res : p2;
    }
    return res;
}

string Palindrome(string s, int l, int r)   // O(n) <=> O(1)
{
    while (l >= 0 && r < s.size())
    {
        if (s[l] == s[r])
        {
            --l;
            ++r;
        }
        else
            break;
    }
    return string(s.begin() + l + 1, s.begin() + r);
}

string replaceSpace(string s) {
    int originSize = s.size();
    int spaceCount = 0;
    for (const auto& ch : s)
    {
        if (ch == ' ')
            ++spaceCount;
    }
    int newSize = originSize + 2 * spaceCount;
    s.resize(newSize);
    int i = originSize - 1, j = newSize - 1;
    while (i >= 0)
    {
        if (s[i] == ' ')
        {
            s[j--] = '0';
            s[j--] = '2';
            s[j--] = '%';
            --i;
        }
        else
            s[j--] = s[i--];
    }

    return s;
}

// First visit --- PreOrder

Traverse(cur->lchild);

// Second visit --- InOrder

Traverse(cur->rchild);

// Third visit --- PostOrder

struct Info
{
  // data...  
};

Info Process(Node* root)
{
    // base-case
    /* if () {} */
    
    Info lData = Process(root->lchild);  // 左子树要信息
    Info rData = Process(root->rchild);  // 右子树要信息
    
    // 利用左子树信息和右子树信息合成当前信息
    Info curData = /* ... */;
    
    // 返回当前信息
    return curData;
}

bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
    // base-case
    if (pRoot1 == nullptr || pRoot2 == nullptr)
        return false;

    bool res = false;
    if (pRoot1->val == pRoot2->val)
        res = DoesTree1HaveTree2(pRoot1, pRoot2);    // 根节点匹配，开始查看子树
    if (res == false)
        res = HasSubtree(pRoot1->left, pRoot2);  // 匹配失败，查看左子树
    if (res == false)
        res = HasSubtree(pRoot1->right, pRoot2); // 又失败，查看右子树

    return res;
}

bool DoesTree1HaveTree2(TreeNode* pRoot1, TreeNode* pRoot2)
{
    if (pRoot2 == nullptr)
        return true;
    if (pRoot1 == nullptr)
        return false;
    if (pRoot1->val != pRoot2->val)
        return false;

    return DoesTree1HaveTree2(pRoot1->left, pRoot2->left) 
        && DoesTree1HaveTree2(pRoot1->right, pRoot2->right);
}

bool verifyPostorder(vector& postorder) {
    if (postorder.size() == 0)
        return true;
    return verifyPostorder(postorder, 0, postorder.size() - 1);
}

bool verifyPostorder(vector& postorder, int l, int r)
{
    int i = l;
    int tar = postorder[r];
    for (; i < r && postorder[i] < tar; ++i)
        ;
    for (int j = i; j < r; ++j)
    {
        if (postorder[j] < tar)
            return false;
    }

    bool leftRes = true;
    if (i > l)
        leftRes = verifyPostorder(postorder, l, i - 1);

    bool rightRes = true;
    if (i < r)
        rightRes = verifyPostorder(postorder, i, r - 1);

    return leftRes && rightRes;
}

bool isBalanced(TreeNode* root) {
    return Process(root).isBT;
}

struct RType
{
    int height;
    bool isBT;
    RType(int height, bool isBT) : height(height), isBT(isBT) {}
};

RType Process(TreeNode* root)
{
    if (root == nullptr)
        return RType(0, true);

    // 左树信息
    RType lData = Process(root->left);
    // 右树信息
    RType rData = Process(root->right);

    // 合成当前信息
    int height = 1 + ::max(lData.height, rData.height);
    bool isBT = lData.isBT && rData.isBT && (abs(lData.height - rData.height) <= 1);

    return RType(height, isBT);
}

TreeNode* Convert(TreeNode* pRootOfTree) {
    TreeNode* pre = nullptr, *head = nullptr;
    Process(pRootOfTree, pre, head);
    return head;
}

void Process(TreeNode* cur, TreeNode* &pre, TreeNode* &head)
{
    if (cur == nullptr)
        return;

    Process(cur->left, pre, head);

    if (head == nullptr && cur->left == nullptr) // head-case
    {
        head = cur;
        pre = cur;
    }
    else    // other-case
    {
        cur->left = pre;
        pre->right = cur;
        pre = cur;
    }


    Process(cur->right, pre, head);
}

// pre-order
vector preorderTraversal(TreeNode* root) {
    if (root == nullptr)
        return vector();
    stack s;
    s.push(root);
    vector res;

    TreeNode* cur;
    while (!s.empty())
    {
        cur = s.top();
        s.pop();
        res.push_back(cur->val);
        if (cur->right)
            s.push(cur->right);
        if (cur->left)
            s.push(cur->left);
    }

    return res;
}

// post-order
vector postorderTraversal(TreeNode* root) {
    if (root == nullptr)
        return vector();
    stack s1, s2;
    s1.push(root);
    vector res;

    TreeNode* cur;
    while (!s1.empty())
    {
        cur = s1.top();
        s1.pop();
        s2.push(cur);
        if (cur->left)
            s1.push(cur->left);
        if (cur->right)
            s1.push(cur->right);
    }

    while (!s2.empty())
    {
        cur = s2.top();
        s2.pop();
        res.push_back(cur->val);
    }

    return res;
}

// in-order
vector inorderTraversal(TreeNode* root) {
    stack s;
    vector res;
    while (root != nullptr || !s.empty())
    {
        if (root != nullptr)
        {
            s.push(root);
            root = root->left;
        }
        else
        {
            root = s.top();
            s.pop();
            res.push_back(root->val);
            root = root->right;
        }
    }
    return res;
}

process() {
    // base-case
    ...
    
    // 处理当前信息
    ...
    
    // 处理后续信息
    process() ...
    
    // 回退状态至当前状态
    ...
}

vector> res;    

vector> subsets(vector& nums) {
    res.push_back(vector());   // 空集情况
    for (int i = 0; i < nums.size(); ++i)
    {
        vector temp;
        process(nums, i, temp);
    }
    return res;
}

void process(vector& nums, int index, vector& temp)
{
    // 处理当前信息
    temp.push_back(nums[index]);
    res.push_back(temp);

    for (int i = index + 1; i < nums.size(); ++i)    // base-case
    {
        // 处理后续信息
        process(nums, i, temp);
        // 恢复状态
        temp.pop_back();
    }
}

vector> res;

vector> permuteUnique(vector& nums) {
    ::sort(nums.begin(), nums.end());
    vector record(nums.size(), false);
    vector temp;
    process(nums, temp, record);
    return res;
}

void process(vector& nums, vector& temp, vector& record)
{
    if (temp.size() == nums.size())
    {
        res.push_back(temp);
        return;
    }

    for (int i = 0; i < nums.size(); ++i)
    {
        if (record[i])
            continue;
        if (i > 0 && nums[i] == nums[i - 1] && !record[i - 1])   // 剪枝逻辑
            continue;
        temp.push_back(nums[i]);
        record[i] = true;
        process(nums, temp, record);
        record[i] = false;
        temp.pop_back();
    }
}

int process(int m, int n, int x, int y)
{
    // base-case
    if (x > m || y > n)
        return 0;
    if ((x == m) && (y == n))
        return 1;

    // 可能性罗列
    int p1 = process(m, n, x + 1, y);
    int p2 = process(m, n, x, y + 1);

    // 返回当前结果
    return p1 + p2;
}

int uniquePaths(int m, int n) {
    vector> record(m + 1, vector(n + 1, -1));
    return process(m, n, 1, 1, record);
}


int process(int m, int n, int x, int y, vector>& record)
{
    // base-case
    if (x > m || y > n)
        return 0;
    else if ((x == m) && (y == n))
        record[x][y] = 1;
    else
    {
        // 已知record的数据，直接返回
        if (record[x][y] != -1)
            return record[x][y];

        // 可能性罗列
        int p1 = process(m, n, x + 1, y, record);
        int p2 = process(m, n, x, y + 1, record);
        record[x][y] = p1 + p2;
    }

    // 返回当前结果
    return record[x][y];
}

int uniquePaths(int m, int n) {
    return dp(m, n);
}

int dp(int m, int n)
{
    // 建立变量为x和y的dp表
    vector> dpTable(m + 2, vector(n + 2, 0));
    // 自底向上构建结果
    for (int x = m; x > 0; --x)
    {
        for (int y = n; y > 0; --y)
        {
            // base-case
            if (x == m && y == n)
                dpTable[m][n] = 1;
            else
            {
                int p1 = dpTable[x + 1][y];
                int p2 = dpTable[x][y + 1];
                dpTable[x][y] = p1 + p2;
            }
        }
    }

    return dpTable[1][1];
}