每日一念
改掉自己想到哪写哪的坏习惯

子串

和为K的子数组

class Solution {/**有点像找出和为0的子数组，只不过这里和变成了k不太对，尝试使用双指针+滑动窗口，完全过不去样例正确做法hashmap存放 sum -- count对nums中的数字进行遍历sum累加sum[j] - sum[i] = k，则表示此时存在一个范围i - j使得和为k*/public int subarraySum(int[] nums, int k) {HashMap<Integer, Integer> map = new HashMap();map.put(0, 1);int sum = 0;int count = 0;for(int num: nums) {sum += num;if(map.containsKey(sum - k)) {count += map.get(sum - k);}map.put(sum, map.getOrDefault(sum, 0) + 1);}return count;}
}

滑动窗口的最大值

class Solution {/**这题总该是双指针+滑动窗口了吧还是不对。。超时LinkedList创建双端队列queue控制后面的元素加进队尾如果新元素大于队中所有元素弹出所有元素，加入新元素（确保队首元素始终是最大值）控制长度 > k 弹出队首元素只要i >= k - 1，每次都记录res[i] = 队首*/public int[] maxSlidingWindow(int[] nums, int k) {int[] res = new int[nums.length - k + 1];if(nums == null || nums.length == 0) {return res;}LinkedList<Integer> dequeue = new LinkedList();for(int i = 0; i < nums.length; i++) {while(!dequeue.isEmpty() && nums[i] > nums[dequeue.peekLast()]) {dequeue.pollLast();}dequeue.offerLast(i);if(i - dequeue.peekFirst() + 1 > k) {dequeue.pollFirst();}if(i - k + 1 >= 0) {res[i - k + 1] = nums[dequeue.peekFirst()];}}return res; }
}

最小覆盖子串

// 困难题，真是头皮发麻

普通数组

最大子数组

class Solution {/**dp[i]表示以nums[i]结尾的最大和的连续子数组dp[i] -- dp[i - 1](nums[i - 1]结尾的)*/public int maxSubArray(int[] nums) {int[] dp = new int[nums.length];dp[0] = nums[0];for(int i = 1; i < dp.length; i++) {dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);}int max = dp[0];for(int i = 0; i < dp.length; i++) {if(dp[i] > max) {max = dp[i];}}return max;}
}

合并区间

