免费咨询律师网站,绍兴高兴区建设网站,上海网页制作费用,网站开发用什么技术可行性题目1#xff1a;矩阵置零题目#xff1a;问题分析#xff1a;使用两个布尔数组来分别记录哪行哪列出现了0#xff0c;当出现0的行和列#xff0c;对应的布尔数组值置为true。再次遍历数组#xff0c;当出现行数组和列数组中的值为true#xff0c;则对应的原数组的值置为…题目1矩阵置零题目问题分析使用两个布尔数组来分别记录哪行哪列出现了0当出现0的行和列对应的布尔数组值置为true。再次遍历数组当出现行数组和列数组中的值为true则对应的原数组的值置为0.代码
class Solution {public void setZeroes(int[][] matrix) {int mmatrix.length;//记录数组的行数int nmatrix[0].length;//记录数组的列数boolean[] rownew boolean[m];boolean[] colnew boolean[n];for(int i0;im;i){for(int j0;jn;j){if(matrix[i][j]0){row[i]col[j]true;}}}for(int i0;im;i){for(int j0;jn;j){if(row[i]||col[j]) matrix[i][j]0;}}}
}时间复杂度O(mn).题目2螺旋矩阵题目问题分析用数组记录四个方向用「行偏移量列偏移量」描述 4 个方向directions的四个元素分别表示右 下 左 上四个方向用directionIndex来访问方向数组中的四个方向是directions数组的索引当遇到已访问的数组元素或是边界的时候就更改访问的方向为下一个方向。代码
class Solution {public ListInteger spiralOrder(int[][] matrix) {ListInteger resultnew ArrayList();int rowsmatrix.length;//总共的行数int columnsmatrix[0].length;//总共的列数boolean[][] visitednew boolean[rows][columns];if(matrixnull||rows0||columns0){return result;}int row0;//当前行int column0;//当前列int[][] directions{{0,1},{1,0},{0,-1},{-1,0}};//分别表示右 下 左 上四个方向int directionIndex0;//当前的方向索引对上上面的数组directions的四个方向for(int i0;irows*columns;i){result.add(matrix[row][column]);visited[row][column]true;int nextRowrowdirections[directionIndex][0];int nextColumncolumndirections[directionIndex][1];if(nextRow0||nextRowrows||nextColumn0||nextColumncolumns||visited[nextRow][nextColumn]){directionIndex(directionIndex1)%4;//越界或是遇到已访问的元素方向换一个}rowrowdirections[directionIndex][0];columncolumndirections[directionIndex][1];}return result;}
}时间复杂度O(N).题目3旋转图像题目问题分析使用翻转操作代替旋转操作先将数组以水平轴翻转再将数组根据对角线翻转。水平翻转只翻转上半部分所以in/2对角线翻转只翻转一半的对角线所以ji.代码
class Solution {public void rotate(int[][] matrix) {int nmatrix.length;for(int i0;in/2;i){//只翻转上半部分for(int j0;jn;j){int tempmatrix[i][j];matrix[i][j]matrix[n-i-1][j];//水平翻转行变列不变matrix[n-i-1][j]temp;}}for(int i0;in;i){for(int j0;ji;j){int tempmatrix[i][j];matrix[i][j]matrix[j][i];//对角线翻转行列互换matrix[j][i]temp;}}}
}时间复杂度O(N^2).题目4搜索二维矩阵II题目
问题分析从右上角开始查找若当前元素大于target则说明当前元素所在列都不可能找到target因为数组从上到下升序排列则往前一列继续查找若当前元素小于target则说明当前元素所在行都不可能找到target因为数组从左到右升序排列则往下一行继续查找。代码
class Solution {public boolean searchMatrix(int[][] matrix, int target) {int i0;int jmatrix[0].length-1;//右上角的数组下标while(imatrix.lengthj0){if(matrix[i][j]target) return true;//找到则返回trueelse if(matrix[i][j]target){j--;}else{i;}}return false;}
}时间复杂度O(MN).题目5相交链表题目问题分析代码
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode pheadA;ListNode qheadB;while(p!q){//p不等于q的时候才循环pq则证明要么到相交节点了要么没有相交节点到空节点了pp!null?p.next:headB;qq!null?q.next:headA;}return p;}
}代码比较两个节点的时候比较的是内存地址是否一致两个链表相交其相交节点的内存地址一定一致。时间复杂度O(MN).题目6环形链表题目问题分析使用快慢指针来求解快慢指针同时从头结点出发快指针每次走两步慢指针每次走一步若是两者相遇这则证明链表中一定存在环。因为快指针相对于慢指针走一步所以若有环快指针一定会追上慢指针。代码
public class Solution {public boolean hasCycle(ListNode head) {ListNode fasthead;ListNode slowhead;while(fast!nullfast.next!null){//因为快指针每次走两步得同时满足fast和fast.next都不为null的情况下才能成功的走完两步slowslow.next;fastfast.next.next;if(slowfast){return true;}}return false;}
}时间复杂度O(N).题目7反转链表题目问题分析使用迭代的头插法来解决这道题目例如链表1-2-3使用头插法就是把新建一个空链表依次把1,2,3插到这个新链表的头部就得到链表3-2-1这就是反转后的链表。代码
class Solution {public ListNode reverseList(ListNode head) {if(headnull||head.nextnull){return head;}ListNode prenull;ListNode curhead;while(cur!null){ListNode nextcur.next;cur.nextpre;precur;curnext;//不断地迭代直至跳出while循环}return pre;}
}时间复杂度O(N).题目8回文链表题目问题分析首先找到链表的中间节点若是原链表有奇数个节点则是最中间一个例如1-2-3,这个链表的中间节点是2若是原链表有偶数个节点则是中间偏右的那个节点5-3-4-1这个链表的中间节点是4。然后把中间节点之后的链表进行反转再依次比较反转后的链表的各个节点与原链表前半部分节点的值。例如原链表为6-4-5-4-6中间的节点为5反转后的链表为head2: 6-4之前的链表head: 6-4-5比较各个节点的值。代码
class Solution {public boolean isPalindrome(ListNode head) {ListNode midmiddleNode(head);ListNode head2reverse(mid);while(head2!null){if(head.val!head2.val) return false;headhead.next;head2head2.next;}return true;}private ListNode middleNode(ListNode head){ListNode slowhead;ListNode fasthead;while(fast!nullfast.next!null){slowslow.next;fastfast.next.next;}return slow;}private ListNode reverse(ListNode head){ListNode prenull;ListNode curhead;while(cur!null){ListNode nextcur.next;cur.nextpre;precur;curnext;}return pre;}
}时间复杂度O(N).
