代码随想录第九期第三天打卡记录

链表基础：

struct ListNode {
    int val;  //结点上存储元素
    ListNode *next;  //指向下一个节点的指针
    ListNode(int x) : val(x), next(nullptr) {}  //结点的构造函数
};

注意：不写构造函数的话，C++会自动的生成这样的一个构造函数，单数不会生成任何的成员变量。

	插入/删除（时间复杂度）	查询（时间复杂度）	使用场景
数组	$O(n)$	$O(1)$	数据量固定，频繁查询，较少增删
链表	$O(1)$	$O(n)$	数据量不固定，频繁增删，较少查询

59.螺旋矩阵: link

以下部分为 c++相关的测试代码。
题目：给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

输入：n = 3
输出：
[[1,2,3],
[8,9,4],
[7,6,5]]

#include<iostream>
using namespace std;
#define MAXWIDTH 10
#include<stdio.h>


void screwArray(int array[MAXWIDTH][MAXWIDTH], int arraySize) {
	int roundNumber = (arraySize % 2 == 0) ? arraySize / 2 : arraySize / 2 + 1;
	//对于每个圈，都是可以根据其圈序号确定其四个顶点的坐标的，
	//这也是绘制每个圈四条边时循环的起止点
	int rank, colomn, count = 0;
	for (int i = 0; i < roundNumber; i++) {
		// compute up  rank 
		for (rank = i, colomn = i; colomn < arraySize - i; colomn++) {  // 此处设置为 qrrySize 维的确保做完外围的操作之后能够保持array的对称性
			count++; // the number used to populate the array  填充数组
			array[rank][colomn] = count;
		}
		//compute right colomn
		for (rank = i + 1, colomn = arraySize - 1 - i; rank < arraySize - i;
			rank++) {
			count++;
			array[rank][colomn] = count;
		}
		//compute bellow rankx`
		for (rank = arraySize - 1 - i, colomn = arraySize - 2 - i;
			colomn >= i; colomn--) {
			count++;
			array[rank][colomn] = count;
		}
		//compute left colomn
		for (rank = arraySize - 2 - i, colomn = i; rank > i; rank--) {
			count++;
			array[rank][colomn] = count;
		}
	}
}

int main() {
	int array[MAXWIDTH][MAXWIDTH];
	int arraySize;

	cout << "input the array arraySize (<10): ";
	cin >> arraySize;

	screwArray(array, arraySize);

	cout << endl << "array is as follows :" << endl;
	for (int i = 0; i < arraySize; i++) {
		for (int j = 0; j < arraySize; j++)
			printf("%5d", array[i][j]);
		cout << endl << endl;
	}

	return 0;
}

以下为Python代码

import numpy as np
import math
a = [[1, 2, 3, 4],
     [12, 13, 14, 5],
     [11, 16, 15, 6],
     [10, 9, 8, 7]]

b = np.array(a)
count = 0
mid = 2
r, c = 0, 0
num = 4
list1 = []
while count < mid:
    r = c = count
    while r < num - count:  # top
        list1.append(b[c][r])
        r = r + 1
    if r + 1 > num - count :
        r -= 1# 这里计算过之后会将最后的结果num   ( count, num-1)
        c += 1 # (count+1 , num-1)
    while c < num - count :  # right
        # if c == count:
        #     c += 1
        list1.append(b[c][r])

        c = c + 1
    if c + 1 > num - count: # down
        c -= 1  # ( num-1, num-1 )
        r -= 1 #  ( num-1, num-2)
    while r >= count: # left
        # r = r - 1
        list1.append(b[c][r])
        r = r - 1
    if r - 1 < count:
        r += 1  ## ( num-1, count )
        c -= 1  # ( num-2, count )
    while c >= count:
        # c = c-1;
        if c != count:
            list1.append(b[c][r])
        c = c - 1
    if c - 1 <= count:
        c += 1
    count += 1
print(list1)

203.移除元素 链接: link

class Solution{
public:
ListNode* removeElements(ListNode* head , int val ){
	ListNode* dummyHead = new ListNode(0);
	dummyHead->next = head;
	ListNode* cur = dummyHead;
	while (cur->next != NULL){
	if (cur->next->val == val){
	ListNode*tmp = cur->next;
	cur->next = cur->next->next;
	delete tmp;
	} else{
	cur = cur->next;
	}
	}
	head = dummyHead->next;
	delete dummyHead;
	return head;
}
};

