记录蛇形矩阵偏移量方法，四个不同方向右下左上，判断什么情况下矩阵遍历完，1.要么出界 2.要么走完

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int n = matrix.size(), m = matrix[0].size();
        int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
        vector<int> res;
        vector<vector<bool>> vis(n, vector<bool>(m));
        for (int i = 0, x = 0, y = 0, d = 0; i < n * m; i ++) {
            res.push_back(matrix[x][y]);
            vis[x][y] = true;
            int nx = x + dir[d][0], ny = y + dir[d][1];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m || vis[nx][ny]) {
                d = (d + 1) % 4;
                nx = x + dir[d][0], ny = y + dir[d][1];
            }
            x = nx, y = ny;
        }

        return res;
    }
};

desc： 给定 n 生成一个包含一到 n^2的矩阵， 按照螺旋矩阵的方式存储

解法：和螺旋矩阵 I 类似，通过偏移量构造

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n, 0));
        int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
       for (int x = 0, y = 0, cnt = 1, d = 0; cnt <= n * n; cnt ++) {
           res[x][y] = cnt;
           int nx = x + dir[d][0], ny = y + dir[d][1];
           if (nx < 0 || nx >= n || ny < 0 || ny >= n || res[nx][ny]) {
               d = (d + 1) % 4;
               nx = x + dir[d][0], ny = y + dir[d][1];
           }
           x = nx, y = ny;
       } 
        return res;
    }
};

desc：给定一个nxm的矩阵，和一个开始走的起点坐标，求螺旋方向走的坐标，并且可以出界， 如下图所示

class Solution {
public:
    vector<vector<int>> spiralMatrixIII(int n, int m, int x, int y) {
        vector<vector<int>> res;
        int tot = n * m;
        res.push_back({x, y});
        int d = 0;
        int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
        // k 循环表示模拟圆环的半径， 有一个规律1, 1, 2, 2, 3, 3...
        for (int k = 1; res.size() < tot; k ++) {
            // i 循环表示矩阵是按照每个半径会走两次
            for (int i = 0; i < 2 && res.size() < tot; i ++) {
                // j循环表示开始走半径为 k 的元素
                for (int j = 0; j < k && res.size() < tot; j ++) {
                        int nx = x + dir[d][0], ny = y + dir[d][1];
                        // 在矩阵内即可添加进去
                        if (nx >= 0 && nx < n && ny >= 0 && ny < m)
                            res.push_back({nx, ny});
                        x = nx, y = ny;
                }
                d = (d + 1) % 4;
            }
        }
        return res;
    }
};

desc: 给定链表从链表中构建一个蛇形矩阵，和 I、II 的构建方式一样

class Solution {
public:
    vector<vector<int>> spiralMatrix(int n, int m, ListNode* head) {
        vector<vector<int>> res(n, vector<int>(m, -1));
        int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
        int x = 0, y = 0, d = 0;
        for (auto p = head; p != nullptr; p=p->next) {
            res[x][y] = p->val;
            int nx = x + dir[d][0], ny = y + dir[d][1];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m || res[nx][ny] != -1) {
                d = (d + 1) % 4;
                nx = x + dir[d][0], ny = y + dir[d][1];
            }
            x = nx, y = ny;
        }
        return res;
    }
};

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-oay7AL1b-1662036839548)(/Users/liyan/Library/Application Support/typora-user-images/image-20220831102437989.png)]

链表快排基本思路

• 选定链表头基准元素
• 建立三个子链表left,mid,right
  • left存储比基准元素小的节点
  • mid 存储和基准元素相等的节点
  • right 存储比基准元素大的节点
• 递归的去排序第二个过程
  • 递归出口节点空或者链表只有一个节点
• 最后将 left 拼接 mid 拼接 right

/**
 * 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* getTail(ListNode* head) {
        while (head->next) head=head->next;
        return head;
    }
    ListNode* sortList(ListNode* head) {
        if (!head || !head->next) return head;

        auto left = new ListNode(-1), mid = new ListNode(-1), right = new ListNode(-1);
        auto ltail = left, rtail = right, mtail = mid;
        // int cnt = 0;
        // int val = head->val;
        // for (auto p = head; p; p = p->next) {
        //     cnt ++;
        // }
        // int n = cnt;
        // for (auto p = head; p; p = p->next) {
        //     cnt --;
        //     if (cnt == n / 2) {
        //         val = p->val;
        //         break;
        //     }
            
        // }
        int val = head->val;
        for (auto p = head; p; p=p->next) {
            if (p->val < val) ltail = ltail->next = p;
            else if (p->val == val) mtail = mtail->next = p;
            else rtail = rtail->next = p;
        }
        ltail->next = mtail->next = rtail->next = nullptr;
        left->next = sortList(left->next);
        right->next = sortList(right->next);

        getTail(left)->next = mid->next;
        getTail(left)->next = right->next;
        auto p = left->next;
        delete left;
        delete mid;
        delete right;
        return p;
    }
};

时间复杂度O(nlogn)、空间复杂度O(logn), 疑问：为什么过不了leetcode 原题

可以将基准值随机选取而不是选取头尾节点

插入排序 算法的步骤:

1. 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
2. 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
3. 重复直到所有输入数据插入完为止。

为了方便处理边界情况，我们建立虚拟头结点，指向原链表头部。
然后扫描原链表，对于每个节点 vv，从前往后扫描结果链表，找到第一个比 vv 大的节点 uu，将 vv 插入到 uu 之前。

时间复杂度分析：一共遍历 nn 个节点，对于每个节点找合适位置时，最多需要遍历 O(n)O(n) 次，所以总时间复杂度是 O(n2)O(n2)。

/**
 * 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* insertionSortList(ListNode* head) {
        ListNode* dummy = new ListNode(-1);
        while (head) { // head 指向当前待插入的节点
            ListNode* next = head->next;   // next指向下一个循环待插入的节点
            ListNode* p = dummy; // dummy存的是待插入的链表
            while (p->next && p->next->val <= head->val) p = p->next; //找到插入 head 的位置 p

            head->next = p->next; // 将head 插入 p后面
            p->next = head; // 

            head = next; // head更新为下一个循环要插入的节点

        }
        return dummy->next;

    }
};

选择排序过程