学校网站建设需求,制作网页游戏平台,wordpress 加入搜索,网上购物网站大全一 螺旋矩阵
题目链接#xff1a;59. 螺旋矩阵 II - 力扣#xff08;LeetCode#xff09; 题目描述#xff1a; 给你一个正整数 n #xff0c;生成一个包含 1 到 n2 所有元素#xff0c;且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。 示例 1#xff1a;… 一 螺旋矩阵
题目链接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为奇数时我们要进行一个单独赋值的操作。当我们进行赋值时要统一操作左开右闭的话每个边都要统一我们这里就采用左开右闭就是每条边的最后一个格子不赋值放到下一条边处理。我们设起始点下标为star0循环次数为loop那么第一次循环开始位置为a[star][star],终止为n-loop;第二次循环开始位置为a[star1][star1]终止位置为n-(loop1),此时便完成了循环最后加一个奇数单独赋值的情况即可。
我们这里就要考虑我们循环赋值要进行多少次 归纳容易发现 n2 循环1次 n3 循环1次,单独赋值一个格子 n4 循环2次 n5 循环2次,单独赋值一个格子 可以发现循环次数为n/2当n为奇数是取整数部分。 代码实现
class Solution {public int[][] generateMatrix(int n) {int a[][] new int[n][n]; //创建一个二维数组 int start0; //起始位置x起始位置yint loop0; //循环的次数 int count1; //要进行赋值的数值初始为1 int i,j;while(loopn/2){ //当循环次数小于要循环的次数时这里的loop也同时控制这终止下标for( jstart;jn-loop;j){ //第一条边行不变列递增a[start][j]count;}for( istart;in-loop;i){ //第二条边列不变行递增a[i][j]count;}for( ;jstart;j--){ //第三条边行不变列递减这里j没初始化是因为上一个for循环最终j的值就是此循环j的起始值a[i][j]count; }for( ;istart;i--){ //第四条边列不变行递减a[i][j]count;}start; //改变下次循环起始位置}if(n%21){ //如果n为奇数 a[n/2][n/2]count;}return a;}
} 分析时间复杂度
外层的 while 循环执行的次数为 n/2 次每次循环都会覆盖矩阵的一圈元素。内层的四个 for 循环的迭代次数依次为 n-1n-1n-1n-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 dumyheadnew ListNode(-1,head);//创建虚拟头结点ListNode perdumyhead; //per指针用来寻找要移除的元素while(per.next!null){ //如果头结点不为空if(per.next.valval){ //找到要删除的元素per.nextper.next.next; //直接连接到删除结点的下一个结点}else{perper.next; //没找到指针后移}}return dumyhead.next;/**返回值为cur.net,cur是一个辅助节点per是用来寻找的需要移除的节点*cur固定指向头节点*/}
}// 采用虚拟头结点的方法class Solution {public ListNode removeElements(ListNode head, int val) {while(head!nullhead.val val){//如果头结点不为空并且头结点为要删除 的值headhead.next; }ListNode curhead; //移动指针查找非结点while(cur!nullcur.next!null){if(cur.next.valval){cur.nextcur.next.next;}else{curcur.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 curhead;ListNode pernull;while(cur!null){ListNode tempcur.next;//这里定义一个临时指针是因为当我们将链接改变方向时cur指针的下一个结点就失去了表达方式所以我们要在改变之前提前存放好该结点。cur.nextper;percur;curtemp;}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] 解题思路
使用虚拟头节点。先定义一个指针指针每次指向即将操作的节点12的前一个节点然后指针指向的节点的下一个节点连接到节点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.nexthead;ListNode curdumyhead;//定义一个移动指针,每次指向要修改的节点的前一个节点while(cur.next!null cur.next.next!null){ListNode temp,temp1;/*定义两个临时指针,都指向要修改的节点的第一个节点*temp指向前两个的第一个temp2指向修改的后两个的第一个**/tempcur.next;//节点1为temptemp1cur.next.next.next;//节点3为temp1,这里做处理是因为一旦节点2的下一个链接节点1便会与节点3断开cur.nextcur.next.next;//虚拟头节点的下一个节点为节点2cur.next.nexttemp;//链接节点1temp.nexttemp1;//链接节点3curcur.next.next;//修改cur到未改变的节点的前一个} return dumyhead.next;}
} 复杂度分析
时间复杂度代码中的 while 循环会遍历链表并在每次循环中交换两个节点。因此时间复杂度是 O(n)其中 n 是链表的节点数。空间复杂度代码只使用了常数级别的额外空间所以空间复杂度是 O(1)。 参考资料
代码随想录_百度搜索 (baidu.com)
力扣LeetCode官网 - 全球极客挚爱的技术成长平台
