动态规划
- 给一个数组，寻找最大的子数组和，可以删除某个子数组中的一个元素或者不删
class Solution {
public int maximumSum(int[] arr) {
int[][] dp = new int[arr.length][2];
dp[0][0] = arr[0];
dp[0][1] = 0;
int res = dp[0][0];
for (int i = 1; i < arr.length; i++) {
dp[i][0] = Math.max(dp[i - 1][0], 0) + arr[i];
dp[i][1] = Math.max(dp[i - 1][1] + arr[i], dp[i - 1][0]);
res = Math.max(Math.max(dp[i][0], dp[i][1]), res);
}
return res;
}
}标准动态规划题，定义一个二维数组做dp数组，第一列记录不删除元素情况的最大前缀和，第二列记录删除元素的最大前缀和。判断删除元素的最大前缀和就是判断 前面删除过元素（dp[i-1] [1]）+当前元素 和 前面未删除元素dp[i-1] [0] 的大小
深度遍历
题记：递归是真难
MEDIUM
这道题题目表达的真的和shit一样
总结一下就是如果根节点到叶子节点的路径和大于limit那么这一条线上的点都不用删除，如果一个节点不存在任何一条这样的路径上就删除
class Solution {
public TreeNode sufficientSubset(TreeNode root, int limit) {
//递归最终还是要回到根节点，所以直接返回root也行
return dfs(root, 0, limit);
}
public TreeNode dfs(TreeNode cur, int sum, int limit) {
//先判断是不是空节点
if (cur == null) return null;
sum = sum + cur.val;
//这部分用来判断叶子节点是不是要删除
if (cur.left == null && cur.right == null) {
if (sum < limit) return null;
return cur;
}
//一定要cur等于，不然相当于没改
cur.left = dfs(cur.left, sum , limit);
cur.right = dfs(cur.right, sum, limit);
//dfs之后还要判断一下是不是要删除
if (cur.left == null && cur.right == null) return null;
return cur;
}
}BFS
MEDIUM
- 题目意思是给了一个二维数组，可以走上下左右，左上左下右上右下，只能走0，最后到右下角的最短路径，没路返回-1.
class Solution {
public int shortestPathBinaryMatrix(int[][] grid) {
int n = grid.length;
//如果起始位置是1，直接返回-1
if (grid[0][0] == 1) return -1;
//dist数组是记录从起始点到当前点的最短路径，初始化为最大值
int[][] dist = new int[n][n];
Arrays.stream(dist).forEach(row -> Arrays.fill(row, Integer.MAX_VALUE));
//队列记录可以到达的点
Queue<int[]> queue = new ArrayDeque<>();
queue.offer(new int[]{0, 0});
dist[0][0] = 1;
while (!queue.isEmpty()) {
int[] temp = queue.poll();
//到达目标位置则返回结果
if (temp[0] == n - 1 && temp[1] == n - 1) return dist[n - 1][n - 1];
//双循环是遍历当前点的八个方向
for (int i = -1; i <= 1; i++) {
for (int j = -1; j <= 1; j++) {
//二维数组不能越界
if (temp[0] + i < 0 || temp[1] + j < 0
|| temp[0] + i >= n || temp[1] + j >= n)
continue;
//判断当前方向是不是0，dist是判断最短距离
if (grid[temp[0] + i][temp[1] + j] == 1
|| dist[temp[0] + i][temp[1] + j] <= dist[temp[0]][temp[1]] + 1)
continue;
//前两个if都通过就可以改这个方向的情况，并且把点放到队列
dist[temp[0] + i][temp[1] + j] = dist[temp[0]][temp[1]] + 1;
queue.offer(new int[]{temp[0] + i, temp[1] + j});
}
}
}
return -1;
}
}记录一下二维数组初始化方法：
//setAll方法
Arrays.setAll(matrix, i -> {
int[] row = new int[matrix[i].length];
Arrays.fill(row, Integer.MAX_VALUE);
return row;
});
//stream流
Arrays.stream(matrix).forEach(row -> Arrays.fill(row, Integer.MAX_VALUE));二分查找
HARD
- 给一个矩阵，每行取一个元素，求所有情况中，和为第k小的情况
//思路：两行两行合并，每次返回这两行合并后的前k个情况
class Solution {
public int kthSmallest(int[][] mat, int k) {
int[] temp = mat[0];
//每次将前两行的结果与下一行在执行merge
for (int i = 1; i < mat.length; i++) {
temp = merge(temp, mat[i], k);
}
return temp[k-1];
}
public int[] merge(int[] a, int[] b, int k) {
//使用小根堆取出最小的k种情况
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < b.length; j++) {
priorityQueue.add(a[i] + b[j]);
}
}
int[] res = new int[Math.min(priorityQueue.size(), k)];
for (int i = 0; i < k && !priorityQueue.isEmpty(); i++) {
res[i] = priorityQueue.poll();
}
return res;
}
}
MYSQL
题记：记录一些方法
550.
SELECT round(sum(b.event_date is not null)/count(*),2) fraction
//不能用count，不管是不是null都会被统计
FROM
(SELECT player_id, MIN(event_date) AS min_date //选最小的一行
FROM activity
GROUP BY player_id) AS a
LEFT JOIN activity AS b
ON a.player_id = b.player_id and datediff(b.event_date, a.min_date)=1; //日期相差一天，前一个日期减后一个1193.
if(condition,condition(true),condition(false))
DATE_FORMAT(date, '%Y-%m-%d') //日期截断选其中的对应位置参数就行
