date: 2020/01/02


链表结构定义

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};


206反转链表(简单)

https://leetcode-cn.com/problems/reverse-linked-list/

ListNode* reverseList(ListNode* head) {
    ListNode *last = NULL, *node = head, *next = head;
    for(; node != NULL; node = next){
        next = node->next;
        node->next = last;
        last = node;
    }

    return last;
}


024两两交换链表中的节点(中等)

【206的升级版】

https://leetcode-cn.com/problems/swap-nodes-in-pairs/

ListNode* swapPairs(ListNode* head) {
    ListNode *node1, *node2;
    ListNode *last = NULL, *next = head;

    while((node1=next) != NULL && (node2=next->next) != NULL){
        next = node2->next;
        node2->next = node1;
        node1->next = next;

        if(last == NULL)
            head = node2;
        else
            last->next = node2;
        last = node1;
    }

    return head;
}


025K个一组翻转链表(困难)

【24的升级版】

https://leetcode-cn.com/problems/reverse-nodes-in-k-group

ListNode* reverseKGroup(ListNode* head, int k) {
    ListNode *last = NULL, *ptr;
    vector<ListNode*> window;

    for(ListNode *ptr = head; ptr != NULL; ){
        window.push_back(ptr);
        ptr = ptr->next;  // 不在for上移动指针,是因为本次循环结束后
                          //    window[k-1]->next == window[k-2]
        if(window.size() == k){
            // 处理上一个group到这一个group的连接
            if(last == NULL)    //  第一个group,需要改变head
                head = window[k-1];
            else    // 非第一个group
                last->next = window[k-1];
            // 处理group内部的连接
            for(int i = k-1; i > 0; i--)
                window[i]->next = window[i-1];
            // 暂存尾部节点,同时必须把next指向下一个group的开头
            //   否则,当下一个group不完整时,就会出现问题
            last = window[0];
            last->next = ptr;
            // 清空记录group的window
            window.clear();
        }
    }
    return head;
}


141环形链表(简单)

https://leetcode-cn.com/problems/linked-list-cycle/

bool hasCycle(ListNode *head) {
    unordered_set<ListNode *> visited;
    for(ListNode *node = head; node != NULL; node = node->next){
        if(visited.find(node) == visited.end()){
            visited.insert(node);
        }else{
            return true;
        }
    }
    return false;
}


image.png

bool hasCycle(ListNode *head) {
    ListNode *fast = head, *slow = head;
    while(fast != NULL && fast->next != NULL){
        slow = slow->next;
        fast = fast->next->next;

        if(slow == fast)
            return true;
    }
    return false;
}


142环形链表-找到入口节点(中等,141的升级版)

https://leetcode-cn.com/problems/linked-list-cycle-ii/submissions/

image.png

image.png

image.png

image.png


ListNode *detectCycle(ListNode *head) {
    ListNode *fast = head, *slow = head;
    while(fast != NULL && fast->next != NULL){
        slow = slow->next;
        fast = fast->next->next;

        if(fast == slow){
            slow = head;
            while(slow != fast){
                slow = slow->next;
                fast = fast->next;
            }
            return slow;
        }
    }
    return NULL;
}


O(1)复杂度删除结点

(这里不是严格意义的删除结点,而是删除结点对应位置的值)

  1. 如果不是尾结点
next = node->next;
node->val = next->val;
node->next = next->next;
delete next;
  1. 如果是尾结点,只能老老实实遍历一遍找到父结点,用常规的方法删除


剑指-复杂链表的复制

https://www.nowcoder.com/practice/f836b2c43afc4b35ad6adc41ec941dba

记录visited的广度优先搜索

