模拟问题(中)

一、顺时针旋转矩阵

解法:倒置翻转

矩阵转置是将上三角矩阵元素与下三角矩阵元素依据对角线位置对称互换，且该过程是可逆的。
这道题可能需要将矩阵画出来，观察一下旋转后的规律：

乍一看没有啥规律，但是旋转后的第一行是不是与原矩阵的第一列很像，就是其翻转之后的结果，那我们可以再尝试画出一个顺时针90度旋转后每行翻转的矩阵：

然后我们会惊喜得发现，这就是互为转置的两个矩阵。因为转置的可逆性，只要过程逆转，就可以得到顺时针旋转90度后的矩阵了。

• 遍历矩阵的下三角矩阵，将其与上三角矩阵对应的位置互换，其实就是数组下标交换后的互换。
• 遍历矩阵每一行，将每一行看成一个数组使用reverse函数翻转。

class Solution {
    
public:
    vector<vector<int> > rotateMatrix(vector<vector<int> > mat, int n) {
    
        //矩阵转置
        for(int i = 0; i < n; i++) 
            for(int j = 0; j < i; j++)
                //交换上三角与下三角对应的元素
                swap(mat[i][j], mat[j][i]);
        //每行翻转
        for(int i = 0; i < n; i++) 
            reverse(mat[i].begin(), mat[i].end());
        return mat;
    }
};

时间复杂度：O(n^2) 转置需要遍历矩阵，逐行翻转也是O(n^2)
空间复杂度：O(1)，常数级变量，没有使用额外辅助空间

解法二:辅助数组

出整体的规律，并使用一个辅助数组来存储新的矩阵。

class Solution {
    
public:
  vector<vector<int> > rotateMatrix(vector<vector<int> > mat, int n) {
    
      // write code here
      vector<vector<int>> ans(n,vector<int>(n));
      for(int i=0;i<n;i++){
    
          for(int j=0;j<n;j++){
    
              ans[j][n-i-1]=mat[i][j];
          }
      }
      return ans;
  }
};

时间复杂度：O(n^2) ，矩阵元素数量n^2.
空间复杂度：O(n^2)，用一个矩阵的空间进行存储。

二、设计LRU缓存结构

解法:哈希表+双向链表

插入与访问值都是O(1)O(1)O(1)，没有任何一种数据结构可以直接做到。

于是我们可以想到数据结构的组合：访问O(1很容易想到了哈希表；插入O(1)的数据结构有很多，但是如果访问到了这个地方再选择插入，且超出长度要在O(1)之内删除，我们可以想到用链表，可以用哈希表的key值对应链表的节点，完成直接访问。但是我们还需要把每次访问的key值节点加入链表头，同时删掉链表尾，所以选择双向链表，便于删除与移动。

于是我们的方法就是哈希表+双向链表。

• 构建一个双向链表的类，记录key值与val值，同时一前一后两个指针。用哈希表存储key值和链表节点，这样我们可以根据key值在哈希表中直接锁定链表节点，从而实现在链表中直接访问，能够做到O(1))时间访问链表任意节点。

    //设置双向链表结构
    class Node{
     
        int key;
        int val;
        Node pre;
        Node next;
        //初始化
        public Node(int key, int val) {
    
            this.key = key;
            this.val = val;
            this.pre = null;
            this.next = null;
        }
    }

• 设置全局变量，记录双向链表的头、尾及LRU剩余的大小，并全部初始化，首尾相互连接好。

//构建初始化连接
//链表剩余大小
this.size = k;
this.head.next = this.tail;
this.tail.pre = this.head;

• 遍历函数的操作数组，检查第一个元素判断是属于set操作还是get操作。
• 如果是set操作，即将key值与val值加入链表，我们先检查链表中是否有这个key值，可以通过哈希表检查出，如果有直接通过哈希表访问链表的相应节点，修改val值，并将访问过的节点移到表头；如果没有则需要新建节点加到表头，同时哈希表中增加相应key值（当然，还需要检查链表长度还有无剩余，若是没有剩余则需要删去链表尾）。

