LeetCode刷题

一螺旋矩阵

题目链接：59. 螺旋矩阵 II - 力扣（LeetCode）

题目描述：

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

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

解题思路：

我们可以发现这个矩阵是由外围一层一层的包围，数值依次递增。观察发现如下规律：

结合这个特点，我们可以用4个for循环来对没一条边赋值，当我们对一圈赋完值后，只要对起始和终止位置在修改即可。当n为偶数时，我们可以刚好循环完，当n为奇数时，我们会剩下一个格子。

如图：

所以当n为奇数时我们要进行一个单独赋值的操作。当我们进行赋值时，要统一操作，左开右闭的话每个边都要统一，我们这里就采用左开右闭，就是每条边的最后一个格子不赋值，放到下一条边处理。我们设起始点下标为star=0，循环次数为loop；那么第一次循环开始位置为a[star][star],终止为n-loop;第二次循环开始位置为a[star+1][star+1]；终止位置为n-(loop+1),此时便完成了循环，最后加一个奇数单独赋值的情况即可。

我们这里就要考虑我们循环赋值要进行多少次？

归纳容易发现：

n=2 循环1次；

n=3 循环1次,单独赋值一个格子；

n=4 循环2次；

n=5 循环2次,单独赋值一个格子；

可以发现循环次数为n/2，当n为奇数是，取整数部分。

代码实现：

class Solution {public int[][] generateMatrix(int n) {int a[][]= new int[n][n];          //创建一个二维数组 int start=0;             //起始位置x，起始位置yint loop=0;                        //循环的次数 int count=1;                       //要进行赋值的数值，初始为1 int i,j;while(loop++<n/2){                 //当循环次数小于要循环的次数时，这里的loop也同时控制这终止下标for( j=start;j<n-loop;j++){    //第一条边：行不变，列递增a[start][j]=count++;}for( i=start;i<n-loop;i++){    //第二条边：列不变，行递增a[i][j]=count++;}for( ;j>start;j--){           //第三条边：行不变，列递减，这里j没初始化是因为，上一个for循环最终j的值就是此循环j的起始值a[i][j]=count++;         }for( ;i>start;i--){          //第四条边：列不变，行递减a[i][j]=count++;}start++;                       //改变下次循环起始位置}if(n%2==1){                         //如果n为奇数 a[n/2][n/2]=count;}return a;}
}

分析时间复杂度：

外层的 while 循环执行的次数为 n/2 次，每次循环都会覆盖矩阵的一圈元素。
内层的四个 for 循环的迭代次数依次为 n-1，n-1，n-1，n-2，分别表示四条边上的元素个数。
因此，总体的时间复杂度为 O(n × n) = O(n²)。

分析空间复杂度：

代码中创建了一个 n × n 的二维数组，因此占用的额外空间为 O(n²)。

综上所述，该代码的时间复杂度为 O(n²)，空间复杂度为 O(n²)。

二移除链表中的元素

题目链接：203. 移除链表元素 - 力扣（LeetCode）

题目描述：

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
示例 2：
输入：head = [], val = 1
输出：[]
示例 3：
输入：head = [7,7,7,7], val = 7
输出：[]

解题思路：

解题思路主要分为两种，一种是带虚拟头节点的，另一种是不带虚拟头节点的。

1.不带虚拟头节点的我们要考虑头节点为要删除的值的情况，和非头节点为要删除的的情况。头结点为要删除的值，只需要将头结点移动到下一个结点，让下一个结点为头结点即可。如图：

非头结点为要删除的值，则只需要找到该删除节点的前一个结点，让它直接连接删除结点的后一个结点即可。如图：

2.带虚拟头节点的只需要将所有节点当作非头结点处理即可。如图：

代码实现：

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode removeElements(ListNode head, int val) {ListNode dumyhead=new ListNode(-1,head);//创建虚拟头结点ListNode per=dumyhead;   //per指针用来寻找要移除的元素while(per.next!=null){   //如果头结点不为空if(per.next.val==val){   //找到要删除的元素per.next=per.next.next;  //直接连接到删除结点的下一个结点}else{per=per.next;    //没找到指针后移}}return dumyhead.next;/**返回值为cur.net,cur是一个辅助节点，per是用来寻找的需要移除的节点*cur固定指向头节点*/}
}//   采用虚拟头结点的方法class Solution {public ListNode removeElements(ListNode head, int val) {while(head!=null&&head.val ==val){//如果头结点不为空并且头结点为要删除 的值head=head.next;             }ListNode cur=head;               //移动指针，查找非结点while(cur!=null&&cur.next!=null){if(cur.next.val==val){cur.next=cur.next.next;}else{cur=cur.next;}}return head;}
}//不用虚拟头结点的方法