RandomListNode* Clone(RandomListNode* pHead)
{
    if(pHead == NULL)
        return NULL;
    
    RandomListNode* head = new RandomListNode(pHead->label);
    map<RandomListNode*, RandomListNode*> visited;    // src->dst
    vector<RandomListNode*> src_next = {pHead}, src_buffer;
    vector<RandomListNode*> dst_next = {head}, dst_buffer;

    while(!src_next.empty()){
        for(int i = 0; i < src_next.size(); i++){
            RandomListNode *src = src_next[i], *dst = dst_next[i];
            if(src->next != NULL){
                if(visited.count(src->next) != 0){
                    dst->next = visited[src->next];
                }else{
                    RandomListNode* next = new RandomListNode(src->next->label);
                    dst->next = next;
                    src_buffer.push_back(src->next);
                    dst_buffer.push_back(next);
                }
            }
            if(src->random != NULL){
                if(visited.count(src->random) != 0){
                    dst->random = visited[src->random];
                }else{
                    RandomListNode* random = new RandomListNode(src->random->label);
                    dst->random = random;
                    src_buffer.push_back(src->random);
                    dst_buffer.push_back(random);
                }
            }
            visited[src] = dst;
        }
        src_next.clear();
        src_next.swap(src_buffer);
        dst_next.clear();
        dst_next.swap(dst_buffer);
    }

    return head;
}


顺时针打印矩阵

找不到原题,自己编下题目吧。

假设有一个方阵,其数值从(0,0)开始自0沿顺时针递增,比如5x5方阵:

image.png

输入方阵尺寸m,打印整个方阵


void print(int m){
    int array[m][m];
    int top = 0, left = 0, bottom = m - 1, right = m - 1;
    int num = 0;
    while(top <= bottom){
        for(int i = left; i <= right; i++)
            array[top][i] = num++;
        top++;
        for(int i = top; i <= bottom; i++)
            array[i][right] = num++;
        right--;
        for(int i = right; i >= left; i--)
            array[bottom][i] = num++;
        bottom--;
        for(int i = bottom; i >= top; i--)
            array[i][left] = num++;
        left++;
    }
    for(int i = 0; i < m; i++){
        for(int j = 0; j < m; j++){
            printf("%d ", array[i][j]);
        }
        printf("\n");
    }
}

公式推导,假设要找到坐标(1, 2)在矩阵里的数值(如下图红色方块)

image.png

通过观察,可以先计算它外围整圈的元素数量,即

image.png

坐标(1, 2)正好在内部子方阵的上侧,

image.png

如果是在右侧呢?

image.png

同理,下侧

image.png

左侧

image.png

综上,

Input: m

foreach i < m, j < m:
    p = min(i, j, (m-i-1), (m-j-1))    # number of margins
    num = sum([4 * (m - 2 * k - 1) for k in range(0, p)])  # number of surrounds
    if i == p:  # TOP
        num += (m - 2 * p - 1) * 0 + (j - p + 1)
    elif (m - j - 1) == p:  # RIGHT
        num += (m - 2 * p - 1) * 1 + (i - p + 1)
    elif (m - i - 1) == p:  # BOTTOM
        num += (m - 2 * p - 1) * 2 + (m - p - j)
    else:  # LEFT (or elif (m - i - 1) == p)
        num += (m - 2 * p - 1) * 3 + (m - p - i)
    print(num)
void print(int m)
    for(int i = 0; i < m; i++){
        for(int j = 0; j < m; j++){
            int p = min(i, min(j, min(m-i-1, m-j-1)));
            int num = 0;
            for(int k = 0; k < p; k++){
                num += 4 * (m - k * 2 - 1);
            }
            if(i == p){
                num += j - p + 1;
            }else if((m-j-1) == p){
                num += (m - p * 2 - 1) + (i - p + 1);
            }else if((m-i-1) == p){
                num += (m - p * 2 - 1) * 2 + (m - 1 - p) - j + 1;
            }else if(j == p){
                num += (m - p * 2 - 1) * 3 + (m - 1 - p) - i + 1;
            }
            printf("%d ", num);
        }
        printf("\n");
    }
}


面试01.07 旋转矩阵(中等)

https://leetcode-cn.com/problems/rotate-matrix-lcci/

void rotate(vector<vector<int>>& matrix) {
    int N = matrix.size();
    if(N <= 1) return;

    for(int i = 0; i <= N / 2; i++){
        for(int j = i; j < (N - i - 1); j++){
            swap(matrix[j][N-1-i], matrix[i][j]);
            swap(matrix[i][j], matrix[N-1-j][i]);
            swap(matrix[N-1-j][i], matrix[N-1-i][N-1-j]);
        }
    }
}