//没有见过这个key，新值加入
if(!mp.containsKey(key)){
     
    Node node = new Node(key, val);
    mp.put(key, node);
    //超出大小，移除最后一个
    if(size <= 0) 
        removeLast();
    //大小还有剩余
    else 
        //大小减1
        size--; 
    //加到链表头
    insertFirst(node); 
}
//哈希表中已经有了，即链表里也已经有了
else{
      
    mp.get(key).val = val;
    //访问过后，移到表头
    moveToHead(mp.get(key)); 
}

• 不管是新节点，还是访问过的节点都需要加到表头，若是访问过的，需要断开原来的连接，再插入表头head的后面。

//移到表头函数
void moveToHead(Node node){
     
    //已经到了表头
    if(node.pre == head)  
        return;
    //将节点断开，取出来
    node.pre.next = node.next;
    node.next.pre = node.pre;
    //插入第一个前面
    insertFirst(node);
}

• 删除链表尾需要断掉尾节点前的连接，同时哈希表中去掉这个key值。

void removeLast(){
     
    //哈希表去掉key
    mp.remove(tail.pre.key);
    //断连该节点
    tail.pre.pre.next = tail; 
    tail.pre = tail.pre.pre;
}

• 如果是get操作，检验哈希表中有无这个key值，如果没有说明链表中也没有，返回-1，否则可以根据哈希表直接锁定链表中的位置进行访问，然后重复第五步，访问过的节点加入表头。

if(mp.containsKey(key)){
    
    Node node = mp.get(key);
    res = node.val;
    moveToHead(node);
}

//双向链表
struct Node{
     
    int key;
    int val;
    Node* pre;
    Node* next;
    //初始化
    Nodke(int k, int v): key(k), val(v), pre(NULL), next(NULL){
    }; 
};

class Solution {
    
public:
    int size = 0;
    //双向链表头尾
    Node* head = NULL; 
    Node* tail = NULL;
    //哈希表记录key值
    unordered_map<int, Node*> mp;

    vector<int> LRU(vector<vector<int> >& operators, int k) {
    
        vector<int> res;
        //构建初始化连接
        //链表剩余大小
        size = k; 
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head->next = tail;
        tail->pre = head;
        //操作数组为空
        if(operators.size() == 0) 
            return res;
        //遍历所有操作
        for(int i = 0; i < operators.size(); i++){
     
            auto op = operators[i];
            if(op[0] == 1) 
                //set操作
                set(op[1], op[2]);
            else if(op[0] == 2) 
                //get操作
                res.push_back(get(op[1]));
        }
        return res;
    }

    //插入函数
    void set(int key, int val){
     
        //没有见过这个key，新值加入
        if(mp.find(key) == mp.end()){
     
            Node* node = new Node(key, val);
            mp[key] = node;
            //超出大小，移除最后一个
            if(size <= 0) 
                removeLast();
            //大小还有剩余
            else 
                //大小减1
                size--; 
            //加到链表头
            insertFirst(node); 
        }
        //哈希表中已经有了，即链表里也已经有了
        else{
      
            mp[key]->val = val;
            //访问过后，移到表头
            moveToHead(mp[key]); 
        }
    }

    //获取数据函数
    int get(int key){
     
        //找不到返回-1
        int res = -1; 
        //哈希表中找到
        if(mp.find(key) != mp.end()){
     
            //获取
            res = mp[key]->val;
            //访问过后移到表头
            moveToHead(mp[key]); 
        }
        return res;
    }
    
    //移到表头函数
    void moveToHead(Node* node){
     
        //已经到了表头
        if(node->pre == head)  
            return;
        //将节点断开，取出来
        node->pre->next = node->next;
        node->next->pre = node->pre;
        //插入第一个前面
        insertFirst(node);
    }
    
    //将节点插入表头函数
    void insertFirst(Node* node){
     
        node->pre = head;
        node->next = head->next;
        head->next->pre = node;
        head->next = node;
    }
    
    //删去表尾函数，最近最少使用
    void removeLast(){
     
        //哈希表去掉key
        mp.erase(tail->pre->key);
        //断连该节点
        tail->pre->pre->next = tail; 
        tail->pre = tail->pre->pre;
    }
};

时间复杂度：O(n)，其中n为操作数组大小，map为哈希表，每次插入的复杂度都是O(1)
空间复杂度：O(k)，链表和哈希表都是O(k)的辅助空间