算法日记 - Day5
轮转数组
- 这个思路比较简单，就是两次局部翻转 + 全局翻转
- 不过需要注意如果
k >= nums.length，是需要取余的
publicvoidrotate(int[]nums,intk){intn=nums.length;k=k%n;if(k==0)return;reverse(nums,0,n-k-1);reverse(nums,n-k,n-1);reverse(nums,0,n-1);}privatevoidreverse(int[]nums,intfrom,intto){while(from<to){inttemp=nums[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[]answer=newint[nums.length];Arrays.fill(answer,1);intpre=1;// 先计算每个位置处 [0, i - 1] 的前缀乘积for(inti=0;i<nums.length-1;++i){pre*=nums[i];answer[i+1]*=pre;}intback=1;// 再加上每个位置处 [i + 1, nums.length - 1] 的后缀乘积for(intj=nums.length-1;j>0;--j){back*=nums[j];answer[j-1]*=back;}returnanswer;}矩阵置零
- 能不能在遍历到
0的时候把数据上下全置为0？不可以，如果置为0，后续你不知道遍历到的0是因为它本身是0还是你自己设置为0的，所以我们需要保留需要置为0的行或者列，最后遍历完之后统一清理。
classSolution{publicvoidsetZeroes(int[][]matrix){intn=matrix.length,m=matrix[0].length;boolean[]rowZero=newboolean[n];// 行是否需要置零boolean[]colZero=newboolean[m];// 列是否需要置零for(inti=0;i<n;++i)for(intj=0;j<m;++j)if(matrix[i][j]==0)rowZero[i]=colZero[j]=true;for(inti=0;i<n;++i)if(rowZero[i])for(intj=0;j<m;++j)matrix[i][j]=0;for(intj=0;j<m;++j)if(colZero[j])for(inti=0;i<n;++i)matrix[i][j]=0;}}时间复杂度是O ( m n ) O(mn)O(mn)，这个是没办法优化的，空间复杂度是O ( m + n ) O(m + n)O(m+n)，还能优化吗？能，有一种用常量空间的解决方案
- 用矩阵第一行保存该列是否被置零
- 用矩阵第一列保存该行是否被置零
哎，为什么能这样呢？你想第一行的如果某个元素它本身是0，你是不是这一列一定是要被清空的，或者这一列它本身是有0的，那最后一定也会被置零的，我放到第一行该列的位置，记录为0没问题吧
但是还有个小问题，需要区分第一行的0是本身这个位置就是0，还是后来置为0的，因为我们是用的第一行第一列来存的，所以后续根据这个置为0的时候，是先把matrix[1][1]右下的位置都根据规则置为空后，再单独处理第一行第一列，假如原来第一行的0是他本身就是0，那我们后续这一行都要清空的，否则就不用操作了 。所以还需要两个标志位。
classSolution{publicvoidsetZeroes(int[][]matrix){intn=matrix.length,m=matrix[0].length;booleanrowZero=false,colZero=false;for(inti=0;i<n;i++)if(matrix[i][0]==0)colZero=true;for(intj=0;j<m;j++)if(matrix[0][j]==0)rowZero=true;// 记录第一行第一列最后是否需要清空for(inti=1;i<n;++i)for(intj=1;j<m;++j)if(matrix[i][j]==0)matrix[i][0]=matrix[0][j]=0;// 遍历for(inti=1;i<n;++i)if(matrix[i][0]==0)for(intj=1;j<m;++j)matrix[i][j]=0;for(intj=1;j<m;++j)if(matrix[0][j]==0)for(inti=1;i<n;++i)matrix[i][j]=0;// 根据第一行第一列清空 matrix[1][1] 右下部分矩阵if(rowZero)for(intj=0;j<m;++j)matrix[0][j]=0;if(colZero)for(inti=0;i<n;++i)matrix[i][0]=0;// 处理第一行第一列}}相交链表
如果相交，那从后往前，肯定是找到交点的，并且这一部分是他们都有的，但是链表从前往后我们怎么找呢？观察示例 1，A 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){intlenA=0,lenB=0;ListNodeA=headA,B=headB;// 计算A、B链表长度while(A!=null){lenA++;A=A.next;}while(B!=null){lenB++;B=B.next;}A=headA;B=headB;// 长度对齐if(lenA<lenB){while(lenA!=lenB){B=B.next;lenB--;}}else{while(lenA!=lenB){A=A.next;lenA--;}}// 此时 A 往后的链表长度等于 B 往后的链表长度while(A!=B){A=A.next;B=B.next;}returnA;}}下面再看一种更好的解法
假设有交点，从交点到结束长度为z zz，A AA头节点到交点长度为x xx，B BB头节点到交点长度为y yy，有等式x + y + z = = x + y + z x + y + z == x + y + zx+y+z==x+y+z，含义是什么呢？我让p pp从headA \text{headA}headA开始走，它遍历完A AA之后从B BB开始，让q qq从headB \text{headB}headB开始走，它遍历完B BB之后从A AA开始，如果有交点，他们一定会相遇！！！如果没有交点，最后两个人都会为null
classSolution{publicListNodegetIntersectionNode(ListNodeheadA,ListNodeheadB){ListNodep=headA;ListNodeq=headB;while(p!=q){p=p!=null?p.next:headB;q=q!=null?q.next:headA;}returnp;}}