入门算法

2022-07-21 阅读量

汉诺塔问题

汉诺塔问题中，3个圆盘至少需要移动7次，移动n个圆盘至少需要操作 $2^n-1$ 次

分治实现

void hanoi(int num, int sou, int tar, int aux){
    static int i=1;
    if(num == 1){
        printf("第%d次：从%c移动至%c\n", i, sou, tar);
        i++;
    }
    else{
        // 将 num-1 个圆盘从起始柱移动到辅助柱上
        hanoi(num-1, sou, aux, tar);
        // 将起始柱上剩余的最后一个大圆盘移动到目标柱上
        printf("第%d次：从%c移动至%c\n", i, sou, tar);
        i++;
        // 辅助柱上的 num-1 圆盘移动到目标柱上
        hanoi(num-1, aux, tar, sou);
    }
}
int main(){
    hanoi(3, 'A', 'B', 'C'); // 以移动3个圆盘为例
}

链表问题

链表翻转【双指针】

/* 1.循环迭代实现 */
ListNode* reverseList(ListNode* head) {
    if(!head||!head->next) return head;
    
    auto a=head, b=head->next;
    while(b){
        auto c = b->next;
        b->next = a;
        a = b, b = c;
    }
    head->next = NULL;  // !
    return a;
}
/* 2.递归实现 */
ListNode* reverseList(ListNode* head) {
    if(!head||!head->next) return head;
    auto tail = reverseList(head->next);
    head->next->next = head;
    head->next = NULL;   // !
    return tail;
}

🍕 链表局部翻转（与上题对比【头插法】）

1.dummy; 2.头插法; 3.循环
【点我跳转>_<】

链表中的节点每k个一组翻转

链表尾到头逆序输出

/* 1.循环迭代实现 */
vector<int> printListReversingly(ListNode* head) {
    vector<int> res;
    while(head){
         /*跟我想的不太一样，这里存储链表的方式是没有头节点的，head即就有意义！*/
        res.insert(res.begin(), head->val);
        head=head->next;
    }
    return res;
}
/* 2.递归实现 */
vector<int> printListReversingly(ListNode* head) {
    if(!head) return {};
    auto res = printListReversingly(head->next);
    res.push_back(head->val);
    return res;
}

O(1)时间删除节点

采用一种覆盖的方式

删除重复节点

/* 把重复元素全部删掉 */
ListNode* deleteDuplication(ListNode* head) {
    auto dummy = new ListNode(-1);
    dummy->next = head;
    
    auto p=dummy;
    while(p->next){
        auto q = p->next;
        while(q && p->next->val==q->val) q = q->next;
        
        if(p->next->next==q) p=p->next;
        else p->next=q;
    }
    return dummy->next;
}

删除倒数第k个节点

ListNode* findKthToTail(ListNode* head, int k) {
    int n = 0;
    for(auto p = pListHead; p; p=p->next) n++;
    if(n<k) return nullptr;
    auto p=pListHead;
    for(int i=0; i<n-k; i++) p=p->next;
    return p;
}

🍤链表中环的入口

Key:

让$second$从相遇点回退$y$步
$first$：只可能在走第一圈时就碰到$second$
$second$：碰到$first$时：走了$2x+2y$；在$first$刚进环时：走了$2x$, 距离环入口$y$，距离$first$ $2y$
推导： $x+y=nc，c=2\pi r$

ListNode *entryNodeOfLoop(ListNode *head) {
    auto i = head, j = head;
    while(i && j){
        i = i->next;
        j = j->next;
        if(j) j=j->next;
        else break;
        
        if(i == j){
            i = head;
            while(i!=j) i = i->next, j = j->next;
            return i;
        }
    }
    return NULL;
}

合并链表

dummy
原题链接

找出两个链表的第一个公共节点

相遇：走过的距离 a+c+b = b+c+a
没有相遇：距离 a+b = b+a
类似追及相遇问题原题链接

二叉搜索树与双向链表

二叉树问题

二叉树的镜像

void mirror(TreeNode* root){
    if(!root) return;
    mirror(root->left);
    mirror(root->right);
    swap(root->left, root->right);
}

重建二叉树

map<int, int> hash;

TreeNode* dfs(vector<int>& preorder, vector<int>& inorder, int pl, int pr, int il, int ir){
    if(pl > pr) return NULL;
    
    TreeNode* root = new TreeNode(preorder[pl]);
    int k = hash[preorder[pl]] - il;
    root->left = dfs(preorder, inorder, pl+1, pl+k, il, il+k-1);
    root->right = dfs(preorder, inorder, pl+k+1, pr, il+k+1, ir);
    return root;
}

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    int len = preorder.size();
    if(!len) return NULL;
    
    for(int i=0; i<len; i++) hash[inorder[i]] = i;
    return dfs(preorder, inorder, 0, len-1, 0, len-1);
}