普通数组
1.合并区间
56. 合并区间
https://leetcode.cn/problems/merge-intervals/
先针对左区间进行排序，这样可以对右边进行考虑，如果intervals 中一个新的区间的左端点小于原ans的右端点，那么就能合并，右端点合并成原p【1】和新ans.get(nums - 1)[1]的最大值，否则没有交接，直接add进ans。
补一下.toArray（）;方法，把将List<>(可变长度的有序列表)转为数组
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals,(p,q) -> p[0] - q[0]);
List<int[]> ans = new ArrayList<>();
for(int [] p :intervals){
int nums = ans.size();
if(nums > 0 && ans.get(nums -1)[1] >= p[0]){
//可以合并
ans.get(nums - 1)[1] = Math.max(ans.get(nums - 1)[1],p[1]);
}
else{
ans.add(p);
}
}
return ans.toArray(new int[ans.size()][]);//返回一个object数组指定一下类型
}
}2.轮转数组
189. 轮转数组https://leetcode.cn/problems/rotate-array/
发现规律，如何反转，就是先把整体反转，然后以k为分界，0-k先反转，k-1到n -1再翻转，只需要写一个reverse函数就完事
class Solution {
public void rotate(int[] nums, int k) {
k %= nums.length;
reverse(nums,0,nums.length -1);
reverse(nums,0,k -1);
reverse(nums,k,nums.length -1);
}
public void reverse(int []nums,int start,int end){
while(start<end){
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
}
}3.除自身以外数组的乘积
238. 除自身以外数组的乘积https://leetcode.cn/problems/product-of-array-except-self/
不让用除法，如果让用，其实可以直接所有的前缀积，除以自身，但是不让用了，就用一手前缀积&后缀积。非常巧妙,注意在算后缀积的时候，要×以前前缀积存到ans的东西
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int pre = 1;
int suf = 1;
int[] ans = new int[n];
for(int i = 0; i < n; ++i){
ans[i] = pre;
pre *= nums[i];
}
//注意后缀积的顺序不太一样
for(int j = n - 1; j >=0; --j){
ans[j] *= suf;//这是×了以前存储的前缀积
suf *= nums[j];
}
return ans;
}
}4.缺失的第一个正数
41. 缺失的第一个正数https://leetcode.cn/problems/first-missing-positive/
有点脑筋急转弯的一个题目，难点在于要求空间复杂度为1，所以哈希的方法不行
学了一手原地哈希
就是把这个nums数组直接看成一个哈希
这个整体过程就是，把1放在下标为0的位置上，一直交换，最后遍历，看哪个不满足
class Solution {
public int firstMissingPositive(int[] nums) {
int len = nums.length;
for(int i = 0; i < len; ++i){
//这里if换成while是因为换完以后要接着换
while(nums[i] > 0 && nums[i] <= len && nums[nums[i] - 1] != nums[i]){
//这个条件其实是有点绕的,将1放在下标为0的位置上
swap(nums,i,nums[i] - 1);//所以就是i和nums[i] - 1来换
}
}
for(int i = 0; i < len; ++i){
if(nums[i] != i + 1){
return i + 1;
}
}
return len + 1;
}
private void swap(int[] nums,int first,int end){
int temp = nums[first];
nums[first] = nums[end];
nums[end] = temp;
}
}其实用一个Hashset也能过，但是空间复杂度是O(n)
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
Set<Integer> hashSet = new HashSet<>();
for(int num : nums){
hashSet.add(num);
}
for(int i = 1; i <= n ;++i){
if(!hashSet.contains(i))
return i;
}
return n + 1;
}
}矩阵
1.矩阵置零
73. 矩阵置零https://leetcode.cn/problems/set-matrix-zeroes/
使用两个标记数组boolen【】行何列各一个，如果一个点为0，把这一行和这一列都置为true，然后再重新遍历
class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
boolean[] row = new boolean[m];
boolean[] col = new boolean[n];
for(int i = 0; i < m; ++i){
for(int j = 0; j < n; ++j){
if(matrix[i][j] == 0){
row[i] = col[j] = true;
}
}
}
for(int i = 0;i < m; ++i){
for(int j = 0; j < n; ++j){
if(row[i] || col[j]){
matrix[i][j] = 0;
}
}
}
}
}2.螺旋矩阵
54. 螺旋矩阵https://leetcode.cn/problems/spiral-matrix/
这种螺旋矩阵的题都是类似的模拟问题，看了k神的题解，真的非常清晰比官解清晰的多得多
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
if(matrix.length ==0){
return new ArrayList<Integer>();
}
int l = 0,r = matrix[0].length -1,t = 0,b = matrix.length - 1,x = 0;
Integer[] res = new Integer[(r + 1) * (b + 1)];
while(true){
for(int i = l; i <= r; i++) res[x++] = matrix[t][i];
if(++t > b) break;
for(int i = t; i <= b; i++) res[x++] = matrix[i][r];
if(--r < l) break;
for(int i = r; i >= l; i--) res[x++] = matrix[b][i];
if(--b < t) break;
for(int i = b; i >= t; i--) res[x++] = matrix[i][l];
if(++l > r) break;
}
return Arrays.asList(res);
}
}3.旋转图像
48. 旋转图像https://leetcode.cn/problems/rotate-image/
这道题目对空间复杂度有要求，要求不能使用辅助矩阵
先使用一下使用辅助矩阵的,重要的点是搞清楚映射公式
但是这个存在一个问题，就是说映射之后会使原始矩阵元素被覆盖，所以要克隆一个相同的辅助矩阵
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
int [][] tmp = new int[n][n];
for(int i = 0; i < n; ++i){
tmp[i] = matrix[i].clone();
}
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
matrix[j][n - 1 - i] = tmp[i][j];
}
}
}
}如果不做一个辅助矩阵，
只要分别以矩阵左上角 1/4 的各元素为起始点执行以上旋转操作，即可完整实现矩阵旋转。
具体来看，当矩阵大小 n 为偶数时，取前 2/n行、前 2/n 列的元素为起始点；当矩阵大小 n 为奇数时，取前 2/n 行、前 2/n+1 列的元素为起始点。
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
for(int i = 0; i < n/2; ++i){
for(int j = 0; j < (n +1) /2; ++j){
//做一个临时变量
int tmp = matrix[i][j];
matrix[i][j] = matrix[n - 1 - j][i];
matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
matrix[j][n - 1 - i] = tmp;
}
}
}
}4.搜索二维矩阵Ⅱ
240. 搜索二维矩阵 IIhttps://leetcode.cn/problems/search-a-2d-matrix-ii/
暴力的话就两遍遍历就能解决,时间复杂度就是O（mn）
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
for(int[] row : matrix){
for(int ele : row){
if(ele == target){
return true;
}
}
}
return false;
}
}再次看了K神的解题，太夸张了，怎么能想到的，用到了从上到下递增和从左到右递增的性质
把左下角这个数作为标志数flag
若 flag > target ，则 target 一定在 flag 所在 行的上方 ，即 flag 所在行可被消去。
若 flag < target ，则 target 一定在 flag 所在 列的右方 ，即 flag 所在列可被消去。
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
//从左下角开始
int i = matrix.length - 1,j = 0;
while(i >= 0 && j < matrix[0].length){
if(matrix[i][j] > target) i--;
else if(matrix[i][j] < target) j++;
else return true;
}
return false;
}
}