顺时针打印链表

void Matrix(vector<vector<int>>& num, int x1, int y1, int x2, int y2)
{
    int n = 1;
    while (x1 <= x2 && y1 <= y2)
    {
        int i = x1, j = y1;
        for (int j = y1; j <= y2; j++)
        {
            num[x1][j] = n++; //right
        }
        if (x1 < x2)
        {
            for (int i = x1 + 1; i <= x2; i++)
            {
                num[i][y2] = n++; //down
            }
        }
        if (x1 < x2 && y1 < y2)
        {
            for (int j = y2 - 1; j >= y1; j--)
            {
                num[x2][j] = n++; //left
            }
        }
        if (x2 - x1 > 1 && y1 < y2)
        {
            for (int i = x2 - 1; i > x1; i--)
            {
                num[i][y1] = n++; //up
            }
        }
        x1++, y1++, x2--, y2--;
    }
}

包含min函数的栈

template<class T> class StackWithMin
{
public:
    void push(T t)
    {
        m_data.push(t);
        if (m_min.empty() || t < m_min.top())
        {
            m_min.push(t);
        }
        else
        {
            m_min.push(m_min.top());
        }
    }

    void pop()
    {
        assert(m_data.size() > 0 && m_min.size() > 0);
        m_data.pop();
        m_min.pop();
    }

    T top()
    {
        assert(m_data.size() > 0 && m_min.size() > 0);
        return m_data.top();
    }

    T min()
    {
        assert(m_data.size() > 0 && m_min.size() > 0);
        return m_min.top();
    }

    bool empty()
    {
        return m_data.empty();
    }
private:
    stack<T> m_data;
    stack<T> m_min;
};

栈的压入弹出序列

bool isPopOrder(int num1[], int num2[], int len)
{
    int *p = num1;
    int *q = num2;
    if (p != NULL && q != NULL && len > 0)
    {
        stack<int> s;
        while (q - num2 < len)
        {
            while (s.empty() || s.top() != *q)
            {
                if (p - num1 == len)
                {
                    break;
                }
                s.push(*p++);
            }
            if (s.top() != *q)
            {
                break;
            }
            s.pop();
            q++;
        }
        if (s.empty() && q - num2 == len)
        {
            return true;
        }
    }

    return false;
}

二叉搜索树的后序遍历序列

bool verifyBST(int num[], int len)
{
    if (num == NULL || len <= 0)
    {
        return false;
    }
    int i = 0;
    while (i < len - 1)
    {
        if (num[i] < num[len - 1])
        {
            i++;
        }
        else
        {
            break;
        }
    }
    int j = i;
    while (j < len - 1)
    {
        if (num[j] > num[len - 1])
        {
            j++;
        }
        else
        {
            return false;
        }
    }

    bool left = true;
    if (i > 0)
    {
        left = verifyBST(num, i);
    }
    bool right = true;
    if (i < len - 1)
    {
        right = verifyBST(num + i, len - i - 1);
    }

    return left && right;
}

二叉树中和为某一值的路径

void findPath(TreeNode *root, int expectedSum, vector<int>& path, int currentSum)
{
    if (root == NULL)
    {
        return;
    }
    path.push_back(root->val);
    currentSum += root->val;
    bool isLeaf = root->left == NULL && root->right == NULL;
    if (expectedSum = currentSum && isLeaf)
    {
        for (auto it = path.begin(); it != path.end(); it++)
        {
            cout<<*it<<" ";
        }
        cout<<endl;
    }

    findPath(root->left, expectedSum, path, currentSum);
    findPath(root->right, expectedSum, path, currentSum);
    currentSum -= root->val;
    path.pop_back();
}

void findPath(TreeNode *root, int expectedSum)
{
    if (root == NULL)
    {
        return;
    }
    vector<int> path;
    int currentSum = 0;
    findPath(root, expectedSum, path, currentSum);
}

复杂链表的复制

ComplexListNode* copyList(ComplexListNode *head)
{
    if (head == NULL)
    {
        return NULL;
    }
    //copy list
    ComplexListNode *p = head;
    while (p != NULL)
    {
        ComplexListNode *p2 = new ComplexListNode(p->val);
        p2->next = p->next;
        p->next = p2;
        p = p2->next;
    }

    //deal with the sibling
    p = head;
    while (p != NULL)
    {
        ComplexListNode *p2 = p->next;
        if (p->sib != NULL)
        {
            p2->sib = p->sib->next;
        }
        p = p2->next;
    }

    //separate the list
    ComplexListNode *newhead = head->next;
    ComplexListNode *pre1 = head;
    ComplexListNode *pre2 = newhead;
    p = newhead->next;
    while (p != NULL)
    {
        pre1->next = p;
        pre1 = p;
        pre2->next = p->next;
        pre2 = p->next;
        p = p->next->next;
    }
    pre1->next = NULL;

    return newhead;
}

二义搜索树与双向链表

void convertHelp(TreeNode *root, TreeNode *&last)
{
    if (root == NULL)
    {
        return;
    }
    TreeNode *cur = root;
    if (cur->left != NULL)
    {
        convertHelp(root->left, last);
    }
    cur->left = last;
    if (last != NULL)
    {
        last->right = cur;
    }
    last = cur;

    if (cur->right != NULL)
    {
        convertHelp(cur->right, last);
    }
}

TreeNode* convert(TreeNode *root)
{
    TreeNode *last = NULL;
    convertHelp(root, last);

    TreeNode *p = last;
    while (p != NULL &&p->left != NULL)
    {
        p = p->left;
    }

    return p;
}

字符串的排列

void perHelp(char *str1, char *str2) 
{
    if (*str2 == '\0')
    {
        cout<<str1<<endl;
    }
    for (char *p = str2; *p != '\0'; p++)
    {
        swap(*p, *str1);
        perHelp(str1, str2 + 1);
        swap(*p, *str1);
    }
}

全排列

int n[10] = {0,1,2,3,4,5,6,7,8,9};

void permutation(int num[], bool flag[], int len, int pos)
{
    for (int i = 0; i < len; i++)
    {
        if (!flag[i])
        {
            num[pos] = n[i];
            flag[i] = true;
            if (pos == len - 1)
            {
                print(num, len);
            }
            else
            {
                permutation(num, flag, len, pos + 1);
            }
            flag[i] = false;
        }
    }
}

组合

/* 算法说明：从n个数中选m个数，可以分解为以下两步:
 * （1）首先从n个数中选取编号最大的数，然后在剩下的n-1个数中选取m-1个数，直到从n-(m-1)个数中选取1个数为止。
 * （2）从n个数中选取编号次小的一个数，继续执行第（1）步，直到当前可选编号最大的数为m。
 */

/* 求从a[n]中选取m个数的可能组合。数组a[n]表示候选集；b[m]用来存储当前组合中的某个元素，
 * 这里存储的是这个元素在a[]中的下标；常量M表示满足条件的一个组合中元素的个数，M=m，M只用来输出结果
 */
void combine(int a[], int b[], int n, int m, int M)
{
    for (int i = n; i >= m; i--)
    {
        b[m - 1] = a[i - 1];
        if (m > 1)
        {
            combine(a, b, i - 1, m - 1, M);
        }
        else
        {
            for (int j = M - 1; j >= 0; j--)
            {
                cout<<b[j]<<" ";
            }
            cout<<endl;
        }
    }
}