class Solution {/**start, end表示要存入的合并的区间起点&终点初始化为intervals[0] intervals[1]遍历intervals数组进行比较合并（intervals数组首先要对intervals[i][0]进行排序）*/public int[][] merge(int[][] intervals) {// Arrays.sort(intervals, new Comparator<int[]>(){//     public int compare(int[] a, int[] b) {//         return Integer.compare(a[0], b[0]);//     }// });// Arrays.sort(intervals, (a, b) -> {//     return Integer.compare(a[0], b[0]);// });for(int i = 0; i < intervals.length - 1; i++) {for(int j = 0; j < intervals.length - 1 - i; j++) {if(intervals[j][0] > intervals[j + 1][0]) {int[] temp = intervals[j];intervals[j] = intervals[j + 1];intervals[j + 1] = temp;}}}// for(int i = 0; i < intervals.length; i++) {//     System.out.println("interval数组的值" + intervals[i][0] + intervals[i][1]);// }List<List<Integer>> res = new ArrayList();int start = intervals[0][0];int end = intervals[0][1];for(int i = 1; i < intervals.length; i++) {// i = 1的【i】【0】比i = 0大，进行合并if(intervals[i][0] <= end) {end = Math.max(end, intervals[i][1]);}else {List<Integer> path = new ArrayList();path.add(start);path.add(end);res.add(path);start = intervals[i][0];end = intervals[i][1];}}List<Integer> path = new ArrayList();path.add(start);path.add(end);res.add(path);// System.out.println(res.size());int[][] ans = new int[res.size()][2];for(int i = 0; i < res.size(); i++) {ans[i][0] = res.get(i).get(0);ans[i][1] = res.get(i).get(1);}return ans;}
}

轮转数组

class Solution {/**循环从队尾拿然后插入队头使用双端队列linkedlist然后发现函数返回void，说明应该要直接在nums基础上改动*/public void rotate(int[] nums, int k) {int len = nums.length;int[] nums1 = new int[len];for(int i = 0; i < len; i++) {nums1[i] = nums[i];}for(int i = 0; i < len; i++) {nums[(i + k)% len] = nums1[i];}}
}

除自身以外数组的乘积

// 双端队列，超时

缺失的第一个正数

class Solution {/**again双端队列？不要思维定势啊喂首先将nums中所有<0 & >n+1的全部设置为不可达的值n+1用res存有效的值 i -- i + 1遍历，第一个i != i + 1，返回都满足，则返回n + 1*/public int firstMissingPositive(int[] nums) {int n = nums.length;int[] res = new int[nums.length];for(int i = 0; i < nums.length; i++) {if(nums[i] <= 0 || nums[i] > n) {nums[i] = n + 1;}}for(int i = 0; i < n; i++) {if(nums[i] != n + 1) {res[nums[i] - 1] = nums[i]; }}for(int i = 0; i < res.length; i++) {// System.out.print("第" + i + "个数为" + res[i]);if(res[i] != i + 1) {return i + 1;}}return n + 1;}
}

矩阵

矩阵置0

class Solution {/**(i, j)处元素值为0，第i行和第j列全部置0*/public void setZeroes(int[][] matrix) {int row = matrix.length;int col = matrix[0].length;List<int[]> res = new ArrayList();for(int i = 0; i < row; i++) {for(int j = 0; j < col; j++) {if(matrix[i][j] == 0) {res.add(new int[]{i, j});}}}for(int i = 0; i < res.size(); i++) {int[] result = res.get(i);for(int m = 0; m < col; m++) {matrix[result[0]][m] = 0;}for(int k = 0; k < row; k++) {matrix[k][result[1]] = 0;}}}
}

螺旋矩阵

class Solution {/**没有技巧，全是感情*/public List<Integer> spiralOrder(int[][] matrix) {int m = matrix.length;int n = matrix[0].length;int upper = 0, lower = m - 1;int left = 0, right = n - 1;List<Integer> res = new ArrayList();while(res.size() < m * n) {// 从左往右，upper++if(upper <= lower) {for(int j = left; j <= right; j++) {res.add(matrix[upper][j]);}upper++;}// 从上往下，right--if(right >= left) {for(int i = upper; i <= lower; i++) {res.add(matrix[i][right]);}right--;}// 从右往左，lower--if(lower >= upper) {for(int j = right; j >= left; j--) {res.add(matrix[lower][j]);}lower--;}// 从下网上, left++if(left <= right) {for(int i = lower; i >= upper; i--) {res.add(matrix[i][left]);}left++;}}return res;}
}

旋转图像

class Solution {/**把原来的矩阵按对角线翻转，再每一行逆序对角线是从左上到右下的线*/public void rotate(int[][] matrix) {int row = matrix.length;int col = matrix[0].length;// 转置需要注意，只遍历下三角for(int i = 0; i < row; i++) {for(int j = 0; j < i; j++) {int tmp = matrix[i][j];matrix[i][j] = matrix[j][i];matrix[j][i] = tmp;}}// for(int i = 0; i < row; i++) {//     for(int j = 0; j < col; j++) {//         System.out.print(matrix[i][j]);//     }// }for(int i = 0; i < row; i++) {reverse(matrix[i]);}}public void reverse(int[] nums) {int left = 0;int right = nums.length - 1;while(left < right) {int tmp = nums[left];nums[left] = nums[right];nums[right] = tmp;left++;right--;}}
}

搜索二维矩阵II

class Solution {/**不知道为什么联想到dp数组，比较dp[i][j]和dp[i - 1][j], dp[i][j - 1]*/public boolean searchMatrix(int[][] matrix, int target) {int row = matrix.length;int col = matrix[0].length;int j = col - 1;int i = 0;while(j >= 0 && i < row) {if(matrix[i][j] < target) {i++;}else if(matrix[i][j] > target) {j--;}else {return true;}}return false;}
}