复杂度分析：

时间复杂度：遍历链表的过程中，需要检查所有的节点的值，并删除符合条件的节点。因此，代码的时间复杂度是 O(n)，其中 n 是链表中的节点数。
空间复杂度：代码只使用了常数级别的额外空间，所以空间复杂度是 O(1)。

所以两种方法的时间度均为均为O(n)，空间复杂度均为O(1);

三反转链表

题目链接：206. 反转链表 - 力扣（LeetCode）

题目描述：

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

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

示例 2：

输入：head = [1,2]
输出：[2,1]
示例 3：

输入：head = []
输出：[]

解题思路：

采用双指针的方法解题我们可以让一个指针在前，一个指针在后依次改变链表中的连接方向，动态效果如图：

代码实现：

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseList(ListNode head) {ListNode cur=head;ListNode per=null;while(cur!=null){ListNode temp=cur.next;//这里定义一个临时指针是因为，当我们将链接改变方向时，cur指针的下一个结点就失去了表达方式，所以我们要在改变之前提前存放好该结点。cur.next=per;per=cur;cur=temp;}return per;}
}

复杂度分析：

时间复杂度：代码中的 while 循环会遍历整个链表，将每个节点的 next 指针改变指向前一个节点。因此，时间复杂度是 O(n)，其中 n 是链表的节点数。
空间复杂度：代码只使用了常数级别的额外空间，所以空间复杂度是 O(1)。

综上所述，该代码的时间复杂度是 O(n)，空间复杂度是 O(1)。

四两两交换链表中的节点

题目链接：24. 两两交换链表中的节点 - 力扣（LeetCode）

题目描述：

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

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

示例 2：

输入：head = []
输出：[]

示例 3：

输入：head = [1]
输出：[1]

解题思路：

使用虚拟头节点。先定义一个指针，指针每次指向即将操作的节点（1，2）的前一个节点，然后指针指向的节点的下一个节点连接到节点2，在将节点2，连接到节点1，要注意一旦指针指向的节点连接到节点2以后，节点1就失去了表达式，所以节点1要提前存放，同理节点2连接到节点1以后节点3也就失去了表达式，节点3也要提前处理。如图：

代码实现：

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode swapPairs(ListNode head) {ListNode dumyhead = new ListNode(-1);//定义一个虚拟头节点dumyhead.next=head;ListNode cur=dumyhead;//定义一个移动指针,每次指向要修改的节点的前一个节点while(cur.next!=null && cur.next.next!=null){ListNode temp,temp1;/*定义两个临时指针,都指向要修改的节点的第一个节点，*temp指向前两个的第一个，temp2指向修改的后两个的第一个**/temp=cur.next;//节点1为temptemp1=cur.next.next.next;//节点3为temp1,这里做处理是因为一旦节点2的下一个链接节点1，便会与节点3断开cur.next=cur.next.next;//虚拟头节点的下一个节点为节点2；cur.next.next=temp;//链接节点1temp.next=temp1;//链接节点3cur=cur.next.next;//修改cur到未改变的节点的前一个}  return dumyhead.next;}
}