leetcode刷题指南
88. Merge Sorted Array
不能重新生成一个数组,只能在原数组上进行操作,为了保证数组之前的内容不被覆盖,因此,从数组的末尾开始,从后往前。
K表示最长的位置,m表示数组1,n表示数组2,进行数值比较
if(nums1[i]>nums2[j]){
nums1[k--]=nums1[i--];
}
else{
nums1[k--]=nums2[j--];
最后,如果nums2还有数值没放到nums1里,而i已经等于0,则将nums2全部放入nums1中。
while(j>=0){
nums1[k--]=nums2[j--];
}
测试用例注意:m为nums1的要比较部分的大小,即[1,2,4,7,9] 3 [2,5,7] 3 是不合理的因为3+3>nums1的总长度5; [1,2,4,7,9] 2 [2,5,7] 3 合理 2+3=5
54. Spiral Matrix
rowbegin第一行 rowend最后一行 colbegin第一列 colend最后一列
按照从左至右(下一次从下一行开始rowbegin++),从上至下(下一次从向左侧的列开始colend--),从右至左(下一次从上一行开始rowend--),从下至上的顺序进行(下一次从向右的列开始colend++)
值得注意的是:循环的判断条件是colbegin<=colend;rowbegin<=rowend 如果以==条件进入循环 进行从左到右和从上到下之后,rowbegin可能>rowend,colbegin可能>colend,所以后两次要进行if(rowbegin<=rowend) 判断 满足条件才能从右至左 if(colbegin<=colend) 判断,满足条件才能从下至上
56. Merge Intervals
对集合start排序,如果当前的start小于前面的end,则可以合并,找到满足这种情况最大的end,将满足这种情况的开始和最大的end,弄成一个集合,存到res里(新创建的)。不满足条件,重新创建start和end组合,存到res里。每次进入循环都是先放进res,再重新获得start 和end。退出循环时,只获得了start和end,并没有放进去,最后一个end没有最后一个没有放进去(无论是否满足条件),将最后的end和start放进去。
注意:collection的排序(集合)
73. Set Matrix Zeroes
对于矩阵中为0的元素,将它同行和同列位置的元素置为0,如果是第一行或者第一列,标志第一行或者第一列是否含有0。对于从第二行,第二列开始的元素,如果第一行,或者第一列为0,则它为0(相当于用第一行和第一列标志交叉的位置是否为0,如果为0,则该行或者该列全部为0)最后将第一行或者第一列本身就含有0的全都置为0
75. Sort Colors
设置三个指针,将为0的元素放到开始和开头的元素互换(index0标志从开始0应该放置位置的元素),将为2的元素放到结尾,和结尾的元素互换(inde2标志从结尾2应该放置位置的元素)。index标志从头开始遍历数组的指针,因为换到开始的都是0,换到结尾的都是2,但是从结尾缓过来的数字不一定是什么,所以换了结尾之后,换过来的也要进行比较,index--。之后再统一向后遍历index++
78.
Subsets
118. Pascal's Triangle
算法的思想是,每次都在上一排基础上的第一个位置添加1,j处的值为原j处和j+1处的值,将新的值加入整体二维数组中。
189.
Rotate Array
1 2 3 4 5 6 7->5 6 7 1 2 3 4
1 2 3 4->4 3 2 1
5 6 7->7 6 5
4 3 2 1 7 6 5->5 6 7 1 2 3 4
就是数组的反转
注意 题目本质是这样的 1 2 3 5 6 7->7 1 2 3 4 5 6->6 7 1 2 3 4 5->5 6 7 1 2 3 4
所以 可能存在K>nums.length 因为k=nums.length 刚好回到原来的数组
因此要取 k=k%nums.length
79.
Word Search
首先,找到第一字母匹配的位置,然后利用递归的方法,对这个位置上下左右四处进行查找,如果i,j即数组下标越界,则为false,如果此处的字母和word中对应位置的字母不相等,为false;设置visited数组表示是否访问过,如果visited[i][j]==true,为false;如果已经在word中走到最后一个字母,则全部判断完成,返回true(注意:这部分必须写在前面的条件之后,否则,数组越界,而长度相等,会返回true,导致错误结果);如果这四种情况有一种为true,则返回true,查看下一个字母。否则,该位置相等开始的点,不能找到word,清空visited数组为false,重新进入board的循环遍历。
递归的流程:如果长度不相等,但是单个字母相等,进入if(search......)到递归查询下一个字母的部分,如果长度相等,返回true.是上一个search的地方,最后会在所有的search结束之后,返回true;所以,最后一个返回的位置,是递归结束的位置。
268. Missing Number
异或运算——————》恒等律:X ⊕ 0 = X 归零律:X ⊕ X = 0
知识点:x xor a xor a=x;
若i==nums[i]
那么:res xor i xor nums[i]==res;
如果序列为 0,1,2,3,5,6,7
那么res=res xor 0 xor 0 xor 1 xor 1 xor 2 xor 2 xor 3 xor 3 xor 4 xor 5 xor 5 xor 5 xor 6 xor 6 xor 7=res xor 4 xor 7,即i==nums[i]或者nums[i]==i+1的部分都抵消掉了,
则 得到 4 res应该xor 7即 退出循环的i(nums.length)因为少了一个数字,i应该比nums[i]刚好大一个
如果不缺少 退出循环,res为0 res xor i还是0
283. Move Zeroes
对于不是0的数,将后面的数按顺序补到前面去,结束了,对所有的空补0
238. Product
of Array Except Self
public int[] productExceptSelf(int[] nums) {
int res[]=new int[nums.length];
int temp=1;
for(int i=0;i<nums.length;i++){
res[i]=temp; 从前到这个位置前一个的乘积
temp=temp*nums[i]; 记录上一i乘积的累计值
}
temp=1;
for(int i=nums.length-1;i>=0;i--){
res[i]=res[i]*temp; 本次将temp(保存的上一个位置)和从前到这个位置前一个的乘积乘起来
temp=temp*nums[i]; 记录上一i乘积的累计值
}
return res;
}
不能用所有数的乘积除以当前数字,因为当前数字可能为0;
采用的方法就是第i处的值 为从0到i-1的乘积 和 从Length-1到i+1乘积 一次从前到后,一次从后向前