轮转数组这个思路比较简单就是两次局部翻转 全局翻转不过需要注意如果k nums.length是需要取余的publicvoidrotate(int[]nums,intk){intnnums.length;kk%n;if(k0)return;reverse(nums,0,n-k-1);reverse(nums,n-k,n-1);reverse(nums,0,n-1);}privatevoidreverse(int[]nums,intfrom,intto){while(fromto){inttempnums[from];nums[from]nums[to];nums[to--]temp;}}除了自身以外数组的乘积如果用除法就所有元素乘积最后遍历每个元素一除时间复杂度O ( n ) O(n)O(n)空间复杂度O ( 1 ) O(1)O(1)如果使用暴力就是从前到后遍历一个一个乘起来跳过自己时间复杂度是O ( n ) O(n)O(n)然后一共n nn个元素所以是O ( n 2 ) O(n^2)O(n2)时间复杂度复杂度提高在哪里呢是因为每次算的时候实际是有重复的每个位置的nums[i]都被计算使用了( n − 1 ) (n - 1)(n−1)次能不能变为一次呢怎么减少重复呢前缀和不过不是计算和而是计算乘积。但是它不是计算前缀和还要跳过一个数还不能除法。前缀和 后缀和不就可以了publicint[]productExceptSelf(int[]nums){// 前缀和 后缀和int[]answernewint[nums.length];Arrays.fill(answer,1);intpre1;// 先计算每个位置处 [0, i - 1] 的前缀乘积for(inti0;inums.length-1;i){pre*nums[i];answer[i1]*pre;}intback1;// 再加上每个位置处 [i 1, nums.length - 1] 的后缀乘积for(intjnums.length-1;j0;--j){back*nums[j];answer[j-1]*back;}returnanswer;}矩阵置零能不能在遍历到0的时候把数据上下全置为0不可以如果置为0后续你不知道遍历到的0是因为它本身是0还是你自己设置为0的所以我们需要保留需要置为0的行或者列最后遍历完之后统一清理。classSolution{publicvoidsetZeroes(int[][]matrix){intnmatrix.length,mmatrix[0].length;boolean[]rowZeronewboolean[n];// 行是否需要置零boolean[]colZeronewboolean[m];// 列是否需要置零for(inti0;in;i)for(intj0;jm;j)if(matrix[i][j]0)rowZero[i]colZero[j]true;for(inti0;in;i)if(rowZero[i])for(intj0;jm;j)matrix[i][j]0;for(intj0;jm;j)if(colZero[j])for(inti0;in;i)matrix[i][j]0;}}时间复杂度是O ( m n ) O(mn)O(mn)这个是没办法优化的空间复杂度是O ( m n ) O(m n)O(mn)还能优化吗能有一种用常量空间的解决方案用矩阵第一行保存该列是否被置零用矩阵第一列保存该行是否被置零哎为什么能这样呢你想第一行的如果某个元素它本身是0你是不是这一列一定是要被清空的或者这一列它本身是有0的那最后一定也会被置零的我放到第一行该列的位置记录为0没问题吧但是还有个小问题需要区分第一行的0是本身这个位置就是0还是后来置为0的因为我们是用的第一行第一列来存的所以后续根据这个置为0的时候是先把matrix[1][1]右下的位置都根据规则置为空后再单独处理第一行第一列假如原来第一行的0是他本身就是0那我们后续这一行都要清空的否则就不用操作了 。所以还需要两个标志位。classSolution{publicvoidsetZeroes(int[][]matrix){intnmatrix.length,mmatrix[0].length;booleanrowZerofalse,colZerofalse;for(inti0;in;i)if(matrix[i][0]0)colZerotrue;for(intj0;jm;j)if(matrix[0][j]0)rowZerotrue;// 记录第一行第一列最后是否需要清空for(inti1;in;i)for(intj1;jm;j)if(matrix[i][j]0)matrix[i][0]matrix[0][j]0;// 遍历for(inti1;in;i)if(matrix[i][0]0)for(intj1;jm;j)matrix[i][j]0;for(intj1;jm;j)if(matrix[0][j]0)for(inti1;in;i)matrix[i][j]0;// 根据第一行第一列清空 matrix[1][1] 右下部分矩阵if(rowZero)for(intj0;jm;j)matrix[0][j]0;if(colZero)for(inti0;in;i)matrix[i][0]0;// 处理第一行第一列}}相交链表如果相交那从后往前肯定是找到交点的并且这一部分是他们都有的但是链表从前往后我们怎么找呢观察示例 1A AA和B BB链表如果有交点只可能从他们尾部长度相等的时候开始也就是A AA第一个结点为4 44的位置B BB第一个结点为6 66的位置如果他们A.next B.next才会出现交点。所以我们可以先找链表长度让他们都从尾部往前开始对齐再往后找交点/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val x; * next null; * } * } */publicclassSolution{publicListNodegetIntersectionNode(ListNodeheadA,ListNodeheadB){intlenA0,lenB0;ListNodeAheadA,BheadB;// 计算A、B链表长度while(A!null){lenA;AA.next;}while(B!null){lenB;BB.next;}AheadA;BheadB;// 长度对齐if(lenAlenB){while(lenA!lenB){BB.next;lenB--;}}else{while(lenA!lenB){AA.next;lenA--;}}// 此时 A 往后的链表长度等于 B 往后的链表长度while(A!B){AA.next;BB.next;}returnA;}}下面再看一种更好的解法假设有交点从交点到结束长度为z zzA AA头节点到交点长度为x xxB BB头节点到交点长度为y yy有等式x y z x y z x y z x y zxyzxyz含义是什么呢我让p pp从headA \text{headA}headA开始走它遍历完A AA之后从B BB开始让q qq从headB \text{headB}headB开始走它遍历完B BB之后从A AA开始如果有交点他们一定会相遇如果没有交点最后两个人都会为nullclassSolution{publicListNodegetIntersectionNode(ListNodeheadA,ListNodeheadB){ListNodepheadA;ListNodeqheadB;while(p!q){pp!null?p.next:headB;qq!null?q.next:headA;}returnp;}}