LeetCode 707题 设计链表

• 题目链接: 707.设计链表
  在链表类中实现这些功能：

• get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。

• addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。

• addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。

• addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。

• deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点

class MyLinkedList {
public:
    // 定义链表节点结构体
    struct LinkedNode {
        int val; // 链表默认的数值
        LinkedNode* next;  // 固定属性
        LinkedNode(int val):val(val), next(nullptr){}
    };

    // 初始化链表
    MyLinkedList() {
        _dummyHead = new LinkedNode(0); // 这里定义的头结点 是一个虚拟头结点，而不是真正的链表头结点
        _size = 0;
    }

    // 获取到第index个节点数值，如果index是非法数值直接返回-1， 注意index是从0开始的，第0个节点就是头结点
    int get(int index) {
        if (index > (_size - 1) || index < 0) {
            return -1;
        }
        LinkedNode* cur = _dummyHead->next;
        while(index--){ // 如果--index 就会陷入死循环
            cur = cur->next;
        }
        return cur->val;
    }

    // 在链表最前面插入一个节点，插入完成后，新插入的节点为链表的新的头结点
    void addAtHead(int val) {
        LinkedNode* newNode = new LinkedNode(val);
        newNode->next = _dummyHead->next;
        _dummyHead->next = newNode;
        _size++;
    }

    // 在链表最后面添加一个节点
    void addAtTail(int val) {
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* cur = _dummyHead;
        while(cur->next != nullptr){
            cur = cur->next;
        }
        cur->next = newNode;
        _size++;
    }

    // 在第index个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
    // 如果index 等于链表的长度，则说明是新插入的节点为链表的尾结点
    // 如果index大于链表的长度，则返回空
    // 如果index小于0，则在头部插入节点
    void addAtIndex(int index, int val) {

        if(index > _size) return;
        if(index < 0) index = 0;        
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* cur = _dummyHead;
        while(index--) {
            cur = cur->next;
        }
        newNode->next = cur->next;
        cur->next = newNode;
        _size++;
    }

    // 删除第index个节点，如果index 大于等于链表的长度，直接return，注意index是从0开始的
    void deleteAtIndex(int index) {
        if (index >= _size || index < 0) {
            return;
        }
        LinkedNode* cur = _dummyHead;
        while(index--) {
            cur = cur ->next;
        }
        LinkedNode* tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;
        _size--;
    }

    // 打印链表
    void printLinkedList() {
        LinkedNode* cur = _dummyHead;
        while (cur->next != nullptr) {
            cout << cur->next->val << " ";
            cur = cur->next;
        }
        cout << endl;
    }
private:
    int _size;
    LinkedNode* _dummyHead;

};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

206.反转链表: link

以下部分为 c++相关的测试代码。
题目：
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

输入：head = [1,2,3,4]
输出:[ 4,3,2,1 ]

输入：	[ ]
输出： [ ] 

注意：

• 链表中节点的数目范围在范围 [0, 10⁴] 内
• -10⁵ <= Node. val <= 10⁵
• pos 的值为 -1 或者链表中的一个有效索引
  解题思路
• 双指针
• 迭代法

class Solution {
public:
    ListNode* reverse(ListNode* pre,ListNode* cur){
        if(cur == NULL) return pre;
        ListNode* temp = cur->next;
        cur->next = pre;
        // 可以和双指针法的代码进行对比，如下递归的写法，其实就是做了这两步
        // pre = cur;
        // cur = temp;
        return reverse(cur,temp);
    }
    ListNode* reverseList(ListNode* head) {
        // 和双指针法初始化是一样的逻辑
        // ListNode* cur = head;
        // ListNode* pre = NULL;
        return reverse(NULL, head);
    }

};

双指针

class Solution {
public:
    ListNode* reverseList(ListNode* head){
    ListNode* pre = NULL;
    ListNode* cur = head；
    ListNode* tmp;
    while(cur){
    	tmp = cur->next;
    	cur->next = pre;
    	pre = cur;
    	cur = tmp;
    }
    return pre;
    }
};