19 旋转图像 48

旋转图像 48

这道题我确是做过，纯纯考数学。
该死，已经忘记咋做了。
只能说，当时听完《代码随想录》只觉顿悟，没成想过了几天跟没见过似的。
这真的不怪代码随想录，因为它每道题都给一个思路，而我想我需要的是套路：通过刷一道题，就能会一类题。
1 2 3 -> 7 4 1
4 5 6 -> 8 5 2
7 8 9 -> 9 6 3
nums[i][j]去哪了？

第一行变成了最后一列
第一列变成了第一行
得到
nums[i][j] -> nums[j][n-1-i]

于是就想出
nums[i][j] -> nums[j][i] -> nums[j][n-1-i]

点击查看代码

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        //对角线翻转
        int n = matrix.size();
        for (int i = 0; i < n; ++i) {
            for (int j = i+1; j < n; ++j) 
                swap(matrix[i][j], matrix[j][i]);
        }
        //水平翻转
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n/2; ++j)
                swap(matrix[i][j], matrix[i][n-j-1]);
        }
    }
};

呵呵，一看题解就会，一自己做就废。
没关系，没关系，见多了做多了自然就知道咋做了。

240 搜索二维矩阵II

好的，也不会。。。。
2025-06-05 10:03:30 星期四
明天再见吧。

这道题已经做过了，

天哪，看一眼灵神的题解，突然意识到从右上角搜索感觉像是二叉搜索树！

相交链表，这样一道简单题我也做不出来了。原因是，循环条件写错了，我还一直没发现，正纳闷呢，怎么总是不对，我印象中就是这样的啊。

反转链表也不会写了？
好久没刷链表题了，不会写也挺正常的。

还好是有点印象的，反转链表不难。
接下来是回文链表。
我也有点印象。
这道题我记得思路是把链表反转一下，然后同时遍历两条链表，一个反转之前，一个反转之后，若遍历结束后值都相同，那说明便是回文链表。
只是我在想，遍历和反转都是O(n)，而且难道是要再构建一条反转的链表，空间复杂度不是O(n)吗？
是这样吗？
题目要求是O(1)空间复杂度啊。
我还有一种想法，就是先遍历，如果遍历一遍都没发现当前节点与下一个节点的值相同那肯定不是回文链表。
如果发现下个节点与当前节点相同，那可能是反转链表。
这样也不行，你怎么就能保证人家链表中没有相同元素呢？
对啊，关键是在找中间节点，然后对后半部分进行反转。

果然，这道题写着简单但是一点也不简单。
快慢指针寻找中间节点+反转

环形链表II
寻找环的入口。
嗯，我知道如何判断有环，但是咋找环的入口呢？

纯纯数学题。

21 合并两个有序数组的链表

下面是我的解法。

点击查看代码

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (list1 == nullptr)
            return list2;
        else if (list2 == nullptr)
            return list1;
        ListNode* dummyHead = (ListNode*)new ListNode(0, list2);
        ListNode* cur = list1;
        ListNode* p = dummyHead;
        while (cur) {
            while (p && p->next && cur->val >= p->next->val) {
                p = p->next;
            }
            ListNode* tmp1 = p->next;
            p->next = cur;
            ListNode* tmp2 = cur->next;
            cur->next = tmp1;
            p = cur;
            cur = tmp2;
        }
        return dummyHead->next;    
    }
};

时间复杂度: $O(n^{2})$

我也没有什么思路，就硬着头皮写，在纸上划划，划完再debug，总算自己写出来了。
然后再看题解，天哪，怎么能有人把代码写得这般优雅？？？

时间复杂度可以进一步优化成\(O(m+n)\)。