杂七杂八啊 || 剑指offer

時の経つのが速すぎ( ；´Д｀)
不知道每天要说多少句本打算……然而……
重新学日语 & 练吉他 & 学pytorch的安排刚定下就扑街……
赶快准备2号面字节跳动后端实习……

---

去南京

12月30日

---

从南京回来了，赶啊躺尸…………我爱傻白，我爱维泽嘻嘻
继续「剑指offer」

数值的整数次方

位运算，一轮一轮手动模拟一下就明白了。思路参考自牛客上的大佬
🌰1011B的1010B次方 = （1011）的（0010）次方 * （1011）的（1000）次方

    double Power(double base, int exp) {
        long long abs_exp = abs(exp);
        double res = 1.0;
        while(abs_exp) {
            if(abs_exp & 1) res *= base; // exp & 1  取exp最低位
            base *= base; 
            abs_exp >>= 1;
        }
        return exp < 0 ? 1/res : res;
    }

链表的倒数第k个结点

快慢指针，注意处理链表本身长度小于k的情况。

    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        int i = 0;
        ListNode* p = pListHead;
        while(p && i < (int)(k)) {
            p = p->next;
            i++;
        }
        if(i != k) return NULL;
        ListNode* q = pListHead;
        while(p) {
            p = p->next, q = q->next;
        }
        return q;
    }

链表反转

没有头结点，注意边界条件。

    ListNode* ReverseList(ListNode* pHead) {
        if(!pHead) return NULL;
        ListNode *p0 = NULL, *p1 = pHead, *p2 = pHead->next;
        while(p2) {
            p1->next = p0;
            p0 = p1;
            p1 = p2;
            p2 = p2->next;
        }
        p1->next = p0;
        return p1;
    }

合并两个排序的链表

手动模拟再写。写函数调试不方便😭，写的不顺真是气嗷。
搞一个dummy node，最后输出它的next会好写很多呀。

ListNode *Merge(ListNode *pHead1, ListNode *pHead2) {
    ListNode *newhead = new ListNode(-1); //dummy node
    ListNode *p0 = newhead, *p1 = pHead1, *p2 = pHead2;
    while (p1 && p2) {
        if (p1->val < p2->val) {
            p0->next = p1;
            p1 = p1->next;
        } else {
            p0->next = p2;
            p2 = p2->next;
        }
        p0 = p0->next;
    }
    if (p1) p0->next = p1;
    else p0->next = p2;
    return newhead->next;
}

⚠️树的子结构

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
这题是薄弱点QAQ，分析一下：

• 首先，若T2是T1的子结构，遍历T1，若出现val与T2根结点权值相同的结点，check以它为根的子树“上半部分”是否和T2相同（isT1_has_T2）。若不同，继续看它的左、右子树是否能包含T2。

• isT1_has_T2递归（边界注意空指针）

  • 若T2的每个结点都匹配了，r2空，return true
  • 若T2还未完全匹配，r1已经为空，return false
  • 以上，边界的空指针检查✅
  • 另一个边界：r1，r2的val不同，return false
  • 递归：左子树同否 && 右子树同否

bool isT1_has_T2(TreeNode *r1, TreeNode *r2) {
    if (!r2) return true;
    if (!r1) return false;
    if (r1->val != r2->val) return false;
    return isT1_has_T2(r1->left, r2->left) &&
           isT1_has_T2(r1->right, r2->right);
}

bool HasSubtree(TreeNode *pRoot1, TreeNode *pRoot2) {
    if (!pRoot1 || !pRoot2) return false;
    bool res = false;
    // DFS 
    if (pRoot1->val == pRoot2->val) {
        res = isT1_has_T2(pRoot1, pRoot2);
    }
    if (!res) res = HasSubtree(pRoot1->left, pRoot2);
    if (!res) res = HasSubtree(pRoot1->right, pRoot2);
    return res;
}